Markov chain sensitivity measured by mean first passage times
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.
- Stationary distributions and mean first passage times of perturbed Markov chains
- Perturbed Markov chains
- Sensitivity to perturbation of the stationary distribution: Some refinements
- Mixing times with applications to perturbed Markov chains
- Sensitivity of the Stationary Distribution of a Markov Chain
- An alternative expression for the mean first passage matrix
- Applications of Paz's inequality to perturbation bounds for Markov chains
- Cutpoint Decoupling and First Passage Times for Random Walks on Graphs
- Derivatives and Perturbations of Eigenvectors
- Derivatives of the Perron root at an essentially nonnegative matrix and the group inverse of an M-matrix
- Entrywise perturbation theory and error analysis for Markov chains
- Finite Continuous Time Markov Chains
- scientific article; zbMATH DE number 3648910 (Why is no real title available?)
- scientific article; zbMATH DE number 3760340 (Why is no real title available?)
- scientific article; zbMATH DE number 3787796 (Why is no real title available?)
- scientific article; zbMATH DE number 19232 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 510827 (Why is no real title available?)
- On the first and second order derivatives of the Perron vector
- Perturbation bounds for the stationary probabilities of a finite Markov chain
- Perturbation of the stationary distribution measured by ergodicity coefficients
- Perturbation theory and finite Markov chains
- Sensitivity of finite Markov chains under perturbation
- Sensitivity of the Stationary Distribution of a Markov Chain
- Sensitivity of the stationary distribution vector for an ergodic Markov chain
- Sensitivity to perturbation of the stationary distribution: Some refinements
- The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities
- The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
- Uniform Stability of Markov Chains
- Using the QR Factorization and Group Inversion to Compute, Differentiate, and Estimate the Sensitivity of Stationary Probabilities for Markov Chains
- Sensitivity of the stationary distribution vector for an ergodic Markov chain
- Improved bounds for a condition number for Markov chains
- Approximation schemes for stochastic mean payoff games with perfect information and few random positions
- A new decision making model based on rank centrality for GDM with fuzzy preference relations
- New perturbation bounds for denumerable Markov chains
- Acute perturbation of the group inverse
- Average case analysis of the Markov chain small-world model
- Strong stability and perturbation bounds for discrete Markov chains
- On single and double Soules matrices
- Mixing times with applications to perturbed Markov chains
- Proximity in group inverses of M-matrices and inverses of diagonally dominant M-matrices
- Stationary distributions and mean first passage times of perturbed Markov chains
- scientific article; zbMATH DE number 7446610 (Why is no real title available?)
- ASYMPTOTIC VARIANCE OF PASSAGE TIME ESTIMATORS IN MARKOV CHAINS
- Online Regret Bounds for Markov Decision Processes with Deterministic Transitions
- Sensitivity of the Stationary Distribution of a Markov Chain
- A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions
- Minimising the largest mean first passage time of a Markov chain: the influence of directed graphs
- A structured condition number for Kemeny's constant
- Sharp entrywise perturbation bounds for Markov chains
- Dobrushin Conditions and Systematic Scan
- Comparison of perturbation bounds for the stationary distribution of a Markov chain
- The Kemeny constant for finite homogeneous ergodic Markov chains
- On the inverse mean first passage matrix problem and the inverse \(M\)-matrix problem
- Markov chain small-world model with asymmetry: a unified and multivariate perspective
- An identity for the bias in Markov reward processes with applications to Markov chain perturbation and Kemeny's constant
- Random walks and flights over connected graphs and complex networks
- Transition matrices for well-conditioned Markov chains
- Maximizing PageRank via outlinks
- On optimal condition numbers for Markov chains
This page was built for publication: Markov chain sensitivity measured by mean first passage times
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1587271)
