Optimal Hoeffding bounds for discrete reversible Markov chains

We build optimal exponential bounds for the probabilities of large deviations of sums \sum_{k=1}^nf(X_k) where (X_k) is a finite reversible Markov chain and f is an arbitrary bounded function. These bounds depend only on the stationary mean E_πf, the end-points of the support of f, the sample size n and the second largest eigenvalue λof the transition matrix.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.