Exact Uniform Sampling of Contingency Tables with Arbitrary Margins

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-\one_{\{v\in\mathcal S\}}e_v, followed by q=x-e_t+e_s and y=U\one-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.1 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 2.2 and a union bound show that the proportion of these enlarged tables with some large entry below L is at most

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 (2.7).□

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

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

The extended two-removal matrix is W\diag(\alpha)K\diag(\alpha), where

For each set define

The sets containing any given pair of indices form a chain. Telescoping the product along this chain gives the exact identity

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

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 (3.5) 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,

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

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 (3.6) and (3.10) give

If u_{j-1}>0, apply (3.11) to e_a; if u_{j+1}>0, apply it to e_b. Either bound is at most

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

proving (3.8).

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 (3.8) over 0\le j\le D' gives

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 (3.8) by w_j and summing only over the admissible indices gives

This proves (3.9), using only scalar zero endpoint weights, never endpoint matrices outside the box.□

Proof. Induct on |\mathcal R|. Lemma 3.2 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 (3.3). Apply Lemma 3.3 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.□

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

Proposition 3.4 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,

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

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

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 3.3, 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

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

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 (3.9). 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

For an explicit common summation kernel, put

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

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 (4.4) and the explicit square identity are the properties of that sum that are used.

The root bound. Iterating Equation (4.5) shows that the sum of Q_t at the level just before processing t is at least its root value. Thus Equation (4.4), 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

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 (4.7) now eliminate the flow and all recursive coefficients:

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 (4.8) 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.1 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

There are fewer than d possible slots t. Multiplication of the limiting inequality by \min(z_-,z_+) now yields Equation (4.1).□

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

Zero-mass children may be omitted. For positive endpoints a<b, Lemma 4.1 makes every intervening mass at least \min(z_a,z_b). Telescoping and Cauchy–Schwarz therefore give

There are at most (U+1)^2 pairs. Thus the contribution in Equation (4.10) is at most (U+1)^4A_0 E_\sigma(H).

Iterating the identity \Var H=\E(\Var(H\mid j))+\Var(\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 \Var_{\mathcal T} for variance under the normalized transversal weights,

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.1, 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

Insert Equation (4.11) to obtain the first bound in Equation (4.9). 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

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 \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 (5.4). Hence Bernoulli’s inequality gives

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\vol(\mathcal P^-)\ge\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 \R^e, without a cube restriction. For u\in\mathcal P_\gamma the point

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

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 (5.7) gives

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

□

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

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

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

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

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 (5.12).

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 (5.13).□

Proof. For nonnegative g with \pi(g>0)\le1/2, integrate the cut inequality over A_u=\{x:g(x)^2>u\} to obtain

The last step is Cauchy–Schwarz and

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

The L^2 contraction followed by Cauchy–Schwarz bounds the total variation distance by

which implies (5.14). 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

We have S\subset M, by writing x=(1-t)x+tx for x\in S. Lemma 5.3 gives

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

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

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 (5.15), and writing D_i=\sum_{v\in V_i}W(v), gives

The second inequality follows from Equation (5.7): 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

Lemma 5.4 supplies inverse gap at most

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

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 2.2, with a=L and threshold 10d\le L/2, gives

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

follow. Theorem 4.3 and U=d^{20} now give an inverse-gap bound of

Indeed the coefficient inside parentheses is at most 770d^4U^6. The graph is connected by Theorem 4.3, and Proposition 2.3 gives \pi_{\min}\ge(C+1)^{-2d}. Lemma 5.4 now gives (6.1).□

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

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 6.1, 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 2.3, 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

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

In particular, no error is divided by a success probability.

Each term in (6.3) 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,

For the second term,

Finally, since T+1\le2T,

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 5.1; the numbers of steps, trials, and calls in (6.2) 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 (6.2):

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

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

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 (6.6) for each X.

Propagating the implemented chain. For a distinct neighbor Y the implemented transition is

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

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

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

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 (6.5), 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 (6.7) 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

Theorem 6.2 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

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 6.3 to compute p_k(z)=a_z/2^R. Form the integer weights

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 (6.9) 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

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.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 (2.1) satisfy d=O(mn+m+n+1) and b=O(d+\log(N+1)+\log d). For the supplied integer k\ge1, Theorem 6.2 gives the first assertion. Theorem 6.4 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.□