96 research outputs found
Fast Mixing for the Low Temperature 2D Ising Model Through Irreversible Parallel Dynamics
No full textWe study tunneling and mixing time for a non-reversible probabilistic cellular automaton. With a suitable choice of the parameters, we first show that the stationary distribution is close in total variation to a low temperature Ising model. Then we prove that both the mixing time and the time to exit a metastable state grow polynomially in the size of the system, while this growth is exponential in reversible dynamics. In this model, non-reversibility, parallel updatings and a suitable choice of boundary conditions combine to produce an efficient dynamical stability
Sampling from a Gibbs Measure with Pair Interaction by Means of PCA
No full textWe consider the problem of approximate sampling from the nite volume Gibbs
measure with a general pair interaction. We exhibit a parallel dynamics (Probabilistic
Cellular Automaton) which eciently implements the sampling. In this dynamics
the product measure that gives the new conguration in each site contains a term
that tends to favour the original value of each spin. This is the main ingredient that
allows one to prove that the stationary distribution of the PCA is close in total variation
to the Gibbs measure. The presence of the parameter that drives the "inertial"
term mentioned above gives the possibility to control the degree of parallelism of the
numerical implementation of the dynamics
Effects of Boundary Conditions on Irreversible Dynamics
No full textWe present a simple one-dimensional Ising-type spin system on which we define a completely asymmetric Markovian single spin-flip dynamics. We study the system at a very low, yet nonzero, temperature, and we show that for free boundary conditions the Gibbs measure is stationary for such dynamics, while introducing in a single site a + condition the stationary measure changes drastically, with macroscopical effects. We achieve this result defining an absolutely convergent series expansion of the stationary measure around the zero temperature system. Interesting combinatorial identities are involved in the proofs
Gaussian Mean Field Lattice Gas
No full textWe study rigorously a lattice gas version of the Sherrington-Kirckpatrick spin glass model. In discrete optimization literature this problem is known as unconstrained binary quadratic programming and it belongs to the class NP-hard. We prove that the fluctuations of the ground state energy tend to vanish in the thermodynamic limit, and we give a lower bound of such ground state energy. Then we present a heuristic algorithm, based on a probabilistic cellular automaton, which seems to be able to find configurations with energy very close to the minimum, even for quite large instances
Shaken Dynamics: An Easy Way to Parallel Markov Chain Monte Carlo
No full textWe define a class of Markovian parallel dynamics for spin systems on arbitrary graphs with nearest neighbor interaction described by a Hamiltonian function H(σ). These dynamics turn out to be reversible and their stationary measure is explicitly determined. Convergence to equilibrium and relation of the stationary measure to the usual Gibbs measure are discussed when the dynamics is defined on Z2. Further it is shown how these dynamics can be used to define natively parallel algorithms to face problems in the context of combinatorial optimization
Probabilistic Cellular Automata for Low-Temperature 2-d Ising Model
No full textWe construct a parallel stochastic dynamics with invariant measure converging to the Gibbs measure of the 2-d low-temperature Ising model. The proof of such convergence requires a polymer expansion based on suitably defined Peierls-type contours
Kac polymers
No full textWe show how a polymer in two dimensions with a self-repelling interaction of Kac type exhibits a diffusive-ballistic transition if considered on the appropriate scale
Exact Solution for a Class of Random Walk on the Hypercube
No full textA class of families of Markov chains defined on the vertices of the n-dimensional hypercube, Ω n ={0,1} n , is studied. The single-step transition probabilities P n,ij , with i,j∈Ω n , are given by Pn,ij=\frac(1-a)dij(2-a)nPnij=(2−)n(1−)dij, where α∈(0,1) and d ij is the Hamming distance between i and j. This corresponds to flip independently each component of the vertex with probability \frac1-a2-a2−1−. The m-step transition matrix Pn,ijmPmnij is explicitly computed in a close form. The class is proved to exhibit cutoff. A model-independent result about the vanishing of the first m terms of the expansion in α of Pn,ijmPmnij is also proved
Criticality of Measures on 2-d Ising Configurations: From Square to Hexagonal Graphs
No full textOn the space of Ising configurations on the 2-d square lattice, we consider a family of non Gibbsian measures introduced by using a pair Hamiltonian, depending on an additional inertial parameter q. These measures are related to the usual Gibbs measure on Z2 and turn out to be the marginal of the Gibbs measure of a suitable Ising model on the hexagonal lattice. The inertial parameter q tunes the geometry of the system. The critical behaviour and the decay of correlation functions of these measures are studied thanks to relation with the Random Cluster model. This measure turns out to be interesting also because it is the stationary measure of a class of Probabilistic Cellular Automata (PCA). Such PCA can be used to obtain a fast sample of the Ising measures on 2-d lattices
- …
