Speeding up Markov chains with deterministic jumps (Q2210752)

Let \(S\) be a finite set and \(P\) an irreducible and aperiodic Markov transition matrix, satisfying \(p_{ii} >0\) for all \(i\), and \(p_{ij}>0\) if and only if \(p_{ji} >0\). Suppose also that the uniform distribution on \(S\) is invariant for \(P\). For a bijection \(f:S \to S\), consider a Markov chain with transition matrix \(Q\) which represents a Markov transition governed by \(P\) followed by deterministic mapping by \(f\); that is, \(Q = \Pi P\) where \(\Pi = (\pi_{ij})_{i,j \in S}\) is the permutation matrix defined by \(\pi_{ij} = 1\) if \(j = f(i)\) and \(0\) otherwise. The uniform distribution is also invariant for \(Q\). The goal of the present paper is to demonstrate the existence of functions \(f\) for which the Markov chain driven by \(Q\) mixes much faster than that driven by \(P\). The authors establish in Theorem 2.1 an expansion condition on \(f\) and \(P\) that ensures that the total-variation convergence of the \(Q\)-chain has an exponential rate that depends only on the value of the smallest positive \(p_{ij}\). The size \(|S|\) of the state space enters explicitly only as a polynomial factor \(\sqrt{ |S| }\). Then in Theorem 2.2 it is shown that for a given \(P\), the class of \(f\) that ensures fast mixing is relatively abundant in a sense that is quantified in terms of \(|S|\). As an example, suppose that \(P\) corresponds to the lazy random walk on the discrete circle \(\mathbb{Z}_n\) that has probability \(1/3\) of jumping left, right, or staying in the same site. Then the \(P\)-chain mixes in time \(O ( n^2)\), while the results of this paper show that all but \(O(n^{-\gamma})\) of the bijections \(f\) on \(\mathbb{Z}_n\) are sufficient to ensure that the corresponding \(Q\)-chain mixes in time \(O(\log n)\); here \(\gamma > 0\) is a universal constant.