Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

Kai-Min Chung, Henry Lam, Zhenming Liu & Michael Mitzenmacher
We prove the first Chernoff-Hoeffding bounds for general nonreversible finite-state Markov chains based on the standard L_1 (variation distance) mixing-time of the chain. Specifically, consider an ergodic Markov chain M and a weight function f: [n] -> [0,1] on the state space [n] of M with mean mu = E_{v = delta mu t ], is at most exp(-Omega( delta^2 mu t / T )) for 0 <= delta <= 1, and exp(-Omega( delta mu...