Chernoff-type bound for finite Markov chains. (English) Zbl 0938.60027

Let \((X_n)\) be an irreducible Markov chain on a finite set \(G\) with transition matrix \(P\) and stationary distribution \(\pi\). Then, for any function \(f\) and for any initial distribution \(q\) the empirical mean \(n^{-1}\sum^n_{i= 1}f(X_i)\) converges in probability to \(\pi f= \sum_y \pi(y)f(y)\). The paper gives exponential bounds for \(P_q\left\{ n^{-1}\sum^n_{i= 1} f(X_i)-\pi f\geq \gamma\right\}\). These bounds involve spectral gap of \(P\).


60F10 Large deviations
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI


[1] Aldous, D. (1987). On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Prob. Engrg. Inform. Sci. 1 33-46. Aldous, D. and Fill, J. Reversible Markov chains and random walks on graphs. Unpublished manuscript. · Zbl 1133.60327
[2] Bahadur, R. R. and Ranga Rao, R. (1960). On deviations of the sample mean. Ann. Math. Statist. 31 1015-1033. · Zbl 0101.12603
[3] Bennett, G. (1962). Probability inequalities for sums of independent random variables. J. Amer. Statist. Assoc. 57 33-45. · Zbl 0104.11905
[4] Chernoff, H. (1952). A measure of asy mptotic efficiency for tests of a hy pothesis based on the sum of observations. Ann. Math. Statist. 23 493-507. · Zbl 0048.11804
[5] Cramér, H. (1938). Sur un nouveau théor eme de la théorie des probabilités. Actualités Sci. Indust. 736. · JFM 64.0529.01
[6] Dembo, A. and Zeitouni, O. (1993). Large Deviations Techniques and Applications. Jones and Bartlett, Boston. · Zbl 0793.60030
[7] Diaconis, P. and Saloff-Coste, L. (1993). Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696-730. · Zbl 0799.60058
[8] Diaconis, P. and Saloff-Coste, L. (1995). What do we know about the Metropolis algorithm? Unpublished manuscript. Diaconis, P. and Saloff-Coste, L. (1996a). Logarithmic Sobolev inequalities and finite Markov chains. Ann. Appl. Probab. 6 695-750. Diaconis, P. and Saloff-Coste, L. (1996b). Nash inequalities for finite Markov chains. J. Appl. Probab. 9 459-510. · Zbl 0867.60043
[9] Dinwoodie, I. (1995). A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Probab. 5 37-43. · Zbl 0829.60022
[10] Fill, J. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1 62-87. · Zbl 0726.60069
[11] Gillman, D. (1993). Hidden Markov chains: rates of convergence and the complexity of inference. Ph.D. dissertation, MIT.
[12] Kato, T. (1966). Perturbation Theory for Linear Operators. Springer, New York. · Zbl 0148.12601
[13] Kolmogorov, A. (1929). Über das Gesetz des iterieten Logaritmus. Math. Ann. 99 309-319.
[14] Mann, B. (1996). Berry-Esseen central limit theorem for Markov chains. Ph.D. dissertation, Harvard Univ.
[15] Marshall, A. W. and Olkin, I. (1979). Inequalities: Theory of Majorization and Its Applications. Academic Press, New York. · Zbl 0437.26007
[16] Nagaev, S. V. (1957). Some limit theorems for stationary Markov chains. Theory Probab. Appl. 2 378-406. · Zbl 0078.31803
[17] Nagaev, S. V. (1961). More exact statements of limits theorems for homogeneous Markov chains. Theory Probab. Appl. 6 62-81. · Zbl 0116.10602
[18] Stout, W. F. (1974). Almost Sure Convergence. Academic Press, New York. · Zbl 0321.60022
[19] Trotter, H. F. (1959). On the product of semi-groups of operators. Proc. Amer. Math. Soc. 10 545-551. JSTOR: · Zbl 0099.10401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.