1 Search Results for "Fahrbach, Matthew"


Document
RANDOM
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases

Authors: Matthew Fahrbach and Dana Randall

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
The six-vertex model in statistical physics is a weighted generalization of the ice model on Z^2 (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model represents its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.

Cite as

Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{fahrbach_et_al:LIPIcs.APPROX-RANDOM.2019.37,
  author =	{Fahrbach, Matthew and Randall, Dana},
  title =	{{Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.37},
  URN =		{urn:nbn:de:0030-drops-112523},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.37},
  annote =	{Keywords: Correlated random walk, Markov chain Monte Carlo, Six-vertex model}
}
  • Refine by Author
  • 1 Fahrbach, Matthew
  • 1 Randall, Dana

  • Refine by Classification
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Correlated random walk
  • 1 Markov chain Monte Carlo
  • 1 Six-vertex model

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail