Linear-time uniform generation of random sparse contingency tables with specified marginals

DOI10.1214/23-AAP2013MaRDI QIDQ6590451FDO

Authors Andrii Arman, Pu Gao, Nicholas Wormald

Publication date 21 August 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

zbMATH Keywords

contingency tablesrejection samplingrandomized generation algorithms

Mathematics Subject Classification ID

Contingency tables (62H17) Random matrices (probabilistic aspects) (60B20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• Improved bounds for sampling contingency tables
• Random generation of 2�n contingency tables
• An approximation algorithm for counting contingency tables
• Sampling contingency tables
• Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3654183 (Why is no real title available?)
• scientific article; zbMATH DE number 638138 (Why is no real title available?)
• scientific article; zbMATH DE number 1089130 (Why is no real title available?)
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A sequential algorithm for generating random graphs
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• An efficient MCMC algorithm to sample binary matrices with fixed marginals
• Approximate counting by dynamic programming
• Counting the 10-point graphs by partition
• Efficient importance sampling for binary contingency tables
• Exact sampling and counting for fixed-margin matrices
• Fast uniform generation of random graphs with given degree sequences
• Fast uniform generation of regular graphs
• Generating Random Regular Graphs Quickly
• Generating random regular graphs
• Improved bounds for sampling contingency tables
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On sampling with Markov chains
• Polynomial-time counting and sampling of two-rowed contingency tables
• Random generation of 2�n contingency tables
• Random generation of combinatorial structures from a uniform distribution
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Sampling Regular Graphs and a Peer-to-Peer Network
• Sampling contingency tables
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Statistical Analysis of Contingency Tables
• The switch Markov chain for sampling irregular graphs (extended abstract)
• Uniform generation of random graphs with power-law degree sequences
• Uniform generation of random regular graphs
• Uniform generation of random regular graphs of moderate degree

This page was built for publication: Linear-time uniform generation of random sparse contingency tables with specified marginals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6590451)