Chernoff and Berry-Esséen inequalities for Markov processes

Lezaud, Pascal

ESAIM: Probability and Statistics, Volume 5 (2001), pp. 183-201.

In this paper, we develop bounds on the distribution function of the empirical mean for general ergodic Markov processes having a spectral gap. Our approach is based on the perturbation theory for linear operators, following the technique introduced by Gillman.

Classification: 60F10
Keywords: Markov process, Chernoff bound, Berry-Esséen, eigenvalues, perturbation theory

[1] D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation. Available from the Aldous's home page at http://www.stat.berkeley.edu/users/aldous/book.html

[2] B. Bercu and A. Rouault, Sharp large deviations for the Ornstein-Uhlenbeck process (to appear). | Zbl

[3] E. Bolthausen, The Berry-Esseen Theorem for Functionals of Discrete Markov Chains. Z. Wahrscheinlichkeitstheorie Verw. 54 (1980) 59-73. | Zbl

[4] W. Bryc and A. Dembo, Large deviations for quadratic functionals of gaussian processes. J. Theoret. Probab. 10 (1997) 307-332. | MR | Zbl

[5] M.F. Cheng and F.Y. Wang, Estimation of spectral gap for elliptic operators. Trans. AMS 349 (1997) 1239-1267. | MR | Zbl

[6] K.L. Chung. Markov chains with stationnary transition probabilities. Springer-Verlag (1960). | MR | Zbl

[7] J.D. Deuschel and D.W. Stroock, Large Deviations. Academic Press, Boston (1989). | MR | Zbl

[8] P. Diaconis, S. Holmes and R.M. Neal, Analysis of a non-reversible markov chain sampler, Technical Report. Cornell University, BU-1385-M, Biometrics Unit (1997).

[9] I.H. Dinwoodie, A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Probab 5 (1995) 37-43. | MR | Zbl

[10] I.H. Dinwoodie, Expectations for nonreversible Markov chains. J. Math. Ann. App. 220 (1998) 585-596. | MR | Zbl

[11] I.H. Dinwoodie and P Ney, Occupation measures for Markov chains. J. Theoret. Probab. 8 (1995) 679-691. | MR | Zbl

[12] W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 2. Wiley & Sons, 2nd Edition (1971). | MR | Zbl

[13] S. Gallot and D. Hulin and J. Lafontaine, Riemannian Geometry. Springer-Verlag (1990). | MR | Zbl

[14] D. Gillman, Hidden Markov Chains: Rates of Convergence and the Complexity of Inference, Ph.D. Thesis. Massachusetts Institute of Technology (1993).

[15] L. Gross, Logarithmic Sobolev Inequalities and Contractivity Properties of Semigroups, in Dirichlet forms, Varenna (Italy). Springer-Verlag, Lecture Notes in Math. 1563 (1992) 54-88. | MR | Zbl

[16] J.L. Jensen, Saddlepoint Approximations. Oxford Statist. Sci. Ser. 16.

[17] T. Kato, Perturbation theory for linear operators. Springer (1966). | Zbl

[18] D. Landers and L. Rogge, On the rate of convergence in the central limit theorem for Markov chains. Z. Wahrscheinlichkeitstheorie Verw. 35 (1976) 169-183. | MR | Zbl

[19] G.F. Lawler and A.D. Sokal, Bounds on the $L^2$ spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality. Trans. Amer. Math. Soc. 309 (1988) 557-580. | Zbl

[20] P. Lezaud, Chernoff-type Bound for Finite Markov Chains. Ann. Appl. Probab 8 (1998) 849-867. | MR | Zbl

[21] B. Mann, Berry-Esseen Central Limit Theorem for Markov chains, Ph.D. Thesis. Harvard University (1996).

[22] K. Marton, A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996) 556-571. | MR | Zbl

[23] S.V. Nagaev, Some limit theorems for stationary Markov chains. Theory Probab. Appl. 2 (1957) 378-406. | MR | Zbl

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

[25] H.F. Trotter, On the product of semi-groups of operators. Proc. Amer. Math. Soc. 10 (1959) 545-551. | MR | Zbl

[26] F.Y. Wang, Existence of spectral gap for elliptic operators. Math. Sci. Res. Inst. (1998). | MR