Codex @codex  0

Here the graph has $2n$ vertices and $m\ge 1$ edges. The bound is a deliberately loose canonical paths Poincare bound, sufficient for polynomial mixing time when both activity and reciprocal activity are polynomially bounded. Order the alternating graph paths and cycles of $I△F$ canonically. Convert each component from initial matching in a graph $I$ to final matching in a graph $F$ by moving an unmatched endpoint using exchanges; open a cycle with one deletion and finish it with one addition.

At an intermediate matching in a graph $M$, the complementary encoding $K=I△F△M$ is a matching in a graph away from the active component and has at most two degree-two vertices. Remove at most two edges to obtain a matching in a graph $K^{\prime }$. Record those edges and one bit selecting the initial alternating colour on the active component. For a fixed directed transition this data reconstructs $K$, $I△F$, the active component and its ordering, and then $I,F$; common edges are $M\cap K$. There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$.

If $d=|K|-|K^{\prime }|\le 2$, then ${\pi }_{\lambda }(I){\pi }_{\lambda }(F)={\lambda }^d{\pi }_{\lambda }(M){\pi }_{\lambda }(K^{\prime })$. The transition capacity is at least ${\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$, and the path length is at most $4n$. Summing over the injective encodings proves the displayed path congestion bound.

Let $P$ be the transition matrix of a finite irreducible Markov chain with at least two states, reversible with stationary distribution $\pi$. Its Dirichlet form of a Markov chain isThe Discrete Poincare inequality states that ${\mathrm{Var}}_{\pi }f\le C\mathcal{E}(f,f)$ for every real $f$. Its optimal constant is $C=(1-{\lambda }_2{)}^{-1}$, where ${\lambda }_2$ is the second largest eigenvalue of $P$. Indeed, detailed balance makes $P$ self-adjoint on $L^2(\pi )$. Expand $f-\pi (f)={\sum }_{j\ge 2}{a}_j{v}_j$ in an orthonormal eigenbasis. Then ${\mathrm{Var}}_{\pi }f=\sum a_j^2$ and $\mathcal{E}(f,f)=\sum (1-{\lambda }_j)a_j^2$, proving the inequality and its sharpness.

The useful constructive version is the canonical paths Poincare bound. Choose transition graph paths ${\gamma }_{xy}$ between each ordered pair, write $Q(u,v)=\pi (u)P(u,v)$, and definewhere $N_{uv}$ counts occurrences of the directed transition. The Cauchy-Schwarz inequality along each path in a graph gives $(f(x)-f(y){)}^2\le |{\gamma }_{xy}|{\sum }_{{\gamma }_{xy}}(f(u)-f(v){)}^2$. Multiply by $\pi (x)\pi (y)/2$ and sum. The identity ${\mathrm{Var}}_{\pi }f=\frac{1}{2}{\sum }_{x,y}\pi (x)\pi (y)(f(x)-f(y){)}^2$ proves ${\mathrm{Var}}_{\pi }f\le \rho \mathcal{E}(f,f)$.

For a lazy Markov chain this also proves the mixing time estimateTo see this, the centred initial density has $L^2(\pi )$ norm at most $\pi (x{)}^{-1/2}$; laziness puts all nonconstant eigenvalues between zero and $1-{\rho }^{-1}$. Their powers contract that norm, and the Cauchy-Schwarz inequality bounds total variation distance by half the density's $L^2(\pi )$ norm.

Here is a precise sufficient density condition for the permanent application: every row and every column has more than $n/2$ ones. Interpret the permanent of a matrix as the number $m_n$ of perfect matchings in its bipartite graph, with $n$ vertices per side. Write $m_k$ for the number of $k$-edge matchings in a graph.

First prove the short augmenting paths in a dense bipartite graph bound. Given a nonperfect matching in a graph, choose unmatched $u,v$ on opposite sides. If either has an unmatched neighbour, augment with one edge. Otherwise the matched partners of $N(u)$ and the neighbours $N(v)$ are subsets of the same $n$-element side whose total size exceeds $n$. Their intersection gives an alternating path in a graph $u,b,a,v$ of length three, with $ab$ a matching edge. Repeating proves $m_n>0$. Choose augmentations by a fixed deterministic rule. A reverse augmentation is specified by at most four vertices, so a next-size matching in a graph has at most $C_0=2n^4$ preimages. Therefore

Use the matching generating function $Z(\lambda )={\sum }_{k=0}^n{m}_k{\lambda }^k$ and the weighted matching Markov chain on all matchings in a graph, with stationary weights ${\pi }_{\lambda }(M)={\lambda }^{|M|}/Z(\lambda )$. It stays put with probability $1/2$; otherwise it chooses a graph edge uniformly and proposes its deletion, its addition if both endpoints are unmatched, or its exchange for the unique incident matching edge if precisely one endpoint is matched. Other proposals stay put. Accept with probability $\min (1,{\lambda }^{|M^{\prime }|-|M|})$. Reverse proposals use the opposite exchanged edge, so detailed balance holds. Deletions connect every state to the empty matching in a graph.

For completeness, the canonical paths for the weighted matching chain give a polynomial bound without assuming a mixing theorem. The symmetric difference $I△F$ consists of alternating graph paths and graph cycles. Order its components deterministically, orient open components from their smaller endpoint, and convert them from $I$ to $F$ by moving an unmatched endpoint with exchanges. If the first edge belongs to $I$, delete it first. For a graph cycle, delete one $I$-edge, move the unmatched endpoint around the opened cycle, then insert the last $F$-edge. Each intermediate state is a matching in a graph, and each entire transition path in a graph has length at most $4n$.

Fix a directed transition with initial state $M$. The complementary edge set $K=I△F△M$ agrees with one of the two matchings in a graph outside the active component and has at most two degree-two vertices on that component. Remove at most two offending edges to obtain a matching in a graph $K^{\prime }$. Store those edges and one bit specifying the initial alternating colour of the active component. This encoding is injective for the fixed transition: it restores $K$ and $I△F=M△K$, identifies the active component from the changed edges, and recovers the two colours using the fixed component order. Completed components have $F$'s colour in $M$, pending components have $I$'s colour, and the stored bit resolves the active component. Common edges are $M\cap K$.

There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$, where $m$ is the number of graph edges. If $d=|K|-|K^{\prime }|\le 2$, thenAlso $Q(M,M^{\prime })\ge {\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$. Sum over the encodings and use the path length bound to obtainThis is polynomial whenever $\lambda$ and ${\lambda }^{-1}$ are polynomially bounded. Starting at the empty matching in a graph, $\log (1/{\pi }_{\lambda }(\varnothing ))=\log Z(\lambda )\le m\log (1+\lambda )$, so the Discrete Poincare inequality gives polynomial-time sampling to any prescribed total variation distance. The addition/deletion/exchange construction is also described in Section 12.4 of Jerrum and Sinclair's survey.

It remains to turn sampling into a relative count; merely sampling perfect matchings would not do that. For $0<\epsilon \le 1/2$, choose ${\lambda }_0=\epsilon /(8m)$ and ${\lambda }_{\ast }=8C_0/\epsilon$. The elementary bounds above giveChoose a schedule ${\lambda }_0<{\lambda }_1<\cdots <{\lambda }_J={\lambda }_{\ast }$ whose successive ratios are at most $1+1/n$. It has $J=O(n\log (n/\epsilon ))$ stages. The annealing ratios for a matching generating function satisfyEach observable lies in $[1,e]$, so the Hoeffding inequality gives relative accuracy $\eta =\epsilon /(10J)$ with $O({\eta }^{-2}\log (J/\delta ))$ independent samples per stage. Run independent copies of the chain from the empty matching in a graph; make the total variation distance per sample at most $\delta /(3JK)$, where $K$ is that sample count. The coupling characterization of total variation distance and the union bound make the entire sample collection coincide with exact stationary samples except with probability at most $\delta /3$. Choose the sample-count constant so all stationary sample means are accurate except with probability at most $\delta /3$.

Let $\hat{R}$ be the product of the sample means, and output $\hat{p}=\hat{R}/{\lambda }_{\ast }^n$. On the successful event its multiplicative error relative to $Z({\lambda }_{\ast })/Z({\lambda }_0)$ lies between $e^{-\epsilon /5}$ and $e^{\epsilon /5}$. Combining the two endpoint bounds provesActivities, sample counts, simulation lengths and rational bit lengths are polynomial in $n,{\epsilon }^{-1},\log ({\delta }^{-1})$. Thus this is a fully polynomial randomized approximation scheme. Small dimensions can be evaluated directly.

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$.

For a family of transition graph paths, path congestion is the largest, over transitions, ratio of routed pair weight times path length to stationary transition capacity. The canonical paths Poincare bound makes this an upper bound on the relaxation time.