Optimal Hoeffding bounds for discrete reversible Markov chains
By C. A. León, François Perron. 2004
86 citations recorded by the source corpus.
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_{\pi}f, the end-points of the support of f, the sample size n and the second largest eigenvalue \lambda of the transition matrix.
Subfields: Management Information Systems, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/50d58456e4a6d06b3049ba641d66794c504c38de
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Management Information Systems
In Statistics and Probability
Citations in the corpus
- Concentration inequalities for Markov chains by Marton couplings and spectral methods (2012, background): “A sharp version of Hoeffding’s inequality for reversible chains was proven in [25].”
- Bernstein's inequalities for general Markov chains (2018, unknown): “Le´on and Perron (2004) proved a Hoe ff ding-type inequality with a sharp variance proxy for a finite-state-space, reversible Markov chain and a time-independent function f i = f .”