A computational method for bounding the probability of reconstruction on trees

DOI10.1137/090751244MaRDI QIDQ3094947zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Elitza Maneva

Publication date 27 October 2011

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

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

zbMATH Keywords

correlationsextremalityGalton-Watson treeGibbs measuregraph coloringgraphsMarkov random fieldsPotts modelreconstructionreplica symmetry breakingtrees

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Markov processes (60J99) Interacting random processes; statistical mechanics type models; percolation theory (60K35) General topics in the theory of algorithms (68W01) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: For a tree Markov random field non-reconstruction is said to hold if as the depth of the tree goes to infinity the information that a typical configuration at the leaves gives about the value at the root goes to zero. The distribution of the measure at the root conditioned on a typical boundary can be computed using a distributional recurrence. However the exact computation is not feasible because the support of the distribution grows exponentially with the depth. In this work, we introduce a notion of a survey of a distribution over probability vectors which is a succinct representation of the true distribution. We show that a survey of the distribution of the measure at the root can be constructed by an efficient recursive algorithm. The key properties of surveys are that the size does not grow with the depth, they can be constructed recursively, and they still provide a good bound for the distance between the true conditional distribution and the unconditional distribution at the root. This approach applies to a large class of Markov random field models including randomly generated ones. As an application we show bounds on the reconstruction threshold for the Potts model on small-degree trees.

Recommendations

• Reconstruction for the Potts model
• Reconstruction on trees and spin glass transition
• Reconstruction for the Potts model
• scientific article; zbMATH DE number 2046068
• A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees

Cited in

(5)

• REPLICA CONDENSATION AND TREE DECAY
• scientific article; zbMATH DE number 2046068 (Why is no real title available?)
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Combinatorial statistics and the sciences
• Reconstruction for the Potts model

This page was built for publication: A computational method for bounding the probability of reconstruction on trees

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