LINEAR-TIME UNIFORM GENERATION OF RANDOM SPARSE CONTINGENCY TABLES WITH SPECIFIED MARGINALS

• 成果类型: Article
• 署名作者: Arman, Andrii; Gao, Pu; Wormald, Nicholas
• 署名单位: University of Manitoba; University of Waterloo; Monash University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP2013
• 发表日期: 2024
• 页码: 2036-2064
• 关键词: random regular graphs; algorithm; selection; number

摘要

We give an algorithm which generates a uniformly random contingency table with specified marginals, that is, a matrix with nonnegative integer values and specified row and column sums. Such algorithms are useful in statistics and combinatorics. When Delta(4) < M/5, where Delta is the maximum of the row and column sums and M is the sum of all entries of the matrix, our algorithm runs in time linear in M in expectation. Most previously published algorithms for this problem are approximate samplers based on Markov chain Monte Carlo, whose provable bounds on the mixing time are typically polynomials with rather large degrees.