Sharp Entrywise Perturbation Bounds for Markov Chains

DOI10.1137/140987900zbMATH Open1319.65009arXiv1410.1431OpenAlexW1926909847WikidataQ43213396 ScholiaQ43213396MaRDI QIDQ5265002FDOQ5265002

Brian van Koten, Jonathan Weare, Erik H. Thiede

Publication date: 21 July 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1410.1431

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Perturbation theory for linear operators.
• Perturbation theory and finite Markov chains
• The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
• Markov Chains
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perturbation bounds for the stationary probabilities of a finite Markov chain
• Comparison of perturbation bounds for the stationary distribution of a Markov chain
• On a question concerning condition numbers for Markov chains
• Markov chain sensitivity measured by mean first passage times
• On the first and second order derivatives of the Perron vector
• Applications of Paz's inequality to perturbation bounds for Markov chains
• Entrywise perturbation theory and error analysis for Markov chains
• Sensitivity of the stationary distribution vector for an ergodic Markov chain
• Using the QR Factorization and Group Inversion to Compute, Differentiate, and Estimate the Sensitivity of Stationary Probabilities for Markov Chains
• Uniform Stability of Markov Chains
• Perturbation of the stationary distribution measured by ergodicity coefficients

Cited In (8)

• 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
• A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs

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)