Robust Mixing

摘要

In this paper, we develop a new "robust mixing" framework for reasoning about adversarially modified Markov Chains (AMMC). Let P be the transition matrix of an irreducible Markov Chain with stationary distribution π. An adversary announces a sequence of stochastic matrices {A_t}_(t > 0) satisfying πA_t = π. An AMMC process involves an application of P followed by A_t at time t. The robust mixing time of an irreducible Markov Chain P is the supremum over all adversarial strategies of the mixing time of the corresponding AMMC process. Applications include estimating the mixing times for certain non-Markovian processes and for reversible liftings of Markov Chains. Non-Markovian card shuffling processes: The random-to-cyclic transposition process is a non-Markovian card shuffling process, which at time t, exchanges the card at position t (mod n) with a random card. Mossel, Peres and Sinclair (2004) showed that the mixing time of this process lies between (0.0345 + o(1))n log n and Cn log n + O(n) (with C ≈ 4 x 10~5). We reduce the constant C to 1 by showing that the random-to-top transposition chain (a Markov Chain) has robust mixing time ≤ n log n + O(n) when the adversarial strategies are limited to those which preserve the symmetry of the underlying Markov Chain. Reversible liftings: Chen, Lovasz and Pak showed that for a reversible ergodic Markov Chain P, any reversible lifting Q of P must satisfy T(P) ≤ T(Q) log(1/π_*) where π_* is the minimum stationary probability. Looking at a specific adversarial strategy allows us to show that T(Q) ≥ r(P) where r(P) is the relaxation time of P. This helps identify cases where reversible liftings cannot improve the mixing time by more than a constant factor.