Paper Info
Title
Convergence rates of Markov chains for some self-assembly and non-saturated Ising models
Abstract
Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.
Year
DOI
Venue
2009
10.1016/j.tcs.2008.12.007
Theor. Comput. Sci.
Keywords
DocType
Volume
empty space,self-assembly model,local Markov chain,self-assembly algorithm,Ising model,complicated system,Sampling algorithm,Self-assembly,non-saturated Ising model,low temperature,Phase transition,convergence rate,Markov chain,high temperature,standard Ising model
Journal
410
Issue
ISSN
Citations 
15
Theoretical Computer Science
3
PageRank 
References 
Authors
0.50
12
2
Name
Order
Citations
PageRank
Sam Greenberg1475.60
Dana Randall2298.15