  In many branches of engineering, Banach contraction mapping theorem is
employed to establish the convergence of certain deterministic algorithms.
Randomized versions of these algorithms have been developed that have proved
useful in data-driven problems. In a class of randomized algorithms, in each
iteration, the contraction map is approximated with an operator that uses
independent and identically distributed samples of certain random variables.
This leads to iterated random operators acting on an initial point in a
complete metric space, and it generates a Markov chain. In this paper, we
develop a new stochastic dominance based proof technique, called probabilistic
contraction analysis, for establishing the convergence in probability of Markov
chains generated by such iterated random operators in certain limiting regime.
The methods developed in this paper provides a general framework for
understanding convergence of a wide variety of Monte Carlo methods in which
contractive property is present. We apply the convergence result to conclude
the convergence of fitted value iteration and fitted relative value iteration
in continuous state and continuous action Markov decision problems as
representative applications of the general framework developed here.
