# DIMACS Princeton Theory Seminar

## Title:

Factoring Graphs to Bound Mixing Rates

## Speaker:

- Dana Randall
- Princeton

## Place:

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

## Time:

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

## Abstract:

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.

dimacs-www@dimacs.rutgers.edu
Document last modified on April 25, 1996