×

Robust mixing. (English) Zbl 1127.60069

Summary: We develop a new robust mixing framework for reasoning about adversarially modified Markov chains (AMMC). Let \(\mathbb{P}\) be the transition matrix of an irreducible Markov chain with stationary distribution \(\pi\). 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 \(\mathbb{P}\) followed by \(\mathbb{A}_t\) at time \(t\). The robust mixing time of an ergodic Markov chain \(\mathbb{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 \(L_t:=t\pmod n\) with a random card. Mossel, Peres and Sinclair (2004) showed a lower bound of \((0.0345+o(1))n\log n\) for the mixing time of the random-to-cyclic transposition process. They also considered a generalization of this process where the choice of \(L_t\) is adversarial, and proved an upper bound of \(Cn\log n+O(n)\) (with \(C\approx 4\times 10^5)\) on the mixing time. We reduce the constant to 1 by showing that the random-to-top transposition chain (a Markov chain) has robust mixing time \(\leq n\log n+ O(n)\) when the adversarial strategies are limited to holomorphic strategies, i.e., those strategies which preserve the symmetry of the underlying Markov chain. We also show a \(O(n\log^2n)\) bound on the robust mixing time of the lazy random-to-top transposition chain when the adversary is not limited to holomorphic strategies.
Reversible liftings: Chen, Lovasz and Pak showed that for a reversible ergodic Markov chain \(\mathbb{P}\), any reversible lifting \(\mathbb{Q}\) of \(\mathbb{P}\) must satisfy \({\mathcal T} (\mathbb{P})\leq{\mathcal T}(\mathbb{Q})\log(1/\pi_*)\) where \(\pi_*\) 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(\mathbb{P})\) is the relaxation time of \(\mathbb{P}\). This gives an alternate proof of the reversible lifting result and helps identify cases where reversible liftings cannot improve the mixing time by more than a constant factor.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
62M09 Non-Markovian processes: estimation
62M15 Inference from stochastic processes and spectral analysis
PDFBibTeX XMLCite
Full Text: DOI EuDML