solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看7301次
Approximating Pairwise Correlations in the Ising Model. (arXiv:1810.05830v1 [cs.DS])
来源于:arXiv
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. 查看全文>>