Variances of first passage times in a Markov chain with applications to mixing times
Loading...
Date
2006
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
Abstract
In an earlier paper the author introduced the statisticηi j ijπ j
m = m = Σ 1
as a measure of the
“mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain
with stationary distribution {pj} and mij as the mean first passage time from state i to state
j of the Markov chain. This was shown to be independent of the initial state i with ηi = η
for all i, minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of
situations. In this paper we explore the variance of the mixing time vi , starting in state i.
The vi , are shown to depend on i and an exploration of recommended starting states, given
knowledge of the transition probabilities, is considered. As a preamble, a study of the
computation of second moments of the mixing times, mij
(2) , and the variance of the first
passage times, in a discrete time Markov chain is carried out leading to some new results.
Description
Keywords
First passage time, Markov chains
Citation
Hunter, J.J. (2006), Variances of first passage times in a Markov chain with applications to mixing times, Research Letters in the Information and Mathematical Sciences, 10, 17-48