Sampling and counting contingency tables with arbitrary margins

← All digests

Family 115 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

A table of counts can have many possible interiors while its row and column totals stay fixed. Drawing uniformly from these possibilities is a basic problem in statistics and combinatorics. Family 115 claims algorithms for arbitrary margins and variable dimensions, including exact sampling in expected polynomial time and approximate counting when individual cells have upper bounds.

1. The question

Suppose rows classify objects by one attribute and columns classify them by another. The entry in a cell counts objects with that combination. If only the totals for each attribute are prescribed, how many tables are possible? Can we draw one without favoring some possibilities over others?

Even a two-by-two example illustrates the distributional issue. If all row and column sums equal two, the feasible tables are

$$\begin{pmatrix}0&2\\2&0\end{pmatrix},\qquad \begin{pmatrix}1&1\\1&1\end{pmatrix},\qquad \begin{pmatrix}2&0\\0&2\end{pmatrix}.$$

Uniform sampling gives each table probability one third. Randomly assigning distinguishable objects can instead favor the middle table, because more assignments produce it. Sampling assignments and sampling tables are different tasks.

The manuscripts seek algorithms whose cost is polynomial in the encoded input, even when both dimensions grow and some margins are enormous.

2. Background and essential definitions

Margins and cell bounds

Let $r_1,\ldots,r_m$ be nonnegative integer row sums and $c_1,\ldots,c_n$ nonnegative integer column sums, with common total $N$. A contingency table is a nonnegative integer matrix $X$ satisfying

$$\sum_{j=1}^{n}X_{ij}=r_i,\qquad \sum_{i=1}^{m}X_{ij}=c_j.$$

Ordinary tables impose no additional forbidden positions or cell capacities. A cell-bounded table also satisfies $X_{ij}\le b_{ij}$, for supplied nonnegative integers $b_{ij}$. A zero bound forbids that cell; such a restriction is often called a structural zero.

The margins and bounds are encoded in binary. Polynomial dependence on $N$ would not suffice, since $N$ may be exponential in its bit length. The relevant numerical size is roughly $\log(N+1)$, together with the dimensions and other input data.

Exact and approximate uniformity

If a finite feasible set is $\Omega$, exact uniformity assigns probability $1/|\Omega|$ to every table.

For distributions $\mu,\nu$, total variation distance is

$$d_{\mathrm{TV}}(\mu,\nu)=\frac12\sum_{X\in\Omega}|\mu(X)-\nu(X)|.$$

A distance at most $\eta$ means that probabilities of all events differ by at most $\eta$. It measures the entire output law, rather than an error in one table entry. An approximately uniform sampler can still return a perfectly feasible table every time.

Expected time and bounded time

Expected polynomial time permits rare very long runs as long as their probability-weighted contribution is controlled. A polynomial bound on every execution is stronger and forbids such runs.

This distinction is central here: the exact sampler has an expected-time guarantee, while the approximate sampler has a deterministic cap on work for each accuracy request.

An FPRAS for counting estimates the number of feasible tables within relative error $\varepsilon$, with failure probability at most $\delta$, using time polynomial in input length, $\varepsilon^{-1}$, and $\log(1/\delta)$.

3. Development history and previous partial results

Diaconis and Gangolli’s survey places fixed-margin arrays in a long statistical and combinatorial tradition. Producing one table is easy in the ordinary setting: repeatedly place the smaller of a remaining row and column total into their intersection. This does not make the result uniformly random.

Dyer and Greenhill obtained efficient approximate counting and sampling for arbitrary two-row margins. Kijima and Matsui developed exact uniform sampling for two rows through coupling from the past. Their computation model and dimension restriction are part of those earlier guarantees.

Cryan and Dyer extended approximate counting to any fixed number of rows. Cryan and collaborators proved rapid mixing of suitable local chains in that setting. A polynomial whose exponent depends on a fixed row count does not establish polynomial complexity when both dimensions are inputs.

Another line of work handles dense margins using volumes of transportation polytopes—the real-valued regions defined by the same row and column equations. Morris improved earlier dense-table bounds through expanded regions and rounding. Sparse-margin exact generation also has strong results under quantitative restrictions, including Arman, Gao, and Wormald.

For zero–one cell bounds, the problem becomes counting bipartite subgraphs with prescribed degrees. Permanent approximation methods already cover this important special case. Larger capacities require treating integer multiplicities without expanding a large number into an equally large explicit combinatorial structure.

M2 discusses earlier fixed-row and large-capacity results for capped tables, then claims to remove these restrictions simultaneously. M1 separately strengthens ordinary-table sampling to exact uniformity, using a correction method from Göbel, Liu, Manurangsi, and Pappik.

4. What the new manuscripts claim

M1 considers ordinary tables with arbitrary nonnegative margins of equal total. Both dimensions may vary. For an accuracy parameter $k\ge1$, it claims a sampler whose law is within $2^{-k}$ of uniform and whose running time is polynomial in

$$m,\ n,\ \log(N+1),\ k.$$

Thus the dependence on a requested total-variation tolerance $\eta$ is polynomial in $\log(1/\eta)$. Every output is feasible.

It also claims an exactly uniform sampler that terminates almost surely and has expected bit time polynomial in $m,n,\log(N+1)$. No fixed-dimension, balance, density, or positivity hypothesis is imposed. This exact statement has no input cell bounds or forbidden positions.

M2 claims an FPRAS for cell-bounded tables with arbitrary binary margins and bounds, including structural zeros. It detects an empty feasible set exactly and bounds bit operations on every execution, even when the estimate is inaccurate.

Its consequences include relative counting for integer arc-value vectors in explicitly given directed flow networks with finite integer capacities and prescribed vertex balances. It also gives feasible almost-uniform sampling with polynomial dependence on the inverse total-variation tolerance.

The stronger accuracy dependence and exactness of M1 should not be transferred to M2’s capped-table or flow sampler: their stated guarantees differ.

5. Why the advance matters

Importance: 3/5, provisional. The family would remove broad restrictions from fundamental constrained-counting problems and carefully account for the binary sizes of numerical inputs.

Uniform fixed-margin sampling can support conditional statistical comparisons: one studies how unusual an observed statistic is among tables sharing the same margins. The theorem supplies a mathematical sampling capability; whether the uniform-table model is appropriate for a particular data analysis remains an application-specific choice.

Cell bounds broaden the combinatorial reach to capacities and forbidden combinations. Their connection to integer flows makes the counting result relevant beyond literal row-and-column tables.

The exact sampler is also conceptually interesting because it separates distributional exactness from bounded execution time. Its value is not that every sample is quickly obtained under all circumstances, but that its exact law comes with a polynomial expected bit cost.

6. The main idea

Separate small coordinates from large completions

M1 treats cells incident to small margins explicitly. The remaining cells form a complete rectangle with large margins. Padding that rectangle ensures that each conditional completion problem has a dense structure suitable for geometric sampling methods.

An explicit small cell has two temporary values, representing its row and column contributions. In a balanced state they agree. Auxiliary states allow a positive discrepancy in one cell and a negative discrepancy in another, providing paths through the state space.

The weight of a small-cell state is the number of large-rectangle completions. Sampling according to these weights and then uniformly completing gives equal mass to complete state-and-completion pairs. An acceptance step removes the padding and recovers an original table.

The implemented sampler does not enumerate all completions. The manuscript instead approximates the required draws using scaled grids and rational computations, then controls the accumulated distributional error.

Correct a very accurate law exactly

A sufficiently accurate finite sampler can be mixed with a small correction distribution so that the resulting law is exactly uniform. Most runs use the fast approximate procedure; a very rare branch performs exhaustive work to draw from the remaining probability mass.

Small total-variation error alone is not a license to assert efficient exact correction. M1 establishes additional control of its actual implemented finite output law, including fallbacks and stopping rules. The correction probability is chosen small enough that the expensive branch still contributes only polynomial expected cost.

This is the precise reason the exact theorem has expected, rather than every-execution, polynomial time.

Handle arbitrary cell capacities without expanding them

M2 first tightens every cell to its attainable interval using flow feasibility. In the graph of large cells, a spanning forest lets some entries be determined from the margins once the remaining free entries are specified.

Only cells with polynomially bounded ranges are expanded into labeled binary choices. Since several labeled choices can describe the same table, reciprocal binomial and factorial corrections cancel this multiplicity on the target states.

Large free ranges are treated through weighted completion sums with soft penalties for constraint violations. Annealing strengthens those penalties. A chain with balanced defect types estimates ratios of successive weighted counts, whose product yields the desired approximation.

The paper uses two related weight extensions for different algebraic inequalities. They agree on target states but serve complementary roles in controlling movement and defect masses. This avoids assuming that one convenient weighting automatically supplies every property needed for counting.

7. Scope, limitations, and open questions

Exact uniform sampling is asserted here for ordinary uncapped tables. Arbitrary forbidden cells belong to the separate counting and approximate-sampling result.

The algorithms are asymptotic constructions with deliberately large polynomial exponents. Neither manuscript presents a practical performance benchmark or proves that a familiar local table-switching implementation already satisfies all these guarantees.

The target objects are integer tables or integer flow vectors, each counted once. Distinguishable-object assignments, weighted statistical models, and sampling only polytope vertices are different distributions.

Sharper running times, simpler samplers, and exact sampling with the full capped-table generality are natural further questions beyond the stated family guarantees.

8. Sources and further reading

M1’s first theorem is the key reference for exactness, accuracy-bit dependence, and expected time. M2’s first theorem gives the capped-table count and every-execution bit bound. Their introductions explicitly compare the dimension, capacity, and computational-model assumptions of earlier work.

Source manuscripts

• M1. OpenAI, Exact Uniform Sampling of Contingency Tables with Arbitrary Margins (September 24, 2026).
• M2. OpenAI, An FPRAS for Cell-Bounded Contingency Tables (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.