查看文章

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 …