= Spectrum of lazy random walk on the hypercube
{title2=$\lambda_k=1-k/n$}
For <random walk> on $\{-1,1\}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the <Walsh characters> $f_J(x)=\prod_{j\in J}x_j$ form an <orthonormal eigenbasis> under the <uniform distribution on a finite set>. Flipping a coordinate in $J$ negates $f_J$, so $Pf_J=(1-|J|/n)f_J$. Hence $1-k/n$ has <multiplicity> $\binom nk$, and the ordinary and absolute <spectral gaps> both equal $1/n$.
Back to article page
