DIMACS TR: 94-39
Large deviation bounds for Markov chains
Author: Nabil Kahale
ABSTRACT
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