Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 215 / 3

On a finite state space with at least two states, as in the surrounding questions, for a real function write $\pi (f)={\sum }_x\pi (x)f(x)$ and ${\mathrm{Var}}_{\pi }(f)={\sum }_x\pi (x)(f(x)-\pi (f){)}^2$. The Poincare inequality for a reversible Markov chain with constant $C$ iswhere the Dirichlet form of a Markov chain isThe associated spectral gap is the ordinary gap $\gamma =1-{\lambda }_2$, with variational formulaEquivalently minimize $\mathcal{E}(f,f)$ subject to $\pi (f)=0$ and $⟨f,f{⟩}_{\pi }=1$. Thus the Poincare inequality for a reversible Markov chain holds precisely for $C\ge 1/\gamma$, and the optimal constant is $1/\gamma$. It controls the ordinary rather than absolute spectral gap, so negative eigenvalues do not invalidate it. If the unspecified state space in this part is infinite, the Poincare inequality for a reversible Markov chain and the variational infimum still make sense on nonconstant functions in $L^2(\pi )$, using the self-adjoint operator on that Hilbert space; the resulting spectral gap need not be represented by an actual second eigenvalue. The finite-state formula above is the intended specialization.

For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity $Q(u,v)=\pi (u)P(u,v)$. For every ordered pair $(x,y)$ choose a path ${\eta }_{xy}$ from $x$ to $y$ using only positive-capacity edges; take the empty path for $x=y$. Let $N_e(\eta )$ count occurrences of the directed edge $e$. The canonical paths Poincare bound says thatis a valid Poincare inequality for a reversible Markov chain constant. Simple paths give $N_e\in \{0,1\}$; allowing repetitions requires the multiplicities shown.

To prove the theorem, expand the variance using two independent samples from $\pi$:Telescoping along ${\eta }_{xy}$ and applying the Cauchy-Schwarz inequality givesInterchange the finite sums, then use the definition of $\rho$:Consequently $\boxed{{\mathrm{Var}}_{\pi }(f)\le \rho \mathcal{E}(f,f),\gamma \ge 1/\rho }$. All edges here are directed, so the $1/2$ in the Dirichlet form of a Markov chain is retained consistently.

The lazy Markov chain has holding probability $1/2$ and transition probability $1/(2n)$ to each neighbour in the hypercube graph. Its stationary distribution is $\pi (x)=2^{-n}$ by symmetry.

For $(x,y)$ choose the path changing the differing coordinates in increasing order. Its length is at most $n$. Fix a directed edge $(u,u^{(k)})$ that flips coordinate $k$. A path uses this edge exactly when $x_k=u_k$, $y_k=-u_k$, $y_j=u_j$ for $j<k$, and $x_j=u_j$ for $j>k$. The coordinates $x_j$ for $j<k$ and $y_j$ for $j>k$ are free. Thus exactly $2^{n-1}$ ordered pairs use it, whileThe unweighted load divided by capacity equals $n$; multiplying by the maximum length yields $\rho \le n^2$. The canonical paths Poincare bound therefore proves the slightly stronger ${\mathrm{Var}}_{\pi }(f)\le n^2\mathcal{E}(f,f)$, and in particular the requestedOne can keep the actual lengths: among these $2^{n-1}$ pairs, coordinate $k$ always differs, and each of the other $n-1$ coordinates differs for half the pairs. Their mean path length is $(n+1)/2$, giving exact congestion $\rho =n(n+1)/2$. This refinement still has order $n^2$.

For each subset $J\subseteq \{1,\dots ,n\}$, take the Walsh character $f_J(x)={\prod }_{j\in J}{x}_j$, including $f_{\varnothing }\equiv 1$. Under the uniform distribution on a finite set these functions are an orthonormal basis: $f_J{f}_K=f_{J△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)$, soThe spectrum of lazy random walk on the hypercube is thereforeAll 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$.