Fast initial conditions for Glauber dynamics
- PDF / 400,660 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 299 Views
Fast initial conditions for Glauber dynamics Eyal Lubetzky1 · Allan Sly2 Received: 15 July 2020 / Revised: 31 October 2020 / Accepted: 5 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In the study of Markov chain mixing times, analysis has centered on the performance from a worst-case starting state. Here, in the context of Glauber dynamics for the one-dimensional Ising model, we show how new ideas from information percolation can be used to establish mixing times from other starting states. At high temperatures we show that the alternating initial condition is asymptotically the fastest one, and, surprisingly, its mixing time is faster than at infinite temperature, accelerating as the inverse-temperature β ranges from 0 to β0 = 21 arctanh( 13 ). Moreover, the dominant test function depends on the temperature: at β < β0 it is autocorrelation, whereas at β > β0 it is the Hamiltonian. Mathematics Subject Classification 60J10 · 60K35
1 Introduction In the study of mixing time of Markov chains, most of the focus has been on determining the asymptotics of the worst-case mixing time, while relatively little is known about the relative effect of different initial conditions. The latter is quite natural from an algorithmic perspective on sampling, since one would ideally initiate the dynamics from the fastest initial condition. However, until recently, the tools available for analyzing Markov chains on complex systems, such as the Ising model, were insufficient for the purpose of comparing the effect of different starting states; indeed, already pinpointing the asymptotics of the worst-case state for Glauber dynamics for the Ising model can be highly nontrivial.
Dedicated to the memory of Harry Kesten.
B
Allan Sly [email protected] Eyal Lubetzky [email protected]
1
Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA
2
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA
123
E. Lubetzky, A. Sly
In this paper we compare different initial conditions for the Ising model on the cycle. In earlier work [11], we analyzed three different initial conditions. The all-plus state is provably the worst initial condition up to an additive constant. Another is a quenched random condition chosen from ν, the uniform distribution on configurations, which with high probability has a mixing time which is asymptotically as slow (one could potentially consider the quenched mixing time w.r.t. other distributions, e.g., the Ising distribution π ). A third initial condition is an annealed random condition chosen from ν, i.e., to start at time 0 from the uniform distribution, which is asymptotically twice as fast as all-plus. Here we consider two natural deterministic initial configurations. The first is the alternating sequence 1 i ≡ 0 (mod 2) alt x (i) = −1 i ≡ 1 (mod 2), which we will show is asymptotically the fastest deterministic initial condition—yet strictly slower than starting from the annealed random condition—for all β
Data Loading...
