The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

Abstract

We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact reconstruction threshold obtained in roughly a decade. We discuss the implications of our result for Glauber dynamics, phylogenetic reconstruction, and so-called ``replica symmetry breaking'' in spin glasses and random satisfiability problems.

Cited by in corpus (6)

• Fuzzy transformations and extremality of Gibbs measures for the Potts model on a Cayley tree
• Reconstruction Threshold for the Hardcore Model
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
• Reconstruction for the Asymmetric Ising Model on Regular Trees
• A computational method for bounding the probability of reconstruction on trees