Mixing Time of Critical Ising Model on Trees is Polynomial in the Height |
| |
Authors: | Jian Ding Eyal Lubetzky Yuval Peres |
| |
Institution: | 1. Department of Statistics, UC Berkeley, Berkeley, CA, 94720, USA 2. Microsoft Research, One Microsoft Way, Redmond, WA, 98052-6399, USA
|
| |
Abstract: | In the heat-bath Glauber dynamics for the Ising model on the lattice, physicists believe that the spectral gap of the continuous-time
chain exhibits the following behavior. For some critical inverse-temperature β
c
, the inverse-gap is O(1) for β < β
c
, polynomial in the surface area for β = β
c
and exponential in it for β > β
c
. This has been proved for
\mathbbZ2{\mathbb{Z}^2} except at criticality. So far, the only underlying geometry where the critical behavior has been confirmed is the complete
graph. Recently, the dynamics for the Ising model on a regular tree, also known as the Bethe lattice, has been intensively
studied. The facts that the inverse-gap is bounded for β < β
c
and exponential for β > β
c
were established, where β
c
is the critical spin-glass parameter, and the tree-height h plays the role of the surface area.
In this work, we complete the picture for the inverse-gap of the Ising model on the b-ary tree, by showing that it is indeed polynomial in h at criticality. The degree of our polynomial bound does not depend on b, and furthermore, this result holds under any boundary condition. We also obtain analogous bounds for the mixing-time of
the chain. In addition, we study the near critical behavior, and show that for β > β
c
, the inverse-gap and mixing-time are both expΘ((β − β
c
)h)]. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|