Sharp entrywise perturbation bounds for Markov chains

DOI10.1137/140987900MaRDI QIDQ5265002zbMATH OpenOpenAlexWikidataFDO

Authors Erik H. Thiede, Brian van Koten, Jonathan Weare

Publication date 21 July 2015

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.1431, http://europepmc.org/articles/pmc4610747

zbMATH Keywords

sensitivity analysisMarkov chainsstochastic matricescondition numbersperturbation boundscomputational statistical physics

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Numerical computation of matrix norms, conditioning, scaling (65F35)

Abstract: For many Markov chains of practical interest, the invariant distribution is extremely sensitive to perturbations of some entries of the transition matrix, but insensitive to others; we give an example of such a chain, motivated by a problem in computational statistical physics. We have derived perturbation bounds on the relative error of the invariant distribution that reveal these variations in sensitivity. Our bounds are sharp, we do not impose any structural assumptions on the transition matrix or on the perturbation, and computing the bounds has the same complexity as computing the invariant distribution or computing other bounds in the literature. Moreover, our bounds have a simple interpretation in terms of hitting times, which can be used to draw intuitive but rigorous conclusions about the sensitivity of a chain to various types of perturbations.

Recommendations

• A critical account of perturbation analysis of Markov chains
• Sensitivity to perturbation of the stationary distribution: Some refinements
• Sensitivity and convergence of uniformly ergodic Markov chains
• Uniform Stability of Markov Chains
• Blockwise Perturbation Theory for Markov Chains

Cites work

• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 19232 (Why is no real title available?)
• Applications of Paz's inequality to perturbation bounds for Markov chains
• Comparison of perturbation bounds for the stationary distribution of a Markov chain
• Entrywise perturbation theory and error analysis for Markov chains
• Group inverses of M-matrices and their applications
• Markov Chains
• Markov chain sensitivity measured by mean first passage times
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On a question concerning condition numbers for Markov chains
• 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
• Perturbation theory for linear operators.
• Sensitivity of the stationary distribution vector for an ergodic Markov chain
• Stationary distributions and mean first passage times of perturbed Markov chains
• 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

Cited in

(11)

• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
• Sensitivity and convergence of uniformly ergodic Markov chains
• A metric on directed graphs and Markov chains based on hitting probabilities
• Acute perturbation of the group inverse
• Aggregation Methods for Computing Steady States in Statistical Physics
• Stratification as a General Variance Reduction Method for Markov Chain Monte Carlo
• Optimizing Weighted Ensemble Sampling of Steady States
• Convergence of stratified MCMC sampling of non-reversible dynamics
• A note on entrywise perturbation theory for Markov chains
• Sensitivity of the stationary distributions of denumerable Markov chains
• A critical account of perturbation analysis of Markov chains

This page was built for publication: Sharp entrywise perturbation bounds for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265002)