Markov Chain Robustness

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.