On Algorithmic Robustness of Corrupted Markov Chains

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 PageRank chain are robust in the sense that, given an arbitrary corruption of the edges emanating from an ε-measure of the nodes, the PageRank distribution of the corrupted chain will be mathsfpoly(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.