Mixing times with applications to perturbed Markov chains

AbstractA measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic ηi=∑j=1mmijπj, where {πj} is the stationary distribution and mij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that ηi=η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities