1 · The essentials
A contingency table is a grid of nonnegative whole numbers whose row totals and column totals are specified in advance. These manuscripts study how to choose such a grid at random and how to estimate how many grids satisfy the requirements. The main manuscript gives a method that, when valid grids exist, selects each one with exactly the same chance. It finishes with probability one, and its average computing cost is bounded by a polynomial in the grid dimensions and the length of the totals written in binary. The repository also reports a method with nearly equal selection chances whose computing cost is polynomial on every run. A companion manuscript gives a randomized way to estimate the number of valid grids even when each cell has its own bound, including cells forced to be zero. The main result has a Lean formalization, although the supplied text does not specify exactly which claims that formalization covers.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine filling a seating chart with numbers of guests while keeping every row total and column total fixed. Sampling means choosing fairly among all valid charts, while counting means estimating how many valid charts there are; extra cell bounds can forbid guests in particular positions.
Why it matters
The guarantees cover varying grid dimensions and totals encoded in binary, rather than requiring small numerical totals or a fixed grid size. The main sampling result needs no positivity, balance, or sparsity assumption. The counting result also accommodates individual cell restrictions, including structural zeros.
2 · Going further
The objects are nonnegative integer matrices with prescribed margins: and . Exact uniform sampling asks for every feasible matrix to have the same output probability. The main manuscript states that its sampler terminates almost surely and has expected bit complexity polynomial in both dimensions and the binary length of the margins, without positivity, balance, sparsity, or fixed-dimension assumptions.
The repository summary distinguishes two sampling guarantees. Exact uniform sampling has an expected polynomial bit-time bound, whereas almost-uniform sampling has a worst-case polynomial bit-time bound. An expected bound controls average cost; it is not a polynomial bound on every execution. The supplied abstracts do not describe the algorithmic construction or the main idea of its argument, so no particular sampling mechanism can be identified from this source.
The companion manuscript addresses counting rather than sampling, with individual entry bounds added to the margin constraints. It states a fully polynomial randomized approximation scheme (FPRAS), allowing both dimensions to vary, all numerical data to be binary-encoded, and zero bounds. Its algorithm uses only unbiased random bits and has a polynomial bound on bit operations on every execution. The source places these manuscripts in the same family but does not specify a reduction or other technical dependency between them.
Useful notions
- Nonnegative integer matrices
- Row and column sums
- Binary encoding and input length
- Uniform random sampling
- Expected versus worst-case running time
- Randomized approximate counting
What was known before / what is new
Before
The source sets out the sampling and counting problems for matrices with prescribed margins. It does not provide a history of earlier algorithms, prior complexity bounds, or a named open problem, so it does not support a more detailed before-and-after comparison.
New
The main manuscript presents exact uniform sampling for arbitrary margins with almost-sure termination and expected polynomial bit complexity. The repository additionally reports almost-uniform sampling with worst-case polynomial bit complexity. The companion manuscript presents an FPRAS for counting tables with individual cell bounds, including structural zeros, with polynomial bit cost on every execution.
Limits and assumptions
The objects are nonnegative integer matrices with prescribed row and column sums; sampling presupposes a nonempty set of valid tables. Exact sampling has an expected polynomial cost guarantee, not a stated polynomial bound on every run. The counting guarantee is randomized and approximate, not exact counting. The main result has a Lean formalization, but the supplied source does not identify its precise coverage, so formal verification cannot be attributed here to every sampling or counting claim. The abstracts omit algorithmic details, quantitative approximation parameters, and any statement of remaining open problems.
Mini glossary
- Contingency table —
- A matrix of nonnegative integers with prescribed row and column sums.
- Margins —
- The prescribed totals of the rows and columns.
- Exact uniform sampling —
- Random selection that gives every valid table the same probability.
- Bit complexity —
- Computing cost measured in operations on bits, with numerical input size measured through its binary encoding.
- Structural zero —
- A cell required by its bound to contain zero.
- FPRAS —
- A fully polynomial randomized approximation scheme, here used to estimate the number of valid tables.
Keywords : Contingency tables · Uniform sampling · Randomized approximate counting
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
For nonnegative integer matrices with prescribed row and column sums, gives exact uniform sampling in expected polynomial bit time and almost-uniform sampling in worst-case polynomial bit time. The dimensions and binary-encoded margins are unrestricted. Also gives a fully polynomial randomized approximation scheme for counting such tables with arbitrary individual cell bounds, including structural zeros, with polynomial cost on every execution.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Exact Uniform Sampling of Contingency Tables with Arbitrary Margins
24/09/2026We give an exact uniform sampler for nonnegative integer contingency tables with arbitrary prescribed margins. It terminates almost surely and has expected bit complexity polynomial in both dimensions and the binary length of the margins. No positivity, balance, sparsity, or fixed-dimension assumption is required.
An FPRAS for Cell-Bounded Contingency Tables
24/09/2026We give a fully polynomial randomized approximation scheme for counting nonnegative integer matrices with prescribed row sums, column sums, and individual entry bounds. Both dimensions vary, all numerical data are encoded in binary, and zero bounds are allowed. The algorithm uses only unbiased random bits and has a polynomial bound on its bit operations on every execution.