A curiously slowly mixing Markov chain

Abstract

We study a Markov chain with very different mixing rates depending on how mixing is measured. The chain is the "Burnside process on the hypercube $C_2^n$." Started at the all-zeros state, it mixes in a bounded number of steps, no matter how large $n$ is, in ${\ell }^1$ and in ${\ell }^2$. And started at general $x$, it mixes in at most $\log n$ steps in ${\ell }^1$. But, in ${\ell }^2$, it takes $\frac{n}{\log n}$ steps for most starting $x$. The ${\ell }^2$ mixing results follow from an explicit diagonalization of the Markov chain into binomial-coefficient-valued eigenvectors.

Please feel free to make comments! (The connection to Schur--Weyl duality has been moved to a separate paper, and some results have been slightly improved.)