Computing bounds for entropy of stationary Z^d Markov random fields

DOI10.1137/120887382MaRDI QIDQ2870521zbMATH OpenOpenAlexFDO

Authors Brian Marcus, Ronnie Pavlov

Publication date 21 January 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

disagreement percolationentropyGibbs measuresMarkov random fields

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Topological entropy (37B40) Thermodynamic formalism, variational principles, equilibrium states for dynamical systems (37D35)

Abstract: For any stationary $m{Z}^d$-Gibbs measure that satisfies strong spatial mixing, we obtain sequences of upper and lower approximations that converge to its entropy. In the case, $d=2$, these approximations are efficient in the sense that the approximations are accurate to within $epsilon$ and can be computed in time polynomial in $1/epsilon$.

Review text

The paper studies stationary \(\mathbb Z^d\) Markov random fields (MRF) satisfying a strong spatial mixing condition (SSM) (with an exponential decay rate \(\alpha\)). Given a stationary measure \(\mu\) which is nearest-neighbor \(\mathbb Z^d\) MRF, the authors provide lower and upper bounds for its entropy which depend on \(\alpha\). These bounds provide an algorithm to explicitly approximate the entropy which is accurate to within \(\epsilon\) in time \(\exp^{O((\log(1/\epsilon))^{(d-1)^2})}\). For \(d=2\) it is accurate to within \(O(1/n)\) in polynomial time (in \(n\)). The algorithms are entirely deterministic and rigorous and do not rely on randomized approaches such as, for example, a Monte Carlo method. The authors discuss the particular case of a stationary Gibbs measure, giving explicitly the SSM condition for such a measure. Finally, they indicate briefly how to extend their approach to study pressure which provides an algorithm with analogous precision.

Recommendations

• Approximating entropy for a class of Z^2 Markov random fields and pressure for a class of functions on Z^2 shifts of finite type
• Markov approximation of homogeneous lattice random fields
• On the complexity of computing maximum entropy for Markovian models
• Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
• scientific article; zbMATH DE number 4044857

Cited in

(16)

• An SMB approach for pressure representation in amenable virtually orderable groups
• On the topological entropy of subshifts of finite type on free semigroups
• An integral representation for topological pressure in terms of conditional probabilities
• Representation and poly-time approximation for pressure of Z^2 lattice models in the non-uniqueness region
• On the complexity of computing maximum entropy for Markovian models
• The topological strong spatial mixing property and new conditions for pressure approximation
• Capacity of higher-dimensional constrained systems
• scientific article; zbMATH DE number 5713895 (Why is no real title available?)
• scientific article; zbMATH DE number 2170418 (Why is no real title available?)
• Approximating entropy for a class of Z^2 Markov random fields and pressure for a class of functions on Z^2 shifts of finite type
• Entropy Bifurcation of Neural Networks on Cayley Trees
• Strong spatial mixing in homomorphism spaces
• Characterization for entropy of shifts of finite type on Cayley trees
• The strip entropy approximation of Markov tree-shifts on Markov-Cayley trees
• On the escape rate of subshifts of finite type and 2-multiplicative integer systems on \(\mathbb{N}^d\)
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Computing bounds for entropy of stationary \(\mathbb{Z}^d\) Markov random fields

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