ﻻ يوجد ملخص باللغة العربية
For $d ge 2$ and all $qgeq q_{0}(d)$ we give an efficient algorithm to approximately sample from the $q$-state ferromagnetic Potts and random cluster models on the torus $(mathbb Z / n mathbb Z )^d$ for any inverse temperature $betageq 0$. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen--Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models. Our algorithms are based on representing the random cluster model as a contour model using Pirogov-Sinai theory, and then computing an accurate approximation of the logarithm of the partition function by inductively truncating the resulting cluster expansion. The main innovation of our approach is an algorithmic treatment of unstable ground states; this is essential for our algorithms to apply to all inverse temperatures $beta$. By treating unstable ground states our work gives a general template for converting probabilistic applications of Pirogov--Sinai theory to efficient algorithms.
A two-type version of the frog model on $mathbb{Z}^d$ is formulated, where active type $i$ particles move according to lazy random walks with probability $p_i$ of jumping in each time step ($i=1,2$). Each site is independently assigned a random numbe
We develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition, and as a step in the argument we give a graph partitioning algorithm with expansion and minimum degree c
A version of the Schelling model on $mathbb{Z}$ is defined, where two types of agents are allocated on the sites. An agent prefers to be surrounded by other agents of its own type, and may choose to move if this is not the case. It then sends a reque
We give the ``quenched scaling limit of Bouchauds trap model in ${dge 2}$. This scaling limit is the fractional-kinetics process, that is the time change of a $d$-dimensional Brownian motion by the inverse of an independent $alpha$-stable subordinator.
Some stochastic systems are particularly interesting as they exhibit critical behavior without fine-tuning of a parameter, a phenomenon called self-organized criticality. In the context of driven-dissipative steady states, one of the main models is t