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.
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
Date
2006
Publisher
Massey University