Mixing times with applications to perturbed Markov chains (Q2497948)

Consider an irreducible discrete time Markov chain \((X_{n})_{n\geq 0}\) with state space \(S=(1,\dots ,m)\), \(m\geq 2.\) Let \((\pi _{j})_{1\leq j\leq m}\) be its stationary distribution and \(m_{ij}\) the mean first passage time from state \(i\) to state \(j\), \(1\leq i,j\leq m\). Define the time to mixing \(T\) as the smallest \(k\geq 1\) such that \(X_{k}\) has probability distribution \(\pi \). It is shown that \(E(T) =\sum_{j=1}^{m}m_{ij}\pi _{j}\) given that \(X_{0}=i\), \(1\leq i\leq m,\) and that actually \(E(T) \) does not depend on \(i\). Two special cases (\(m=2\) and \(m=3\)) are discussed in some detail, leading to some general results. It is shown, e.g., that (i) \(E(T) =(m+1) /2\) for a period \(m\) Markov chain and, in general, \(E( T) \geq (m+1) /2\), thus yielding \((m+1) /2\) as the minimal bound for \(E(T) \); (ii)\ \(E(T) =1+(m-1) ^{2}/m\varepsilon \) for an \(m\)-state chain with transition probabilities \( p_{ii}=1-\varepsilon ,\;p_{ij}=\varepsilon /(m-1) \) for \(j\neq i, \)\ \(1\leq i,j\leq m\), \(0<\varepsilon \leq 1\), and (iii) \(E(T) =1+\sum_{k<j}( \varepsilon _{k}\varepsilon _{j}) ^{-1}/\sum_{i}\varepsilon _{i}^{-1}\) for an \(m\)-state chain with nonzero transition probabilities \(p_{ii}=1-\varepsilon _{i}\), \(p_{i,i+1}=\varepsilon _{i}\), with \(i+1=1\) when \(i=m\), \(0<\varepsilon _{i}\leq 1\), \(1\leq i\leq m\). Finally, the impact of perturbing the transition probabilities on the stationary distribution is considered. A new bound involving \(E(T) \) for the \(1\)-norm of the difference between the stationary probability vectors of the original and the perturbed chain is established.