We build optimal exponential bounds for the probabilities of large deviations of sums ∑k=1nf(Xk) where (Xk) is a finite reversible Markov chain and f is an arbitrary bounded function. These bounds depend only on the stationary mean
${\mathbb {E}}_{\pi}f,$
the end-points of the support of f, the sample size n and the second largest eigenvalue λ of the transition matrix.
Publié le : 2004-05-14
Classification:
Large deviations,
Markov chains,
Chernoff bounds,
Perron–Frobenius eigenvalue,
65C05
@article{1082737118,
author = {A. Le\'on, Carlos and Perron, Fran\c cois},
title = {Optimal Hoeffding bounds for discrete reversible Markov chains},
journal = {Ann. Appl. Probab.},
volume = {14},
number = {1},
year = {2004},
pages = { 958-970},
language = {en},
url = {http://dml.mathdoc.fr/item/1082737118}
}
A. León, Carlos; Perron, François. Optimal Hoeffding bounds for discrete reversible Markov chains. Ann. Appl. Probab., Tome 14 (2004) no. 1, pp. 958-970. http://gdmltest.u-ga.fr/item/1082737118/