Concentration inequalities for Markov processes via coupling

Frank Redig (Mathematical Institute Leiden university)
Jean Rene Chazottes (CPHT, Ecole Polytechnique, Paris)

Abstract


We obtain moment and Gaussian bounds for general coordinate-wise Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling time exists, then we obtain a variance inequality. If a moment of order $1+a$ $(a > 0)$ of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order $1+ a$ is finite, uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1162-1180

Publication Date: May 31, 2009

DOI: 10.1214/EJP.v14-657

References

  1. R. Adamczak, A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electron. J. Prob. 13, 1000-1034, (2008). 2424985
  2. S. Bobkov and F. G"otze. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999), 1--28. J. Funct. Anal. 163 (1999), 1--28. 1682772
  3. S. Boucheron, O. Bousquet, G. Lugosi and P. Massart, Moment inequalities for functions of independent random variables. Ann. Prob. 33, 514-560, (2005). 2123200
  4. X. Bressaud, R. Fern'andez, and A. Galves. Decay of correlations for non-H"olderian dynamics. A coupling approach. Electron. J. Probab. 4 (1999), no. 3 (19 pp.). 1675304
  5. D.L. Burkholder. Sharp inequalities for martingales and stochastic integrals. Colloque Paul L'evy sur les Processus Stochastiques (Palaiseau, 1987). Ast'erisque No. 157-158 (1988), 75--94. 0976214
  6. S. Chatterjee. Stein's method for concentration inequalities. Probab. Theory Related Fields 138 (2007), no. 1-2, 305--321. 2288072
  7. J.-R. Chazottes, P. Collet, C. K"ulske and F. Redig. Concentration inequalities for random fields via coupling. Probab. Theory Related Fields 137 (2007), no. 1-2, 201--225. 2278456
  8. P. Collet. Variance and exponential estimates via coupling. Bull. Braz. Math. Soc. 37 (2006), no. 4, 461--475. 2284882
  9. H. Djellout, A. Guillin and L. Wu. Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab. 32 (2004), no. 3B, 2702--2732. 2078555
  10. R. Douc, A. Guillin and E. Moulines. Bounds on Regeneration Times and Limit Theorems for Subgeometric Markov Chains. Annales Inst. H. Poincar'e, to appear.
  11. R. Douc, G. Fort, E. Moulines and P. Soulier, Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Prob. 14 , 1353-1377, (2004). 2071426
  12. R. Douc, E. Moulines and P. Soulier, Computable convergence rates for sub-geometric ergodic Markov chains. Bernoulli 13 , 831-848 (2007). 2348753
  13. A. Fey-den Boer, R. Meester, Ronald, C. Quant, and F. Redig. A probabilistic approach to Zhang's sandpile model. Comm. Math. Phys. 280 , 351--388, (2008). 2395474
  14. S. Goldstein. A note on specifications. Z. Wahrsch. Verw. Gebiete, 46 , 45-51 (1978/79). 0512331
  15. L. Kontorovich and K. Ramanan. Concentration Inequalities for Dependent Random Variables via the Martingale Method, prepint (2007), to appear in Ann. Probab. Mathreview number not available
  16. L. Kontorovich. Obtaining Measure Concentration from Markov Contraction, preprint, 2007 (arXiv:0711.0987). Mathreview number not available
  17. M. Ledoux. The concentration of measure phenomenon, Mathematical Surveys and Monographs 89 American Mathematical Society, Providence R.I., 2001. 1849347
  18. T.M. Liggett, Interacting particle systems. Reprint of the 1985 original. Classics in Mathematics. Springer-Verlag, Berlin, 2005. 2108619
  19. C. McDiarmid. On the method of bounded differences, Surveys in Combinatorics 1989, Cambridge University Press, Cambridge (1989) 148--188. 1036755
  20. K. Marton. Bounding D-distance by informational divergence: a method to prove measure concentration. Ann. Probab. 24 (1996), no. 2, 857--866. 1404531
  21. K. Marton. A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996), no. 3, 556--571. [Erratum: Geom. Funct. Anal. 7 (1997), no. 3, 609--613.] 1392329
  22. K. Marton. Measure concentration for a class of random processes. Probab. Theory Related Fields 110 (1998), no. 3, 427--439. 1616492
  23. Y.H. Mao, Convergence rates in strong ergodicity for Markov processes. Stochastic Process. Appl. 116 , no. 12, 1964--1976, (2006). 2307067
  24. E. Rio. In'egalit'es de Hoeffding pour les fonctions lipschitziennes de suites d'ependantes. [Hoeffding inequalities for Lipschitz functions of dependent sequences] C. R. Acad. Sci. Paris S'er. I Math. 330 (2000), no. 10, 905--908. 1771956
  25. P.-M. Samson. Concentration of measure inequalities for Markov chains and $Phi$-mixing processes. Ann. Probab. 28 (2000), no. 1, 416--461. 1756011
  26. H. Thorisson. Coupling, stationarity, and regeneration. Probability and its Applications (New York). Springer-Verlag, New York, 2000. 1741181
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.