A non-local Random Walk on the Hypercube

Abstract

This paper studies the random walk on the hypercube $(\mathbb{Z}/2\mathbb{Z}{)}^n$ which at each step flips $k$ randomly chosen coordinates. We prove that the mixing time for this walk is of order $\frac{n}{k}\log n$. We also prove that if $k=o(n)$, then the walk exhibits cutoff at $\frac{n}{2k}\log n$ with window $\frac{n}{2k}$.

arXiv comment17 pages, accepted for publication by the Applied Probability Trust in Advances in Applied Probability 49.4 (December 2017)