SHARP ENTRYWISE PERTURBATION BOUNDS FOR MARKOV CHAINS

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 pertu...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 2015, Vol.36 (3), p.917-941
Main Authors: Thiede, Erik, VAN Koten, Brian, Weare, Jonathan
Format: Article
Language:English
Subjects:
Chains
Computation
Error detection
Extreme values
Invariants
Markov chains
Molecular conformation
Perturbation methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0895-4798
1095-7162
DOI:10.1137/140987900