Random Function Iterations for Stochastic Fixed Point Problems
From MaRDI portal
Publication:6344984
arXiv2007.06479MaRDI QIDQ6344984FDOQ6344984
Authors: Neal Hermer, D. Russell Luke, Anja Sturm 
Publication date: 13 July 2020
Abstract: 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 studying the stochastic feasibility problem}, namely, to find points that are, with probability 1, fixed points of the random functions [Hermer, Luke, Sturm, 2019]. 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 iterations converge to an invariant measure for the corresponding Markov operator. There are two major types of convergence: almost sure convergence of the iterates to a fixed point in the case of stochastic feasibility, and convergence in distribution more generally. We show how common structures in deterministic fixed point theory can be exploited to establish existence of invariant measures and convergence of the Markov chain. We show that weaker assumptions than are usually encountered in the analysis of Markov chains guarantee linear/geometric convergence. 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.
Numerical analysis or methods applied to Markov chains (65C40) Applications of functional analysis in probability theory and statistics (46N30) Discrete-time Markov processes on general state spaces (60J05) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Existence of optimal solutions to problems involving randomness (49J55)
This page was built for publication: Random Function Iterations for Stochastic Fixed Point Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344984)
