Information flow on trees

DOI10.1214/AOAP/1060202828MaRDI QIDQ1425477zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Yuval Peres

Publication date 21 March 2004

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0107033

zbMATH Keywords

information flowtree network

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Theory of error-correcting codes and error-detecting codes (94B99)

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>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 $la{m}_2(M)$ denote the second largest eigenvalue of $M$, in absolute value. A CLT of Kesten and Stigum~(1966) implies that if $b|la{m}_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|la{m}_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|la{m}_2(M){|}^2<1$, yet the {em configuration} at level $n$ is not asymptotically independent of the root variable.

Review text

The authors try to answer the following question: Let \(T\) be a tree network, where each edge acts as an independent copy of a given channel \(M\). Suppose that information is propagated from the root. For which \(T\) and \(M\) the configuration obtained at level \(n\) of \(T\) typically contains significant information on the root variable?

Recommendations

• scientific article; zbMATH DE number 2151257
• Broadcasting on trees and the Ising model.
• Reconstruction on trees: Beating the second eigenvalue
• scientific article; zbMATH DE number 1380585
• Reconstruction on trees and spin glass transition

Cites work

• A Limit Theorem for Multidimensional Galton-Watson Processes
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Broadcasting on trees and the Ising model.
• Gibbs measures and dismantlable graphs
• Glauber dynamics on trees and hyperbolic graphs
• Graph homomorphisms and phase transitions
• How to share a secret
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1195779 (Why is no real title available?)
• scientific article; zbMATH DE number 1304724 (Why is no real title available?)
• scientific article; zbMATH DE number 1380585 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• Markov random fields on an infinite tree
• On the extremality of the disordered state for the Ising model on the Bethe lattice
• On the maximum tolerable noise for reliable computation by formulas
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Random walk in a random environment and first-passage percolation on trees
• Random walks and percolation on trees
• Reconstruction on trees: Beating the second eigenvalue
• Remarks on the limiting Gibbs states on a (d+1)-tree
• Robust phase transitions for Heisenberg and other models on general trees
• Taxonomy with confidence

Cited in

(56)

• An impossibility result for reconstruction in the degree-corrected stochastic block model
• Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees
• The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
• Glauber dynamics on trees: Boundary conditions and mixing time
• Glauber dynamics on trees and hyperbolic graphs
• Robust reconstruction on trees is determined by the second eigenvalue.
• Phylogenetic mixtures: concentration of measure in the large-tree limit
• Sufficient condition for root reconstruction by parsimony on binary trees with general weights
• On the computational tractability of statistical estimation on amenable graphs
• Ising model on trees and factors of IID
• Species tree estimation under joint modeling of coalescence and duplication: sample complexity of quartet methods
• Concentration of Markov chains indexed by trees
• The critical Ising model on trees, concave recursions and nonlinear capacity
• Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Spectral redemption in clustering sparse networks
• On memory in exponentially expanding spaces
• Nondiscriminatory propagation on trees
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Phase transitions in phylogeny
• Community detection and stochastic block models: recent developments
• scientific article; zbMATH DE number 2151257 (Why is no real title available?)
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Fuzzy transformations and extremality of Gibbs measures for the Potts model on a Cayley tree
• Biased landscapes for random constraint satisfaction problems
• Optimization of the dynamic transition in the continuous coloring problem
• Gibbs measures of Potts model on Cayley trees: a survey and applications
• Phase transition for the Ising model with mixed spins on a Cayley tree
• Extremality of translation-invariant phases for a three-state SOS-model on the binary tree
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Teasing Apart Two Trees
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• Community detection and percolation of information in a geometric setting
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• The Swendsen–Wang dynamics on trees
• Combinatorial statistics and the sciences
• Gibbs periodic measures for a two-state HC-model on a Cayley tree
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• On the inference of large phylogenies with long branches: how long is too long?
• The extremality of disordered phases for the mixed spin-(1,1/2) Ising model on a Cayley tree of arbitrary order
• Inference in balanced community modulated recursive trees
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Exact phase transitions for stochastic block models and reconstruction on trees
• Gibbs measures for hardcore-solid-on-solid models on Cayley trees
• Global alignment of molecular sequences via ancestral state reconstruction
• Reconstruction for the Potts model
• Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture
• Likelihood-based root state reconstruction on a tree: sensitivity to parameters and applications
• Three-state p-SOS models on binary Cayley trees
• Sparse reconstruction in spin systems. II: Ising and other factor of IID measures
• Majority rule has transition ratio 4 on Yule trees under a 2-state symmetric model
• On the purity of the free boundary condition Potts measure on random trees
• Reconstruction of random colourings
• On the variational distance of two trees
• Equity trees and graphs via information theory
• Gibbs measures and phase transitions on sparse random graphs

This page was built for publication: Information flow on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1425477)