A tail inequality for suprema of unbounded empirical processes with applications to Markov chains

Radoslaw Adamczak (Polish Academy of Sciences)


We present a tail inequality for suprema of empirical processes generated by variables with finite $\psi_\alpha$ norms and apply it to some geometrically ergodic Markov chains to derive similar estimates for empirical processes of such chains, generated by bounded functions. We also obtain a bounded difference inequality for symmetric statistics of such Markov chains.

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

Pages: 1000-1034

Publication Date: June 29, 2008

DOI: 10.1214/EJP.v13-521


  1. Baxendale P. H. Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Ann. Appl. Probab. 15 (2005), no. 1B, 700--738. MR2114987 (2005m:60164)
  2. Boucheron S., Bousquet O., Lugosi G., Massart P. Moment inequalities for functions of independent random variables. Ann. Probab 33 (2005), no. 2, 514-560. MR2123200 (2006a:60024)
  3. Bousquet O. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334 (2002), no. 6, 495--500. MR1890640 (2003f:60039)
  4. Einmahl U., Li D. Characterization of LIL behavior in Banach space. To appear in Trans. Am. Math. Soc.
  5. Giné E., Latała R., Zinn J. Exponential and moment inequalities for U-statistics. In High Dimensional Probability II, 13-38. Progr. Probab. 47. Birkhauser, Boston, Boston, MA, 2000. MR1857312. MR1857312 (2002i:60035)
  6. Glynn P. W., Ormoneit D. Hoeffding's inequality for uniformly ergodic Markov chains. Statist. Probab. Lett. 56 (2002), no. 2, 143--146. MR1881167. MR1881167 (2002k:60143)
  7. Klein T., Rio, E. Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005), no. 3, 1060--1077. MR2135312. MR2135312 (2006c:60022)
  8. Kontorovich L., Ramanan K. Concentration Inequalities for Dependent Random Variables via the Martingale Method. To appear in Ann. Probab.
  9. Kontoyiannis I., Lastras-Montaño L., Meyn S. P. Relative Entropy and Exponential Deviation Bounds for General Markov Chains. 2005 IEEE International Symposium on Information Theory. Math. Review number not available.
  10. Ledoux M. On Talagrand's deviation inequalities for product measures. ESAIM: Probability and Statistics, 1 (1996), 63-87. MR1399224 (97j:60005)
  11. Ledoux M. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. MR1849347 (2003k:28019)
  12. Ledoux M., Talagrand M. Probability in Banach spaces. Isoperimetry and processes. Ergebnisse der Mathematik und ihrer Grenzgebiete (3), 23. Springer-Verlag, Berlin, 1991. MR1102015 (93c:60001)
  13. Marton K. A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996), no. 3, 556--571. MR1392329 (97g:60082)
  14. Marton K. Erratum to: "A measure concentration inequality for contracting Markov chains". Geom. Funct. Anal. 6 (1996), no. 3, 556--571. MR1466340 (98h:60096)
  15. Marton, K. Measure concentration for a class of random processes. Probab. Theory Related Fields 110 (1998), no. 3, 427--439. MR1616492 (99g:60074)
  16. Massart, P. About the constants in Talagrand's concentration inequalities for empirical processes. Ann. Probab. 28 (2000), no. 2, 863--884. MR1782276 (2001m:60038)
  17. Mendelson S. Tomczak-Jaegermann N., A subgaussian embedding theorem. Israel J. Math. Vol. 164 (2008). Math Review number not available.
  18. Meyn, S. P., Tweedie, R. L. Markov chains and stochastic stability. Communications and Control Engineering Series. Springer-Verlag London, Ltd., London, 1993. MR1287609 (95j:60103)
  19. Montgomery-Smith S.J. Comparison of sums of independent identically distributed random vectors. Probab. Math. Statist. 14 (1993), no. 2, 281--285. MR1321767 (96b:60042)
  20. Panchenko D. Symmetrization approach to concentration inequalities for empirical processes. Ann. Probab. 31 (2003), no. 4, 2068--2081. MR2016612 (2005c:60023)
  21. Pisier, G. Some applications of the metric entropy condition to harmonic analysis. Banach spaces, harmonic analysis, and probability theory., 123--154, Lecture Notes in Math., 995, Springer, Berlin, 1983. MR0717231 (85f:60061)
  22. Roberts, G. O., Rosenthal, J. S. General state space Markov chains and MCMC algorithms. Probab. Surv. 1 (2004), 20--71. MR2095565 (2005i:60135)
  23. Samson, P.M. Concentration of measure inequalities for Markov chains and $Phi$-mixing processes. Ann. Probab. 28 (2000), no. 1, 416--461. MR1756011 (2001d:60015)
  24. Talagrand M. New concentration inequalities in product spaces. Invent. Math. 126 (1996), no. 3, 505--563. MR1419006 (99b:60030)
  25. van der Vaart, Aad W., Wellner, Jon A. Weak convergence and empirical processes. With applications to statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996. MR1385671 (97g:60035)

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