Contingency tables: exact sampling and relative counting

Source and verification

This article explains family 115 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Fixed margins and the uniform law

A contingency table is a nonnegative integer matrix with prescribed row sums $r_i$ and column sums $c_j$, where both margin vectors have the same total $N$. Let $\Omega (r,c)$ be the finite set of all such tables. The uniform law assigns each matrix one unit of counting weight, independent of how its entries might be represented by labeled objects.

Both dimensions vary, and margins are encoded in binary. A runtime polynomial in $N$ can be exponential in the input length. Without cell bounds, equal nonnegative totals guarantee feasibility: repeatedly send as much as possible between a row and column with remaining positive margins, removing each exhausted margin.

For two probability laws on a finite space, total variation distance is

$$\mathrm{TV}(\mu ,\nu )=\frac{1}{2}\sum _x|\mu (x)-\nu (x)|.$$

It bounds the difference in probability of every event, including each individual table.

🏷️ Two sampling guarantees with different time bounds

Sampling manuscript statement

For arbitrary margins of equal total, one algorithm returns a feasible table within $2^{-k}$ total variation of uniform in time polynomial in the dimensions, $\log (N+1)$, and the requested accuracy bits $k\ge 1$.

A second algorithm returns an exactly uniform table, terminates almost surely, and has polynomial expected bit complexity in the dimensions and $\log (N+1)$. It may perform exhaustive computation on a very rare branch. (OpenAI, 2026)

The first algorithm has a work bound on every run. The second does not. Both use unbiased random bits, with no fixed-row, balance, sparsity, or large-margin hypothesis.

For example, row and column margins $(2,2)$ permit exactly the three tables

$$\begin{array}{c}\left(\begin{array}{cc}a& 2-a\\ 2-a& a\end{array}\right),\\ a\in \{0,1,2\}.\end{array}$$

An exact uniform sampler must assign probability $1/3$ to each. A fair-bit algorithm using at most a fixed number $B$ of bits has output probabilities that are multiples of $2^{-B}$, after padding early halts. It cannot produce this law exactly. Unbounded but almost-surely finite execution, as in rejection sampling, naturally permits the denominator three.

🏷️ Small explicit cells and large completion rectangles

The approximate sampler explicitly represents only cells incident to small margins, below a polynomial threshold. The remaining cells form a complete rectangle. Padding makes every conditional completion problem for that rectangle a large-margin problem.

Each small cell temporarily has two views, one for its row and one for its column. Agreement gives a transversal state; the auxiliary chain also permits one positive and one negative unit discrepancy. A small state’s ideal weight is the number of its padded completions.

If a state with $C_s$ completions is selected with probability $C_s/{\sum }_u{C}_u$, and then one completion is chosen uniformly, each state/completion pair has probability

$$\frac{C_s}{{\sum }_u{C}_u}\cdot \frac{1}{C_s}=\frac{1}{{\sum }_u{C}_u}.$$

Accepting a transversal whose large entries permit removal of the padding therefore produces the uniform original law after unpadding. The source proves a repair bound controlling defect mass and acceptance probability.

This calculation describes the target distribution. The implemented sampler does not evaluate exact completion counts: ideal transition probabilities are realized through completion draws, which are then approximated and coupled to finite-bit routines.

🏷️ Conditional transport and bounded computation

Expose the small-cell values of a transversal in a fixed order. After fixing a prefix, compare the conditional fibers for adjacent values of the next cell. Quadratic forms indexed by pairs of unit removals have at most one positive eigenvalue, and the manuscript proves that this property survives its required balanced summations.

A weighted telescoping calculation turns those forms into an energy bound for signed transport between neighboring fibers. Conditional-variance decomposition and repair then give a Poincaré inequality and a polynomial mixing estimate for the small-state law.

Dense completions are implemented on scaled finite grids with rational arithmetic and dyadic choices. A continuous log-concave density enters the conductance and rejection analysis, but large coordinate ranges are not exhaustively enumerated in an ordinary run. Bounds on attempts and explicit fallbacks ensure every run of the approximate algorithm finishes within its polynomial cap.

🏷️ Exact correction by a rare residual law

The exact sampler requires more than closeness in total variation. The source also proves that the actual implemented approximate law, including all stopping rules and fallbacks, can be tabulated with an exponential input-size factor but only polynomial dependence on the requested accuracy bits.

Here is the finite probability identity behind the correction. Let $M=|\Omega |$, let $U(z)=1/M$, and choose a dyadic $0<\delta <1$ with $M\delta \le 1$. If the implemented approximate law $p$ has total variation error at most ${\delta }^2$, then

$$\begin{array}{rl}(1-\delta )p(z)& \le (1-\delta )(1/M+{\delta }^2)\\ & \le 1/M.\end{array}$$

Thus

$$q(z)=\frac{U(z)-(1-\delta )p(z)}{\delta }$$

is nonnegative and sums to one. Run the approximate sampler with probability $1-\delta$, and sample this residual law with probability $\delta$. The mixture is exactly $U$.

The rare branch enumerates the tables, tabulates $p$, and forms exact integer weights for $q$. A uniform integer below a given bound is drawn by fair-bit rejection; its acceptance probability is greater than one half. The resulting draw is exact and terminates almost surely.

If the exhaustive cost is at most $2^{P(L)}$ times a polynomial in accuracy, choosing $\delta$ sufficiently smaller than $2^{-P(L)}$ can keep its expected contribution polynomial. This works here because the ordinary sampler depends polynomially on the number of accuracy bits, and law tabulation has the stated separate dependence. A generic approximate sampler with an unknown or much more expensive output law would not justify this conversion.

🏷️ Counting with individual cell bounds

The second manuscript allows upper bounds $X_{ij}\le b_{ij}$, including zero bounds that forbid cells. Write $Z(r,c,b)$ for the number of feasible tables, counting each once.

Cell-bounded counting claim

One uniform randomized bit algorithm returns a nonnegative relative-$\epsilon$ estimate of $Z(r,c,b)$ with probability at least $1-\delta$. It returns zero on every execution when the feasible set is empty, and has polynomial worst-case work in the encoded input length, ${\epsilon }^{-1}$, and $\log ({\delta }^{-1})$. No counting or sampling oracle is supplied. (OpenAI, 2026a)

This is an FPRAS, not an assertion that the exact expected-time sampler above handles arbitrary forbidden positions. The unbounded-cell sampling theorem and cell-bounded counting theorem have different formulations.

🏷️ Forest coordinates and multiplicity corrections

Flow feasibility tightens each cell to its attainable interval. Subtracting its minimum produces a range $[0,b_s]$ with both endpoints attainable. Large-range cells form a bipartite graph; a maximum-capacity spanning forest expresses its tree entries through free nonforest entries and margin equations. Root-margin discrepancies and violated tree bounds receive soft penalties.

For a small cell, use counts $x_s,y_s$ with row contribution $x_s$ and column contribution $b_s-y_s$. Agreement means $x_s+y_s=b_s$. At an annealing stage $j$, a completion weight $h_j(x,y)$ sums penalized contributions of free large entries. The starting total is explicit, while the final total differs from the feasible count by a controlled small relative contamination.

Representing a small cell of bound $b_s$ by $b_s$ labeled pairs creates $\left(\genfrac{}{}{0ex}{}{b_s}{x_s}\right)$ transversals with the same occupancy. Assign each weight

$$\frac{h_j(x,y)}{{\prod }_s\left(\genfrac{}{}{0ex}{}{b_s}{x_s}\right)}$$

to restore exactly $h_j(x,y)$ per profile. Only small ranges are expanded. Two factorial formulas extend these weights to defect states: one supplies omission inequalities for transport, the other addition inequalities for defect masses. They agree on transversals and are polynomially comparable on the permitted defects.

The chain learns type multipliers and adjacent annealing ratios. Its trace on transversals mixes rapidly; separate variance bounds control the observables actually estimated. Approximate weight evaluations use bins corrected for their different numbers of integer points. Caps and fresh-error coupling account for every adaptive numerical request, including runs on which an estimate fails.

🏷️ Key steps and proof outlines

Coupling a bounded sampler without conditioning away errors

The approximate algorithm has finite caps on its chain length, completion attempts and outer trials. Its analysis couples the implemented finite-bit chain to an ideal chain, charging each transition discrepancy before any success conditioning. If a step can disagree with probability at most $\eta$ and at most $T$ steps occur, a union bound gives discrepancy at most $T\eta$. A deterministic map from the final state to an output cannot increase total variation.

This is why fallback behavior belongs in the law being analyzed. Replacing the actual law by its conditional law given “all subroutines succeeded” would introduce a normalization by a possibly small success probability. The source’s algorithm section instead adds mixing, finite-bit and all-failed-trial errors directly, with explicit caps chosen so their sum is below the requested tolerance. (OpenAI, 2026b)

Exact law tabulation sums states, not random tapes

The rare correction requires knowing the actual approximate output law. Enumerating all random-bit strings would be far too expensive as precision increases. The key structural fact is that only the small state persists between transitions. Completion randomness is fresh, so one can tabulate its output law separately for each small state, form a finite transition matrix $Q$, and propagate distributions by $v_{t+1}=v_{t}Q$.

If each transition has dyadic denominator $2^q$, the law after $t$ steps has denominator dividing $2^{tq}$. Adding many paths changes numerator sizes but does not multiply denominator exponents by the number of paths. The enumerated state spaces depend on the input dimensions and margin bit lengths, while accuracy increases only the number of propagation steps and the lengths of arithmetic registers.

Stopping rules also have exact formulas. If one trial returns output $z$ with unconditional success mass $g(z)$ and fails with probability $f$, then at most $J$ trials followed by a fixed fallback $z_0$ have output law

$$p(z)=g(z)\sum _{j=0}^{J-1}{f}^j+1_{\{z=z_0\}}{f}^J.$$

The finite sum counts success on each possible trial; the last term counts all trials failing. This expression uses no division by $1-f$ and remains valid at $f=1$.

The residual law has nonnegative integer weights

Let the tabulated law be $p(z)=a_z/2^R$, let $M$ be the number of feasible tables, and choose the rare-branch probability $\delta =2^{-D}$. The pointwise domination already proved in the source ensures $(1-\delta )p(z)\le 1/M$. Define

$$n_z=2^{R+D}-M(2^D-1)a_z.$$

These are nonnegative integers, and summing over outputs gives ${\sum }_z{n}_z=M{2}^R$. Sampling proportionally to $n_z$ therefore realizes the exact residual distribution. A uniform integer below $M{2}^R$ is generated by drawing enough fair bits and rejecting integers outside the range; each attempt succeeds with probability greater than one half. The mixture of the common approximate branch and rare residual branch is exactly uniform.

The expected-time calculation is explicit: if tabulation costs $2^{P(L)}\mathrm{poly}(k)$ and the ordinary branch needs accuracy $k=O(D)$, choose $D$ large enough that $2^{-D}{2}^{P(L)}\mathrm{poly}(D)$ is polynomial. This works because $k$ counts accuracy bits. A dependence polynomial in $2^k$ would destroy the argument.

The bounded-table companion keeps a different guarantee

Cell bounds can make the feasible set empty, so the counting companion begins with an exact flow-feasibility check. Its lifted labels must cancel occupancy multiplicities before the target partition function is counted, and its paired defect extensions support the required transport inequalities. Those are the counterparts of the small-state weight and mixing steps above. The output remains a bounded-time relative approximation; it does not use the rare exhaustive residual branch to promise exact counting. The distinction between exact sampling in expectation and relative counting on every tape is part of the theorem, not merely an implementation detail.

See Also

• Common integer bases generalizes the binary-capacity issue and imports the paired factorial corrections developed here.
• Perfect-matching counting provides another example where added states, conditioning, and weighted sampling require distinct accounting.

🏷️ Manuscripts and verification scope

• Exact Uniform Sampling of Contingency Tables with Arbitrary Margins — pinned manuscript and companion source.
• An FPRAS for Cell-Bounded Contingency Tables — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Both links point to the same comparator file, which contains the unbounded-cell exact and bounded-time sampling statements and the separate cell-bounded FPRAS. Expected-time exactness and worst-case-time approximate guarantees remain distinct. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. An FPRAS for Cell-Bounded Contingency Tables.

🐻  OpenAI 2026b. Exact Uniform Sampling of Contingency Tables with Arbitrary Margins.