A computational method for bounding the probability of reconstruction on trees - Computer Science > Discrete MathematicsReportar como inadecuado




A computational method for bounding the probability of reconstruction on trees - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.



Autor: Nayantara Bhatnagar, Elitza Maneva

Fuente: https://arxiv.org/







Documentos relacionados