Approximating pairwise correlations in the Ising model

DOI10.1145/3337785MaRDI QIDQ5205819zbMATH OpenOpenAlexWikidataFDO

Authors Leslie Ann Goldberg, Mark Jerrum

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.05830

zbMATH Keywords

Ising modelMarkov chainMonte Carlo

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20) Approximation algorithms (68W25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Monte Carlo methods applied to problems in statistical mechanics (82M31)

Abstract: In the Ising model, we consider the problem of estimating the covariance of the spins at two specified vertices. In the ferromagnetic case, it is easy to obtain an additive approximation to this covariance by repeatedly sampling from the relevant Gibbs distribution. However, we desire a multiplicative approximation, and it is not clear how to achieve this by sampling, given that the covariance can be exponentially small. Our main contribution is a fully polynomial time randomised approximation scheme (FPRAS) for the covariance. We also show that that the restriction to the ferromagnetic case is essential --- there is no FPRAS for multiplicatively estimating the covariance of an antiferromagnetic Ising model unless RP = #P. In fact, we show that even determining the sign of the covariance is #P-hard in the antiferromagnetic case.

Recommendations

• scientific article; zbMATH DE number 177833
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• The Complexity of Ferromagnetic Ising with Local Fields
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Ising partition function: zeros and deterministic approximation

Cited in

(8)

• A Bayesian analysis of Monte Carlo correlation times for the two-dimensional Ising model
• The complexity of approximating the complex-valued Potts model
• Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Exact Goodness‐of‐Fit Testing for the Ising Model
• The Ising correlation C(M, N) for ν = −k
• A new correlation inequality for Ising models with external fields

This page was built for publication: Approximating pairwise correlations in the Ising model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205819)