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.