Chernoff and Berry-Esséen inequalities for Markov processes
ESAIM: Probability and Statistics, Volume 5  (2001), p. 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
@article{PS_2001__5__183_0,
     author = {Lezaud, Pascal},
     title = {Chernoff and Berry-Ess\'een inequalities for Markov processes},
     journal = {ESAIM: Probability and Statistics},
     publisher = {EDP-Sciences},
     volume = {5},
     year = {2001},
     pages = {183-201},
     zbl = {0998.60075},
     language = {en},
     url = {http://www.numdam.org/item/PS_2001__5__183_0}
}
Lezaud, Pascal. Chernoff and Berry-Esséen inequalities for Markov processes. ESAIM: Probability and Statistics, Volume 5 (2001) , pp. 183-201. http://www.numdam.org/item/PS_2001__5__183_0/

[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 1101.60320

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

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

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

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

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

[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 1325039 | Zbl 0829.60022

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

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

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

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

[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 1292277 | Zbl 0812.47037

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

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

[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 407938 | Zbl 0315.60014

[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 0716.60073

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

[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 1392329 | Zbl 0856.60072

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

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

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

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