Exponential concentration inequalities for additive functionals of Markov chains

Adamczak, Radosław; Bednorz, Witold

ESAIM: Probability and Statistics, Tome 19 (2015), pp. 440-481.

Using the renewal approach we prove exponential inequalities for additive functionals and empirical processes of ergodic Markov chains, thus obtaining counterparts of inequalities for sums of independent random variables. The inequalities do not require functions of the chain to be bounded and moreover all the involved constants are given by explicit formulas whenever the usual drift condition holds, which may be of interest in practical applications e.g. to MCMC algorithms.

R. Adamczak, A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electron. J. Probab. 13 (2008) 1000–1034. | Zbl

R. Adamczak and W. Bednorz, Orlicz integrability of additive functionals of Harris ergodic Markov chains. To Appear in High Dimensional Probability VII. Cargèse Volume. Preprint arXiv:1201.3567 (2012).

K.B. Athreya and P. Ney, A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245 (1978) 493–501. | Zbl

J. Bae and S. Levental, Uniform CLT for Markov Chains and Its Invariance Principle: A Martingale Approach. J. Theoret. Probab. 8 (1995) 549–570. | Zbl

P.H. Baxendale, Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Ann. Appl. Probab. 15 (2005) 700–738. | Zbl

P. Bertail and S. Clémencon, Sharp bounds for the tails of functionals of Markov chains. Teor. Veroyatost. Primenen. 54 (2009) 609–619; translation in Theory Probab. Appl. 54 (2010) 505–515. | Zbl

A.A. Borovkov, Estimates for the distribution of sums and maxima of sums of random variables when the Cramér condition is not satisfied. Sib. Math. J. 41 (2000) 811–848. | Zbl

A.A. Borovkov, Probabilities of large deviations for random walks with semi-exponential distributions. Sib. Math. J. 41 (2000) 1061–1093. | Zbl

O. Bousquet, Concentration Inequalities for Sub-additive Functions Using the Entropy Method, Stochastic Inequalities and Applications. Progr. Probab. Springer, Basel (2003). | Zbl

J.-R. Chazottes and F. Redig, Concentration inequalities for Markov processes via coupling. Electron. J. Probab. 14 (2009) 1162–1180. | Zbl

X. Chen, Limit theorems for functionals of ergodic Markov chains with general state space. Mem. Amer. Math. Soc. 139 (1999) 664, | Zbl

S. Clémencon, Moment and probability inequalities for sums of bounded additive functionals of regular Markov chains via the Nummelin splitting technique. Statist. Probab. Lett. 55 (2001) 227–238. | Zbl

R. Douc, G. Fort, E. Moulines and P. Soulier, Practical Drift Conditions for Subgeometric Rates of Convergence. Ann. Appl. Probab. 14 (2004) 1353–1377. | Zbl

R. Douc, A. Guillin and E. Moulines, Bounds on regeneration times and limit theorems for subgeometric Markov chains. Ann. Inst. Henri Poincaré, Probab. Stat. 44 (2008) 239–257. | Zbl

U. Einmahl and D. Li, Characterization of LIL behavior in Banach space. Trans. Amer. Math. Soc. 360 (2008) 6677–6693. | Zbl

G. Fort and E. Moulines, Convergence of the Monte Carlo expectation maximization for curved exponential families. Ann. Statist. 31 (2003) 1220–1259. | Zbl

F. Gao, A. Guillin and L. Wu, Bernstein type’s concentration inequalities for symmetric Markov processes. Teor. Veroyatnost. i Primenen. 58 (2013) 521–549 | Zbl

S.F. Jarner and E. Hansen, Geometric ergodicity of Metropolis algorithms. Stoch. Proc. Appl. 85 (2000) 341–361 | Zbl

A.A. Johnson and G.L. Jones, Gibbs Sampling for a Bayesian Hierarchical General Linear Model. Electron. J. Stat. 4 (2010) 313–333. | Zbl

G.L. Jones and J.P. Hobert, Sufficient burn-in for Gibbs samplers for a hierarchical random effects model. Ann. Statist. 32 (2004) 784–817. | Zbl

P. Kevei and D. Mason, A More General Maximal Bernstein Type Inequality. High Dimensional Probability VI. The Banff Volume. Vol. 66 of Progr. Probab. Birkhäuser (2013). | Zbl

T. Klein and E. Rio, Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005) 1060–1077. | Zbl

L. Kontorovich and K. Ramanan, Concentration inequalities for dependent random variables via the martingale method. Ann. Probab. 36 (2008) 2126–2158. | Zbl

I. Kontoyiannis and S.P. Meyn, Geometric ergodicity and the spectral gap of non-reversible Markov chains. Probab. Theory Related Fields 154 (2012) 327–339. | Zbl

I. Kontoyiannis and S.P. Meyn, Spectral Theory and Limit Theorems for Geometrically Ergodic Markov Processes. Ann. Appl. Probab. (2003) 304–362. | Zbl

I. Kontoyiannis and S.P. Meyn, Large Deviations Asymptotic and the Spectral Theory of Multiplicatively Regular Markov Processes. Electron. J. Probab. 10 (2005) 61–123. | Zbl

K. Łatuszyński, B. Miasojedow and W. Niemiro, Nonasymptotic bounds on the estimation error of MCMC algorithms. Bernoulli 19 (2013) 2033–2066. | Zbl

M. Ledoux and M. Talagrand, Probability in Banach spaces. Isoperimetry and processes. In vol. 23 of Results in Math. and Rel. Areas. Springer-Verlag, Berlin (1991). | Zbl

S. Levental, Uniform limit theorems for Harris recurrent Markov chains, Probab. Theory Relat. Fields 80 (1988) 101–118. | Zbl

P. Lezaud, Chernoff and Berry-Esseen inequalities for Markov processes. ESAIM: PS 5 (2001) 183–201. | Zbl

K.L. Mengersen and R.L. Tweedie, Rates of convergence of the Hastings and Metropolis Algorithms. Ann. Statist. 24 (1996) 101–121. | Zbl

K. Marton, A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996) 556–571. | Zbl

F. Merlevede, M. Peligrad and E. Rio, A Bernstein type inequality and moderate deviations for weakly dependent sequences. Probab. Theory Relat. Fields 151 (2011) 435–474. | Zbl

S.P. Meyn, R.L. Tweedie, Markov Chains and Stochastic Stability. Communications and Control Engineering Series. Springer-Verlag, Ltd., London (1993). | Zbl

E. Nummelin, A splitting technique for Harris recurrent Markov chains. Z. Wahrsch. Verw. Gebiete 43 (1978) 309–318. | Zbl

E. Nummelin, General Irreducible Markov Chains and Non-Negative Operators. Cambridge Univ. Press. (1984). | Zbl

J.W. Pitman, An Identity for Stopping Times of a Markov Process. In Stud. Probab. Stat. (papers in honour of Edwin J. G. Pitman). North-Holland, Amsterdam (1976) 41–57. | Zbl

J.W. Pitman, Occupation measures for Markov chains. Adv. Appl. Probab. 9 (1977) 69–86. | Zbl

D. Revuz and M. Yor, Continuous Martingales and Brownian motion, 3rd edition. Springer-Verlag (2005). | Zbl

E. Rio, Processus empiriques absolument réguliers et entropie universelle. Probab. Theory Relat. Fields 111 (1998) 585–608. | Zbl

E. Rio, Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes. C. R. Acad. Sci. Paris Sér. I Math. 330 (2000) 905–908. | Zbl

G.O. Roberts and R.L. Tweedie, Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 (1996) 95–110. | Zbl

P.M. Samson, Concentration of measure inequalities for Markov chains and $\Phi$-mixing processes. Ann. Probab. 28 (2000) 416–461. | Zbl

M. Talagrand, New concentration inequalities in product spaces. Invent. Math. (1996) 503–563. | Zbl

S. van de Geer and J. Lederer, The Bernstein-Orlicz norm and deviation inequalities. Probab. Theory Relat. Fields 157 (2013) 225–250. | Zbl

A.W. van der Vaart and J.A. Wellner, Weak Convergence and Empirical Processes. With Applications to Statistics. Springer Ser. Stat. Springer-Verlag, New York (1996). | Zbl

O. Wintenberger, Deviation inequalities for sums of weakly dependent time series. Electron. Commun. Probab. 15 (2010) 489–503. | Zbl

O. Wintenberger, Weak transport inequalities and applications to exponential and oracle inequalities. Preprint arXiv:1207.4951v2 (2014).