Hoeffding’s Inequality for Uniformly Recurrent Markov Chains

P. W. Glynn and D. Ormoneit

Statistics and Probability Letters. Vol. 56 (2), 143-146 (2002)

We provide a generalization of Hoeffding’s inequality to partial sums that are derived from a uniformly ergodic Markov chain. Our exponential inequality on the deviation of these sums from their expectation is particularly useful in situations where we require uniform control on the constants appearing in the bound.