  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.
