Show simple item record

dc.contributor.authorGreenberg, Samen_US
dc.date.accessioned2009-06-08T18:43:31Z
dc.date.available2009-06-08T18:43:31Z
dc.date.issued2008-12-01en_US
dc.identifier.urihttp://hdl.handle.net/1853/28090
dc.description.abstractAlgorithms 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 "monotonic surfaces", where some point on a surface is sightly raised or lowered each step, but with a greater rate of raising than lowering. 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 surfaces, 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 examine a local chain on the perfect and near-perfect matchings of the square-octagon lattice, and show for one boundary condition the chain will mix in polynomial time, while for another it will mix exponentially slowly. Strikingly, the two boundary conditions only differ at four vertices. These are the first rigorous proofs of such a phenomenon on lattice graphs.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectMarkov chainen_US
dc.subjectLatticeen_US
dc.subjectTheoryen_US
dc.subjectRandom samplingen_US
dc.subject.lcshSampling (Statistics)
dc.subject.lcshLattice theory
dc.subject.lcshMarkov processes
dc.titleRandom sampling of lattice configurations using local Markov chainsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Randall, Dana; Committee Member: Heitsch, Christine; Committee Member: Mihail, Milena; Committee Member: Trotter, Tom; Committee Member: Vigoda, Ericen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record