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

Andrii Arman, Pu Gao, Nicholas Wormald

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.…