Fast mixing of a randomized shift-register Markov chain

We present a Markov chain on the $n$-dimensional hypercube $\{0,1\}^n$ which satisfies $t_{\rm mix}(ε) = 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+δ})$ where $δ>0$. The deterministic moves correspond to a linear shift register.

No reviews yet.

No comments yet.