Name
Abstract | ||
|---|---|---|
Many natural Markov chains undergo a phase transition as a temperature parameter is varied; a chain can be rapidly mixing at high temperature and slowly mixing at low temperature. Moreover, it is believed that even at low temperature, the rate of convergence is strongly dependent on the environment in which the underlying system is placed. It is believed that the boundary conditions of a spin configuration can determine whether a local Markov chain mixes quickly or slowly, but this has only been verified previously for models defined on trees. We demonstrate that the mixing time of Broder's Markov chain for sampling perfect and near-perfect matchings does have such a dependence on the environment when the underlying graph is the square-octagon lattice. We show the same effect occurs for a related chain on the space of Ising and “near-Ising” configurations on the two-dimensional Cartesian lattice. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11830924_27 | APPROX-RANDOM |
Keywords | Field | DocType |
related chain,boundary condition,markov chain,low temperature,temperature parameter,underlying graph,two-dimensional cartesian lattice,square-octagon lattice,high temperature,natural markov chain,local markov chain,rate of convergence,mixing time,phase transition | Statistical physics,Boundary value problem,Discrete mathematics,Markov chain mixing time,Square lattice,Continuous-time Markov chain,Phase transition,Markov chain,Ising model,Balance equation,Geometry,Mathematics | Conference |
Volume | ISSN | ISBN |
4110 | 0302-9743 | 3-540-38044-2 |
Citations | PageRank | References |
2 | 0.40 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nayantara Bhatnagar | 1 | 90 | 10.03 |
| Sam Greenberg | 2 | 47 | 5.60 |
| Dana Randall | 3 | 29 | 8.15 |