Chernoff and Berry–Esséen inequalities for Markov processes

Pascal Lezaud

ESAIM: Probability and Statistics (2010)

  • Volume: 5, page 183-201
  • ISSN: 1292-8100

Abstract

top
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.

How to cite

top

Lezaud, Pascal. "Chernoff and Berry–Esséen inequalities for Markov processes." ESAIM: Probability and Statistics 5 (2010): 183-201. <http://eudml.org/doc/197777>.

@article{Lezaud2010,
abstract = { 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. },
author = {Lezaud, Pascal},
journal = {ESAIM: Probability and Statistics},
keywords = {Markov process; Chernoff bound; Berry–Esséen; eigenvalues; perturbation theory.; Berry-Esséen; perturbation theory},
language = {eng},
month = {3},
pages = {183-201},
publisher = {EDP Sciences},
title = {Chernoff and Berry–Esséen inequalities for Markov processes},
url = {http://eudml.org/doc/197777},
volume = {5},
year = {2010},
}

TY - JOUR
AU - Lezaud, Pascal
TI - Chernoff and Berry–Esséen inequalities for Markov processes
JO - ESAIM: Probability and Statistics
DA - 2010/3//
PB - EDP Sciences
VL - 5
SP - 183
EP - 201
AB - 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.
LA - eng
KW - Markov process; Chernoff bound; Berry–Esséen; eigenvalues; perturbation theory.; Berry-Esséen; perturbation theory
UR - http://eudml.org/doc/197777
ER -

References

top
  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  URIhttp://www.stat.berkeley.edu/users/aldous/book.html
  2. B. Bercu and A. Rouault, Sharp large deviations for the Ornstein-Uhlenbeck process (to appear).  
  3. E. Bolthausen, The Berry-Esseen Theorem for Functionals of Discrete Markov Chains. Z. Wahrscheinlichkeitstheorie Verw.54 (1980) 59-73.  
  4. W. Bryc and A. Dembo, Large deviations for quadratic functionals of gaussian processes. J. Theoret. Probab.10 (1997) 307-332.  
  5. M.F. Cheng and F.Y. Wang, Estimation of spectral gap for elliptic operators. Trans. AMS349 (1997) 1239-1267.  
  6. K.L. Chung. Markov chains with stationnary transition probabilities. Springer-Verlag (1960).  
  7. J.D. Deuschel and D.W. Stroock, Large Deviations. Academic Press, Boston (1989).  
  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. Probab5 (1995) 37-43.  
  10. I.H. Dinwoodie, Expectations for nonreversible Markov chains. J. Math. Ann. App.220 (1998) 585-596.  
  11. I.H. Dinwoodie and P Ney, Occupation measures for Markov chains. J. Theoret. Probab.8 (1995) 679-691.  
  12. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 2. Wiley & Sons, 2nd Edition (1971).  
  13. S. Gallot and D. Hulin and J. Lafontaine, Riemannian Geometry. Springer-Verlag (1990).  
  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.  
  16. J.L. Jensen, Saddlepoint Approximations. Oxford Statist. Sci. Ser. 16.  
  17. T. Kato, Perturbation theory for linear operators. Springer (1966).  
  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.  
  19. G.F. Lawler and A.D. Sokal, Bounds on the L2 spectrum for Markov chains and Markov processes: A generalization of Cheeger's inequality. Trans. Amer. Math. Soc.309 (1988) 557-580.  
  20. P. Lezaud, Chernoff-type Bound for Finite Markov Chains. Ann. Appl. Probab8 (1998) 849-867.  
  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.  
  23. S.V. Nagaev, Some limit theorems for stationary Markov chains. Theory Probab. Appl.2 (1957) 378-406.  
  24. P.M. Samson, Concentration of measure inequalities for Markov chains and Φ-mixing processes, Ann. Probab. 28 (2000) 416-461.  
  25. H.F. Trotter, On the product of semi-groups of operators. Proc. Amer. Math. Soc.10 (1959) 545-551.  
  26. F.Y. Wang, Existence of spectral gap for elliptic operators. Math. Sci. Res. Inst. (1998).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.