2026-07-23T15:38:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25405 2026-03-19T13:04:36Z ddc:004 open_access

Markov Chain Robustness Zuckerman, David Markov chain random walk mixing time hitting time cover time robustness expander graph When a Markov chain models nature or social interactions, it is likely not followed exactly, but only approximately. We therefore introduce several notions of robustness for a Markov chain P. Our standard adversary can dynamically change transition probabilities of P by 1 ± ε, and our strong adversary can completely control each transition independently with probability ε, as in a model by Azar, Broder, Karlin, Linial, and Philips [Y. Azar et al., 1996]. These adversaries are equivalent up to constant factors if the degrees are constant. Our adversarial chains need not converge. We define and prove various robustness properties of a reversible chain P, i.e., a random walk on a connected undirected graph G. Let d be the maximum degree, Δ the diameter, π the stationary distribution, and t_{mix} the mixing time. 1) We define a natural analogue π^+(S) that upper bounds limiting frequencies in a set S in the adversarial chain. We show that if ε = O(1/√{dt_{up}}), where t_{up} is a variant of the mixing time, then π^+(S) = O(π(S)^{1-α}) for any α > 0. 2) We define the mixing time robustness as the largest ε such that the approximate mixing time increases by only a constant factor, and prove that it is Ω(1/√{dt_{mix}}). 3) We define the hitting time robustness as the largest ε such that the maximum hitting time increases by only a constant factor, and show that it is Ω(1/t_{mix}). For trees, we show it is Ω(1/Δ). 4) We define the cover time robustness as the largest ε such that the cover time increases by only a constant factor. We show that in most graphs it’s at least the hitting time robustness. 5) We characterize the mixing, hitting, and cover time robustnesses for constant-degree regular expander graphs up to constant factors. They are Θ(1), Θ(1/log n), and Θ(1/log n), respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Zuckerman 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.118 urn:nbn:de:0030-drops-254056 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.118 eng https://creativecommons.org/licenses/by/4.0/legalcode