Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T20:11:00.900Z Has data issue: false hasContentIssue false

Large Deviation Bounds for Markov Chains

Published online by Cambridge University Press:  01 December 1997

NABIL KAHALE
Affiliation:
AT&T Labs–Research, Florham Park, NJ 07932, USA; (e-mail: kahale@research.att.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 for a certain class of Markov chains. It beats the best previously known results in this direction. We present an application to the leader election problem.

Information

Type
Research Article
Copyright
1997 Cambridge University Press