11/24/97 - Mark Huber
Cornell University
Exact Sampling and Approximate Counting Techniques

One popular method for random sampling is to construct a Markov chain that has the desired distribution as its stationary distribution, and then run the Markov chain for "a long time". This method only gives an approximate sample, since the chain will never be exactly in the stationary distribution. Recently, methods such as coupling from the past (CFTP) have been developed that allow for exact sampling from the stationary distribution of Markov chains, but CFTP only applies to certain classes of chains. We use the CFTP methodology to develop the first polynomial time exact sampling algorithms for finding proper $k$-colorings and sink-free orientations of a graph. Counting the number of $k$-colorings of a graph is a #P-complete problem, but Jerrum showed how to turn a sampling algorithm for this problem into an approximate counting algorithm. We present a method for approximately counting $k$-colorings which improves upon the running time of Jerrum's method by a factor of (m/n)^2.