DIMACS Princeton Theory Seminar


Factoring Graphs to Bound Mixing Rates


Dana Randall


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:00 PM (Lunch will be served at 11:45 AM)
Wednesday, May 1, 1996


Consider the following Markov chain whose state space is the set of all proper three-colorings of a rectangular lattice region. Start >from an arbitrary three-coloring. Then randomly choose a vertex v and a color c and recolor v with color c if possible. Repeat this many times. This process is used in practice to study combinatorial properties of the set of three-colorings and provides insight into statistical mechanics models related to ice and antiferromagnetism. However, although it is straightforward to show that the stationary distribution of the Markov chain is uniform, it is not known how many steps are required in order to generate good samples.

In this talk we present a technique for analyzing the convergence rate of a closely related Markov chain, thereby providing the first provably efficient algorithm for generating random three-colorings of these regions. The proof relies on a general "factorization technique" for proving that a Markov chain is rapidly mixing. First, we decompose the state space into a small number of overlapping pieces. We then show that if a Markov chain is rapidly mixing when restricted to each of the pieces, and if the pieces are sufficiently well connected, then the Markov chain is rapidly mixing on the entire state space. This factorization theorem allows us to apply coupling techniques developed for other planar lattice problems [Luby, Randall, Sinclair] in order to show that the three-coloring Markov chain is rapidly mixing.

As a second application, we present a related factorization theorem which addresses the mixing rate of a Markov chain defined by the Metropolis algorithm. This theorem has been applied to a type of simulated tempering known as umbrella sampling [Madras and Piccioni]. Intuitively, simulated tempering augments a state space with a parameter representing temperature and then allows the temperature to also vary randomly during the simulation.

This is joint work with Neal Madras.

Document last modified on April 25, 1996