<p>We study random iterations of averaged operators in Hilbert spaces and prove that the associated residuals converge exponentially fast, both in expectation and almost surely. Our results provide quantitative bounds in terms of a single geometric parameter, giving sharp control of convergence rates under minimal assumptions. As an application, we introduce the concept of random nonlinear fusion frames. Here the atoms are generated dynamically from the residuals of the iteration and yield exact synthesis with frame-like stability in expectation. We show that these frames achieve exponential sampling complexity and encompass important special cases such as random projections and randomized Kaczmarz methods. This reveals a link between stochastic operator theory, frame theory, and randomized algorithms, and establishes a structural tool for constructing nonlinear frame-like systems with strong stability and convergence guarantees.</p>