Information flow on trees

By Elchanan Mossel, Yuval Peres. The Annals of Applied Probability, 2001

145 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b9333687c93cae04a42111314cc33a9457a366fd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. James B. Martin
  2. Utkir A. Rozikov
  3. Yuri M. Suhov

In Mathematical Physics

  1. James B. Martin
  2. Utkir A. Rozikov
  3. Yuri M. Suhov

In Statistics and Probability

  1. James B. Martin
  2. Utkir A. Rozikov
  3. Yuri M. Suhov

Citations in the corpus