On Algorithmic Robustness of Corrupted Markov Chains
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913950333927424 |
|---|---|
| author | Gaitonde, Jason Mossel, Elchanan |
| author_facet | Gaitonde, Jason Mossel, Elchanan |
| contents | We study the algorithmic robustness of general finite Markov chains in terms of their stationary distributions to general, adversarial corruptions of the transition matrix. We show that for Markov chains admitting a spectral gap, variants of the \emph{PageRank} chain are robust in the sense that, given an \emph{arbitrary} corruption of the edges emanating from an $ε$-measure of the nodes, the PageRank distribution of the corrupted chain will be $\mathsf{poly}(\varepsilon)$ close in total variation to the original distribution under mild conditions on the restart distribution. Our work thus shows that PageRank serves as a simple regularizer against broad, realistic corruptions with algorithmic guarantees that are dimension-free and scale gracefully in terms of necessary and natural parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15176 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Algorithmic Robustness of Corrupted Markov Chains Gaitonde, Jason Mossel, Elchanan Probability Data Structures and Algorithms We study the algorithmic robustness of general finite Markov chains in terms of their stationary distributions to general, adversarial corruptions of the transition matrix. We show that for Markov chains admitting a spectral gap, variants of the \emph{PageRank} chain are robust in the sense that, given an \emph{arbitrary} corruption of the edges emanating from an $ε$-measure of the nodes, the PageRank distribution of the corrupted chain will be $\mathsf{poly}(\varepsilon)$ close in total variation to the original distribution under mild conditions on the restart distribution. Our work thus shows that PageRank serves as a simple regularizer against broad, realistic corruptions with algorithmic guarantees that are dimension-free and scale gracefully in terms of necessary and natural parameters. |
| title | On Algorithmic Robustness of Corrupted Markov Chains |
| topic | Probability Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.15176 |