Fast mixing of a randomized shift-register Markov chain

Abstract

We present a Markov chain on the $n$-dimensional hypercube $\{0,1{\}}^n$ which satisfies $t_{\mathrm{mix}}(\epsilon )=n[1+o(1)]$. This Markov chain alternates between random and deterministic moves and we prove that the chain has cut-off with a window of size at most $O(n^{0.5+\delta })$ where $\delta >0$. The deterministic moves correspond to a linear shift register.

17 pages. Revised Sections 1 and 2, added additional references. Proof of Lemma 5 expanded