==== TABLE OF CONTENTS ====
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//algorithms.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//dense.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//introduction.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//macros.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//main.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//model-and-graph.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//repair.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//signatures.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//transport.tex
Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//sources.bib
===========================
==== BEGIN Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//algorithms.tex ====
\section{Sampling algorithms and exact correction}\label{sec:algorithms}
We now turn the weighted graph bound into an algorithm using unbiased random
bits. All deterministic choices, including greedy completions, neighbor
orders, and tie breaking, are fixed once and for all. Abbreviate
$\Omega(r,c)$ by $\Omega$. Write
$\nu_X$ for the uniform law on $\mathcal F_X$ and $z_0$ for a greedy original
table. Its restriction to the small slots gives a starting transversal $X_0$.
\subsection{The ideal chain}
Set
\[
q_{\rm s}=\lceil\log_2(32d^2)\rceil,
\qquad p=2^{-q_{\rm s}}.
\]
List the distinct feasible neighbors of a state $X$ in a fixed order.
Assign one of the $2^{q_{\rm s}}$ equally likely binary strings to each
neighbor and let all remaining strings propose a hold. This gives every
edge the same proposal probability $p$ in both directions. As explained in
Lemma~\ref{lem:repair}, the list is obtained by testing all unit exchanges,
the repair of $X$ when it is a defect, and the uniquely reconstructed inverse
repair of each possible ordered defect type. There are at most $5d^2+1$
neighbors. Each test checks only coordinate bounds, the allowed occupancy
pattern, and residual margins; it does not evaluate $f$.
Here is the completion adjustment used for a nonholding proposal $X\to Y$.
For a nonempty block $\mathcal B=I\times J$, fix a reference row $i_0$ and
column $j_0$, independently of $X$. Let
$\Delta R_i=R_i(Y)-R_i(X)$ and $\Delta P_j=P_j(Y)-P_j(X)$ be the changes in
its padded margins. Define the integer matrix $D_{XY}$ by
\[
(D_{XY})_{ij}=\begin{cases}
\Delta R_i,&i\ne i_0,\ j=j_0,\\
\Delta P_j,&i=i_0,\ j\ne j_0,\\
\Delta R_{i_0}-\sum_{j'\ne j_0}\Delta P_{j'},&i=i_0,\ j=j_0,\\
0,&i\ne i_0,\ j\ne j_0.
\end{cases}
\]
The equality of total row and column changes verifies all its row and column
sums, including the reference column. Also $D_{YX}=-D_{XY}$. Along a unit
exchange or repair edge each individual residual changes by at most two;
hence every displayed entry has magnitude at most $10d$. These formulas
also apply to a block with a single row or column.
The ideal transition draws $a\sim\nu_X$ and accepts $Y$ precisely when
$a+D_{XY}$ is nonnegative. It then belongs to $\mathcal F_Y$ because its
margins are already correct. A rejected proposal holds at $X$. If the block
is empty, every edge proposal is accepted. Denote this ideal kernel by $P$.
\begin{proposition}[Small-chain bound]\label{prop:small-chain}
The kernel $P$ is lazy and reversible for $\pi(X)=f(X)/\Lambda$. On every
edge it satisfies
\[
P(X,Y)\ge \frac{1}{128d^2}
\min\left\{1,\frac{f(Y)}{f(X)}\right\}.
\]
If there is more than one state, its inverse spectral gap is at most
$d^{160}$. Moreover
$\pi_{\min}\ge(C+1)^{-2d}$, and, for every $t\ge0$,
\begin{equation}\label{eq:small-mixing}
\TV\bigl(P^t(X_0,\cdot),\pi\bigr)
\le (C+1)^{2d}\exp(-t/d^{160}).
\end{equation}
A one-state chain is already stationary.
\end{proposition}
\begin{proof}
The proposal holds with probability at least
$1-(5d^2+1)/(32d^2)>1/2$, and rejection can only increase this probability.
Translation by $D_{XY}$ bijects the set of acceptable completions in
$\mathcal F_X$ with the corresponding set in $\mathcal F_Y$. Calling its
cardinality $c_{XY}=c_{YX}$ gives
$f(X)P(X,Y)=p c_{XY}=f(Y)P(Y,X)$.
Every nonempty completion-block margin is at least $L$. Rejection implies
that one of at most $d$ entries of a uniform completion is less than $10d$.
Lemma~\ref{lem:small-entry}, with $a=L$ and threshold $10d\le L/2$, gives
\[
\Pp(\text{rejection})\le \frac{40d^5}{L}
=\frac{40}{d^7}<\frac12.
\]
Consequently $c_{XY}\ge f(X)/2$, and in particular
$c_{XY}\ge\min(f(X),f(Y))/2$. Since $p\ge1/(64d^2)$, both the stated
transition bound and the Dirichlet-form comparison
\[
\mathcal E_P(H)\ge \frac{E(H)}{128d^2\Lambda}
\]
follow. Theorem~\ref{thm:poincare} and $U=d^{20}$ now give an inverse-gap
bound of
\begin{align*}
128d^2\bigl((1+2d^2)4d^2(U+1)^6+2\bigr)
&\le 98{,}560d^{126}\le d^{160}.
\end{align*}
Indeed the coefficient inside parentheses is at most $770d^4U^6$.
The graph is connected by Theorem~\ref{thm:poincare}, and
Proposition~\ref{prop:stationary-success} gives
$\pi_{\min}\ge(C+1)^{-2d}$. Lemma~\ref{lem:mixing} now gives
\eqref{eq:small-mixing}.
\end{proof}
\subsection{A bounded almost-uniform sampler}
For an integer $k\ge1$, put
\begin{equation}\label{eq:outer-parameters}
J_{\rm o}=d^4(k+1),\qquad
T=d^{200}(k+b)^2,\qquad h=d^4(k+b)^2.
\end{equation}
The implemented chain replaces every ideal completion draw by the
subroutine of Theorem~\ref{thm:dense-draw} with accuracy $h$; write $\mu_X$
for its output law on $\mathcal F_X$ and $Q$ for the resulting kernel.
Starting anew at $X_0$ on each trial, perform the following bounded procedure.
\begin{enumerate}
\item Run $Q$ for $T$ transitions and then make one further, independent
completion draw with law $\mu_X$ at the final state.
\item If $X$ is a transversal and every large completion entry is at least
$L$, subtract $L$ on the large block and return the resulting original
table. Otherwise this trial fails.
\item Repeat for at most $J_{\rm o}$ independent trials, and return $z_0$
if all of them fail.
\end{enumerate}
All randomness in different draws and trials is fresh. In particular, a
completion used to test a transition is discarded after that test; the
current small state is the chain's entire persistent state.
\begin{theorem}[Almost-uniform sampling]\label{thm:almost-uniform}
The preceding procedure returns a feasible table with law $p_k$ satisfying
\[
\TV\bigl(p_k,\operatorname{Uniform}(\Omega)\bigr)\le2^{-k}.
\]
Its worst-case number of bit operations is bounded by a fixed polynomial
in $d,b,k$.
\end{theorem}
\begin{proof}
We first control adaptive approximation. The dense guarantee is uniform
over feasible states:
$\TV(\mu_X,\nu_X)\le\eta:=2^{-h}$.
From a common state, couple the proposal and holding decision identically,
and maximally couple the two completion draws if there is a nonholding
proposal. Agreement of these draws gives the same acceptance decision and
the same next state. Thus
\[
\sup_X\TV\bigl(Q(X,\cdot),P(X,\cdot)\bigr)\le\eta.
\]
Couple successively until the first disagreement. Conditional on agreement
so far, the common state may be adaptive, but the same uniform conditional
bound still applies. After $T$ transitions and the terminal completion, the
probability of a disagreement is at most $(T+1)\eta$. This argument uses
neither reversibility nor a stationary-law assertion for $Q$.
By Proposition~\ref{prop:small-chain}, the additional error from replacing
the ideal terminal state by a stationary one is at most
$\tau=(C+1)^{2d}e^{-T/d^{160}}$.
In a stationary ideal trial every pair $(X,a)$ has probability
$\pi(X)/f(X)=1/\Lambda$. By Proposition~\ref{prop:stationary-success},
successful pairs are in bijection with $\Omega$, and the success probability
$s_*=|\Omega|/\Lambda$ is at least $1/[2(1+d^2)]$.
The first success among $J_{\rm o}$ independent stationary trials therefore
has, including the fallback, the exact law
\[
\bigl[1-(1-s_*)^{J_{\rm o}}\bigr]
\operatorname{Uniform}(\Omega)
+(1-s_*)^{J_{\rm o}}\delta_{z_0}.
\]
For clarity, each particular table receives first-success mass
$\sum_{j=0}^{J_{\rm o}-1}(1-s_*)^j/\Lambda
=[1-(1-s_*)^{J_{\rm o}}]/|\Omega|$.
Pregenerate all potential trials in both procedures, then apply the same
deterministic first-success-or-fallback map. The union bound and contraction
of total variation under a deterministic map give total error at most
\begin{equation}\label{eq:outer-error}
e^{-J_{\rm o}/[2(1+d^2)]}
+J_{\rm o}(C+1)^{2d}e^{-T/d^{160}}
+J_{\rm o}(T+1)2^{-h}.
\end{equation}
In particular, no error is divided by a success probability.
Each term in \eqref{eq:outer-error} is at most $2^{-k-2}$. Here are explicit
checks. Put $t=k+b\ge15$, so $d\le t$, $k+2\le t$, and
$\log_2(C+1)0$, apart from
possible source endpoints. Source integrals zero give a trivial
inequality; otherwise write $M_F=\int F>0$, $M_G=\int G>0$.
Let $u(a),v(a)$, $00$ and $P(x,x)\ge1/2$.
Set $Q(x,y)=\pi(x)P(x,y)$ and
\[
\mathcal E_P(H)=\sum_{\{x,y\}\subseteq V}
Q(x,y)(H(x)-H(y))^2,
\]
where unordered pairs have distinct endpoints. If
$\Var_\pi H\le K\mathcal E_P(H)$ for all $H$, with $K\ge1$, then,
writing $\pi_{\min}=\min_{x\in V}\pi(x)$, for every integer $t\ge0$,
\begin{equation}\label{eq:elementary-mixing}
\norm{P^t(x,\cdot)-\pi}_{\TV}
\le \pi_{\min}^{-1}e^{-t/K}.
\end{equation}
If, for some $\kappa>0$, every cut satisfies
\[
Q(A,A^c):=\sum_{x\in A,\,y\notin A}Q(x,y)
\ge\kappa\min\{\pi(A),\pi(A^c)\},
\]
then the variance inequality holds with $K=2/\kappa^2$.
\end{lemma}
\begin{proof}
For nonnegative $g$ with $\pi(g>0)\le1/2$, integrate the cut inequality
over $A_u=\{x:g(x)^2>u\}$ to obtain
\[
\kappa\norm{g}_{L^2(\pi)}^2
\le\sum_{\{x,y\}}Q(x,y)|g(x)^2-g(y)^2|
\le\bigl(2\mathcal E_P(g)\norm{g}_{L^2(\pi)}^2\bigr)^{1/2}.
\]
The last step is Cauchy--Schwarz and
\[
\sum_{\{x,y\}}Q(x,y)(g(x)+g(y))^2
\le2\sum_x\pi(x)(1-P(x,x))g(x)^2
\le2\norm{g}_{L^2(\pi)}^2.
\]
Consequently $\norm{g}_{L^2(\pi)}^2\le2\kappa^{-2}\mathcal E_P(g)$,
also when $g=0$. Choose a $\pi$-median $a$ of $H$ and apply this to
$(H-a)_+$ and $(a-H)_+$. Their squared norms sum to
$\norm{H-a}_{L^2(\pi)}^2$, and their energies sum to at most
$\mathcal E_P(H)$, by the corresponding inequality on each edge.
Since the variance is the minimum squared deviation from a constant,
this proves the cut assertion.
For mixing, reversibility makes $P$ self-adjoint on $L^2(\pi)$ and gives
$\mathcal E_P(H)=\langle H,(I-P)H\rangle_\pi$.
The stochastic kernel $2P-I$ is an $L^2(\pi)$ contraction by Jensen's
inequality and stationarity. Hence the eigenvalues of $P$ are in $[0,1]$.
The variance inequality bounds those on the mean-zero subspace by
$1-1/K\le e^{-1/K}$. For
$g_x(y)=\one_{\{y=x\}}/\pi(x)-1$, reversibility gives
\[
(P^tg_x)(y)=\frac{P^t(x,y)}{\pi(y)}-1,
\qquad \norm{g_x}_{L^2(\pi)}^2=\pi(x)^{-1}-1.
\]
The $L^2$ contraction followed by Cauchy--Schwarz bounds the total
variation distance by
\[
\tfrac12\sqrt{\pi(x)^{-1}-1}\,e^{-t/K},
\]
which implies \eqref{eq:elementary-mixing}.
On a singleton all asserted variances and
distances vanish; it may simply be regarded as already mixed.
\end{proof}
Use the axis-neighbor Metropolis chain on $\mathcal V$. Each of the
$2e$ signed coordinate directions is proposed with probability
\[
q_B=2^{-q_{\rm bin}},\qquad
q_{\rm bin}=\lceil\log_2(8d)\rceil;
\]
the unused probability, or a proposal leaving the cube, holds. A
proposal $v'$ within the cube is accepted with probability
$\min(1,W(v')/W(v))$. This chain is reversible for
$\pi_B(v)=W(v)/Z_B$ and holds with probability at least $3/4$.
\Needspace{8\baselineskip}
\begin{proposition}[Bin conductance and mixing]\label{prop:bin-gap}
For every nontrivial cut of the bin states, its stationary edge
conductance divided by the smaller stationary side mass is at least
\[
\kappa_B=\frac1{10^5d^2K_0}.
\]
Starting at any bin, after
$H=d^{50}(h+1)^2$ steps the total-variation distance from $\pi_B$ is at
most $2^{-4(h+d)}$.
\end{proposition}
\begin{proof}
Write $\mu(E)=\int_E\rho$ and $D=(0,K_0)^e$. For a cut
$\mathcal V=V_1\sqcup V_2$, choose $S$ to be the union of the open bins
on the side of smaller \emph{continuous} mass. Then
$0<\mu(S)\le\mu(D)/2$. Set
\[
t=\frac1{4dK_0},\qquad r=tK_0=\frac1{4d},\qquad
M=(1-t)S+tD.
\]
We have $S\subset M$, by writing $x=(1-t)x+tx$ for $x\in S$.
Lemma~\ref{lem:integral-interpolation} gives
\begin{equation}\label{eq:dense-mass-gain}
\mu(M\setminus S)\ge(2^t-1)\mu(S)
\ge t\log(2)\mu(S).
\end{equation}
This is actual gained mass even though $S$ need not be convex.
We next cover this gain by neighborhoods of cut faces. Ignore the
finite union of grid hyperplanes, a null set. If $z\in M\setminus S$,
write $z=(1-t)x+ty$ with $x\in S$, $y\in D$. The segment from $x$ to
$z$ stays inside the open convex cube and has sup-norm length less than
$r$. Its initial bin lies on the selected side and its terminal bin
lies on the other side. Follow the segment through its finitely many
grid crossings. At a crossing in several coordinates simultaneously,
the incident bins are indexed by the two choices in each crossing
coordinate, and are connected by axis-neighbor faces through that same
point. If the incoming and outgoing bins have different labels, a face
path between them contains an opposite-label pair. Its common closed
face contains the crossing point. Since some crossing changes the
label, $z$ is at sup distance less than $r$ from a cut face. No exterior
face is needed: the entire segment lies in $D$.
For such a closed unit face $F$, take its sup-distance-$r$ neighborhood
intersected with $D$, denoted $F^{(r)}$. Its volume is at most
\[
2r(1+2r)^{e-1}
\le\frac1{2d}\exp\left(\frac{e-1}{2d}\right)\le1.
\]
If $v$ is the lower corner of either bin adjacent to $F$, every point
$z\in F^{(r)}$ satisfies $\norm{z-v}_\infty\le1+r$. Hence
\[
\rho(z)\le2^{(Ad/B)(1+r)}\rho(v)\le4W(v),
\]
and the same inequality holds for the other adjacent corner $v'$.
Thus $\mu(F^{(r)})\le4\min(W(v),W(v'))$. Combining the face cover with
Equation~\eqref{eq:dense-mass-gain}, and writing
$D_i=\sum_{v\in V_i}W(v)$, gives
\begin{align*}
\sum_{\substack{vv'\text{ axis-neighbors}\\v\in V_1,\ v'\in V_2}}
\min(W(v),W(v'))
&\ge\frac{t\log(2)}4\mu(S)\\
&\ge\frac{t\log(2)}{16}\min(D_1,D_2).
\end{align*}
The second inequality follows from
Equation~\eqref{eq:bin-density-comparison}: the selected continuous side
has mass at least one quarter of its own discrete weight, which is at
least $\min(D_1,D_2)$. It does not require the two notions of smaller
side to agree. Stationary edge conductance is
$q_B\min(W(v),W(v'))/Z_B$. Since $q_B\ge1/(16d)$, the cut ratio is at
least $\log(2)/(1024d^2K_0)\ge\kappa_B$.
The weights satisfy $2^{-4Ad}\le W(v)\le1$, so
\[
\pi_{B,\min}\ge\frac{2^{-4Ad}}{K_0^e},\qquad
\log\pi_{B,\min}^{-1}\le4d^5\log2+d\log(4d^8)\le4d^5.
\]
Lemma~\ref{lem:mixing} supplies inverse gap at most
\[
K_B=2\kappa_B^{-2}=3.2\cdot10^{11}d^{20}\le d^{32}
\quad(d\ge14).
\]
It bounds the error at time $H$ by
$\exp(4d^5-H/K_B)$. Since $d^{18}\ge4d^5$ and
$d^5h(h+2)\ge(d+1)h\ge h+d$, we have
\[
\frac H{K_B}-4d^5\ge d^{18}(h+1)^2-4d^5
\ge4d^5h(h+2)\ge4(h+d)\log2.
\]
This proves the asserted error.
\end{proof}
\subsection{A bounded random-bit implementation}
We finish the proof of Theorem~\ref{thm:dense-draw}, keeping explicit
bounds that will also describe the finite output law in
Section~\ref{sec:algorithms}. Use the integer schedule
\begin{equation}\label{eq:dense-schedule}
J=d^4(h+1),\qquad H=d^{50}(h+1)^2.
\end{equation}
Run at most $J$ independent trials, each running $H$ bin-chain steps from $0$.
At the end of each bin walk use Equation~\eqref{eq:dense-offset-output},
but obtain each offset from the bounded draw
\begin{equation}\label{eq:dense-offset-bits}
\begin{gathered}
k_{ij}=\lceil\log_2(w_{ij}+1)\rceil+4(h+d),\quad
Z_{ij}\text{ uniform on }\{0,\ldots,2^{k_{ij}}-1\},\\
\beta_{ij}=\left\lfloor\frac{w_{ij}Z_{ij}}{2^{k_{ij}}}\right\rfloor.
\end{gathered}
\end{equation}
Return the first feasible table. If all $J$ trials fail, return a fixed
greedy feasible table with the required margins.
Each offset probability differs from $1/w_{ij}$ by at most $2^{-k_{ij}}$:
its number of preimages is either the floor or the ceiling of
$2^{k_{ij}}/w_{ij}$. Thus its total-variation error is at most
$w_{ij}/2^{k_{ij}}\le2^{-4(h+d)}$. Coupling the independent offsets
coordinate by coordinate bounds their joint error by
$d2^{-4(h+d)}$. Proposition~\ref{prop:bin-gap} bounds the bin error by
$2^{-4(h+d)}$, so a complete implemented trial, including its success
flag, differs from an ideal trial by at most
$(1+d)2^{-4(h+d)}$.
Couple the $J$ independent trial records until the first discrepancy.
This bounds the difference between the implemented first-success
procedure and its ideal counterpart by
$J(1+d)2^{-4(h+d)}$, without conditioning on an approximate success event.
By Proposition~\ref{prop:bin-acceptance}, the ideal procedure has uniform
law on success and failure probability at most $(63/64)^J$. Its greedy
fallback therefore changes the uniform law by at most this probability.
The total error is at most
\begin{equation}\label{eq:dense-total-error}
(63/64)^J+J(1+d)2^{-4(h+d)}\le2^{-h}.
\end{equation}
For explicit numerical bounds, $d^4\ge128$ gives
$(63/64)^J\le\exp(-J/64)\le2^{-2(h+1)}\le2^{-h-2}$.
Also $d\le2^{d/2}$, $d+1\le2^d$, and $h+1\le2^h$ give
$J(1+d)2^{-4(h+d)}\le2^{-3h-d}\le2^{-h-2}$.
All actual outputs are feasible by the acceptance test or the fallback.
It remains to account for every computation in the bit model.
At an integer bin corner $v$, the entries $X_{ij}(v)$ are integer sums
of products $w_{ij}v_{ij}$ and margins. Since $w_{ij}s$ implies either $i'=i,j'>j$, in which case $v=s$, or
$i'>i$, in which case every small receiver $v$ follows $s$.
Only $s,t,v$ can change, proving prefix preservation and the claimed
special value.
\end{proof}
For later use, fix a balanced prefix $\sigma$ before $s$, and let
$z_-,z_+$ be the total transversal weights extending it with special
values $x_s=l-1,l$, respectively. Let $c_{st,l}^{\sigma}$ be the total
weight of defects extending that prefix with negative $s$ satisfying
$x_s=l-1,q_s=l$ and positive $t>s$. Lemma~\ref{lem:repair} maps this
entire class injectively, with completions, into one fixed child. Hence
\begin{equation}\label{eq:conditional-repair}
c_{st,l}^{\sigma}\le
\begin{cases}z_+,&i'=i,\\z_-,&i'\ne i,\end{cases}
\qquad\text{and in particular}\qquad
c_{st,l}^{\sigma}\le\max\{z_-,z_+\}.
\end{equation}
Figure~\ref{fig:repair} illustrates the large-receiver case.
\input{figures/repair}
There are fewer than $4d^2$ ordered unit exchanges. A defect has one
designated repair; a transversal has at most $d^2$ inverse repairs,
one for each ordered defect type. Thus the degree is at most
$5d^2+1$. Neighbors can be listed with polynomial bit work using
\eqref{eq:repair-map} and its inverse, testing the boxes, patterns and
residuals, and removing duplicates. No completion count is needed.
On a repair edge the weight in \eqref{eq:graph-energy} equals the
source defect's weight.
\subsection{Stationary mass and unpadding}
The repair bounds defect mass by transversal mass. To recover an original
table from a padded completion, we also need to control the probability
that a large entry is smaller than the padding. The following estimate
applies to unrestricted tables with any prescribed margins.
\begin{lemma}[Small entries]\label{lem:small-entry}
Consider the uniform law on all nonnegative integer tables with prescribed
margins, with at most $m$ rows and $n$ columns and no entry restrictions.
If both margins incident to a cell are at least $a\ge4d$, then, for every
integer $t$ with $00$ for every box-valid $X$ of the indicated total. On the
transversal and defect patterns,
\begin{equation}\label{eq:soft-limit}
\lim_{\eta\downarrow0}f_\eta(X)=f(X).
\end{equation}
Indeed, a term has $D=0$ exactly when the full row and column margins are
$\bar r,\bar c$ and the small row and column totals do not exceed $r,c$.
When the large slots are balanced, these conditions specify precisely the
nonnegative residuals and padded completions defining $f$. On a line
without a large slot, the full-margin equality also makes the residual
zero. The capacity $C$ excludes no such completion, by its choice in
\eqref{eq:parameters}. Each zero-penalty term tends to one, all other
terms tend to zero, and the sum is finite.
We use the following convention throughout. Some coordinates have fixed
box-valid values $\sigma$, of total $c=|\sigma|$; a disjoint collection
$\mathcal R$ of whole slots is summed over its balanced profiles; and all
remaining coordinates are active. For an assignment $v$ to the active
coordinates, let
\[
\Phi_{\sigma,\mathcal R}(v)
=\sum_{b\in\prod_{s\in\mathcal R}
\{(a,B_s-a):0\le a\le B_s\}}
F_\eta(\sigma,v,b).
\]
Thus the summation domain is fixed, even when $v$ changes.
A box-valid active display $p$ for two removals satisfies
\begin{equation}\label{eq:two-removal-total}
c+|p|+\sum_{s\in\mathcal R}B_s=T+2.
\end{equation}
Its two-removal matrix has entries
$M_{ih}=\Phi_{\sigma,\mathcal R}(p-e_i-e_h)$.
In particular, two removals at the same coordinate give a diagonal entry;
an invalid removal gives zero. The display has total $T+2$, whereas
every nonzero entry is evaluated at total $T$.
\begin{lemma}[Laminar factors]\label{lem:laminar-signature}
With no balanced slots summed, every two-removal matrix just defined has
at most one positive eigenvalue.
\end{lemma}
\begin{proof}
Before imposing the box and total, the formula $\eta^{D(\xi)}$ is a
product of positive log-concave sequences in sums over a laminar family
of coordinate sets. Here laminar means that any two sets are disjoint
or one contains the other. The sets are the $x$ coordinates of each row
and their small-slot subsets, and the $y$ coordinates of each column and
their small-slot subsets. The row and column families are disjoint
because they use different coordinates. For example, the column
factors have the form
\[
\eta^{|K-z-\bar c_j|},\qquad
\eta^{(K'-z-c_j)_+},
\]
where $z$ is the relevant sum of $y$ coordinates and $K,K'$ are the
corresponding sums of capacities. All exponents are convex in $z$;
since $\log\eta<0$, the factors are log-concave on all integers.
An active coordinate with $p_i=0$ gives a zero row and column of $M$;
discard these indices temporarily. Restrict the laminar sets to the
remaining indices and absorb fixed coordinates into shifts of their
scalar factors. Combine factors whose restricted sets coincide, and
absorb empty sets into a positive constant. We obtain distinct
nonempty laminar sets $G$, positive log-concave sequences $\psi_G$, and
arguments $t_G$ at the display. Evaluate their formula even for invalid
removals for the moment. Let $W>0$ be its value at the display and put
\[
\alpha_i=\prod_{G\ni i}\frac{\psi_G(t_G-1)}{\psi_G(t_G)},
\qquad
\gamma_G=\frac{\psi_G(t_G)\psi_G(t_G-2)}{\psi_G(t_G-1)^2}\in(0,1].
\]
The extended two-removal matrix is
$W\diag(\alpha)K\diag(\alpha)$, where
\[
K_{ih}=\prod_{G\supseteq\{i,h\}}\gamma_G.
\]
For each set define
\[
a_G=(1-\gamma_G)\prod_{G'\supsetneq G}\gamma_{G'}\ge0.
\]
The sets containing any given pair of indices form a chain. Telescoping
the product along this chain gives the exact identity
\begin{equation}\label{eq:laminar-blocks}
K=\one\one^{\mathsf T}
-\sum_G a_G\one_G\one_G^{\mathsf T}.
\end{equation}
Consequently $K$ is nonpositive on $\{v:\one^{\mathsf T}v=0\}$ and
has at most one positive eigenvalue. The only still-invalid removals
are diagonal ones at coordinates with $p_i=1$. Replacing each such
entry by zero subtracts a nonnegative diagonal matrix from $K$, so preserves
that conclusion. Positive diagonal congruence and restoration of the
zero rows and columns complete the proof.
\end{proof}
We next sum over a fresh slot of capacity $B$. Two occupancies are
needed. At occupancy $B$, summing the profiles $(j,B-j)$ eliminates a
balanced slot and preserves the signature. At occupancy $B+1$, the
same calculation gives a weighted quadratic estimate; this is the
estimate used to bound the transport construction in the next section.
Both conclusions follow from a discrete second-difference inequality.
\begin{lemma}[Pair summation]\label{lem:pair-summation}
Fix a box-valid display $p$ on the old active coordinates, a fresh slot
of capacity $B\ge2$, and fixed context and balanced sums as above.
Choose its displayed occupancy $D'\in\{B,B+1\}$ so that
\begin{equation}\label{eq:pair-total}
c+|p|+D'+\sum_{s\in\mathcal R}B_s=T+2.
\end{equation}
Write $\Phi(r,a,b)$ for the weight after the balanced sums, with old
values $r$ and fresh pair $(a,b)$. The box-valid displays
$(p,j,D'-j)$ are indexed by
\[
\mathcal J=
\begin{cases}
\{0,\ldots,D'\},&D'=B,\\
\{1,\ldots,D'-1\},&D'=B+1.
\end{cases}
\]
Their two-removal matrices have the blocks
\begin{align*}
(V_j)_{ih}&=\Phi(p-e_i-e_h,j,D'-j),\\
S(l)_i&=\Phi(p-e_i,l,D'-1-l),\\
u_j&=\Phi(p,j-1,D'-1-j).
\end{align*}
Thus $V_j$ records two old removals, $S(l)$ one old and one fresh
removal, and $u_j$ one removal from each fresh coordinate of display
$j$. Put $S(l)=0$ outside
$0\le l\le D'-1$ and $u_j=0$ outside $1\le j\le D'-1$.
Suppose each matrix
\begin{equation}\label{eq:pair-block}
M_j=\begin{pmatrix}
V_j&S(j-1)&S(j)\\
S(j-1)^{\mathsf T}&u_{j-1}&u_j\\
S(j)^{\mathsf T}&u_j&u_{j+1}
\end{pmatrix},\qquad j\in\mathcal J,
\end{equation}
has at most one positive eigenvalue. The entries $u_{j-1}$ and
$u_{j+1}$ are the double removals at the first and second fresh
coordinates, respectively.
For every real old vector $h$ satisfying
$\sum_{l=0}^{D'-1}h^{\mathsf T}S(l)=0$, define
\begin{equation}\label{eq:pair-cumulative}
g_j=\frac{\sum_{l=0}^{j-1}h^{\mathsf T}S(l)}{u_j}
\quad(1\le j\le D'-1),\qquad
g_j=0\quad\text{otherwise}.
\end{equation}
All these divisions are valid, and
\begin{equation}\label{eq:pair-one}
-h^{\mathsf T}V_jh\ \ge\
2u_jg_j^2-u_{j-1}g_{j-1}^2-u_{j+1}g_{j+1}^2,
\qquad j\in\mathcal J.
\end{equation}
If $D'=B$, the matrix $\sum_{j=0}^B V_j$ has at most one positive
eigenvalue.
If $D'=B+1$, then
\begin{equation}\label{eq:pair-weighted}
2\sum_{j=1}^{D'-1}u_jg_j^2
\ \le\
-h^{\mathsf T}\left(\sum_{j=1}^{D'-1}j(D'-j)V_j\right)h.
\end{equation}
\end{lemma}
\begin{proof}
First, $u_j>0$ for every $1\le j\le D'-1$. Its pair values
$(j-1,D'-1-j)$ are within $[0,B]^2$ in both cases. They have total
$D'-2$, so \eqref{eq:pair-total} puts the full configuration on the
total-$T$ slice. Choose any balanced box-valid profile, for example
$(0,B_s)$, at each summed slot. The unchanged old profile and fixed
context then give a positive term of $F_\eta$. This proves positivity
even when the context violates the original margins or some old
displayed coordinates are zero.
The cumulative definition and the balance condition imply, including
$l=0,D'-1$,
\begin{equation}\label{eq:pair-difference}
h^{\mathsf T}S(l)=u_{l+1}g_{l+1}-u_lg_l.
\end{equation}
We use an elementary consequence of the signature assumption. If a
symmetric matrix $M$ has at most one positive eigenvalue and
$e^{\mathsf T}Me>0$, then
\begin{equation}\label{eq:positive-projection}
v^{\mathsf T}Mv\le
\frac{(v^{\mathsf T}Me)^2}{e^{\mathsf T}Me}.
\end{equation}
Indeed, subtract from $v$ its $M$-orthogonal projection onto $e$.
The remaining vector must have nonpositive square, since otherwise it
and $e$ span a positive definite two-dimensional subspace.
For $j\in\mathcal J$, put $v=(h,g_j,-g_j)$, and let $e_a,e_b$ denote
the two fresh coordinate directions. Equations
\eqref{eq:pair-block} and \eqref{eq:pair-difference} give
\[
v^{\mathsf T}M_je_a=u_{j-1}(g_j-g_{j-1}),\qquad
v^{\mathsf T}M_je_b=u_{j+1}(g_{j+1}-g_j).
\]
If $u_{j-1}>0$, apply \eqref{eq:positive-projection} to $e_a$; if
$u_{j+1}>0$, apply it to $e_b$. Either bound is at most
\[
u_{j-1}(g_j-g_{j-1})^2+u_{j+1}(g_j-g_{j+1})^2.
\]
If both diagonals vanish, then $u_j>0$ and $e_a+e_b$ has square $2u_j$
and is $M_j$-orthogonal to $v$. The same upper bound, now zero, follows.
These cases cover all admissible $j$: at $j=0$ or $D'$ the inward
diagonal is positive, and at every other index $u_j>0$.
An exact expansion now yields
\begin{align*}
&v^{\mathsf T}M_jv
-u_{j-1}(g_j-g_{j-1})^2-u_{j+1}(g_j-g_{j+1})^2\\
&\hspace{2em}=h^{\mathsf T}V_jh
+2u_jg_j^2-u_{j-1}g_{j-1}^2-u_{j+1}g_{j+1}^2,
\end{align*}
proving \eqref{eq:pair-one}.
For clarity, the smallest capacity is covered without a positive
diagonal at every display. When $B=D'=2$, the displays $j=0,2$ use
the diagonal $u_1>0$, and $j=1$ uses the positive sum direction with
square $2u_1$. When $B=2,D'=3$, the only displays are $j=1,2$;
they have, respectively, positive diagonal $u_2$ and $u_1$.
The out-of-box displays $j=0,3$ are never evaluated.
Write $a_j=u_jg_j^2$, zero outside $1\le j\le D'-1$.
For $D'=B$, summing \eqref{eq:pair-one} over $0\le j\le D'$ gives
\[
-h^{\mathsf T}\Bigl(\sum_{j=0}^{D'}V_j\Bigr)h
\ge\sum_{j=0}^{D'}(2a_j-a_{j-1}-a_{j+1})=0.
\]
Thus the sum is nonpositive on the kernel of
$h\mapsto h^{\mathsf T}\sum_l S(l)$, a subspace of codimension at most
one. A positive eigenspace of dimension two would intersect that
kernel nontrivially, so the sum has at most one positive eigenvalue.
For $D'=B+1$, let $w_j=j(D'-j)$, with $w_0=w_{D'}=0$.
Multiplying \eqref{eq:pair-one} by $w_j$ and summing only over the
admissible indices gives
\[
\sum_{j=1}^{D'-1}w_j(2a_j-a_{j-1}-a_{j+1})
=\sum_{j=1}^{D'-1}(2w_j-w_{j-1}-w_{j+1})a_j
=2\sum_{j=1}^{D'-1}a_j.
\]
This proves \eqref{eq:pair-weighted}, using only scalar zero endpoint
weights, never endpoint matrices outside the box.
\end{proof}
\begin{proposition}[Signature after balanced summation]
\label{prop:signature}
Fix $0<\eta<1$. For arbitrary box-valid fixed context $\sigma$,
arbitrary balanced-slot summation set $\mathcal R$, and arbitrary
box-valid active display $p$ satisfying \eqref{eq:two-removal-total},
the matrix
\[
\bigl(\Phi_{\sigma,\mathcal R}(p-e_i-e_h)\bigr)_{i,h}
\]
has at most one positive eigenvalue.
\end{proposition}
\begin{proof}
Induct on $|\mathcal R|$. Lemma~\ref{lem:laminar-signature} proves
the empty case. For a nonempty set choose $t\in\mathcal R$, regard
its two coordinates as active at $(j,B_t-j)$, and sum only over
$\mathcal R\setminus\{t\}$. Every resulting matrix $M_j$ has at most
one positive eigenvalue by induction; its total is $T+2$ by
\eqref{eq:two-removal-total}. Apply Lemma~\ref{lem:pair-summation}
with $D'=B_t$. The matrix $\sum_{j=0}^{B_t}V_j$ is exactly the required
matrix after also summing slot $t$, and has the asserted signature.
All capacities here are at least two. Zero active coordinates give
zero rows and columns throughout and need no additional assumption.
\end{proof}
This is a specific closure under balanced-pair summation, proved by
\eqref{eq:pair-one}; arbitrary sums of matrices with this signature
need not preserve it. In the transport argument, a weighted matrix
$V_t=\sum_j j(D'-j)V_j$ will be tested against real vectors $h$ whose
entries may have either sign. Equation~\eqref{eq:pair-weighted}
controls these quadratic evaluations under the stated balance condition.
We make no signature assertion for $V_t$ itself. In particular,
Proposition~\ref{prop:signature} is applied before this weighted sum,
on the entire softened total-$T$ box, even when the resulting
two-removal configurations lie outside the graph patterns.
==== END Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//signatures.tex ====
==== BEGIN Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins//transport.tex ====
\section{Transport and the graph variance bound}\label{sec:transport}
We now turn the quadratic property into a variance bound for the graph of
Section~\ref{sec:graph}. A signed flow compares adjacent conditional means;
decomposing variance over successive conditions gives a bound on the
transversals, and the repair map extends it to the full graph. All large
slots are summed with their balances throughout. The remaining slots are
exposed in row-major order. Fix a real-valued function $H$ on the feasible
small-state graph.
The flow-energy comparison is the standard quadratic electrical-network
method; see Aldous and Fill~\cite[Section~3.7.1]{AF2002}. The recursive
signed demands and their bound for integer slots are constructed here.
A \emph{context} $\sigma$ fixes balanced profiles on a prefix of small slots.
Write $\mathcal T_\sigma$ for the transversals with this context and
$z_\sigma=\sum_{X\in\mathcal T_\sigma}f(X)$. If $s$ is the next slot,
its child $j$ fixes $(x_s,y_s)=(j,U-j)$, and has mass $z_j$ and weighted
mean $H_j$. Means are used only for positive masses.
Let $E_\sigma(H)$ be the sum of
$\min(f(X),f(Y))(H(X)-H(Y))^2$ over unordered \emph{unit-exchange} edges
whose endpoints respect $\sigma$. In particular $E_\sigma(H)\le E(H)$;
repair edges need not be included in $E_\sigma$. A superscript $\eta$ on
masses or means, and $E_{\eta,\sigma}$ on this energy, will indicate the
softened weights from Definition~\ref{def:soft-weight}. For the softened
energy we include all box-admissible transversal and defect patterns with
the context, including states whose limiting weight is zero.
\subsection{Child weights and adjacent means}
\begin{lemma}[Child log-concavity]\label{lem:child-logconcavity}
At every context with positive transversal mass, the child masses
$(z_j)_{j=0}^U$ are log-concave and their positive support is an integer
interval. If $z_a,z_b>0$ and $a\le j\le b$, then
$z_j\ge\min(z_a,z_b)$.
\end{lemma}
\begin{proof}
For $0<\eta<1$ every child mass is positive. For $1\le j0$. Extend $H$ by arbitrary fixed finite
values to the box-admissible graph patterns whose limiting weights are
zero, and suppress $\eta$ on masses. We seek a signed flow with divergence
$f_\eta(X)/z_-$ at each transversal in the minus child,
$-f_\eta(X)/z_+$ at each transversal in the plus child, and zero elsewhere.
For such a flow $J$, summation by parts and Cauchy--Schwarz give
\[
(H_-^\eta-H_+^\eta)^2
\le \left(\sum_{XY}\frac{J(X,Y)^2}
{\min(f_\eta(X),f_\eta(Y))}\right)
E_{\eta,\sigma}(H),
\]
where each unit-exchange edge is oriented once. Thus it is enough to
bound the flow's resistance energy. We build its signed demands by
successively exposing the remaining small slots, and charge its energy
to a quadratic potential along that recursion.
Display the special slot $s$ as $(l,U+1-l)$, where $1\le l\le U$.
Removing its first or second coordinate gives the minus or plus child,
respectively. The flow uses these endpoint transversals and defects
with $s$ positive and one other unexposed small slot negative.
\emph{Balanced recursion.}
A recursion node $\nu$ displays the special pair and some subsequent
small pairs, the latter all with occupancy $U$. Let $p$ be this display,
and call its coordinates the old indices. With the context included,
and all undisplayed slots assigned their balanced occupancies, the total
is $T+1$, where $T=\sum_s B_s$. For an old index $i$, let $s_i$ be the
total softened weight obtained by removing one unit there and summing
all undisplayed slots with their balances. Invalid removals have weight
zero. Assign coefficients $h_i$ satisfying
\begin{equation}\label{eq:balanced-demands}
\sum_i s_i h_i=0,\qquad \Phi_\nu=\sum_i s_i h_i^2.
\end{equation}
The quantity $s_i h_i$ is the signed demand on that one-removal fiber;
the first equality requires total demand zero at the node. At the root
the two coefficients are $1/z_-$ and $-1/z_+$, giving the prescribed
endpoint demands and root potential $1/z_-+1/z_+$.
To process the next ordinary slot $v$, branch over its balanced profiles
$(j,U-j)$, $0\le j\le U$. In the notation of
Lemma~\ref{lem:pair-summation}, use the auxiliary occupancy $D'=U+1$.
Then $S(j)$ is the vector of old-hole weights in branch $j$, and $u_j$
is the no-old-hole weight with pair $(j-1,U-j)$. Thus $u_1,\ldots,u_U$
are positive and $u_0=u_{U+1}=0$. Since $\sum_j S_i(j)=s_i$, define
\begin{equation}\label{eq:transport-g}
g_j=\frac{\sum_{a=0}^{j-1}h^T S(a)}{u_j}\quad(1\le j\le U),
\qquad g_0=g_{U+1}=0.
\end{equation}
Balance gives $h^TS(j)=u_{j+1}g_{j+1}-u_jg_j$, including both endpoints.
In child $j$, retain all old coefficients and give the two new
coordinates coefficients $g_j,-g_{j+1}$. Their one-hole masses are
$u_j,u_{j+1}$, so the child is balanced. Summing child potentials
conserves the old terms and adds exactly
\begin{equation}\label{eq:potential-increment}
\sum_{j=0}^U\Phi_{\nu j}-\Phi_\nu
=2\sum_{j=1}^Uu_jg_j^2
\le -h^TV_{\nu,v}h.
\end{equation}
Here $V_{\nu,v}$ is the matrix of two-old-hole weights with $v$ displayed
at $(a,U+1-a)$, summed over $1\le a\le U$ with multiplier
$a(U+1-a)$ and over all other undisplayed slots with their balances.
The inequality is precisely Equation~\eqref{eq:pair-weighted}.
Each individual display before the two removals has total $T+2$.
\emph{A future quadratic form.}
For any slot $t$ still to be processed, define
$Q_t(\nu)=h^TV_{\nu,t}h$ by the same rule. If a different slot $v$ is
split now, we claim
\begin{equation}\label{eq:future-monotonicity}
\sum_{j=0}^U Q_t(\nu j)\ge Q_t(\nu).
\end{equation}
For an explicit common summation kernel, put
\[
K_t(r,w)=\sum_{a=1}^U a(U+1-a)
\sum_{b}F_\eta\bigl(\sigma,r,w,(a,U+1-a),b\bigr).
\]
Here $r$ assigns the old coordinates, $w$ assigns the current pair $v$,
and $b$ ranges over the Cartesian product of balanced profiles of every
remaining slot other than $t$, including all large slots.
As usual, an invalid coordinate assignment contributes zero. This is
a single fixed summation domain; all penalties are evaluated on the
full configurations. Every kernel entry used below has total $T$.
The old--old terms in the children partition the parent's balanced sum
over $v$. For a mixed term, removing old index $i$ and the first new
coordinate in branch $j$ gives
$K_t(p-e_i,(j-1,U-j))$ with coefficient $2h_i g_j$.
Removing $i$ and the second new coordinate in branch $j-1$ gives the
identical kernel entry with coefficient $-2h_i g_j$.
These terms cancel. All legal resulting pairs have occupancy $U-1$;
the unmatched formal endpoint removals are invalid and have weight zero.
For the new--new terms, each resulting pair $(k,U-2-k)$, $0\le k\le U-2$,
has exactly the following contributions:
\begin{center}
\begin{tabular}{lll}
\toprule
Removed coordinates & Branch & Coefficient\\
\midrule
First twice & $k+2$ & $g_{k+2}^2$\\
First and second & $k+1$ & $-2g_{k+1}g_{k+2}$\\
Second twice & $k$ & $g_{k+1}^2$\\
\bottomrule
\end{tabular}
\end{center}
They all multiply $K_t(p,(k,U-2-k))$. Hence the exact identity is
\begin{equation}\label{eq:future-square}
\sum_{j=0}^U Q_t(\nu j)-Q_t(\nu)
=\sum_{k=0}^{U-2}K_t(p,(k,U-2-k))
(g_{k+2}-g_{k+1})^2\ge0.
\end{equation}
All omitted boundary removals are invalid. Auxiliary entries with two
holes in an ordinary pair need not be graph states: they belong to the
full softened total-$T$ slice where the signature proposition applies.
No signature property of the weighted sum $V_{\nu,t}$ is being asserted;
Equation~\eqref{eq:potential-increment} and the explicit square identity
are the properties of that sum that are used.
\emph{The root bound.}
Iterating Equation~\eqref{eq:future-monotonicity} shows that the sum of
$Q_t$ at the level just before processing $t$ is at least its root value.
Thus Equation~\eqref{eq:potential-increment}, summed over levels, bounds
the total leaf potential by the root potential minus the sum of the
root $Q_t$'s. Let $c_t=c_{st,l}^{\eta,\sigma}$ be the total weight of
defects respecting $\sigma$ with special pair $(l-1,U-l)$ negative,
slot $t$ positive, and every other small slot balanced.
These auxiliary defects differ from the special-positive defects used by
the leaf flow: the off-diagonal entry removes both special coordinates
from $(l,U+1-l)$, leaving $(l-1,U-l)$.
At the root, the off-diagonal entry of $V_{\nu,t}$ is this sum with
multiplier $a(U+1-a)$ on the positive pair $t$, so it is at most
$(U+1)^2c_t$. Its diagonal entries are nonnegative. Substituting the
root coefficients and dropping their nonpositive contributions to
$-Q_t$ gives
\begin{equation}\label{eq:leaf-potential}
\sum_{\nu\text{ leaf}}\Phi_\nu
\le \frac1{z_-}+\frac1{z_+}
+\frac{2(U+1)^2}{z_-z_+}\sum_{t>s}c_t.
\end{equation}
The sum ranges only over the other unexposed small slots. With no such
slots the recursion consists of its root and this bound still holds.
\emph{Leaf flows and their divergences.}
At a leaf let $D$ denote the entire small-coordinate display, including
the fixed context. For its unfixed coordinate indices $i$, the valid
one-removal states $X_i=D-e_i$ have
weights $s_i=f_\eta(X_i)>0$, and form a clique of unit exchanges.
Choose a maximum-weight vertex as hub. On the edge from each nonhub
$X_i$ to the hub send signed flow $s_i h_i$; its conductance is exactly
$s_i$. The flow's divergence at $X_i$ is $s_i h_i$, and balance gives
the same prescribed divergence at the hub. Its resistance energy is
at most $\sum_i s_i h_i^2=\Phi_\nu$.
Different leaf cliques have disjoint edge sets: the coordinatewise
maximum of the endpoints recovers $D$, which uniquely determines the
leaf. Their flows can therefore be added without an energy multiplier.
An endpoint transversal has a unique leaf representation. Its ordinary
balanced profiles determine all branches, and its special hole is in
the first coordinate for the minus child and the second for the plus
child. Its coefficient remains $1/z_-$ or $-1/z_+$ throughout.
Every other used state has special slot positive and a unique ordinary
negative pair, say $(a,U-1-a)$ in slot $v$. It has exactly two leaf
representations: fill the first coordinate, giving branch $a+1$ and
coefficient $g_{a+1}$, or fill the second, giving branch $a$ and
coefficient $-g_{a+1}$. All earlier profiles are determined by the state,
so both coefficients come from the same recursion parent. Later splits
retain them. Both representations carry the identical weight
$f_\eta(X)$, and their divergences cancel. This also holds for
$a=0,U-1$.
Consequently the summed flow $J$ has divergence $f_\eta/z_-$ on the
minus child, $-f_\eta/z_+$ on the plus child, and zero elsewhere.
The resistance-energy comparison from the start of the proof and
Equation~\eqref{eq:leaf-potential} now eliminate the flow and all
recursive coefficients:
\begin{equation}\label{eq:soft-transport}
(H_-^\eta-H_+^\eta)^2
\le\left(\frac1{z_-^\eta}+\frac1{z_+^\eta}
+\frac{2(U+1)^2\sum_{t>s}c_{st,l}^{\eta,\sigma}}
{z_-^\eta z_+^\eta}\right)E_{\eta,\sigma}(H).
\end{equation}
\emph{The limit and conditional repair.}
The extension of $H$ was fixed independently of $\eta$. For this fixed
input all sums are finite. Since the two limiting
child masses are positive, every quantity in
Equation~\eqref{eq:soft-transport} converges as $\eta\downarrow0$.
We take this limit only after obtaining that inequality; convergence
of the demands, the $g_j$'s, or the flows is unnecessary.
For the limiting $c_{st,l}^\sigma$, Lemma~\ref{lem:repair} injects
state/completion pairs into one of the two child fibers. Specifically,
since $t$ follows $s$ in row-major order, the receiver is either $s$
itself or lies in a later row, and all earlier assignments are preserved.
The repaired special value is $l$ in the first case and $l-1$ in the
second, with the choice fixed by $s,t$. Thus
\[
c_{st,l}^\sigma\le\max(z_-,z_+).
\]
There are fewer than $d$ possible slots $t$. Multiplication of the
limiting inequality by $\min(z_-,z_+)$ now yields
Equation~\eqref{eq:conditional-transport}.
\end{proof}
\subsection{From conditional transport to variance}
\begin{theorem}[Graph Poincar\'e inequality]\label{thm:poincare}
For every real function $H$ on the feasible small graph,
\begin{equation}\label{eq:graph-poincare}
\Lambda\Var_{f/\Lambda}H
\le \left((1+2d^2)4d^2(U+1)^6+2\right)E(H)
\le 770d^4U^6 E(H).
\end{equation}
In particular, the feasible graph is connected.
\end{theorem}
\begin{proof}
First restrict to transversals. At a positive-mass context $\sigma$,
put $p_j=z_j/z_\sigma$. The between-child contribution to its
unnormalized variance is
\begin{equation}\label{eq:child-variance}
z_\sigma\Var_p(H_j)
=\frac1{z_\sigma}\sum_{a