Chung, KaiMin ;
Lam, Henry ;
Liu, Zhenming ;
Mitzenmacher, Michael
ChernoffHoeffding Bounds for Markov Chains: Generalized and Simplified
Abstract
We prove the first ChernoffHoeffding bounds for general nonreversible finitestate Markov chains based on the standard L_1 (variation distance) mixingtime 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 < pi}[f(v)], where pi is the stationary distribution of M. A tstep random walk (v_1,...,v_t) on M starting from the stationary distribution pi has expected total weight E[X] = mu t, where X = sum_{i=1}^t f(v_i). Let T be the L_1 mixingtime of M. We show that the probability of X deviating from its mean by a multiplicative factor of delta, i.e., Pr [ X  mu t >= delta mu t ], is at most exp(Omega( delta^2 mu t / T )) for 0 <= delta <= 1, and exp(Omega( delta mu t / T )) for delta > 1. In fact, the bounds hold even if the weight functions f_i's for i in [t] are distinct, provided that all of them have the same mean mu.
We also obtain a simplified proof for the ChernoffHoeffding bounds based on the spectral expansion lambda of M, which is the square root of the second largest eigenvalue (in absolute value) of M tilde{M}, where tilde{M} is the timereversal Markov chain of M. We show that the probability Pr [ X  mu t >= delta mu t ] is at most exp(Omega( delta^2 (1lambda) mu t )) for 0 <= delta <= 1, and exp(Omega( delta (1lambda) mu t )) for delta > 1.
Both of our results extend to continuoustime Markov chains, and to the case where the walk starts from an arbitrary distribution x, at a price of a multiplicative factor depending on the distribution x in the concentration bounds.
BibTeX  Entry
@InProceedings{chung_et_al:LIPIcs:2012:3437,
author = {KaiMin Chung and Henry Lam and Zhenming Liu and Michael Mitzenmacher},
title = {{ChernoffHoeffding Bounds for Markov Chains: Generalized and Simplified}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {124135},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3437},
URN = {urn:nbn:de:0030drops34374},
doi = {10.4230/LIPIcs.STACS.2012.124},
annote = {Keywords: probabilistic analysis, tail bounds, Markov chains}
}
2012
Keywords: 

probabilistic analysis, tail bounds, Markov chains 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 