1
$\begingroup$

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 functions though and convergence rate is exponential in Prohorov's metric.

While talking about the convergence rate of probability measures towards the invariant measure, we need to talk about some metric on the space of probability measures, which also a question, which metric to use in this case to find the rate. Thanks.

$\mu_n(A)=\mathbb P(X_n\in A)$ i.e $X_n\sim \mu_n$,

I am looking for some reference on the Wasserstein metric. Thanks for helping!

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ @riemann Although RW's answer is quite complete for MO, let me mention that detailed elementary proofs are available in a paper of mine: arxiv.org/abs/1909.01655 (there is e.g. a small trick to avoid the Law of Large Numbers and still get the optimal convergence condition $\sum p_i \log L_i <0$. $\endgroup$ Jan 11, 2020 at 14:00
  • 1
    $\begingroup$ @RW "Let me denote by $d^*$ the transportation metric on the space of probability measures on a metric state space $(X,d)$". Makes perfect sense if $X$ is bounded, but what if it isn't? I surmise the choice of the Prokhorov metric (with all related complications) was made exactly for that reason. $\endgroup$
    – fedja
    Jan 11, 2020 at 19:18
  • 1
    $\begingroup$ @fedia - Convergence in the transportation metric does imply weak convergence even when $X$ is not compact. $\endgroup$
    – R W
    Jan 11, 2020 at 19:47
  • 1
    $\begingroup$ @riemann: this is not the place for extended discussion. The case of a finite number of maps is obtained by using a finite combination of Dirac masses for $\eta$. Lemma 3.2 is the main (rather trivial) point (proposition 3.9 to get the most general condition). $\otimes$ denotes the product of measures. $\endgroup$ Jan 11, 2020 at 20:31
  • 1
    $\begingroup$ @fedja: it is not very difficult to manage unbounded spaces by considering measures with finite moment of order $q$ for some small enough $q$, but this is a point to indeed consider. $\endgroup$ Jan 11, 2020 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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