ON SAMPLING WITH MARKOV-CHAINS

In this paper, we apply some recent eigenvalue bounds based on heat ke rnel estimates to provide polynomial bounds on Markov chain approaches to a number of sampling problems. In particular, for the space S of m by n contingency tables (which are arrays of non-negative integers ha ving fixed row and column sums), we give the first bounds on the mixin g time for the natural walk on S which is polynomial in m, n and the r ow and column sums, provided the minimum row and column sums are large enough.