Proof. The defect relation is \(q=x-e_t+e_s\), and \(x_t\ge1\). If \(v\) is small, the changes to \(x\) lie in row \(i'\), with zero total; the changes to \(q\) are \(q'-q=e_v-e_s\), in column \(j\), also with zero total. Hence all residual margins are unchanged. The new common entries are nonnegative. Their row totals are the old \(x\) row totals and their column totals are the old \(q\) column totals. At each small slot, one of these totals is bounded by an original margin strictly below \(U\), proving the capacity constraint. If \(j'=j\), then \(v=t\) and the two changes to \(x\) cancel; the reset of \(q\) is confined to that column. If \(i'=i\), then \(v=s\): the transfer increments the negative slot, decrements the positive slot, and leaves \(q\) unchanged. These include both possible coincidences.

If \(v\) is large, it differs from \(s,t\), and \(x'=x-e_t\), \(q'=q-e_s\). These vectors remain nonnegative and within capacity, since \(x_t\ge1\) and \(q_s=x_s+1\ge1\). Only the residuals of row \(i'\) and column \(j\) increase, each by one. Both lines meet the large block. Adding one to completion entry \(v\) therefore gives a valid target completion. Its entries remain below \(C\) by the total bound already proved.

For fixed \(s,t\), the repaired vector recovers \(x=x'+e_t-\mathbf{1}_{\{v\in\mathcal S\}}e_v\), followed by \(q=x-e_t+e_s\) and \(y=U\mathbf{1}-q\). In the large-receiver case subtract \(e_v\) from the target completion; otherwise retain it. These inverses on the image prove both injections.

Finally, \(t>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. ◻

Proof. Let the marked cell be \((i,j)\) and its entry be \(h<t\). The other entries in its row have sum at least \(a/2\), as do the other entries in its column. Unless this event is empty, choose deterministically \(j'\ne j\) and \(i'\ne i\) whose donor entries are both at least \(a/(2d)\). Such choices exist because each line has fewer than \(d\) entries. If there is only one row or column, the event is empty instead. For every \(v=1,\ldots,\lfloor a/(2d)\rfloor\), subtract \(v\) from the entries \((i,j')\) and \((i',j)\) and add \(v\) at \((i,j)\) and \((i',j')\). The resulting table is nonnegative with the same margins. Given this table and the labels \((i',j',h)\), its marked entry determines \(v\), and reversing the four changes recovers the source. There are at most \(td^2\) possible labels for each output. Since \(\lfloor a/(2d)\rfloor\ge a/(4d)\), double counting these moves gives the asserted bound. No upper entry bound is imposed in this argument. ◻

Proof. For each of at most \(|\mathcal S|(|\mathcal S|-1)\le d^2\) defect types, the joint injection in Lemma 2 bounds its total weight by \(Z_0\). This proves the upper bound on \(\Lambda\); the other mass inequalities follow from inclusion and the greedy starting table. There are \(\Lambda\) joint objects \((X,A)\), each specified by \(2|\mathcal S|+|\mathcal B|\le2mn<2d\) integer coordinates in \([0,C]\). Thus \(\Lambda\le(C+1)^{2d}\), and the positive integer weights \(f(X)\) give the minimum-mass bound.

Consider all unrestricted tables with the enlarged margins \(\bar r,\bar c\), and call their number \(F\). Every transversal and completion gives one such table, so \(Z_0\le F\). Each large cell has both enlarged margins at least \(U\). Lemma 3 and a union bound show that the proportion of these enlarged tables with some large entry below \(L\) is at most \[|\mathcal B|\frac{4Ld^3}{U}\le\frac{4Ld^4}{U} =\frac4{d^4}<\frac12.\] Here \(L\le U/2\) and \(U\ge4d\); an empty block has no bad cells. Every enlarged table passing this test can be unpadded to an original table. Conversely, padding every original table gives exactly one passing table and a feasible transversal with its completion. Consequently the successful pairs are in bijection with \(\Omega(r,c)\) and number at least \(F/2\ge Z_0/2\). Under the stated joint law every pair has probability \((f(X)/\Lambda)(1/f(X))=1/\Lambda\), proving conditional uniformity and (7). ◻

Proof. For \(0<\eta<1\) every child mass is positive. For \(1\le j<U\), display the next pair as \((j+1,U-j+1)\) and sum every other unexposed slot with its balance. The display is in its box and has two excess units. Its two-removal matrix is \[\begin{pmatrix}z_{j-1}^\eta&z_j^\eta\\ z_j^\eta&z_{j+1}^\eta\end{pmatrix}.\] Proposition 8 gives at most one positive eigenvalue. The trace is positive, so the determinant is nonpositive: \((z_j^\eta)^2\ge z_{j-1}^\eta z_{j+1}^\eta\). Consequently the successive differences of \(\log z_j^\eta\) are nonincreasing, and for \(a<j<b\), \[z_j^\eta\ge (z_a^\eta)^{(b-j)/(b-a)}(z_b^\eta)^{(j-a)/(b-a)}.\] Finite sums converge as \(\eta\downarrow0\). The local inequalities give log-concavity in the limit; the displayed interpolation gives positivity between positive endpoints and the asserted lower bound. ◻

Proof. We first work at a fixed \(\eta>0\). 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.

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 \[ \sum_i s_i h_i=0,\qquad \Phi_\nu=\sum_i s_i h_i^2. \tag{20}\] 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 7, 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 \[ 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. \tag{21}\] 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 \[ \sum_{j=0}^U\Phi_{\nu j}-\Phi_\nu =2\sum_{j=1}^Uu_jg_j^2 \le -h^TV_{\nu,v}h. \tag{22}\] 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 (16). Each individual display before the two removals has total \(T+2\).

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 \[ \sum_{j=0}^U Q_t(\nu j)\ge Q_t(\nu). \tag{23}\] 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:

They all multiply \(K_t(p,(k,U-2-k))\). Hence the exact identity is \[ \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. \tag{24}\] 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 (22) and the explicit square identity are the properties of that sum that are used.

The root bound. Iterating Equation (23) shows that the sum of \(Q_t\) at the level just before processing \(t\) is at least its root value. Thus Equation (22), 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 \[ \sum_{\nu\text{ leaf}}\Phi_\nu \le \frac1{z_-}+\frac1{z_+} +\frac{2(U+1)^2}{z_-z_+}\sum_{t>s}c_t. \tag{25}\] 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.

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 (25) now eliminate the flow and all recursive coefficients: \[ (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). \tag{26}\]

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 (26) 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 2 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 (19). ◻

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 \[ z_\sigma\mathop{\mathrm{Var}}_p(H_j) =\frac1{z_\sigma}\sum_{a<b}z_a z_b(H_a-H_b)^2. \tag{28}\] Zero-mass children may be omitted. For positive endpoints \(a<b\), Lemma 9 makes every intervening mass at least \(\min(z_a,z_b)\). Telescoping and Cauchy–Schwarz therefore give \[\begin{align*} \frac{z_a z_b}{z_\sigma}(H_a-H_b)^2 &\le \min(z_a,z_b)(b-a) \sum_{j=a}^{b-1}(H_j-H_{j+1})^2\\ &\le U\sum_{j=a}^{b-1}\min(z_j,z_{j+1})(H_j-H_{j+1})^2\\ &\le U^2 A_0 E_\sigma(H). \end{align*}\] There are at most \((U+1)^2\) pairs. Thus the contribution in Equation (28) is at most \((U+1)^4A_0 E_\sigma(H)\).

Iterating the identity \(\mathop{\mathrm{Var}}H=\mathbb{E}(\mathop{\mathrm{Var}}(H\mid j))+\mathop{\mathrm{Var}}(\mathbb{E}(H\mid j))\) down the exposure tree expresses the full unnormalized transversal variance as the sum of these contributions. At any fixed depth, the energies \(E_\sigma\) use disjoint edge sets, because distinct contexts assign different prefix coordinates. There are at most \(d\) internal levels, and \(A_0\le4d(U+1)^2\). Hence, writing \(\mathop{\mathrm{Var}}_{\mathcal T}\) for variance under the normalized transversal weights, \[ Z_0\mathop{\mathrm{Var}}_{\mathcal T}H\le4d^2(U+1)^6E(H). \tag{29}\] If there are no small slots, the transversal space is a singleton and this inequality holds directly.

Let \(\overline H\) be the transversal mean, and compare each defect \(X\) to its repair \(\mathcal R(X)\). By Lemma 2, \(f(X)\le f(\mathcal R(X))\), the repair map is injective within each of fewer than \(d^2\) defect types, and its edge has conductance \(f(X)\). Distinct defects give distinct repair edges. It follows that \[\begin{align*} \Lambda\mathop{\mathrm{Var}}_{f/\Lambda}H &\le\sum_{X\in\mathcal X}f(X)(H(X)-\overline H)^2\\ &\le Z_0\mathop{\mathrm{Var}}_{\mathcal T}H +2\sum_{X\notin\mathcal T}f(X) (H(X)-H(\mathcal R(X)))^2\\ &\hspace{1.5em}+2\sum_{X\notin\mathcal T}f(X) (H(\mathcal R(X))-\overline H)^2\\ &\le (1+2d^2)Z_0\mathop{\mathrm{Var}}_{\mathcal T}H+2E(H). \end{align*}\] Insert Equation (29) to obtain the first bound in Equation (27). Since \(U\ge1\), \(1+2d^2\le3d^2\) and \((U+1)^6\le64U^6\) give the second bound. Finally, the indicator of a nonempty proper connected component would have positive variance and zero energy, which is impossible. The one-state case is already connected. ◻

Proof. The unique bin-and-offset representation of a feasible integer table has a bin of weight one. The table’s probability before rejection is therefore \[ \frac1{Z_B}\prod_{i<a,\,j<c}\frac1{w_{ij}}, \tag{38}\] independent of the table. The dependent entries are integers because they are integer sums and differences. This proves conditional uniformity, including tables on faces and widths of different sizes.

For the success bound, let \(n_{\rm full}\) be the number of bins whose entire closure is contained in \(\mathcal P\). Each has weight one and accepts every offset, so its contribution to the success probability is \(1/Z_B\). We compare \(n_{\rm full}\) and \(Z_B\) with \(\mathop{\mathrm{vol}}(\mathcal P)\). Set \(\mathcal P^- =\{u:T_{ij}(u)\ge2d/B\text{ for every }i,j\}\). The affine map \(u\mapsto(1-\alpha)u+\alpha u_*\) with \(\alpha=4d^2/B\) sends \(\mathcal P\) into \(\mathcal P^-\) by Equation (33). Hence Bernoulli’s inequality gives \[ \mathop{\mathrm{vol}}(\mathcal P^-)\ge(1-4d^2/B)^e\mathop{\mathrm{vol}}(\mathcal P) \ge(1-4d^3/B)\mathop{\mathrm{vol}}(\mathcal P) \ge\tfrac12\mathop{\mathrm{vol}}(\mathcal P). \tag{39}\] Except on grid boundaries, every point of \(\mathcal P^-\) lies in a bin whose entire closure is in \(\mathcal P\): the change of any normalized entry across that bin is at most \(d/B\). These bins cover \(\mathcal P^-\) up to a null set and each has volume one, so \(n_{\rm full}\ge\mathop{\mathrm{vol}}(\mathcal P^-)\ge\mathop{\mathrm{vol}}(\mathcal P)/2\).

To bound \(Z_B\), for any \(\gamma\ge0\) consider the entire relaxed polytope \(\mathcal P_\gamma=\{u:T_{ij}(u)\ge-\gamma\text{ for all }i,j\}\) in \(\mathbb{R}^e\), without a cube restriction. For \(u\in\mathcal P_\gamma\) the point \[z=\frac{u+2d\gamma u_*}{1+2d\gamma}\] belongs to \(\mathcal P\), since the affine coefficients sum to one and each \(T_{ij}(z)\ge0\). Thus \(\mathcal P_\gamma\subset u_*+(1+2d\gamma)(\mathcal P-u_*)\), and \[ \mathop{\mathrm{vol}}(\mathcal P_\gamma) \le(1+2d\gamma)^e\mathop{\mathrm{vol}}(\mathcal P) \le\exp(2d^2\gamma)\mathop{\mathrm{vol}}(\mathcal P). \tag{40}\] This argument also covers points with negative free coordinates. The sublevel set \(\{p\le(j+1)/A\}\) inside the sampling cube is contained in \(\mathcal P_{d/B+(j+1)/A}\). Summing the upper bounds for the penalty layers and using Equation (36) gives \[\begin{align*} Z_B&\le4\int_{[0,K_0]^e}\rho(u)\,du\\ &\le4\sum_{j\ge0}2^{-j} \exp\bigl(2d^2(d/B+(j+1)/A)\bigr)\mathop{\mathrm{vol}}(\mathcal P) \le32\mathop{\mathrm{vol}}(\mathcal P). \end{align*}\] For the last numerical bound put \(a_0=2/d^2\) and \(b_0=2/d^5\). Since \(a_0+b_0\le1/4\), both \(\exp(a_0)\) and \(\exp(a_0+b_0)\) are at most \(4/3\). The geometric sum is at most \(4(4/3)/(1-(4/3)/2)=16\), which is stronger than asserted. Consequently \[\mathbb{P}\{\text{success}\}\ge\frac{n_{\rm full}}{Z_B} \ge\frac{\mathop{\mathrm{vol}}(\mathcal P)/2}{32\mathop{\mathrm{vol}}(\mathcal P)}=\frac1{64}.\] ◻

Proof. We first prove the one-dimensional integral assertion in the slightly larger class needed for slices. Suppose \(F,G,H\) are nonnegative, supported on bounded finite unions of intervals, and, after removal of finitely many endpoints, are continuous and either zero or bounded above and below by positive constants on each interval piece. Assume \(H((1-t)x+ty)\ge F(x)^{1-t}G(y)^t\) whenever \(F(x)G(y)>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)\), \(0<a<1\), be the quantiles of \(F/M_F\) and \(G/M_G\). Split \((0,1)\) at the cumulative probabilities of the finitely many support endpoints and continuity breakpoints of both densities. On each remaining open interval \(I\), the quantiles are continuously differentiable, strictly increasing, and satisfy \[u'(a)=\frac{M_F}{F(u(a))},\qquad v'(a)=\frac{M_G}{G(v(a))}.\] These statements follow directly by inverting the continuously differentiable cumulative function on a positive interval piece, whose derivative is positive. The function \(z(a)=(1-t)u(a)+tv(a)\) is also strictly increasing and continuously differentiable on \(I\). Its images \(z(I)\) for distinct pieces are disjoint. Change of variables on each piece, followed by the weighted arithmetic–geometric mean inequality, yields \[\begin{align*} \int H &\ge\sum_I\int_I H(z(a))z'(a)\,da\\ &\ge\sum_I\int_I F(u(a))^{1-t}G(v(a))^t \left(\frac{M_F}{F(u(a))}\right)^{1-t} \left(\frac{M_G}{G(v(a))}\right)^t da\\ &=M_F^{1-t}M_G^t. \end{align*}\] The pieces have total parameter length one. A gap in a source support causes a quantile jump at one of the excluded parameter values; the corresponding gaps between image intervals merely omit nonnegative contributions to \(\int H\). Thus neither disconnected supports nor density jumps require continuity across a gap.

The assertion for dimension \(q=1\) follows by restricting the ambient continuous weights to their sets. Induct on \(q\). For each first coordinate \(x\), let \(S_i(x)\) be the slice in the remaining \(q-1\) coordinates and put \[F_i(x)=\int_{S_i(x)}f_i(x,x')\,dx'.\] Whenever \(S_1(x)\) and \(S_2(y)\) are nonempty, their interpolation is contained in \(S_0((1-t)x+ty)\). The induction hypothesis for these slices therefore gives \[F_0((1-t)x+ty)\ge F_1(x)^{1-t}F_2(y)^t.\] To justify the one-dimensional step for the marginals, partition the first-coordinate axis by all endpoints of all the boxes. On each open piece, a slice domain is a fixed union of boxes or is empty. In the nonempty case it has fixed positive volume. Each ambient weight has a positive minimum and finite maximum on the compact box, so its marginal is bounded above and below by positive constants there. Uniform continuity of the weight on the compact box proves continuity of the marginal on that piece by integration over this fixed domain. These are exactly the hypotheses of the one-dimensional argument just proved. Applying that argument and then iterated integration proves Equation (41).

Finally, the interpolation of two finite unions of open axis-aligned boxes is the finite union of all pairwise interpolations of their boxes, each again such a box. Convexity of \(p\) gives the required pointwise inequality for \(f_0=f_1=f_2=\rho\), proving Equation (42). ◻

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\lVert g\rVert_{L^2(\pi)}^2 \le\sum_{\{x,y\}}Q(x,y)|g(x)^2-g(y)^2| \le\bigl(2\mathcal E_P(g)\lVert g\rVert_{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\lVert g\rVert_{L^2(\pi)}^2.\] Consequently \(\lVert g\rVert_{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 \(\lVert H-a\rVert_{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)=\mathbf{1}_{\{y=x\}}/\pi(x)-1\), reversibility gives \[(P^tg_x)(y)=\frac{P^t(x,y)}{\pi(y)}-1, \qquad \lVert g_x\rVert_{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 (43). On a singleton all asserted variances and distances vanish; it may simply be regarded as already mixed. ◻

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 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 14 gives \[ \mu(M\setminus S)\ge(2^t-1)\mu(S) \ge t\log(2)\mu(S). \tag{44}\] 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 \(\lVert z-v\rVert_\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 (44), 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 (36): 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 15 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. ◻

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 3, with \(a=L\) and threshold \(10d\le L/2\), gives \[\mathbb{P}(\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 11 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 11, and Proposition 4 gives \(\pi_{\min}\ge(C+1)^{-2d}\). Lemma 15 now gives (50). ◻

Proof. We first control adaptive approximation. The dense guarantee is uniform over feasible states: \(\mathop{\mathrm{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\mathop{\mathrm{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 17, 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 4, 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 \[ 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}. \tag{52}\] In particular, no error is divided by a success probability.

Each term in (52) 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)<b\). First, \[\frac{J_{\rm o}}{2(1+d^2)} \ge\frac{d^2(k+1)}4\ge49(k+1)\ge(k+2)\ln2.\] For the second term, \[\ln\bigl(J_{\rm o}(C+1)^{2d}\bigr)+(k+2)\ln2 \le2t^2+6t\le3t^2\le d^{40}t^2=T/d^{160}.\] Finally, since \(T+1\le2T\), \[\begin{align*} \log_2\bigl(J_{\rm o}(T+1)\bigr)+k+2 &\le204\log_2d+2\log_2t+\log_2(k+1)+k+3\\ &\le209t\le d^4t^2=h. \end{align*}\] Their sum is less than \(2^{-k}\).

For the running time, neighbor lists have polynomial size, and all state coordinates, residuals, and completion entries have \(O(b+\log d)\) bits. The proposal uses exactly \(q_{\rm s}\) unbiased bits. Each completion call has bounded polynomial bit cost by Theorem 12; the numbers of steps, trials, and calls in (51) are fixed polynomials. Comparisons, additions, integer multiplications and divisions, and loop counters all have polynomial bit cost, for example with schoolbook arithmetic. Only feasible completions and the feasible fallback can be returned. Empty and singleton-dimensional blocks use their deterministic completion rule. This proves the claimed worst-case bound. ◻

Proof. The finite spaces. Use the dense sampler’s notation \(A=d^4\) and \(K_0=4d^8\). There are at most \(\mathsf S:=2^{2db}\) feasible small states, since their number is at most \((C+1)^{2d}\). A completion fiber, the original table space, an offset space, and the bin space each have at most \(\mathsf V:=2^{db}\) elements: use \((C+1)^d\le2^{db}\) and \(K_0<C\). They can be enumerated by listing coordinate arrays and retaining those that pass their defining tests. None of these coordinate ranges depends on \(k\). This exhaustive calculation is used only for the exact correction, not during an ordinary run of the bounded sampler.

Caching a dense completion law. The following denominator allowances are uniform over all feasible small states, with \(h\) as in (51): \[\begin{align*} Q_0&=\lceil\log_2(8d)\rceil+8Ad, &r_{\max}&=b+1+4(h+d),\\ H&=d^{50}(h+1)^2, &J_{\rm D}&=d^4(h+1),\\ R_1&=H Q_0+d r_{\max}, &R_{\rm D}&=J_{\rm D}R_1. \tag{53}\end{align*}\] Every bin transition has denominator dividing \(2^{Q_0}\): its proposal needs \(\lceil\log_2(8d)\rceil\) bits and every dyadic acceptance test needs at most \(8Ad\) bits. For each input \(X\), enumerate its bins, compute their transition matrix as \(B_X/2^{Q_0}\) with integer entries, and propagate the point mass at zero for \(H\) steps. At step \(t\) the vector uses denominator \(2^{tQ_0}\); its next numerator is the previous integer vector multiplied by \(B_X\). Adding contributions from many paths changes the numerator, not the denominator exponent.

Offsets are tabulated without enumerating their random bits. For width \(w\) and the actual bit count \(r=\lceil\log_2(w+1)\rceil+4(h+d)\le r_{\max}\), the probability of offset \(u\in\{0,\ldots,w-1\}\) is \[ 2^{-r}\left( \left\lceil\frac{(u+1)2^r}{w}\right\rceil -\left\lceil\frac{u2^r}{w}\right\rceil\right). \tag{54}\] Indeed these two endpoints count the integers \(z\) with \(u\le wz/2^r<u+1\). Integer ceiling division evaluates the count exactly. Enlarge its denominator to \(2^{r_{\max}}\), pad unused free coordinates to \(d\), and combine with the propagated bin law. Enumerating bin and offset tuples, constructing the candidate table, and applying its feasibility test gives the implemented dense trial’s success numerators \(\alpha_X(a)\) and failure numerator \(\phi_X\), all with denominator \(2^{R_1}\). Sorting of margins and its inverse are deterministic functions of \(X\); we always record completions in the original block coordinates.

Let \(a_X^0\) be the dense call’s fixed greedy fallback. The complete dense output law is exactly \[ \mu_X(a)=\frac{ \displaystyle\sum_{j=0}^{J_{\rm D}-1} \phi_X^j\alpha_X(a)2^{R_1(J_{\rm D}-j-1)} +\mathbf{1}_{\{a=a_X^0\}}\phi_X^{J_{\rm D}} }{2^{R_{\rm D}}}. \tag{55}\] This is a finite first-success sum and the all-fail mass. It introduces no division by a success probability. A deterministic empty or singleton-dimensional completion call uses the same denominator by ignoring the reserved bits. Cache (55) for each \(X\).

Propagating the implemented chain. For a distinct neighbor \(Y\) the implemented transition is \[ \begin{aligned} Q(X,Y)=p\sum_{a\in\mathcal F_X}\mu_X(a) \mathbf{1}_{\{a+D_{XY}\in\mathcal F_Y\}},\\ Q(X,X)=1-\sum_{Y\ne X}Q(X,Y). \end{aligned} \tag{56}\] For an empty block interpret the indicator as one. These entries share denominator \(2^{R_{\rm D}+q_{\rm s}}\). Since only \(X\) persists between steps and completion randomness is fresh, ordinary vector propagation \(v_{t+1}=v_tQ\), starting at \(X_0\), computes the exact adaptive state law. Append the terminal completion draw and the unpadding test. This yields the one-outer-trial success masses \(g(z)\) and failure mass \(f_0=1-\sum_z g(z)\) with common denominator \(2^{R_{\rm T}}\), where \[R_{\rm T}=T(R_{\rm D}+q_{\rm s})+R_{\rm D}.\] Explicitly, \(g(z)\) is the sum of \(v_T(X)\mu_X(a)\) over pairs passing that test and producing \(z\). The final law is \[ p_k(z)=g(z)\sum_{j=0}^{J_{\rm o}-1}f_0^j +\mathbf{1}_{\{z=z_0\}}f_0^{J_{\rm o}}, \tag{57}\] whose denominator divides \(2^R\) for \(R=J_{\rm o}R_{\rm T}\). Both geometric sums are evaluated by bounded integer multiplication and addition. Algebraically, the common denominators reserve ignored bits for holds, shorter draws, and stopped trials; neither tabulation nor sampling enumerates those bit strings.

Bit complexity. The denominator exponents are bounded by fixed polynomials. With \(q=d+b+k+2\ge31\), one has \(h\le q^6\), \(h+1\le q^7\), \(Q_0\le q^6\), \(r_{\max}\le q^7\), \(H\le q^{64}\), and hence \[R_1\le q^{71},\quad R_{\rm D}\le q^{82},\quad R_{\rm T}\le q^{285},\quad R\le q^{290}\le q^{300}.\] Here we used \(T\le q^{202}\), \(J_{\rm o}\le q^5\), and \(q_{\rm s}\le q^2\). Probability numerators never exceed their common denominator. Intermediate products and sums may be stored with the prescribed stage’s denominator, so their bit lengths, including the offset counts in (54), are polynomial as well. Candidate tables that fail feasibility can have negative dependent entries, but their entries are integer sums of \(O(d)\) quantities of size \(O(C)\) and still have \(O(b+\log d)\) bits.

For each state, dense matrix propagation costs at most \(H\mathsf V^2\) arithmetic operations. Bin–offset summation, even with a scan of all completions to identify the output, costs at most \(\mathsf V^3\); the geometric composition costs at most \(J_{\rm D}\mathsf V\). Constructing (56) uses at most \(\mathsf S^2\mathsf V\) terms. Small-state propagation uses \(T\mathsf S^2\), terminal completion and output lookup at most \(\mathsf S\mathsf V^2\), and the last geometric composition at most \(J_{\rm o}\mathsf V\). Including the cache calculation for all \(\mathsf S\) states, the total number of arithmetic operations is at most \(2^{10db}\operatorname{poly}(d,b,k)\); multiplying by the established polynomial bit cost per operation gives the stated, looser \(2^{500db}\) bound. The iteration counts \(H,J_{\rm D},T,J_{\rm o}\) depend polynomially on \(k\); none of the enumerated spaces does. ◻

Proof. Set \[D=d^6b^2,\qquad k=2D,\qquad\delta=2^{-D},\qquad M=|\Omega|.\] Theorem 18 gives, for every \(z\in\Omega\), \(p_k(z)\le1/M+\delta^2\). Also \(M\le(C+1)^d\le2^{db}\) and \(D\ge db\), so \(M\delta\le1\). Therefore \[(1-\delta)p_k(z) \le\frac{1-\delta}{M}+(1-\delta)\delta^2 \le\frac1M.\] It follows that \(r(z)=[1/M-(1-\delta)p_k(z)]/\delta\) is a probability law.

Use \(D\) independent bits to enter a correction branch precisely when all are zero. On the complementary event run the bounded sampler with accuracy \(k\). On the correction branch, enumerate \(\Omega\) to obtain \(M\) and use Proposition 19 to compute \(p_k(z)=a_z/2^R\). Form the integer weights \[ n_z=2^{R+D}-M(2^D-1)a_z, \qquad \sum_{z\in\Omega}n_z=M2^R. \tag{58}\] They are nonnegative by the pointwise domination just proved, and the sum follows from \(\sum_z a_z=2^R\). Thus \(r(z)=n_z/(M2^R)\). All integers in (58) have \(O(R+D+\log M)\) bits; the fact that \(M\) can be large as a number does not make its binary representation long.

To sample this law exactly, put \(V=M2^R\) and draw a uniform integer in \(\{0,\ldots,V-1\}\) by using \(\lceil\log_2V\rceil\) bits and repeating whenever their value is at least \(V\). If \(V=1\), use zero bits. The acceptance probability is greater than \(1/2\), so the expected number of attempts is less than two, and termination is almost sure. A scan of cumulative weights \(n_z\) then selects the output exactly according to \(r\). Use fresh bits on each attempt and after the branch decision.

The output law is \((1-\delta)p_k+\delta r=\operatorname{Uniform}(\Omega)\). The correction branch has conditional expected cost at most \(2^{500db}\operatorname{poly}(d,b,k)\), including enumeration, integer arithmetic, and the exact integer draw. Its contribution to the unconditional expectation is polynomial, since \[\delta\,2^{500db} =2^{-db(d^5b-500)}\le1 \qquad(d\ge14,\ b\ge d).\] Substituting \(k=2d^6b^2\) into a fixed polynomial preserves polynomial dependence on \(d,b\). The other branch and the branch decision also have polynomial cost. This proves the expectation and termination claims. ◻

Proof of Theorem 1. If either dimension is empty, if \(N=0\), or if one dimension is one, return the unique feasible table as in Section 2. Otherwise the parameters in (1) satisfy \(d=O(mn+m+n+1)\) and \(b=O(d+\log(N+1)+\log d)\). For the supplied integer \(k\ge1\), Theorem 18 gives the first assertion. Theorem 20 gives the second. Their bounds therefore have the stated dependence on dimensions and binary margin size. All outputs are feasible, and the exact algorithm’s only unbounded loop is the almost-surely terminating integer rejection on its correction branch. ◻