Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient sampling and counting algorithms for the Potts model on $mathbb Z^d$ at all temperatures
113
0
0.0
(
0
)
Added by
Will Perkins
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 number of particles. At time 0, the particles at the origin are activated and assigned type 1 and the particles at one other site are activated and assigned type 2, while all other particles are sleeping. When an active type $i$ particle moves to a new site, any sleeping particles there are activated and assigned type $i$, with an arbitrary tie-breaker deciding the type if the site is hit by particles of both types in the same time step. We show that the event $G_i$ that type $i$ activates infinitely many particles has positive probability for all $p_1,p_2in(0,1]$ ($i=1,2$). Furthermore, if $p_1=p_2$, then the types can coexist in the sense that $mathbb{P}(G_1cap G_2)>0$. We also formulate several open problems. For instance, we conjecture that, when the initial number of particles per site has a heavy tail, the types can coexist also when $p_1 eq p_2$.
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 conditions on the subgraphs induced by each part. These results extend previous work of Jenssen, Keevash, and Perkins (2019) on the Potts model and related problems in expander graphs, and of Oveis Gharan and Trevisan (2014) on partitioning into expanders.
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 request to an agent of opposite type chosen according to some given moving distribution and, if the move is beneficial for both agents, they swap location. We show that certain choices in the dynamics are crucial for the properties of the model. In particular, the model exhibits different asymptotic behavior depending on whether the moving distribution has bounded or unbounded support. Furthermore, the behavior changes if the agents are lazy in the sense that they only swap location if this strictly improves their situation. Generalizations to a version that includes multiple types are discussed. The work provides a rigorous analysis of so called Kawasaki dynamics on an infinite structure with local interactions.
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 that of Activated Random Walks. Long-range effects intrinsic to the conservative dynamics and lack of a simple algebraic structure cause standard tools and techniques to break down. This makes the mathematical study of this model remarkably challenging. Yet, some exciting progress has been made in the last ten years, with the development of a framework of tools and methods which is finally becoming more structured. In these lecture notes we present the existing results and reproduce the techniques developed so far.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
