ACO Home Page   Admission Information Program Description Affiliated Faculty Students Alumni Research Program ACO News ACO Events ACO Internal   Georgia Tech College of Computing School of Ind. Sys. Eng. School of Mathematics School of Electrical Eng.   Help Advanced Search   Contact WEBmaster

Sam Greenberg

Title: Random Sampling of Lattice Configurations Using Local Markov Chains

Time:	Wednesday, July 2nd, 2:00pm
Location:	KACB 2100
Advisor:	Prof. Dana Randall
Committee:	Prof. Christine Heitsch, School of Mathematics
	Prof. Milena Mihail, College of Computing
	Prof. Dana Randall, College of Computing
	Prof. Tom Trotter, School of Mathematics
	Prof. Eric Vigoda, College of Computing
Reader:	Prof. Eric Vigoda, College of Computing

Abstract:

Algorithms based on Markov chains are ubiquitous across scientific disciplines, as they provide a method for extracting statistical information about large, complicated systems. Although these algorithms may be applied to arbitrary graphs, many physical applications are more naturally studied under the restriction to regular lattices. We study several local Markov chains on lattices, exploring how small changes to some parameters can greatly influence efficiency of the algorithms.

We begin by examining a natural Markov Chain that arises in the context of self-assembly, where tiles tiles attach and detach from a large substrate, but with a greater rate of association than disassociation. We show that this chain is rapidly mixing (converges quickly to the equilibrium) using a coupling argument; the novelty of our proof is that it requires defining an exponentially increasing distance function on pairs of tilings, allowing us to derive near optimal results in many settings.

Next, we present new methods for lower bounding the time local chains may take to converge to equilibrium. For many models that we study, there seems to be a phase transition as a parameter is changed, so that the chain is rapidly mixing above a critical point and slow mixing below it. Unfortunately, it is not always possible to make this intuition rigorous. We present the first proofs of slow mixing for three sampling problems motivated by statistical physics and nanotechnology: independent sets on the triangular lattice (the hard-core lattice gas model), weighted even orientations of the two-dimensional Cartesian lattice (the 8-vertex model), and non-saturated Ising (tile-based self-assembly). Previous proofs of slow mixing for other models have been based on contour arguments that allow us prove that a bottleneck in the state space constricts the mixing. The standard contour arguments do not seem to apply to these problems, so we modify this approach by introducing the notion of "fat contours" that can have nontrivial area. We use these to prove that the local chains defined for these models are slow mixing.

Finally, we study another important issue that arises in the context of phase transitions in physical systems, namely how the boundary of a lattice can affect the efficiency of the Markov chain. We define a local chain for Ising and near-Ising configurations on the Cartesian lattice and show for one boundary condition it will mix in polynomial time, while for another it will mix exponentially slowly. We show an analogous result for a chain on matchings of the square-octagon lattice, where, strikingly, the two boundary conditions only differ at only four vertices. These are the first rigorous proofs of this phenomenon on lattice graphs.

<Plain-Text Page>  (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: June 30, 2008 Georgia Tech Disclaimer: Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.