Information flow on trees
| dc.creator | Mossel, Elchanan | |
| dc.creator | Peres, Yuval | |
| dc.date | 2001-07-04 | |
| dc.date.accessioned | 2026-07-07T04:42:29Z | |
| dc.date.available | 2026-07-07T04:42:29Z | |
| dc.description | 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 level 2 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. This is related to certain secret-sharing protocols. 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~(1966) implies that if $b |\lam_2(M)|^2 >1$, then the {\em 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 {\em configuration} at level $n$ is not asymptotically independent of the root variable. | |
| dc.identifier | https://arxiv.org/abs/math/0107033 | |
| dc.identifier | http://arxiv.org/abs/math/0107033 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61800 | |
| dc.subject | Probability | |
| dc.subject | Mathematical Physics | |
| dc.subject | Combinatorics | |
| dc.title | Information flow on trees | |
| dc.type | text |