Sampling and counting contingency tables with arbitrary margins

The explanation

Fill a grid of two rows and three columns with whole numbers, none negative. Each row must add up to 3. Each column must add up to 2. Such a grid is called a contingency table. The required sums are its margins. Exactly 7 tables fit these margins. One has 1, 1, 1 in both rows. Another has 0, 1, 2 on top and 2, 1, 0 below.

Two jobs come with such tables. Counting asks how many tables fit: here, 7. Uniform sampling asks for one table drawn at random, with every table equally likely. Here each would get a chance of 1/7. A third twist adds a cap on single cells, called a cell bound. A cap of 0 forbids a cell outright. Forbid the top-left cell above, and only 2 tables remain. For grids this small, a computer can simply list every table.

Now take a 3-by-3 grid with every margin equal to one million. Each margin takes only 7 digits to write. Yet 125,000,750,001,875,002,250,001 tables fit, about 1.25 × 10^23. Listing them is hopeless. Computer scientists call a method fast when its time grows like a fixed power of the input's length. Here the length counts rows, columns and the digits of the margins, not their size. The papers work in binary digits, but the idea is the same. A bound that grows with the margin total itself would not count as fast.

Earlier work covered special shapes. In 2000, Dyer and Greenhill counted and sampled approximately for tables with two rows. In 2003, Kijima and Matsui gave exactly uniform sampling for two rows. Cryan and Dyer, and Dyer alone, handled any fixed number of rows in 2003. Their time bounds depend on that fixed row count. Dyer, Kannan and Mount in 1997, and Morris in 2002, worked with large margins. Arman, Gao and Wormald in 2021 handled sparse margins under a size condition. Their survey reported that no fast, nearly uniform sampler for arbitrary margins was known.

Cell bounds had their own history. Jerrum, Sinclair and Vigoda in 2004 covered the case where every cap is 0 or 1. In 2010, Cryan, Dyer and Randall handled large caps, or a fixed number of rows. They named the unrestricted case as an open problem.

The one obstacle was mixing. Real margins can be huge in some rows and tiny in others. Huge values cannot be stepped through one unit at a time. Tiny values break the smooth geometry that methods for large margins rely on. The papers split the table along that line. Cells that touch a small margin are handled one at a timeSource 1. The rest form a block of large numbers, treated with geometric tools. In the sampling paper, that block is padded first so every part of it counts as largeSource 1. A draw is kept only when the padding can be removed cleanlySource 2.

The first paper proves two samplers for any margins with matching totals. You choose an accuracy level k. One sampler always finishes within a fixed power of the input length and k. Its output can be slightly unfair, by at most 2^-k in total variationSource 3. Total variation is the largest amount any group of tables can gain or lose in probability. The other sampler is exactly uniform. It stops with probability 1, and its average running time is fastSource 4. A rare branch does slow, exhaustive work, so single runs can take much longerSource 5,Source 6.

The second paper proves an approximate counting scheme with cell bounds, zero caps included. Ask for an error of ε and a failure chance of δ. The estimate then lands within a factor 1 ± ε of the true countSource 7. That happens with probability at least 1 − δ. One fixed power bound limits the work on every run. If no table fits, it returns zero every timeSource 7. Such a scheme is called an FPRAS.

Back in the 3-by-3 grid, each of those 10^23 tables can now get an exactly equal chance. The average cost grows with the number of digits, not with one million. Still, the papers call their power bounds deliberately largeSource 5. These are guarantees about growth, not practical running timesSource 8. Exact counting stays hard: Dyer, Kannan and Mount proved it is #P-complete even for two rows. The exact sampler also does not cover cell boundsSource 9.

How sure is this? A computer proof checker called Lean has checked formal versions of the main statements. They are the exact sampler, the bounded-time sampler and the counting scheme with cell bounds. All three sit in one Comparator challenge file, a fixed reference statement for checking. The counting paper's consequences for network flows are not in the Lean scope note. No specialist review has been published.

What it doesn't show. This does not count tables exactly, and it does not give a practical running time.