Name
Abstract | ||
|---|---|---|
Sampling algorithms based on Markov chains arise in many areas of computing, engineering and science. The idea is to perform a random walk among the elements of a large state space so that samples chosen from the stationary distribution are useful for the application. In order to get reliable results, we require the chain to be rapidly mixing, or quickly converging to equilibrium. For example, to sample independent sets in a given graph G, the so-called hard-core lattice gas model, we can start at any independent set and repeatedly add or remove a single vertex (if allowed). By defining the transition probabilities of these moves appropriately, we can ensure that the chain will converge to a use- ful distribution over the state space Ω. For instance, the Gibbs (or Boltzmann) distribution, parameterized by Λ0, is defined so that p(Λ)=π(I)=Λ|I| /Z, where $Z = \sum_{J \in \Omega} \Lambda^{|J|}$ is the normalizing constant known as the partition function. An interesting phenomenon occurs as Λ is varied. For small values of Λ, local Markov chains converge quickly to stationarity, while for large values, they are prohibitively slow. To see why, imagine the underlying graph G is a region of the Cartesian lattice. Large independent sets will dominate the stationary distribution π when Λ is sufficiently large, and yet it will take a very long time to move from an independent set lying mostly on the odd sublattice to one that is mostly even. This phenomenon is well known in the statistical physics community, and characterizes by a phase transition in the underlying model. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13731-0_29 | SWAT |
Keywords | Field | DocType |
underlying random structure,large value,stationary distribution,ful distribution,large independent set,cartesian lattice,large state space,graph g,phase transition,sampling algorithm,sample independent set,independent set,markov chain,transition probability,boltzmann distribution,partition function,state space,random walk,statistical physics | Discrete mathematics,Combinatorics,Partition function (statistical mechanics),Random walk,Markov chain,Independent set,Stationary distribution,Normalizing constant,State space,Gibbs sampling,Mathematics | Conference |
Volume | ISSN | ISBN |
6139 | 0302-9743 | 3-642-13730-X |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dana Randall | 1 | 29 | 8.15 |