Journal of Convex Analysis 30 (2023), No. 4, 1073--1114
Copyright Heldermann Verlag 2023
Nonexpansive Markov Operators and Random Function Iterations for Stochastic Fixed Point Problems
Neal Hermer
Institute for Numerical and Applied Mathematics, University of Goettingen, Germany
n.hermer@math.uni-goettingen.de
D. Russell Luke
Institute for Numerical and Applied Mathematics, University of Goettingen, Germany
r.luke@math.uni-goettingen.de
Anja Sturm
Institute for Numerical and Applied Mathematics, University of Goettingen, Germany
asturm@math.uni-goettingen.de
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 measure the stochastic fixed point problem. This generalizes earlier work of the authors [Random function iterations for consistent stochastic feasibility, Numer. Funct. Analysis Opt. 40/4 (2019) 386--420] 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 deterministic 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.
Keywords: Averaged mappings, nonexpansive mappings, stochastic feasibility, inconsistent stochastic fixed point problem, iterated random functions, convergence of Markov chain.
MSC: 60J05, 46N10, 46N30, 65C40, 49J55; 49J53, 65K05.
[ Fulltext-pdf (311 KB)] for subscribers only.