Random adjacent transposition shuffle

On the symmetric group $S_n$, this Markov chain chooses uniformly from the identity and the $n-1$ adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities $1/n$ to existing neighbours.

For the random adjacent transposition shuffle with $n\ge 2$, the generator $P-I$ is the interchange process on a path graph with each edge rate $1/n$. The Aldous spectral gap theorem reduces its spectral gap to that of the single-label random walk. The eigenfunctions $k\mapsto \cos (\ell \pi (k-1/2)/n)$, for $0\le \ell <n$, have generator eigenvalues $-2(1-\cos (\ell \pi /n))/n$; direct substitution verifies both the interior and endpoint equations. Consequently $\gamma \sim {\pi }^2/n^3$.

For the random adjacent transposition shuffle on $S_n$ with $n\ge 2$, the position $f(\sigma )={\sigma }^{-1}(i)$ of one label is uniform on $\{1,\dots ,n\}$ in equilibrium, so ${\mathrm{Var}}_{\pi }(f)=(n^2-1)/12$. Each adjacent transposition moves the label with probability $2/n$, giving $\mathcal{E}(f,f)=(n-1)/n^2$. The Poincare inequality for a reversible Markov chain variational formula therefore gives $\gamma \le 12/[n^2(n+1)]$. In particular the continuous uniform distribution on $(0,1)$ has variance $1/12$, not $1/6$.