We give an algorithm that generates a uniformly random contingency table with specified marginals, i.e. a matrix with non-negative 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.
翻译:我们给出一种算法, 生成一个单一随机的应急表, 包含指定的边际, 即一个带有非负整数的矩阵, 以及指定的行和列总和。 这种算法在统计和组合分析中有用。 当$\ Delta4 < M/5$, 其中$\ Delta$是行和列总和, 和$M$是矩阵所有条目的总和时线, 我们的算法在预期中以美元为线性运行。 这个问题的多数先前公布的算法都是基于Markov 链 Monte Carlo 的大致样本, 其混合时间的可辨别界限一般是相当大的多数值 。