Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

DOI10.4230/LIPIcs.STACS.2012.124zbMath1245.68143arXiv1201.0559MaRDI QIDQ2904755

Michael Mitzenmacher, Henry Lam, Kai-Min Chung, Zhenming Liu

Publication date: 23 August 2012

Full work available at URL: https://arxiv.org/abs/1201.0559

zbMATH Keywords

Markov chains; probabilistic analysis; tail bounds

Mathematics Subject Classification ID

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)