= Solution
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, while
$$
Q(u,u^{(k)})=\frac{2^{-n}}{2n},\qquad
\sum_{(x,y):e\in\eta_{xy}}\pi(x)\pi(y)=2^{n-1}2^{-2n}=2^{-n-1}.
$$
The unweighted load divided by capacity equals $n$; multiplying by the maximum length yields $\rho\leq n^2$. The <canonical paths Poincare bound> therefore proves the slightly stronger $\operatorname{Var}_\pi(f)\leq n^2\mathcal E(f,f)$, and in particular the requested
$$
\boxed{\operatorname{Var}_\pi(f)\leq2n^2\mathcal E(f,f),\qquad\gamma\geq\frac1{2n^2}.}
$$
One 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$.
Back to article page
