Consider a process in which information is transmitted from a given
root node 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
can be reversed with probability $\varepsilon$, and these errors occur
independently. The goal is to reconstruct $R$ from the values which arrive at
the $n$th level of the tree. This model has been studied in information
theory,genetics and statistical mechanics.We bound the reconstruction
probability from above, 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 tends to 1/2 as $n \to \infty$ if $(1 - 2\varepsilon)^2 <
p_c(T)$, but the reconstruction probability stays bounded away from ½ if
the opposite inequality holds. Here $p_c(T)$ is the critical probability for
percolation on $T$; in particular $p_c(T) = 1/b$ for the $b + 1$-regular tree.
The asymptotic reconstruction problem is equivalent to purity of the
“free boundary” Gibbs state for the Ising model on a tree. The
special case of regular trees was solved in 1995 by Bleher, Ruiz and Zagrebnov;
our extension to general trees depends on a coupling argument and on a
reconstruction algorighm that weights the input bits by the electrical current
flow from the root to the leaves.