Information flow on trees

Mossel, Elchanan ; Peres, Yuval

Ann. Appl. Probab., Tome 13 (2003) no. 1, p. 817-844 / Harvested from Project Euclid

Résumé

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

Détail

Publié le : 2003-08-14
Classification:  Information flow,  reconstruction problem,  tree index Markov chain,  Markov random field,  census,  second Eigenvalue,  Thompson's principle,  Reed-Solomon codes,  secret sharing,  60J80,  60K35,  60F05,  94B99