1 Search Results for "Lam, Henry"


Document
Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

Authors: Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
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 <- pi}[f(v)], where pi is the stationary distribution of M. A t-step 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 mixing-time 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 Chernoff-Hoeffding 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 time-reversal Markov chain of M. We show that the probability Pr [ |X - mu t| >= delta mu t ] is at most exp(-Omega( delta^2 (1-lambda) mu t )) for 0 <= delta <= 1, and exp(-Omega( delta (1-lambda) mu t )) for delta > 1. Both of our results extend to continuous-time 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.

Cite as

Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 124-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.STACS.2012.124,
  author =	{Chung, Kai-Min and Lam, Henry and Liu, Zhenming and Mitzenmacher, Michael},
  title =	{{Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{124--135},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.124},
  URN =		{urn:nbn:de:0030-drops-34374},
  doi =		{10.4230/LIPIcs.STACS.2012.124},
  annote =	{Keywords: probabilistic analysis, tail bounds, Markov chains}
}
  • Refine by Author
  • 1 Chung, Kai-Min
  • 1 Lam, Henry
  • 1 Liu, Zhenming
  • 1 Mitzenmacher, Michael

  • Refine by Classification

  • Refine by Keyword
  • 1 Markov chains
  • 1 probabilistic analysis
  • 1 tail bounds

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail