Information flow on trees

Elchanan Mossel, Yuval Peres

Abstract

This paper investigates the reconstruction problem on tree networks: determining when the state of a root node can be recovered from the configuration of nodes at level $n$ as $n \to \infty$. We examine the fundamental gap between reconstruction based on the full spatial configuration of leaves versus reconstruction based solely on the "census" (the counts of each state). We prove that for a $b$-ary tree and a channel $M$, the census of variables at level $n$ is asymptotically independent of the root variable if $b|\lambda_2(M)|^2 < 1$, where $\lambda_2(M)$ is the second largest eigenvalue of the transition matrix. Furthermore, we demonstrate the existence of channels where information flow is non-monotonic, resembling secret-sharing protocols where the root is independent of its grandchildren yet recoverable from sufficiently deep levels of the tree.

Introduction

Consider a game of "telephone" played on a branching tree $T$. A message originates at the root and is propagated down to children through noisy channels, where each edge acts as an independent copy of a transition matrix $M$. As the depth of the tree increases, the noise accumulates. The central question is whether any significant information about the root variable survives at the leaves as the tree grows infinitely deep.

This problem, known as the reconstruction problem, has deep roots in several disparate fields:

  • Biology: Reconstructing ancestral DNA sequences from the genomes of extant species.
  • Information Theory: Determining the capacity of broadcast networks to tolerate noise.
  • Statistical Physics: Analyzing the uniqueness of Gibbs measures in models like the Ising or Potts models on trees, where the question is whether the boundary conditions can influence the state at the center.

The Census vs. Configuration Distinction

A critical contribution of this work is the formal distinction between reconstruction (using the full spatial configuration of leaf states) and census-reconstruction (using only the aggregate counts of each state at the leaves).

Historically, the Kesten-Stigum theorem (1966) provided a sufficient condition for reconstruction: if $b|\lambda_2(M)|^2 > 1$, then the census of variables at any level contains significant information about the root. However, the necessity of this condition for census-based methods remained an open question. We establish a converse: if $b|\lambda_2(M)|^2 < 1$, the census at level $n$ becomes asymptotically independent of the root. This confirms that the Kesten-Stigum bound is the sharp threshold for "counting-based" inference.

Non-Monotonic Information and Secret Sharing

One of the most surprising findings in this study is that information flow on trees is not always monotonic in a simple sense. We construct a specific channel for a $b$-ary tree where the root variable is completely independent of the configuration at level 2. Under traditional intuition, one might assume the signal is lost forever.

However, we show that for a sufficiently large branching factor $B > b$, the mutual information between the configuration at level $n$ and the root variable remains bounded away from zero. This phenomenon is analogous to "secret sharing" in cryptography, where individual pieces of data (or small groups of pieces) reveal nothing about the secret, but the collective assembly of the entire configuration allows for full recovery. This demonstrates that the full spatial arrangement of states can preserve signals that disappear in local or aggregate views.

Theoretical Framework and Results

Eigenvalue Analysis and Coupling

To prove non-reconstruction, we employ coupling arguments, attempting to show that processes starting from different root states eventually produce identical leaf distributions. We use $\lambda_2(M)$ as a proxy for the fidelity of the channel. For asymmetric binary channels (Ising models with an external field) and symmetric $q$-ary channels (Potts models), we improved the upper bounds on information flow, narrowing the range where the behavior of the model was previously unknown.

General Trees and Branching Numbers

While much of the literature focuses on regular $b$-ary trees, we extend these results to general trees using the concept of the "branching number" $br(T)$. We show that if $br(T)|\lambda_2|^2 > 1$, reconstruction is possible. This approach treats the tree similarly to an electrical network, where noise acts as a form of resistance and the branching number represents the "capacity" of the circuit to carry the signal.

Conclusion and Future Work

Our work clarifies the limits of aggregate data in tree-based inference, proving that the Kesten-Stigum threshold is the definitive limit for census-based reconstruction. We also highlight the complexity of information flow by demonstrating that the absence of a local signal (at level 2) does not preclude the existence of a global signal at level $n$.

Future research remains to be done on the "critical case" where $b|\lambda_2(M)|^2 = 1$. While we have proven census reconstruction is impossible at this threshold for Potts and asymmetric Ising models, a universal proof for all channels remains a conjecture. Additionally, the computational complexity of performing reconstruction in "secret sharing" channels—where simple counting fails—presents a significant challenge for algorithmic development.

Summary updated

Abstract

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&gt;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 &gt;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 &lt; 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 &lt;1$, yet the {\em configuration} at level $n$ is not asymptotically independent of the root variable.
BibTeX
@article{mossel2003information,
  author = {Elchanan Mossel and Yuval Peres},
  title = {{Information flow on trees}},
  journal = {The Annals of Applied Probability},
  year = {2003},
  doi = {10.1214/aoap/1060202828},
}
Figure