# A computational method for bounding the probability of reconstruction on trees - Computer Science > Discrete Mathematics

A computational method for bounding the probability of reconstruction on trees - Computer Science > Discrete Mathematics - Download this document for free, or read online. Document in PDF available to download.

Abstract: For a tree Markov random field non-reconstruction is said to hold if as thedepth of the tree goes to infinity the information that a typical configurationat the leaves gives about the value at the root goes to zero.

The distributionof the measure at the root conditioned on a typical boundary can be computedusing a distributional recurrence.

However the exact computation is notfeasible because the support of the distribution grows exponentially with thedepth.In this work, we introduce a notion of a survey of a distribution overprobability vectors which is a succinct representation of the truedistribution.

We show that a survey of the distribution of the measure at theroot can be constructed by an efficient recursive algorithm.

The key propertiesof surveys are that the size does not grow with the depth, they can beconstructed recursively, and they still provide a good bound for the distancebetween the true conditional distribution and the unconditional distribution atthe root.

This approach applies to a large class of Markov random field modelsincluding randomly generated ones.

As an application we show bounds on thereconstruction threshold for the Potts model on small-degree trees.

Author: ** Nayantara Bhatnagar, Elitza Maneva**

Source: https://arxiv.org/