Optimal Hoeffding bounds for discrete reversible Markov chains

2004/05/01 by Carlos A. Leon, Carlos A. León, François Perron +1 · 1 citation
Business, Management and Accounting · Mathematics · #Advanced Queuing Theory Analysis #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #math.PR #msc:65C05.

paper · pdf · doi:10.1214/105051604000000170

published as Annals of Applied Probability 2004, Vol. 14, No. 2, 958-970

openalex publication_date 2004/05/01 · arxiv created 2004/05/14 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

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_πf, the end-points of the support of f, the sample size n and the second largest eigenvalue λ of the transition matrix.

Citations

• Probability Inequalities for Sums of Bounded Random Variables

Cited by

• Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments

Related

• Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains
• Hoeffding's lemma for Markov Chains and its applications to statistical learning
• A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
• Hoeffding's inequalities for geometrically ergodic Markov chains on general state space
• Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified