We study the convergence of random function iterations for finding an invariant measure

of the corresponding Markov operator. We call the problem of finding such an invariant mea-

sure the stochastic fixed point problem. This generalizes earlier work studying the stochastic

feasibility problem, namely, to find points that are, with probability 1, fixed points of the

random functions. When no such points exist, the stochastic feasibility problem is

called inconsistent, but still under certain assumptions, the more general stochastic fixed

point problem has a solution and the random function iteration converges to an invariant

measure for the corresponding Markov operator. We show how common structures in de-

terministic fixed point theory can be exploited to establish existence of invariant measures

and convergence in distribution of the Markov chain. This framework specializes to many

applications of current interest including, for instance, stochastic algorithms for large-scale

distributed computation, and deterministic iterative procedures with computational error.

The theory developed in this study provides a solid basis for describing the convergence of

simple computational methods without the assumption of infinite precision arithmetic or

vanishing computational errors.

## Article

Download

View Nonexpansive Markov Operators and Random Function Iterations for Stochastic Fixed Point Problems