DIMACS TR: 94-39

Large deviation bounds for Markov chains

Author: Nabil Kahale


We study the fraction of time that a Markov chain spends in a given subset of states. We give an exponential bound on the probability that it exceeds its expectation by a constant factor. Our bound depends on the mixing properties of the chain, and is asymptotically optimal. It beats the best previously known results in this direction. We present an application to the leader election problem.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-39.ps
DIMACS Home Page