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.