Information flow on trees

• 成果类型: Article
• 署名作者: Mossel, E; Peres, Y
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2003
• 页码: 817-844
• 关键词: galton-watson processes; ising-model; limit theorems; bethe lattice; reconstruction; percolation; state

摘要

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 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 lambda(2)(M) denote the second largest eigenvalue of M, in absolute value. A CLT of Kesten and Stigum implies that if b\lambda(2)(M)\(2) > 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\lambda(2)(M)\(2) < 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\lambda(2)(M)\(2) < 1, yet the configuration at level n is not asymptotically independent of the root variable.