Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T21:31:46.295Z Has data issue: false hasContentIssue false

Reversal of Markov Chains and the Forget Time

Published online by Cambridge University Press:  01 June 1998

LÁSZLÓ LOVÁSZ
Affiliation:
Department of Computer Science, Yale University, New Haven, CT 06510, USA (e-mail: [email protected])
PETER WINKLER
Affiliation:
Bell Laboratories 2C-379, Murray Hill, NJ 07974, USA (e-mail: [email protected])
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 three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to ‘forget’ where it started. One of these is the mixing time, the minimum mean length of a stopping rule that yields the stationary distribution from the worst starting state. A second is the forget time, the minimum mean length of any stopping rule that yields the same distribution from any starting state. The third is the reset time, the minimum expected time between independent samples from the stationary distribution.

Our main results state that the mixing time of a chain is equal to the mixing time of the time-reversed chain, while the forget time of a chain is equal to the reset time of the reverse chain. In particular, the forget time and the reset time of a time-reversible chain are equal. Moreover, the mixing time lies between absolute constant multiples of the sum of the forget time and the reset time.

We also derive an explicit formula for the forget time, in terms of the 'access times' introduced in [11]. This enables us to relate the forget and reset times to other mixing measures of the chain.

Type
Research Article
Copyright
1998 Cambridge University Press