= Solution
For each <subset> $J\subseteq\{1,\ldots,n\}$, take the <Walsh character> $f_J(x)=\prod_{j\in J}x_j$, including $f_\varnothing\equiv1$. Under the <uniform distribution on a finite set> these functions are an <orthonormal basis>: $f_Jf_K=f_{J\triangle K}$ has mean zero unless $J=K$, since the coordinates are independent fair signs. There are $2^n$ such functions, the full dimension of the function space.
Flipping a coordinate in $J$ changes the sign, while flipping one outside $J$ leaves the value unchanged. The total probability of a sign change is $|J|/(2n)$, so
$$
Pf_J=\left(1-\frac{|J|}{n}\right)f_J.
$$
The <spectrum of lazy random walk on the hypercube> is therefore
$$
\boxed{\lambda_k=1-\frac{k}{n}\quad\text{with multiplicity }\binom nk,\quad0\leq k\leq n.}
$$
All <eigenvalues> are nonnegative and the second largest is $1-1/n$. Hence both the ordinary <spectral gap> and the absolute <spectral gap> equal $\boxed{\gamma=1/n}$. The requested bound in part (c) is smaller than the exact gap by a factor $2n$; even the refined increasing-coordinate <canonical paths Poincare bound> loses a factor $(n+1)/2$. The true optimal <Poincare inequality for a reversible Markov chain> constant is $n$.
Back to article page
