Information flow on trees

Consider a tree network T, where each edge acts as an independent copy of a given channel M, and information is propagated from the root. For which T and M does the configuration obtained at level n of T typically contain significant information on the root variable? This problem arose independently in biology, information theory and statistical physics. For all b, we construct a channel for which the variable at the root of the break b-ary tree is independent of the configuration at the second level of that tree, yet for sufficiently large B>b, the mutual information between the configuration at level n of the B-ary tree and the root variable is bounded away from zero for all n. This construction is related to Reed--Solomon codes. We improve the upper bounds on information flow for asymmetric binary channels (which correspond to the Ising model with an external field) and for symmetric q-ary channels (which correspond to Potts models). Let ₂ (M) denote the second largest eigenvalue of M, in absolute value. A CLT of Kesten and Stigum implies that if b |₂ (M) |² >1, then the census of the variables at any level of the b-ary tree, contains significant information on the root variable. We establish a converse: If b |₂ (M) |² < 1, then the census of the variables at level n of the b-ary tree is asymptotically independent of the root variable. This contrasts with examples where b |₂ (M) |² <1, yet the configuration at level n is not asymptotically independent of the root variable.