Broadcasting on trees and the Ising model

Consider a process in which information is transmitted from a given root no de on a noisy tree network T. We start with an unbiased random bit R at the root of the tree and send it down the edges of T. On every edge the bit ca n be reversed with probability epsilon, and these errors occur independentl y. The goal is to reconstruct R from the values which arrive at the nth lev el of the tree. This model has been studied in information theory, genetics and statistical mechanics. We bound the reconstruction probability from ab ove, using the maximum flow on T viewed as a capacitated network, and from below using the electrical conductance of T. For general infinite trees, we establish a sharp threshold: the probability of correct reconstruction ten ds to 1/2 as n --> infinity if (1- 2 epsilon)(2) < p(c)(T), but the reconst ruction probability stays bounded away from 1/2 if the opposite inequality holds. Here p(c)(T) is the critical probability for percolation on T; in pa rticular p(c)(T) = 1/b for the b + 1-regular tree. The asymptotic reconstru ction problem is equivalent to purity of the "free boundary" Gibbs state fo r the Ising model on a tree. The special case of regular trees was solved i n 1995 by Bleher, Ruiz and Zagrebnov; our extension to general trees depend s on a coupling argument and on a reconstruction algorithm that weights the input bits by the electrical current flow from the root to the leaves.