Markov chain sensitivity measured by mean first passage times (Q1587271): Difference between revisions

For an \(n\)-state time-homogeneous irreducible Markov chain with transition matrix \(P\) and stationary distribution \(\pi^T= \{\pi_j\}^n_{j=1}\), if \(M_{ij}\) denotes the mean first passage time from state \(i\) to state \(j\), then, as is well known, \(M_{jj}= 1/\pi_j\). If \(\widetilde P= P-E\) is the transition matrix of a similar chain, of which the stationary distribution is \(\widetilde\pi^T= \{\widetilde\pi_j\}^n_{j=1}\), the authors show that \(\pi^{-1}_j|\pi_j- \widetilde\pi_n|\leq{1\over 2}\|E\|_\infty\max_{i\neq j} M_{ij}\). This bound, in focussing on relative local perturbation in \(\pi_j\), complements bounds of global character such as those of the reviewer on \(\|\pi-\widetilde\pi\|_1\) using an ergodicity coefficient in the condition number. Reference to the reviewer's [24], listed as ``to appear'', has appeared in [Stat. Probab. Lett. 17, No. 2, 163-168 (1993; Zbl 0777.60065)]. The mean first passage matrix would seem to be expensive to compute from a practical point of view.