Chernoff-Hoeffding Bounds for Markov Chains

We (Kai-Min Chung, Henry Lam, Zhenming Liu and myself) have a STACS paper on Chernoff-Hoeffding bounds for Markov chains (arxiv version here).  Such bounds are used, for example, to say the amount of time a Markov chain spends in each state is close to its expectation (given by the stationary distribution) with high probability after a suitable amount of time.  Since successive states in a Markov chain are dependent, this sort of result does not trivially follow from regular Chenroff-Hoeffding bounds.  Such bounds for Markov chains is a reasonably old subject; I recall the state of the art being a paper by Nabil Kahale (Large Deviation Bounds for Markov Chains, available online) back around when I was in graduate school.

So what's new in our work?  Our paper gives Chernoff-Hoeffding bounds for general nonreversible finite-state Markov chains based on the standard L_1 mixing-time of the chain.  Previous bounds seem to focus on reversible Markov chains (although some of these bounds can be generalized using a technique called, coincidentally, reversibilization, a term which seems to date back to a 1991 paper by James Fill), and are based on the arguably less-easy-to-use spectral expansion of the chain.  Along the way, we also give a simplified proof for Chernoff-Hoeffding bounds based on the spectral expansion of the chain.

But some things I think are also nice about the paper is it utilizes elementary techniques, is (relatively) easy to read, has clean result statements, and provides a survey-like context for this area.  If you happen to need a tail bound for your Markov chain process, I hope you'll take a look.