= Solution
The <symmetric group> has $n!$ elements, not the printed order $n$. For $n\geq2$ the identity and the $n-1$ adjacent <transpositions> have probabilities $1/n$, so the specified <transition matrix> is normalized. Its <stationary distribution> is uniform and it satisfies <detailed balance>, since each <transposition> is its own inverse. Adjacent <transpositions> generate the <symmetric group>, making this an <irreducible Markov chain>; the positive holding probability makes it an <aperiodic Markov chain>.
For a fixed label $i$, right multiplication swaps positions, so $f(\sigma)=\sigma^{-1}(i)$ is the label's position. Under the <uniform distribution on a finite set> it is uniform on $\{1,\ldots,n\}$. Therefore
$$
\pi(f)=\frac{n+1}{2},\qquad\operatorname{Var}_\pi(f)=\frac{n^2-1}{12}.
$$
For each generator $s_j=(j,j+1)$, the squared change $[f(\sigma s_j)-f(\sigma)]^2$ is one if the label occupies either of the two positions, and zero otherwise. Its stationary <expected value> is $2/n$, giving
$$
\mathcal E(f,f)=\frac12\sum_{j=1}^{n-1}\frac1n\frac2n=\frac{n-1}{n^2}.
$$
Thus the <tagged-label Rayleigh quotient for adjacent transpositions> gives the corrected bound
$$
\boxed{\gamma\leq\frac{12}{n^2(n+1)}=\frac{12}{n^3}(1+o(1)).}
$$
The printed factor six cannot be obtained: the hint's <variance of a uniform distribution> is wrong. Directly, $\operatorname{Var}(U)=\int_0^1u^2\,du-(\int_0^1u\,du)^2=1/12$. Bounded <convergence in distribution> of $U_n$ does imply convergence of its first two moments, hence convergence of its <variance>, but the limit is $1/12$.
More strongly, the claimed asymptotic bound itself is false for this kernel. The <Aldous spectral gap theorem> states that the <interchange process> on a finite connected weighted <graph> has the same <spectral gap> as the single-label <random walk> with identical edge rates; see https://arxiv.org/abs/0906.1238[Theorem 1.1 and its proof]. Here $P-I$ is that <interchange process> generator on a <path graph> with edge rates $1/n$. For the tagged-label generator, direct substitution of $g_\ell(k)=\cos(\ell\pi(k-1/2)/n)$ gives <eigenvalues> $-2(1-\cos(\ell\pi/n))/n$, $0\leq\ell<n$, including the reflecting endpoint equations. These $n$ distinct <eigenvalues> exhaust the tagged-label function space. Consequently the theorem yields
$$
\boxed{\gamma=\frac2n\left(1-\cos\frac\pi n\right)\sim\frac{\pi^2}{n^3},}
$$
which exceeds $6/n^3$ asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.
Back to article page
