School of Computing
University of Leeds
4pm Tuesday 2nd July 2002
Room 2511, JCMB, King's Buildings
A contingency table is a matrix of natural numbers with given row and column sums. Contingency tables arise naturally in practical statistics, where they are used to tabulate the results of surveys. The problem of determining the "statistical significance" of survey data then motivates the problem of sampling uniformly at random from the state space of contingency tables with the given row and column sums.
The typical method used for randomly sampling contingency tables is the Markov chain Monte Carlo (MCMC) method - the MCMC method involves defining a Markov chain which induces some random changes in a contingency table, to give another contingency table with the same row and column sums. Then the MCMC method of sampling is to start with a fixed contingency table and repeatedly apply the Markov chain to the table for a "large" number of steps, so that the final table generated is a "random" contingency table.
The important question with respect to the MCMC method is "How many steps of the chain must be performed before we have a truly random sample"? The goal is to obtain a Markov chain which will converge to the uniform distribution after a polynomial number of steps. It has been known for some time that a natural Markov chain called the "2-by-2 heat-bath" Markov chain converges in polynomial time, when the table has only two rows.
In my talk I will consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. We prove that the 2-by-2 heat-bath Markov chain converges to the uniform distribution in polynomial time (when the number of rows is constant).
During my talk I will spend quite a bit of time motivating the problem of sampling contingency tables, and describing the 2-by-2 heat-bath chain. I will give a very rough idea of the techniques we use to prove that the chain mixes in polynomial-time (at a high level).