Browse › Theoretical computer science › 115 Sampling and counting contingency tables with arbitrary margins
Exact Uniform Sampling of Contingency Tables with Arbitrary Margins
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We 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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- EcoDataLab, contingency-tables: Open research on bounded contingency tables (GitHub repository, October 2026). Describes itself as auditing and improving OpenAI result #115, including a separate Lean development (1511 named declarations) with a bounded sampler of total variation at most $2^{-h}$; it notes that "the source claim of exact expected-polynomial sampling concerns ordinary tables" and does not transfer it to the cell-bounded setting. [AI-generated per source] [family-level]
Formalization
- OpenAI math release, Sampling and counting contingency tables with arbitrary margins: Lean scope note (lean/docs/115.md, 2026). The release's scope statement: the exact sampler terminates almost surely, outputs feasible tables, and gives each table exactly the uniform limiting probability; it also covers the bounded-time $2^{-k}$ total-variation sampler and the companion cell-bounded FPRAS, all in the shared Comparator file
ContingencyTables.lean. [AI-generated per source] [family-level]
Related prior literature mentioned by others
- Cryan, Dyer, Randall, Approximately Counting Integral Flows and Cell-Bounded Contingency Tables (SIAM J. Comput. 39 (2010)). Cited in third-party listings of this family as the source naming unrestricted cell-bounded counting as open; it is cited in the companion FPRAS paper but not in this one. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Miller, Harrison, Exact Enumeration and Sampling of Matrices with Specified Margins (arXiv:1104.0323, 2011). A dynamic-programming exact counter and exactly uniform sampler for integer and binary matrices with given margins, polynomial when column sums are bounded; a point of comparison for the paper's unconditional exact uniform sampler (Theorem 1.1(ii)).
Digests and expositions
- Latent Seminar, Contingency tables: exact sampling and relative counting (Latent Seminar, 2026-10-07). Explains the sampling manuscript's rare residual correction and the counting manuscript's forest coordinates and multiplicity corrections, stating that it reviews selected sections rather than independently verifying the full proofs. [family-level]
News and blogs
- Sean Moran, What OpenAI’s 719 Maths Papers Mean for Data Science (Towards AI, 2026-10-11). The section on random tables discusses this manuscript's uniform fixed-margin sampling claim, distinguishes its distribution from record shuffling, and notes the implementation work needed to assess practical running time.
Elsewhere
- Emergent Mind: family 115
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026,
author = {{OpenAI}},
title = {{Exact Uniform Sampling of Contingency Tables with Arbitrary Margins}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026/main.pdf}{OAI:Exact-Uniform-Sampling-of-Contingency-Tables-with-Arbitrary-Margins-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/115.md. The Lean statements have not been checked by people against the paper's claims.
Family 115: Sampling and counting contingency tables with arbitrary margins
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.
Other papers in this family:
- An FPRAS for Cell-Bounded Contingency Tables · September 24, 2026