- Author:
- Dror Weitz,
- Chair:
- Alistair Sinclair
This dissertation studies relationships between fast convergence to equilibrium (mixing in time) of natural Markov chain Monte Carlo algorithms for discrete spin systems, and decay of correlations with distance in the corresponding equilibrium distribution (mixing in space). The results fall into four main groups.
In the first part we generalize the Dobrushin and Dobrushin-Shlosman conditions for uniqueness of the Gibbs measure (a form of mixing in space) by presenting conditions of any finite size for models on any underlying graph. We give two dual conditions, one requiring that the total influence on a site is small, and the other that the total influence of a site is small.
In the second part we critically examine a known sharp equivalence between appropriate notions of mixing in time and in space. For this part, the discussion applies only to systems on the d -dimensional integer lattice Z d . We give new, purely combinatorial arguments to prove that, if the mixing time of the Glauber dynamics is O ( n log n ), then spin correlations decay exponentially fast with distance in the Gibbs distribution.
In the third part we develop a new framework for analyzing the mixing time for spin systems on trees. The main technical result here is that on trees, an appropriate form of mixing in space implies O ( n log n ) mixing time of the Glauber dynamics. The novelty of this implication is that it is specific to the boundary condition. This allows us to give the first comprehensive analysis (in any context) of the effect of boundary conditions on the mixing time for the Ising and other models.
In the fourth part we explore directions for extending our results for trees to the 2-dimensional integer lattice Z 2 . The main motivation here is resolving a long standing conjecture which states that, conditioned on the all-(+) boundary, the mixing time re mains bounded by a fixed polynomial in n at all temperatures. (Notice that for the free boundary case, the mixing time at low temperatures is known to be very slow, specifically exp(?( n ))). (Abstract shortened by UMI.)
Cited By
- Harrow A, Mehraban S and Soleimanifar M Classical algorithms, correlation decay, and complex zeros of partition functions of Quantum many-body systems Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, (378-386)
- Hayes T, Vera J and Vigoda E (2015). Randomly coloring planar graphs with fewer colors than the maximum degree, Random Structures & Algorithms, 47:4, (731-759), Online publication date: 1-Dec-2015.
- Gamarnik D, Katz D and Misra S (2015). Strong spatial mixing of list coloring of graphs, Random Structures & Algorithms, 46:4, (599-613), Online publication date: 1-Jul-2015.
- Yin Y and Zhang C Approximate counting via correlation decay on planar graphs Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, (47-66)
- Štefankovič D, Vempala S and Vigoda E (2009). Adaptive simulated annealing: A near-optimal connection between sampling and counting, Journal of the ACM, 56:3, (1-36), Online publication date: 1-May-2009.
- Hayes T, Vera J and Vigoda E Randomly coloring planar graphs with fewer colors than the maximum degree Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, (450-458)
- Weitz D Counting independent sets up to the tree threshold Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, (140-149)
Index Terms
- Mixing in time and space for discrete spin systems
Recommendations
Mixing in time and space for lattice spin systems: A combinatorial view
Isaac Newton Institute Programme “Computation, Combinatorics and Probability”: Part IIThe paper considers spin systems on the d-dimensional integer lattice ℤd with nearest-neighbor interactions. A sharp equivalence is proved between decay with distance of spin correlations (a spatial property of the equilibrium state) and rapid mixing of ...
A Mixing Matrix Estimation Algorithm for the Time-Delayed Mixing Model of the Underdetermined Blind Source Separation Problem
Considering the time-delayed mixing model of the underdetermined blind source separation problem, we propose a novel mixing matrix estimation algorithm in this paper. First, we introduce the short-time Fourier transform (STFT) to transform the mixed ...
Spin---orbit hybrid entangled channel for spin state quantum teleportation using genetic algorithms
We present a physical model of spin quantum teleportation protocol (QTP) in a triple quantum dot array using a genetic algorithm approach. The information to teleport is spin-coded in one electron confined in a single quantum dot (SQD). The remaining ...