NDLI: A Computational Method for Bounding the Probability of Reconstruction on Trees

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Bhatnagar, Nayantara Maneva, Elitza
Copyright Year	2011
Abstract	For a tree Markov random field, nonreconstruction 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 as follows: 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.
Starting Page	854
Ending Page	871
Page Count	18
File Format	PDF
ISSN	08954801
DOI	10.1137/090751244
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	2
Volume Number	25
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2011-07-01
Access Restriction	Subscribed
Subject Keyword	replica symmetry breaking Gibbs measure Disordered systems Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs extremality Interacting random processes; statistical mechanics type models; percolation theory graph coloring Markov random field Potts model Phase transitions reconstruction General GaltonWatson tree
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamical Gibbs-non-Gibbs transitions in Widom-Rowlinson models on trees

Absence of Replica Symmetry Breaking in the Random Field Mixed-Spin Ginzburg-Landau Model

Extremal inhomogeneous Gibbs states for SOS-models and finite-spin models on trees

Structure of Gibbs measures for planar FK-percolation and Potts models

Absence of Replica Symmetry Breaking in Finite Fifth Moment Random Field Ising Model

Introduction to (generalized) Gibbs measures

Metastability for Glauber dynamics on the complete graph with coupling disorder

On the Purity of the free boundary condition Potts measure on random trees

Lipschitz percolation

A Computational Method for Bounding the Probability of Reconstruction on Trees

Similar Documents

Dynamical Gibbs-non-Gibbs transitions in Widom-Rowlinson models on trees

Absence of Replica Symmetry Breaking in the Random Field Mixed-Spin Ginzburg-Landau Model

Extremal inhomogeneous Gibbs states for SOS-models and finite-spin models on trees

Structure of Gibbs measures for planar FK-percolation and Potts models

Absence of Replica Symmetry Breaking in Finite Fifth Moment Random Field Ising Model

Introduction to (generalized) Gibbs measures

Metastability for Glauber dynamics on the complete graph with coupling disorder

On the Purity of the free boundary condition Potts measure on random trees

Lipschitz percolation

A Computational Method for Bounding the Probability of Reconstruction on Trees