Eigenvalue bounds for Markov Chains on Multislices

Consider the following natural random walk whose states are the balanced vectors of $\{0,1\}^n$, i.e., the balanced Boolean slice with an equal number of $0$s and $1$s, where a single step of the random walk takes a state $u$ to a state $v$ at Hamming distance exactly $n/2$ from it. One would expect this random walk to mix extremely rapidly, and indeed this has been known since (at least) the work of Delsarte in 1978.

 

Now consider the following variant of the above random walk: The states now are elements of the "balanced multislice" in $\{-1,0,1\}^n$, i.e. vectors with exactly $1/3$rd fraction of the letters $-1$, $0$ and $1$, and a single step moves from a balanced vector $u$ to a random balanced vector $v$ obtained by flipping exactly $1/3$ fraction of each of the letters of $u$ to $-1$, $0$ and $1$. (So for a single coordinate $i$, $v_i$ is uniform in $\{-1,0,1\}$ conditioned on $u_i$.) It is intuitive to believe that such a random walk should also converge to the uniform distribution over all balanced vectors extremely fast, but this seems not to have been known till now.

 

In this talk I will use and convey my limited knowledge of representation theory to show how to prove such a result. Specifically we show that for every s, the random walk matrix of any *symmetric* walk on the balanced multislice in Z_s^{sn} that takes *nearly uniform* steps has second eigenvalue o_n(1). ["Symmetric" requires random walk is invariant under permutations of S_n, and "Nearly uniform" implies that if the walk moves from u to v with positive probability that the distribution of (u_i,v_i) for random i is nearly uniform on Z_s^2.]