Optimal Hoeffding bounds for discrete reversible Markov chains

Abstract

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.

Cited by in corpus (9)

• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Robust Distributed Optimization With Randomly Corrupted Gradients
• Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
• Hypothesis testing for Markov chain Monte Carlo
• Uniform mixing time for Random Walk on Lamplighter Graphs
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• Large Deviations and Effective Equidistribution
• Covariate shift in nonparametric regression with Markovian design