Polynomial-time counting and sampling of two-rowed contingency tables

In this paper a Markov chain for contingency tables with two rows is define d. The chain is shown to be rapidly mixing using the path coupling method. We prove an upper bound for the mixing time of the chain. The upper bound i s quadratic in the number of columns and linear in the logarithm of the tab le sum. By considering a specific problem, we prove a lower bound for the m ixing time of the chain. The lower bound is quadratic in the number of colu mns and linear in the logarithm of the number of columns. A fully polynomia l randomised approximation scheme for this problem is described. (C) 2000 P ublished by Elsevier Science B.V. All rights reserved.