Robust Mixing

In this paper, we develop a new “robust mixing” framework for reasoning about adversarially modified Markov Chains (AMMC). Let ℙ be the transition matrix of an irreducible Markov Chain with stationary distribution

π

. An adversary announces a sequence of stochastic matrices

$\{{\mathbb{A}}_t\}_{t > 0}$

satisfying

$\pi{\mathbb{A}}_t = \pi$

. An AMMC process involves an application of ℙ followed by

${\mathbb{A}}_t$

at time

t

. The robust mixing time of an irreducible Markov Chain ℙ 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 {\pmod 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 ×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, Lovász and Pak showed that for a reversible ergodic Markov Chain ℙ, any reversible lifting ℚ of ℙ must satisfy

${\mathcal{T}}({\mathbb{P}}) \leq {\mathcal{T}}(\mathbb{Q})\log (1/\pi_*)$

where

π

*

is the minimum stationary probability. Looking at a specific adversarial strategy allows us to show that

${\mathcal{T}}(\mathbb{Q}) \geq r({\mathbb{P}})$

where

r

(ℙ) is the relaxation time of ℙ. This helps identify cases where reversible liftings cannot improve the mixing time by more than a constant factor.