Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

Probability inequalities for sums of bounded random variables

W. Hoeffding · 1963

Earlier work this paper cites.

Some inequalities for reversible markov chains

D. Aldous · 1982

Earlier work this paper cites.

Eigenvalue bounds on convergence to stationarity for nonreversible markov chains, with an application to the exclusion process

A. Fill · 1991

Earlier work this paper cites.

Improved bounds for mixing rates of markov chains and multicommodity flow

A. Sinclair · 1992

Earlier work this paper cites.

The Markov chain Monte Carlo method: an approach to approximate counting and integration

M. Jerrum and A. Sinclair · 1996

Earlier work this paper cites.

A chernoff bound for random walks on expander graphs

D. Gillman · 1997

Earlier work this paper cites.

Large deviation bounds for markov chains

N. Kahale · 1997

Cited alongside, same era.

Chernoff-type bound for finite markov chains

P. Lezaud · 1998

Cited alongside, same era.

On testing expansion in bounded degree graphs

O. Goldreich and D. Ron · 2000

Cited alongside, same era.

Optimal hoeffding bounds for discrete reversible markov chains

C. A. Leon and F. Perron · 2004

Cited alongside, same era.

A randomness-efficient sampler for matrix valued functions and applications

A. Wigderson and D. Xiao · 2005

Cited alongside, same era.

Randomness efficient sampling within nc 1 {}^{\mbox{1}}

A. Healy · 2008

Cited alongside, same era.

Tail estimates for sums of variables sampled by a random walk

R. Wagner · 2008

Later among the works it cites.

Improving random walk estimation accuracy with uniform restart

K. Avrachenkov, B. Ribeiro, and D. Towsley · 2010

Later among the works it cites.

Measuring the mixing time of social graphs

A Mohaisen, A. Yun, and Y Kim · 2010

Later among the works it cites.

Online algorithms for the multi-armed bandit problem with markovian rewards

C. Tekin and M. Liu · 2010

Later among the works it cites.

An analysis of random-walk cuckoo hashing

A. Frieze, P. Melsted, and M. Mitzenmacher · 2011

Later among the works it cites.