Could anyone give me some references for the convergence rate of Markov chain arising from the random iteration of Lipschitz functions which moves as follows:

$$ X_{n+1}= f_{\omega_n}(X_n)$$ where $f_1,\dots, f_s$ are Lipschitz functions (with Lipschitz constants $L_i$ and $\sum_{k=1}^{s} p_kL_k <1$ )on $\mathcal X$, a metric space with a metric $d$ it is complete and separable say. $\omega_0,\omega_1,\dots, \omega_n,\dots$ are i.i.d discrete random variable taking values in $\{1,2,\dots,s<\infty\}$. $p_k=\mathbb P(\omega_i=k)$.

I found Diaconis and Freedman's Paper where they didn't talk about the finite number of function though and convergence rate is exponential in Prohorov's metric. I am looking for some reference on Wasserstein metric or so. Thanks for helping!


It is much more natural and convenient to metrize the weak topology on the space of measures with the transportation (aka Kantorovich-Rubinshtein, aka 1-Wasserstein) metric, especially in what concerns iterated function systems and various convergence issues in this context, see Kaimanovich (1985).

Let me denote by $d^*$ the transportation metric on the space of probability measures on a metric state space $(X,d)$. If $f$ is a map of $X$ to itself with the Lipschitz constant $L$, then obviously $$ d^*(f(\lambda),f(\mu))\le L d^*(\lambda,\mu) \;. $$ Therefore if one has a family of such maps contracting on average, i.e., in the discrete case $$ A := \sum p_i \log L_i < 0 \;, $$ where $p_i$ are the weights of individual transformations $f_i$, and $L_i$ are their Lipschitz constants, then by the law of large numbers the time $n$ distribution of your Markov chain converges exponentially fast to its unique stationary distribution. Note that the right condition is $\sum p_i \log L_i<0$ rather than $\sum p_i L_i < 1$.

Moreover, for almost every Bernoulli sequence $f_{\omega_1},f_{\omega_2},\dots$ and any initial point $x\in X$ the sequence of iterations $f_{\omega_1} \dots f_{\omega_n}(x)$ exponentially fast converges to a point $z_{\omega_1,\omega_2,\dots}$ independent of $x$, and the distribution of these limit points coincides with the stationary distribution of the chain.

  • $\begingroup$ The metric $d^*$ is defined on the space of measures, therefore whenever I talk about $d^*$ its arguments are measures. What I have said is essentially contained in Theorem 5.1 from Diaconis-Freedman. However, the fact that they were not aware of the transportation metric and argued in terms of the quite unnatural Prokhorov metric instead made their arguments way much longer than necessary. $\endgroup$ – R W Sep 1 at 14:11
  • $\begingroup$ No - $f(\mu)$ is the image of the measure $\mu$ under the map $f$. $\endgroup$ – R W Sep 1 at 15:25
  • $\begingroup$ Yes - it's also called the push forward measure. $\endgroup$ – R W Sep 1 at 16:37
  • $\begingroup$ The Lipschitz constant of the iterated random product $f_{\omega_1} \dots f_{\omega_n}(x)$ will almost surely behave like $e^{nA}$, where $A=\sum p_i \log L_i$ is negative. All this is in a pretty detailed way explained in Diaconis and Freedman, one just has to apply it to the transportation metric instead of Prokhorov's one. $\endgroup$ – R W Sep 2 at 21:44
  • $\begingroup$ They look to me like ad hoc moment conditions - they are of course satisfied when one deals with finitely many transformations and are only needed to make sure everything remains under control even if the distribution is spread out. $\endgroup$ – R W Sep 4 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.