# Robustness of large-scale stochastic matrices to localized perturbations

arXiv: https://arxiv.org/abs/1309.0158 · HTML: https://mlsanity.com/paper/1309.0158/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2013.

## Built on by (most cited first, 1 of 1)

- [Wisdom of Crowds Through Myopic Self-Confidence Adaptation](https://mlsanity.com/paper/2506.18195/) (2025)

## Abstract (arXiv)

Upper bounds are derived on the total variation distance between the invariant distributions of two stochastic matrices differing on a subset W of rows. Such bounds depend on three parameters: the mixing time and the minimal expected hitting time on W for the Markov chain associated to one of the matrices; and the escape time from W for the Markov chain associated to the other matrix. These results, obtained through coupling techniques, prove particularly useful in scenarios where W is a small subset of the state space, even if the difference between the two matrices is not small in any norm. Several applications to large-scale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging and consensus algorithms, and interacting particle systems.