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₌₈ₗ 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ₔ), where tₔ 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₌₈ₗ). 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₌₈ₗ). 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.
David Zuckerman (Thu,) studied this question.