= Spectral gap of the adjacent transposition shuffle
{title2=$\gamma=2(1-\cos(\pi/n))/n$}
For the <random adjacent transposition shuffle> with $n\geq2$, 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\leq\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$.
Back to article page
