An FPRAS for Cell-Bounded Contingency Tables

Proof. If a free edge had larger capacity than a tree edge on its path, exchanging those two edges would increase the total tree capacity. This proves the path inequality. Leaf elimination proves existence and uniqueness of the nonroot solution: at a nonroot leaf its margin equation determines the edge to its parent, after which that vertex can be removed. The same procedure proves integrality and that all tree values are affine functions of the free values. No equation is imposed at the last, root vertex. For a singleton component there are no unknown tree values and no nonroot equations.

Changing a free value affects tree values along its tree path. Small-cell profiles need more care: their two physical views need not agree, so their contributions must be counted by incidences rather than cancelled as an ordinary flow. The following cut identities keep both effects explicit. Give a row vertex sign \sigma_v=1 and a column vertex sign \sigma_v=-1. For a small-cell incidence (v,s), let

For a large cell write \Delta z_e=z_e-X^*_e, including solved tree cells in this notation. Remove a tree edge t, and let U_t be the vertex set on the side away from the root; let v_t be the endpoint of t in U_t. Sum the differences of the nonroot margin equations over U_t, with signs \sigma_v. Internal large edges cancel. If v(e,U_t) is the unique endpoint in U_t of a free edge crossing the cut, the result is

The last sum is over incidences, including both incidences when a small edge has both endpoints in U_t; its two values can differ for an unbalanced profile.

Each crossing free edge has t on its tree path. Hence |\Delta z_e|\le b_e+1\le2b_t even on the extended real free box. Every small incidence satisfies |\Delta a_{v,s}|\le b_s<W\le b_t. There are at most d free edges and 2d small incidences. Equation (7) therefore gives |\Delta z_t|\le4db_t.

For a whole large-cell component U with root v_0, the analogous signed sum cancels every large-cell contribution and gives

This proves independence from all free values, also for a singleton component. Summing absolute values over components yields \sum_{v_0}|\delta_{v_0}|\le2\sum_{s\in\mathcal S}b_s\le2dW. Since X^*_t\in[0,b_t], the displacement bound now implies

It also places z_t in [-4db_t,(4d+1)b_t]\subseteq[-10db_t,10db_t].

Finally, subtract (7) for two free vectors with the same small profile. Each coefficient in normalized coordinates is \pm(b_e+1) for an edge crossing the cut, and its absolute value divided by b_t is at most two. Thus

Distance from an interval is convex and is 1-Lipschitz. Composing with the affine tree values and summing at most d tree terms proves convexity and (6); the root terms are constant in the free coordinates.□

Proof. We first prove the removal assertion without summation. Coordinates with z_i=0 give zero rows and columns and may be discarded. Temporarily evaluate all remaining entries using the product of factors, even when a repeated removal would give a negative coordinate. This evaluation is well-defined because the factors are defined on all integers. Write

Log-concavity gives 0<\gamma_G\le1. Factor out the value of the product at the display and, from each matrix index i, the positive single-removal ratio

Thus, up to a positive scalar and a positive diagonal congruence, the entry at i,h is \prod_{G\supseteq\{i,h\}}\gamma_G. Restrict the factor sets to the retained coordinates and combine duplicates if necessary. Laminarity then gives the matrix identity

For each entry the identity telescopes along the chain of sets containing both indices. The right-hand side is a rank-one positive semidefinite matrix minus a positive semidefinite matrix, so it has at most one positive eigenvalue. The only invalid removals still present are repeated removals from a coordinate with displayed value one. Their positive diagonal entries must be replaced by zero, which subtracts a nonnegative diagonal matrix. This cannot increase the number of positive eigenvalues.

We now induct on the number of summed pairs. Suppose some pairs have already been summed, and let \Psi denote the resulting weight before the next pair of capacity M\ge1 is summed. Fix a box-valid display z on the other coordinates, two above their new required total. For 0\le k\le M, apply the induction hypothesis to the display (z,k,M-k). The resulting matrix, with the two pair coordinates listed last, is

where

Every N_k has at most one positive eigenvalue. As usual, all out-of-box terms are zero. In particular, S(-1)=S(M)=0, and u_k=0 outside 1\le k\le M-1. The matrix after summation is \sum_{k=0}^M V_k. We must find one common subspace of codimension at most one on which this sum is nonpositive; simply adding the matrices N_k would not establish that property.

If M=1, put S=S(0). After deleting their zero pair axis, N_0 and N_1 have the respective forms

When S\ne0, the null-axis projection just proved shows that both V_0 and V_1 are nonpositive on \{a:a^{\mathsf T}S=0\}. Their sum therefore has at most one positive eigenvalue. If any displayed coordinate z_i is positive, then S_i=\Psi(z-e_i,0,0)>0: the profile has the required total and every previously summed pair supplies a positive balanced term. Thus S=0 can occur only when z=0, in which case all removals are invalid and V_0=V_1=0. This proves the width-one case.

Assume henceforth that M\ge2. For each interior index k, u_k>0: the displayed coordinates are box-valid and have the correct total, and any balanced profile on each previously summed pair supplies a positive term in the original positive-factor model.

For larger widths the common subspace is determined by the sum of the one-removal vectors S(l). Cumulative sums provide auxiliary coordinates whose contributions will telescope. Consider an old-index vector a satisfying the single linear condition

Define

The endpoint condition on a, as well as the cumulative-sum definition at interior indices, gives

For v_k=(a,g_k,-g_k), its products under the form N_k with the first and second new coordinate axes are, respectively,

If either of those axes has positive square, applying (10) to that axis and adding the other nonnegative term gives

If both axis squares vanish, their diagonal entries u_{k-1},u_{k+1} are zero. The endpoint cases k=0,M have a positive other diagonal because M\ge2; hence in the remaining case u_k>0. The sum of the two axes then has square 2u_k>0 and product zero with v_k. Applying (10) to this sum again gives (17), whose right-hand side is now zero. This includes the case M=2,k=1.

Substitute (16) into (17) and expand. The terms involving g_kg_{k-1} and g_kg_{k+1} cancel, leaving

Sum this inequality over 0\le k\le M. Every interior u_kg_k^2 cancels, and all exterior terms are zero. Consequently \sum_kV_k, which is the desired matrix after summing the next pair, is nonpositive on the kernel of one linear functional. Its number of positive eigenvalues is therefore at most one. This completes the induction.

Finally reflect every coordinate in its box: z_i\mapsto m_i-z_i. A factor on a set G remains a positive log-concave sequence in the sum on G, with its argument reversed and translated. A balanced pair of capacity M remains balanced under this reflection, so reflection commutes with balanced summation. The reflected remaining weight is \Phi^\vee(z)=\Phi(m-z). A display two below the original total becomes a display two above the reflected total, and

The removal assertion for the reflected model is precisely the addition assertion for the original model.□

Proof. Introduce a finite physical interval [\ell_s,\ell_s+M_s] for every retained cell. For small and free cells take [0,b_s], and for a tree cell take

Lemma 2.1 shows that these tree intervals contain every completion required by the definition of h_j. Represent a physical row-view value as \ell_s+x_s and a physical column-view value as \ell_s+M_s-y_s, where 0\le x_s,y_s\le M_s. The two views agree when x_s+y_s=M_s. Use the full total slice

For a row or column vertex v, let \kappa_v be its prescribed margin and write its physical line sum as

For 0<\alpha<1, give each box-valid profile on the full total slice the positive weight

Each factor is log-concave in its indicated coordinate sum. Row factors use disjoint groups of x coordinates, and column factors use disjoint groups of y coordinates. These two collections are also disjoint from one another. The only additional factors are unary tree factors, each nested in its row group. Thus the entire family is laminar. Letting \alpha\downarrow0 imposes every nonroot equation exactly while retaining the root and tree penalties.

Sum every large-cell pair at balance. The widths of all summed pairs are positive. The remaining total is p. For every small count profile on that slice and every free-cell assignment, the exact nonroot equations have a unique tree completion, and it lies in the chosen intervals by Lemma 2.1. Therefore, in the equality limit, each free assignment contributes exactly one term, with precisely the root and tree penalty defining h_j; there is no multiplicity from tree coordinates. The removal assertion follows from Lemma 3.1 and passage to a finite limit. Reflecting all coordinates, including those that are summed, gives the addition assertion by the same lemma.□

Proof. Use the finite interval representation and positive weight (19) at j=H, with 0<\alpha<1. Sum every cell pair except t at balance. All retained cells have positive width, including small cells of bound one, so Lemma 3.1 applies. The remaining required total is M_t. Let a_{t;\alpha}(k) be the resulting weight of the retained balanced pair with physical value k, for \ell_t\le k\le\ell_t+M_t. It is positive throughout this integer interval: after fixing the retained pair, any balanced choices for all other pairs satisfy the boxes and total slice, and every factor is positive. Exact nonroot equations are not required before taking the limit.

At an interior value k, the retained profile is

Adding one to both coordinates gives a box-valid display two above its required total. Lemma 3.1 applied to the two remaining coordinates gives the matrix

with at most one positive eigenvalue. Its positive trace implies a nonpositive determinant, so

All these marginal masses are positive. Their logarithms therefore have nonincreasing successive differences, which proves global interpolation between any two values in the interval.

Now let \alpha\downarrow0. The sums are finite, and the surviving profiles satisfy every nonroot equation. For each balanced small profile and free assignment those equations have exactly one tree completion, contained in the chosen intervals by Lemma 2.1. The surviving weight is exactly 2^{-D}. Consequently, term by term,

Pass the global interpolation inequality to this limit. For positive limiting endpoint masses its right-hand side is positive, giving (21) and ruling out any internal support gap. No inference from adjacent inequalities alone after the limit is needed.□

Proof of Proposition 2.2. Expand C(H) over balanced small profiles and free integer vectors, giving each assignment mass 2^{-D}. The forest equations determine one tree vector for each such assignment. It represents a feasible table exactly when every root deviation is zero and every tree value belongs to its allowed interval. These assignments each have mass one, so C(H)\ge Z\ge1. The total number of assignments is \prod_{s\in\mathcal S}(b_s+1)\prod_{e\in\mathcal F}(b_e+1)\le2^K, and every mass is at most one.

Call an assignment far if a root deviation is nonzero or a tree value has distance at least \gamma b_t from [0,b_t]. A nonzero root deviation is an integer of absolute value at least one. Since \gamma<1 and A\gamma\ge4K, every far assignment has D\ge4K. The total mass of all far assignments is therefore at most 2^K2^{-4K}=2^{-3K}\le\epsilon/128. Because C(H)\ge1, this also bounds its fraction of the total mass.

For each tree cell t, its marginal satisfies

The endpoint inequalities follow from endpoint attainability after tightening and the unit mass of each feasible table. If k<0 and a_t(k)>0, use (21) from k toward b_t. For every integer 0\le r\le\lfloor(b_t-k)/K\rfloor, writing \alpha=r/(b_t-k)\le1/K, the endpoint cases and interpolation give

All these integers lie between k and b_t. Their number is \lfloor(b_t-k)/K\rfloor+1\ge b_t/K, and hence a_t(k)/C(H)\le2K/b_t.

For the other exterior side, let k>b_t with a_t(k)>0 and interpolate toward zero. Every integer 0\le r\le\lfloor k/K\rfloor satisfies

There are \lfloor k/K\rfloor+1\ge b_t/K such integers, giving the same bound a_t(k)/C(H)\le2K/b_t. The bound also holds when a_t(k)=0.

On either exterior side of [0,b_t], the number of integers at positive distance strictly less than \gamma b_t is \max\{\lceil\gamma b_t\rceil-1,0\}<\gamma b_t. Consequently the fraction of mass with 0<\dist(z_t,[0,b_t])<\gamma b_t is at most 4\gamma K. A union bound over at most d tree cells bounds all these near violations by 4d\gamma K=\epsilon/128. Every infeasible assignment is far or has such a near tree violation. We conclude that

Finally, C(H)\le Z/(1-\epsilon/64)\le(1+\epsilon/32)Z for 0<\epsilon<1, as claimed.□

Proof. Fixing inclusions enlarges the set of fixed elements in the quadratic test, and fixing exclusions restricts that test to a principal submatrix. Positivity is retained whenever the residual degree is valid.

We prove the contraction assertion through a symmetric cubic tensor. Suppose T_{iuh} is positive on triples of distinct indices and zero on repetitions, and every slice T_i=(T_{iuh})_{u,h} has at most one positive eigenvalue. There are at least three indices. For a vector a with all entries positive, set

Tensor symmetry gives

The strict inequality holds even with exactly three indices: the two indices other than i give a strictly positive term. Applying (10) to every slice and then summing with coefficients a_i yields

Thus the symmetric matrix M'=D_*^{-1/2}MD_*^{-1/2} satisfies M'\preceq(M')^2. It has the positive eigenvector u=D_*^{1/2}a with eigenvalue one. Every off-diagonal entry of M, and hence of M', is strictly positive, because a third distinct index contributes a positive term. The matrix with entries M'_{ih}u_h/u_i is therefore irreducible and row-stochastic. The maximum principle bounds the absolute values of its real eigenvalues by one and shows that its eigenvalue-one eigenspace consists of the constant vectors. Since M' is symmetric, eigenvalue one is simple. On the other hand, (25) requires every eigenvalue \lambda of M' to satisfy \lambda\le\lambda^2, so a positive eigenvalue must be at least one. There can consequently be only one positive eigenvalue. Positive diagonal congruence gives the same conclusion for M. For nonnegative a, replace it by a+\varepsilon\mathbf 1 and pass to the matrix limit as \varepsilon\downarrow0. This establishes the full-matrix contraction assertion.

Now sum a pair \{\alpha,\beta\} at occupancy one in a positive weight F on k-subsets:

If k-1<2, the desired addition property is vacuous. Otherwise fix k-3 included elements outside the pair. The remaining three-element weights form a tensor T of the kind just considered. Each slice is an addition matrix of F, with a zero row and column at its fixed index. Contract with the indicator of \{\alpha,\beta\}. Restricting the resulting full matrix to the other indices gives exactly the addition matrix of F^\downarrow. The result is therefore valid. Every valid residual weight is a sum of positive terms, so positivity also persists.

Finally, complementation interchanges fixed inclusions with fixed exclusions and preserves occupancy one in a two-element pair. Applying the addition argument to complement weights proves all the omission assertions.□

Proof. The case p=1 is immediate for the original two properties, so consider a quadratic test when it is nonvacuous. For the omission property of f, fix p-2 omitted elements. This leaves a display of p+2 elements from which two must be removed. Group its elements by small-cell row or column coordinate, and write n_u for the number in group u.

Within a group, all distinct-copy matrix entries are equal, and the diagonal entries are zero. Vectors whose entries sum to zero in each group have nonpositive square: in each group the form is a nonnegative multiple of \mathbf 1\mathbf 1^{\mathsf T}-I. These vectors have no coupling to vectors that are constant within each group. It remains to examine the latter subspace.

Let its value on group u be t_u. For distinct groups u,v, the n_un_v ordered-copy multiplicity cancels the two factorial reductions when passing from displayed counts n to n-e_u-e_v. For a single group u, the multiplicity n_u(n_u-1) similarly cancels the factorial reduction for two removals. If n_u<2 this term is zero. The resulting quadratic form is exactly

with zero entries for invalid removals. By Corollary 3.2, it has at most one positive eigenvalue. Together with the nonpositive group-sum-zero subspace, this proves the omission property of f.

For the addition property of \widetilde f, fix p-2 included elements, with coordinate counts r_u. There are n_u=b_u-r_u available elements in coordinate group u, where b_u=b_s for either coordinate of cell s. After adding two elements, the factorial numerator of \widetilde f is the product of the remaining-capacity factorials. The same group decomposition and the same multiplicity cancellation therefore give, up to a common positive scalar, the form

Invalid additions give zero entries. The addition assertion of Corollary 3.2 proves that this form has at most one positive eigenvalue. The group-sum-zero subspace again contributes only nonpositive squares. This proves the addition property of \widetilde f.

All p-subset weights in (22) are strictly positive. The closure assertions now follow from Lemma 4.1, applied respectively in omission and addition variables.□

Proof. Fix the inclusions and exclusions specified by \sigma. For (26), sum every other unassigned pair at occupancy one, leaving only i,l. By Lemma 4.2, the remaining positive two-element weight has an addition matrix with at most one positive eigenvalue. Restrict its quadratic form to vectors constant on each of the two pairs. The resulting matrix is

The diagonal factor two counts the two orders of the elements in a full pair; the off-diagonal sums exactly the transversals. The matrix has positive trace and at most one positive eigenvalue, so its determinant is nonpositive. This proves (26).

For (27), sum every other unassigned pair at occupancy one, leaving the six elements in i,l,k and a positive weight on their three-element subsets. Form its symmetric cubic tensor, zero on repeated indices. Contract it along the indicator of the two elements of pair k. By the full-matrix assertion of Lemma 4.1, the resulting matrix has at most one positive eigenvalue even while the two contracted indices are retained. Restrict its form to vectors constant on each pair, and call the resulting three-by-three matrix N, indexed by i,l,k. Its relevant entries are

For example, in N_{ik} the full pair k can contribute either of its elements to the contraction and the other to the matrix index, explaining the factor two. All entries of N are nonnegative, and N_{ll}>0.

By (10), the Schur complement against the l,l entry is negative semidefinite. Its two remaining coordinates i,k therefore satisfy

The square-root factors are nonnegative by the same Schur complement condition. The second inequality uses N_{ii},N_{kk}\ge0 and the nonnegativity of the off-diagonal entries. Substituting (28) gives (27).□

Proof. We seek a signed edge current whose divergence is f(S)/s_0 at states with hole P_0, -f(S)/s_1 at states with hole P_1, and zero at all ordinary-hole states. Orient each edge once, write I_{SS'} for its signed current, and write c_{SS'} for its conductance. Such a current satisfies, by summation by parts and Cauchy–Schwarz,

It therefore suffices to bound its flow energy by the coefficient in (32).

The local routing step explains the energy quantity we will use. A complete display R contains the two singleton elements and one chosen element from every ordinary slot. Its one-hole sets S_i=F\cup(R\setminus\{i\}), i\in R, form a clique of exchange edges. For an element i, write W_i for its slot’s multiplier. Put m_i=f(S_i). For any coefficients h_i with \sum_i m_i h_i=0, regard m_i h_i as the prescribed signed divergence at S_i. Choose a hub h_* maximizing W_i m_i, and send current m_i h_i from each nonhub S_i to the hub. Balance gives the prescribed divergence at the hub as well. Each used edge has conductance W_i m_i at its nonhub endpoint, so this routing has energy at most

We now assign these balanced demands recursively. Their sum over complete displays will have the required source and sink divergences; the recursion will also bound the sum of their routing energies.

Fix an order of the ordinary slots. Initially display the two singleton elements. Expose ordinary slots in that order, branching into two children according to which element of the next slot is added to the display. At a node write R for its displayed elements, excluding F. For i\in R, let m_i be the sum of f over sets that contain F\cup(R\setminus\{i\}), omit the nondisplayed mates in already processed slots, and have single occupancy in every unprocessed ordinary slot. These sets all have size p, and m_i>0. At a complete display this definition reduces to m_i=f(S_i). Maintain coefficients h_i, interpreted as demand per unit unmultiplied weight, satisfying

At the root their values are 1/s_0 and -1/s_1 at the elements of P_0 and P_1, respectively. Assign the node the potential

At a leaf this potential bounds the routing energy just computed. Each W_i is fixed by its slot throughout the recursion. These multipliers enter the energy bound and the eventual hub choice, but not the recursive coefficients or prescribed divergences.

Suppose the next slot t has elements a,b. For an old hole i\in R, let m_i^a,m_i^b be its masses in the two children. Then m_i^a+m_i^b=m_i. The mass of the newly introduced hole, at a in the first child and at b in the second, is the same positive number u: in either case the entire slot t is empty. Put X=\sum_{i\in R}h_i m_i^a. Retain every old coefficient unchanged, and give the new hole coefficient -X/u in the a child and X/u in the b child. Equation (34) holds in both children because \sum_i h_i m_i^b=-X. The sum of their potentials exceeds the parent potential by exactly

We bound these increments using the omission signature. At any node, and for any unprocessed ordinary slot t, define a symmetric matrix V_t(R) on the displayed elements, with zero diagonal. For distinct i,k\in R, its entry is the sum of f over configurations with holes at i,k in the display, double occupancy in slot t, and single occupancy in every other unprocessed slot. Fixed inclusions, exclusions, and previously excluded mates remain in force. All these configurations have size p.

When t=\{a,b\} is the next slot, V_t(R) is the old block of

This form has at most one positive eigenvalue. To see the precise application, fix the context and exclude the nondisplayed mates of processed slots. Sum all unprocessed ordinary slots other than t at occupancy one. On the remaining ground set R\cup\{a,b\} the resulting degree is |R|, so N is its two-omission matrix. Lemmas 4.2 and 4.1 give the asserted signature. In particular, this argument uses the full-domain weight f even when an entry of V_t(R) describes multiple empty and full original pairs. No comparison with \widetilde f is made here.

Extend h by zero at a,b and put d_{ab}=e_a-e_b. The vector e_a+e_b has square 2u>0 under N. Both h and d_{ab} are orthogonal to it in this form, since (34) holds and the two new diagonal entries are zero. A symmetric form with at most one positive eigenvalue is nonpositive on the form-orthogonal complement of a positive-square vector: another positive-square vector in that complement would span a positive definite plane with the first vector. On the complement, Cauchy–Schwarz for the negative of the form applies. Here

Consequently

Fix now a slot t to be processed at a later level. When a preceding slot is split, the sum of the two child quantities h^{\mathsf T}V_t(R)h equals the parent quantity. The old entries split additively. A cross entry involving the new hole represents a configuration in which the split slot is empty, so it is identical in the two children. Its contributions cancel because the new coefficients are opposite and all old coefficients are retained. There is no new diagonal contribution. Iterating this identity shows that, immediately before processing t, the sum of these quadratic quantities over the whole level is their value at the root. The root matrix has off-diagonal entry v_t and zero diagonal, so that value is -2v_t/(s_0s_1). By (35) and (36), the total potential increase at the level of slot t is at most 2v_t/(s_0s_1W_t). The root potential is 1/(s_0W_{P_0})+1/(s_1W_{P_1}). Thus the sum of all leaf potentials is bounded by the parenthetical coefficient in (32).

Route the prescribed demands at every leaf by the clique construction above. Its energy is at most \Psi(R,h). Different leaves cannot use the same edge: the union of two distinct endpoints of a leaf edge is exactly F\cup R, and so determines the entire display and its unique sequence of choices. Hence the assembled flow has energy at most the sum of the leaf potentials.

It remains to identify the divergence after summing the leaf flows. A state with a singleton hole has one leaf representation; its divergence is f(S)/s_0 or -f(S)/s_1. A state S with an ordinary hole at slot t has exactly two representations, obtained by adjoining either element of t to S\setminus F. Every other displayed ordinary choice is fixed by S. The two histories agree before processing t, so the same X,u create opposite coefficients there. Those coefficients remain unchanged at every later branch, regardless of the later masses and new coefficients. At the leaves both masses are exactly f(S), and their divergences cancel. This reasoning also applies if the state is a hub in either leaf, since its net divergence is still m_i h_i. The assembled flow therefore has the required divergence, and (33) together with the leaf-potential bound proves (32). If s=0, the root is already a complete display and the same clique argument applies directly.□

Proof. We decompose the transversal variance along a tree of partial assignments, choosing the next pair as a function of the current assignment. Let \sigma fix some pairs to specified single choices. For distinct unassigned labels define

Lemma 4.4 gives

For the second inequality, use the conditional defect inequality on the first factors and the unconditioned inequality with indices k,l,i on the second factors. Form a directed graph with arc i\to l when a_{il}>1. It has no directed two-cycle. A shortest longer directed cycle could be shortened using the second inequality in (38), also a contradiction. Thus this graph has a sink k, for which a_{kt}\leq1 at every other unassigned label t. If only one label remains, choose it as k.

Branch on the two choices in pair k. Apply Lemma 5.1 with the two elements of k as singleton slots, both of multiplier one, and with the other unassigned pairs as ordinary slots. Keep \sigma fixed. A singleton-hole state is a transversal respecting \sigma; an ordinary-hole state at t has type tk and multiplier W_t=w_{tk}. The auxiliary doubled-slot mass is exactly v_t=c_{kt}^\sigma. Thus every one-hole state in this application belongs to \mathcal X with precisely its weight \lambda. The good-multiplier bound, followed by two uses of (24), gives

These comparisons involve only actual defect types.

Let s_0,s_1 and \bar g_0,\bar g_1 be the masses and means of the two transversal children, so s_0+s_1=z_\sigma. Their unnormalized between-means variance contribution is

Let \mathfrak D_\sigma(g) be the sum in (31) restricted to edges whose two endpoints respect \sigma. The slot energy in this application is a subgraph energy, so it is at most \mathfrak D_\sigma(g). Multiplying (32) by s_0s_1/z_\sigma and using (39) yields

The first two terms in the transport coefficient contribute exactly (s_0+s_1)/z_\sigma=1; the ordinary slots contribute at most 8pq^2.

Iterate this branching until every pair is fixed. The conditional variance identity decomposes C\Var_\mu(g) as the sum of the between-means contributions over the internal nodes. At any depth, two distinct nodes disagree on the choice of the pair fixed at their first divergence. Their restricted state sets are disjoint, even if subsequent pairs were chosen in different orders. Consequently their internal edge sets are disjoint and

An edge crossing a fixed-pair choice is internal to neither of the two resulting restrictions; it does not create a duplicate charge. There are p possible branching depths. Summing (40) proves (37). The conditioning tree and sink choices are used only in this proof.□

Proof. Of the four possible joint choices in pairs i,l, choose one whose transversal mass is at least C/4. Denote the selected elements by a_i,a_l and their mates by b_i',b_l'. In Lemma 5.1, fix a_l included and b_i' excluded, and take P_0=\{a_i\}, P_1=\{b_l'\}. All other pairs are ordinary slots. A hole at P_0 gives the entire defect type il, whereas a hole at P_1 gives the selected conditional transversal class. Thus

An ordinary hole at t has type tl, restricted to the choice a_i in pair i, and has multiplier W_t=w_{tl}. A doubled ordinary slot with both singleton slots empty is a subset of type it, so v_t\leq c_{it}. All one-hole states and their exchange edges are therefore genuine states and edges of the chain, with the same endpoint weights. Their energy is at most \mathfrak D(g).

The lift comparison and Lemma 4.4 give, for each ordinary slot t,

The first two terms in the coefficient of (32) are at most 4/C+4/C. For its last term, (29) and (42) give

This proves the first inequality of (41) with \bar g' the selected conditional mean. The conditioning event has \mu-probability at least 1/4; conditional Cauchy–Schwarz gives

which proves the second inequality.□

Proof. Let m=\mathbb E_\mu g. Lemma 5.3 and (a+b)^2\leq2a^2+2b^2 give

Variance is no larger than squared deviation about any fixed constant. Therefore

using Proposition 5.2 in the last step. Finally, (31) and (30) give \mathfrak D(g)/C\leq10p^4\mathcal E(g). When p=1 the defect sum is empty and \mathcal Q=I; the same inequalities apply.□

Proof. Write G_c=G-\mathbb E_\pi G and v=\Var_\pi(G). Because \mathcal Q is an orthogonal projection fixing constants, for every g,

On the mean-zero subspace, I-P is positive definite and invertible: reversibility makes P self-adjoint, and finite irreducibility makes its eigenvalue one simple. Take g=(I-P)^{-1}G_c on this subspace and put

The previous inequality gives a^2\leq K_{\mathrm{obs}}va, and hence a\leq K_{\mathrm{obs}}v, also when a=0.

Laziness puts the spectrum of P in [0,1]: the operator 2P-I is itself a reversible stochastic contraction. Thus the stationary covariances c_t=\langle G_c,P^tG_c\rangle_\pi are nonnegative, and finite spectral decomposition on the mean-zero subspace gives

For a stationary trajectory the mean squared error of the average is

Finally, the law of an entire trajectory started from \nu is bounded by U times the corresponding stationary trajectory law: only the initial factor changes in the product of transition probabilities. Applying this domination to the nonnegative squared error proves (45).□

Proof. Finite irreducibility ensures finite expected hitting and return times to \mathcal A. Explicitly, from each state choose a finite positive-probability path to \mathcal A. Finiteness of the state space gives a common bound on path length and a positive lower bound on these path probabilities. The Markov property then gives a geometric bound in blocks on the hitting-time tail. Applying this after the first transition also bounds the strictly positive return time. These qualitative bounds justify the harmonic extensions and occupation sums below; no polynomial estimate is assumed at this point.

For a function h on \mathcal A, let \widehat h be its harmonic extension

Then \widehat h=h on \mathcal A, (I-P)\widehat h=0 off \mathcal A, and (I-P)\widehat h=(I-P_{\mathrm{tr}})h on \mathcal A by conditioning on the first transition. For harmonic extensions \widehat h,\widehat k of h,k, it follows that

Symmetry of the left side proves reversibility of the stochastic kernel P_{\mathrm{tr}} with respect to \mu, and thus stationarity. Tracing positive-probability paths of P proves irreducibility. Also P_{\mathrm{tr}}(x,x)\geq P(x,x)\geq1/2.

Let \mathcal E_{\mathrm{tr}}(h) =\langle h,(I-P_{\mathrm{tr}})h\rangle_\mu. Taking k=h in (48) gives the exact normalization

Proposition 5.2 therefore implies

This is the stated inverse-gap bound. The inequality 2p^2C_{\mathrm p}\leq K_{\mathrm{obs}} follows immediately from (43) and p\geq1.

For the pointwise estimate put e_x(z)=\mathbf 1_{\{x\}}(z)/\mu(x)-1. Reversibility and spectral contraction on mean-zero functions give

which proves (46).

To compute the mean return cost, start the underlying chain with law \mu on \mathcal A and define the finite occupation measure

Shifting the sum by one transition removes the initial law and adds the return law. Both are \mu, since the trace is stationary. Thus mP=m. Uniqueness of the stationary probability measure for the finite irreducible chain implies m=c\pi for some positive constant c. Before the return, the only visit to \mathcal A is at time zero, so m restricted to \mathcal A is exactly \mu. Consequently c\pi(\mathcal A)=1 and

Pointwise domination of the starting law proves (47). Since \mu is stationary for the trace, \nu P_{\mathrm{tr}}^r\leq U\mu for every deterministic integer r\geq0. Applying (47) to each of these laws and using the Markov property at return times bounds the expected sum of s excursion lengths by sU/\pi(\mathcal A). This last bound is unconditional at the deterministic trace indices; it does not assert domination after conditioning on an arbitrary past event or on meeting a running-time cap.

When p=1, every state is a transversal, P_{\mathrm{tr}}=P, and every return costs exactly one underlying transition. The stated bounds include this case.□

Proof. In dimension one, write A_i=\int_{S_i}f_i for i=1,2; zero source mass makes the conclusion immediate. Let x(u),y(u) be the increasing quantiles of the two normalized source densities, 0<u<1. Away from finitely many subdivision parameters they are continuously differentiable, with

The map z(u)=(1-t)x(u)+ty(u) is increasing. Its smooth pieces have disjoint images contained in S_0; jumps merely omit nonnegative contributions to the target integral. Change of variables on these pieces, followed by the weighted arithmetic–geometric mean inequality, gives

This argument also permits nonnegative piecewise-continuous densities with finitely many zero intervals, provided each nonzero piece is bounded above and bounded away from zero.

For the induction on dimension, fix first coordinates x_1,y_1 of the two sources and put z_1=(1-t)x_1+ty_1. The corresponding slices satisfy the same set inclusion and interpolation hypothesis in one lower dimension. The induction hypothesis therefore gives the one-dimensional interpolation inequality for the three marginal integrals over slices. Subdivide the first-coordinate axis at the finitely many box endpoints. On each resulting interval every slice domain is constant; positivity and continuity on the ambient compact box make each nonzero marginal continuous, bounded, and bounded away from zero there. Thus the one-dimensional argument just proved applies to the marginals. Iterated integration proves the claim.□

Proof. Write \mu for unnormalized integration against \varrho_a on D_0=(0,B)^e. For a fixed cut, let S be the union of the open unit bins on the side of smaller continuous mass. Grid hyperplanes have zero mass, so \mu(S)\le\mu(D_0)/2. Set

The set M is a finite union of open boxes and contains S. Lemma 6.2, applied with all three functions equal to \varrho_a, gives

We cover the added mass by neighborhoods of cut faces. Consider a point z\in M\setminus S off the grid hyperplanes, and choose x\in S, y\in D_0 with z=(1-t)x+ty. The segment from x to z has sup-norm length less than r. At some grid-crossing event its entering and exiting bins have different cut membership. If several coordinates cross simultaneously, flip those coordinates one at a time between the entering and exiting bins. All intermediate bins are incident to the crossing point and lie in the cube. At least one consecutive pair belongs to opposite sides of the cut. Its closed common face contains the crossing point, so z is within sup distance r of an actual axis-adjacent cut face.

This proves containment, up to the null set of grid hyperplanes, in the union of the radius-r neighborhoods of the cut faces. It does not charge a multiplicity for the number of incident bins. Disconnectedness of S causes no change in the argument. The segment stays in the open ambient cube, and intersecting a face neighborhood with that cube only reduces its volume.

Each face neighborhood has volume at most

Every point in it is within sup distance 1+r of either adjacent lower corner. The logarithmic Lipschitz bound and \varrho_a(v)\le V_a(v) therefore bound its density by 2^{1+r}V_a(v)\le4V_a(v) for each of the two adjacent corners separately. Thus, if F is the sum of \min\{V_a(v),V_a(w)\} over cut edges, the covering gives \mu(M\setminus S)\le4F.

Let m be the smaller of the two unnormalized discrete side masses. By (52),

This remains true if the smaller continuous side is the larger discrete side. Combining with (55) yields F\ge tm/32. The directional proposal probability is at least 1/(8d), so the normalized conductance is at least

□

Proof. Each output has either \lfloor2^k/M\rfloor or \lceil2^k/M\rceil preimages. Summing its deviation from probability 1/M gives a total-variation bound at most M2^{-k}. Computing the displayed integer quotient needs no rejection step.□

Proof. Lemma 2.1 gives 0\leq D\leq H. Each summand in h_{j+1} is therefore between one half and one times the corresponding summand in h_j, proving (59). The factorial factor in f_j is independent of j. Summing the same inequalities over any type gives

These bounds imply the multiplier comparison and \mu_j\leq 2\mu_{j+1}.

On a transversal the factorial factor is \prod_s\binom{b_s}{x_s}^{-1}\geq 2^{-p}. Also h_j(x,y)\geq M_f2^{-H}, while

Their quotient proves (60).

At parameter zero, h_0=M_f, so

We give an explicit formula for every defect total. Fix distinct pair labels i,l, with i empty and l full. For each small cell s, let

There are n_s singly occupied pairs left in that cell. If exactly k of these use their row elements, then x_s=k+v_s, y_s=n_s-k+v_s, with multiplicity \binom{n_s}{k}. Hence

This includes the case in which i,l lie in the same cell: then u_s=v_s=1 and n_s=b_s-2\geq 0. All factorial arguments are at most p, and all sums have at most p+1 terms. Using the common denominator b_s! within each bracket, the numerators and denominators in (62) have O(L+p\log(p+1)) bits. There are at most p(p-1) such totals. The multipliers

are therefore positive rationals of polynomial bit length and are computable by bounded integer arithmetic. In fact the local bracket in (62) equals b_s+1, 1, (b_s+1)(b_s+2)/6, or (b_s+1)/6, according as the cell contains neither designated pair, only the hole, only the full pair, or both. If s(i) denotes the cell containing pair i, the equivalent initializer is

Finally, the asserted sampler assigns any particular transversal probability

This proves its distribution. The finite-choice description will be implemented with bounded fair-bit draws below.□

Proof. We make the conditioning in the argument explicit. Let \mathcal F_j be the sigma-field generated by the completed trajectories, transition decisions, and counts of phases before j in the capped reference experiment. The stored multipliers and the event that all these earlier phases were successful are \mathcal F_j-measurable. Fix a past history on that event. The multipliers w^{(0)},\ldots,w^{(j)} are now fixed and good; this will follow inductively from the update calculation below. The current phase uses independent fresh randomness.

For analysis of this one phase, define a virtual experiment that continues its restart without a transition cap, and then takes its N_{\rm av} observations using fresh randomness. Write M=H+p+K. Lemma 5.6 and (60) imply that, from any starting transversal, a stage of \tau trace steps has pointwise relative error at most

Its endpoint law is consequently at most 2\mu_a. At the entrance to stage a=1, the law is \mu_0\leq 2\mu_1. At every later stage it is at most 2\mu_{a-1}\leq 4\mu_a. Invariance of the trace law preserves the bound 4\mu_a throughout that stage.

For good multipliers, \pi(\mathcal A)\geq 1/(5p^2). The warm return-cost bound of Lemma 5.6 therefore bounds the expected number of underlying transitions in each trace step by 20p^2. The virtual restart uses at most H\tau trace steps, so its expected total cost is at most 20p^2H\tau. Markov’s inequality gives

For j=0, the cost is zero and the same upper bound holds.

The virtual restart endpoint is at most 2\mu_j, including j=0. Since \mu_j is the conditional law of the current stationary distribution \pi on \mathcal A, this endpoint law is at most 10p^2\pi on the full state space. Each type indicator and G_j is fixed by the projection \mathcal Q of Section 5. They take values in [0,1]. Their stationary means p_T,u, given by (63), are at least 1/(20p^2): this is the type probability bound for defect types, while p_0\geq 1/(5p^2) and C(j+1)/C(j)\geq 1/2.

By Lemma 5.5, each empirical mean in the virtual observation trajectory has mean squared error about its stationary mean at most

There are p(p-1)+2\leq 2p^2 observables. Markov’s inequality and a union bound therefore give

These bounds concern the virtual, uncapped current phase. Whenever its restart cost is at most B_{\rm ret}, it agrees with the actual capped phase. Thus failure of the capped phase is contained in the union of the two virtual failure events in (68) and (69). In particular, we never condition the endpoint law on surviving the cap.

It remains to check that empirical success maintains the induction and controls the output. Because \eta<1/4, empirical success makes every type count positive. By (63), the exact ratio w_{il}^{(j)}p_0/p_{il} is the current ideal multiplier C(j)/c_{il}(j). The relative errors in \widehat p_0,\widehat p_{il} change this value by a factor between (1-\eta)/(1+\eta) and its reciprocal, both lying in [1/2,2]. Lemma 7.1 changes the ideal multiplier by at most another factor two at the next parameter. Equation (66) therefore satisfies (29) for j+1. The update estimates the current ideal multiplier directly; its error does not multiply the earlier error in w^{(j)}.

The same empirical bounds, and u/p_0=C(j+1)/C(j), give

Initialization is good by Lemma 7.1. For every successful fixed past, the conditional probability of a current failure is at most 2/[100(H+1)]. Summing the probabilities of the first failing phase gives total failure probability at most

On the complementary event, the ratio product telescopes and its logarithmic errors sum to (67).□

Proof. We first bound the number of outer random actions. Let s_{\rm sm} be the number of positive small cells, so s_{\rm sm}\leq\min(p,d), and put

This bounds all underlying transitions in the capped run. Each transition needs at most two weight evaluations, four outer draws (a hold coin, two element choices, and an acceptance threshold), and one transition count. Each of at most HN_{\rm av} observations needs at most two additional weight evaluations. Initial sampling needs at most 2s_{\rm sm} outer draws per phase. Consequently

A visited state has a single type, whose counter is incremented. There is no separate sampling for each defect type. Initializing the p(p-1) counters and computing their updates are additional deterministic polynomial computations.

For the coupling, expose the completed joint history of both processes immediately before each requested evaluation or draw. The event that the processes have matched so far, and the current evaluation input, are measurable in this history. A new evaluation uses a fresh bit stream independent of that history. Its conditional failure probability is therefore at most \xi, uniformly over the requested profile. This conclusion remains valid after earlier matching and accuracy events, because they concern only already exposed randomness.

Before a discrepancy, both runs have the same state and stored multipliers. Couple their initial and proposal draws at total variation cost at most \xi per finite choice. Conditional on matching proposals and accurate evaluations, let r be the reference acceptance ratio before clipping and r' the computed ratio. The exact factorial and multiplier factors are the same in both runs, and hence

It follows, regardless of the magnitude or quality of the multipliers, that

The dyadic threshold adds at most \xi to this absolute probability difference. To realize a common-uniform coupling, let Y be the actual fresh uniform k-bit integer used for the acceptance decision, and write its dyadic threshold as m/2^k. In the proof alone, introduce V uniform on [0,1), independent of Y, the completed joint past, and the current weight evaluations. Then U=(Y+V)/2^k is uniform on [0,1), and the implemented test Y<m is exactly U<m/2^k. Use U<\min(1,r) for the reference decision. Their mismatch probability is the absolute difference of these thresholds, with the bound just obtained. The auxiliary variable V is never sampled by the algorithm.

The coupling preserves the reference transition marginal conditional on the completed joint past. We do not condition the reference process on the event that the entire coupling eventually succeeds. Matching paths have exactly the same integer type counts, and the update (66) depends only on those counts. Thus their stored multipliers remain exactly equal, even though their observations of G_j need not be equal. Trace return times and cap decisions are functions of the matched state paths, so they also agree. A union bound over (71), charging evaluation failures and draw or acceptance discrepancies, is at most 10J_*\xi. On the remaining event, each positive observed weight ratio has logarithmic relative error at most 4\xi. Zero observations are zero in both runs.

We next prove the unconditional resource bound. Since all input cells are listed explicitly and the parameters are included in the input length, d,K=O(L). The definitions in (2) give, for example,

All quantities in (64) and (70), including \xi^{-1}, are therefore bounded by fixed polynomials in L,\epsilon^{-1}. Their rational encodings have polynomial length. The state can be stored using 2p membership bits or p element labels; the small counts and state type can be recovered by bounded scans.

There is also a uniform size bound for stored multipliers on unsuccessful histories. Let B_0=O(L+p\log(p+1)) bound the initial numerator and denominator lengths obtained from (62). On every nonaborting history,

Thus, even without fraction reduction, its numerator and denominator each have at most

bits, up to a fixed additive constant. A zero count causes an abort before any such division. This bound does not assume good multipliers or accurate weight calls.

Proposition 6.1 supplies a deterministic polynomial bound on the work and output length of each evaluation, including its statistically unsuccessful executions. More explicitly, its ratio averages always lie in [1/2,1] and its rounded correction average always lies in [1/16,8], so every call at parameter j returns a number in

Its bounded dyadic precision and bounded numbers of rational operations give a polynomial representation length as well. The inputs of this subroutine are j, a valid small-count profile, and the fixed tolerances; multiplier values are not subroutine inputs. Multiplication by the exact factorial factor adds only O(p\log(p+1)) bits. Combining this bound with (72) proves that every Metropolis ratio and threshold comparison has polynomial-sized operands.

For the output arithmetic, let B_f be an unconditional polynomial bound on the lengths of evaluated f-weights. Each observation ratio has O(B_f)-bit numerator and denominator. Adding N_{\rm av} such rationals using their product as a common denominator requires O(N_{\rm av}B_f+\log(N_{\rm av}+1)) bits. Dividing by a nonzero empirical type probability adds only O(\log(N_{\rm av}+1)) bits. The product of the H phase estimates and C(0) therefore has polynomial bit length. Ordinary integer arithmetic on these bounded operands, including the output operation, has polynomial cost.

Finally, every outer loop has its displayed deterministic cap, and the evaluation subroutine itself has bounded loops and finite bit draws. Initialization and counter updates add at most polynomially many operations on the bounded integers just described. No part of this resource argument conditions on empirical accuracy, on successful coupling, or on survival of a restart. An abort outputs the rational zero; otherwise all estimates are positive rationals. This proves the claim on every execution.□

Proof of Theorem 1.1. For an infeasible input the preliminary deterministic test returns zero on every execution, as required. Suppose that the input is feasible.

First let p\geq 1. Combine Proposition 7.2 with Lemma 7.3. Except on an event of probability at most 1/50+10J_*\xi, there is no abort, reference and implemented paths agree, and every positive observation differs from its reference counterpart by a factor between \exp(-4\xi) and \exp(4\xi). The same bounds hold for sums of these positive observations. Since type counts agree exactly, each implemented ratio estimate differs from its reference ratio by at most that same logarithmic amount. The implemented output \widehat Z consequently satisfies

The failure bound is less than 1/4, since 10J_*\xi=\eta/100.

Proposition 2.2 gives

Together with (73), this implies the desired relative inequalities. Indeed, e^{-\epsilon/16}\geq 1-\epsilon/16, and for 0<\epsilon<1,

Thus a single implemented run succeeds with probability greater than 3/4.

The case p=1 is already included in this argument. The enlarged state space then consists of the two transversals, the defect-type family and multiplier updates are empty, and \pi(\mathcal A)=1. Only the type-zero indicator and G_j are observed. All denominators and time bounds used above remain defined.

If p=0, there is a single small-count profile and C(H)=h_H(\varnothing). The call specified at the start of this section returns a positive rational satisfying

with probability at least 15/16. The contamination bound again places this interval inside [(1-\epsilon)Z,(1+\epsilon)Z]. The evaluation procedure covers zero free coordinates as well, in which case its sum and bin space each have one element. This branch invokes none of the p-dependent chain parameters and has the same required polynomial bit bound.

It remains to obtain the requested failure probability. Put

run the appropriate constant-success algorithm independently R times, and return the median of its nonnegative rational outputs. Let F be the number of runs outside the desired relative interval. Independence and the single-run failure bound 1/4 give

A bad median requires at least half the runs to fail, so

The middle inequality follows, for example, from (5/(4\sqrt2))^{10}<1/2.

Lemma 7.3, or Proposition 6.1 for p=0, bounds the work and output length of every run by one fixed polynomial in L,\epsilon^{-1}. The number of repetitions is O(\log(\delta^{-1})); exact comparisons and median selection on their polynomial-length rational outputs also have polynomial bit cost. Ceilings of binary logarithms used for the parameters and bit counts are computable by integer shifts and comparisons. All randomness in the implemented procedure consists of independent unbiased bits. Partition functions, defect totals away from parameter zero, proof-only conditioning trees, and transport flows are never queried or enumerated. The only weight evaluation used is the bounded procedure proved in Proposition 6.1. This establishes a uniform FPRAS with the stated bound on every execution.□

Proof. The flow-to-table bijection. If some \ell_e>u_e, or if \sum_v\beta_v\ne0, the flow set is empty; return zero for counting and report infeasibility for sampling. The second test is necessary because every arc cancels in the sum of the balance equations. If V=E=\varnothing, there is one empty flow, which can be counted and returned directly. In all other cases, shift the lower bounds by putting

Then 0\le x_e\le c_e and the new balance is \beta'_v.

For each original arc e=(u,v) introduce a private new vertex w_e and replace the arc by u\to w_e\to v, giving both arcs cap c_e and giving w_e balance zero. The two arc values must agree at w_e, so this is a bijection on flows, including when u=v. The private vertices make all subdivided arc cells distinct and off-diagonal, also for parallel arcs. Write W=V\cup\{w_e:e\in E\} and E' for the subdivided vertices and arcs, and let c_a be the inherited cap of a\in E'. Extend \beta' by zero at the new vertices. For q=|W|=|V|+|E|>0, put

where h^+=\max\{h,0\} and h^-=\max\{-h,0\}. Index a q\times q table by W in both coordinates, use row margins R and column margins C, and set

The cases are disjoint, and the margin totals agree because \sum_w\beta'_w=0.

Given a subdivided flow z, put its arc values in the arc cells. At vertex w the unique possible diagonal entry is

It is nonnegative since K dominates every incident capacity sum. If \beta'_w\ge0, then y_w=K-\operatorname{in}_w(z); if \beta'_w\le0, then y_w=K-\operatorname{out}_w(z). Thus y_w\le K, so the table is feasible. Conversely, subtracting a table’s column equation from its row equation gives the subdivided balance at every vertex. The private-vertex balances equate the two copies of each original arc, and the diagonal entries are forced by the displayed formula. Adding back \ell gives the unique original flow. This proves a bijection with \Omega(R,C,b).

The table has q^2 explicitly written caps. Its parameters are sums and differences of polynomially many binary integers, so their bit lengths and the total table-data length L_{\mathrm{tab}} are polynomial in the network-data length. Both directions of the bijection use only polynomially many operations on such integers; no capacity is expanded in unary. The deterministic feasibility test in Section 2 handles all remaining infeasibility, including edgeless and zero-capacity cases. If the table is infeasible, return zero for counting and report infeasibility for sampling. Otherwise Theorem 1.1 on the table gives the counting assertion with the stated bit bound.

Sampling by conditional counts. We use the self-reduction principle connecting approximate counting and almost-uniform generation [18, Theorem 6.3], implemented here by bisecting binary cell intervals. The argument below gives the required feasibility, total-variation, and bounded-bit guarantees.

After this root feasibility test, write \Omega(r,c,b)=\Omega(R,C,b) for the constructed feasible table set and initialize each cell interval to [0,b_{ij}]. At a reached node, let [a_{ij},d_{ij}]\subseteq[0,b_{ij}] be the current integer interval for cell (i,j). Shifting X_{ij} by a_{ij} is a bijection to a bounded-table instance with

Reject negative residual data before applying the feasibility test. Process the cells in a fixed order. For a nonsingleton interval [a,d], put m=\lfloor(a+d)/2\rfloor and use the disjoint children [a,m] and [m+1,d], continuing until every interval is a singleton. A path has at most

decisions, and every conditioned input has polynomial binary length. If D=0, the already-tested feasible table is unique and is returned directly. No assumption that attainable cell values form an interval is used.

At a reached node, test both children for feasibility. Their feasible sets partition the parent’s feasible set, so at least one is feasible. If exactly one is feasible, take it. If both are feasible, let their positive counts be N_0,N_1 and call Theorem 1.1 separately on the two child instances with relative error \eta and failure probability \gamma, using fresh independent bits. Write the nonnegative outputs as \widehat N_0,\widehat N_1. If their sum is zero, take child zero, which is known to be feasible. Otherwise put \widehat p=\widehat N_0/(\widehat N_0+\widehat N_1). Using t further fresh bits, draw U uniformly from \{0,\ldots,2^t-1\} and take child zero exactly when U<\lfloor2^t\widehat p\rfloor. This implements probability p_t=2^{-t}\lfloor2^t\widehat p\rfloor, with |p_t-\widehat p|\le2^{-t}, in bounded bit time. In particular, a zero estimate is never used as an infeasibility certificate, and every reached child is feasible.

For exact counts the branch probability is p=N_0/(N_0+N_1), and these exact conditional probabilities telescope to the uniform law on feasible singleton leaves. On successful estimates, write \widehat N_i=N_i(1+e_i) with |e_i|\le\eta. Then

At each reached history, the fresh count calls fail with probability at most 2\gamma in total. Averaging over them and the fresh branch bits, the conditional total-variation error of the implemented branch choice relative to the exact one is therefore at most

This bound also covers the zero-sum fallback; a one-feasible-child node has zero error. Couple the two branch choices whenever their prefixes agree. The probability of any mismatch is at most Da, so the output total-variation distance from the uniform table law is at most Da. This averages failures at each adaptive history, without conditioning on a path-dependent event that all count calls succeed.

Set D_+=\max\{1,D\} and choose

Since \eta<1/2, the preceding bound gives Da\le\tau/2\le\tau. There are at most 2D count calls and 2D+1 feasibility tests. Their input lengths are polynomial in L, including the binary encoding of \tau, while \eta^{-1}=8D_+/\tau and \log(\gamma^{-1})=\log(8D_+/\tau). Theorem 1.1 bounds both the work and the output lengths of every count call, including failed ones. Thus exact ratio arithmetic and the t-bit threshold draw also have polynomial cost on every execution; the ceiling defining t is computable by integer shifts and comparisons. The inverse bijection returns a feasible flow and preserves the total-variation distance. This proves the sampling and runtime assertions.□