{"ID":2892023,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.15176","arxiv_id":"2507.15176","title":"On Algorithmic Robustness of Corrupted Markov Chains","abstract":"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.","short_abstract":"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{arbitra...","url_abs":"https://arxiv.org/abs/2507.15176","url_pdf":"https://arxiv.org/pdf/2507.15176v1","authors":"[\"Jason Gaitonde\",\"Elchanan Mossel\"]","published":"2025-07-21T01:48:12Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.DS\"]","methods":"[]","has_code":false}