Reconstruction thresholds on regular trees

2003/05/28 by Jean Martin, James B. Martin, Martin, James B.
Mathematics · Physics and Astronomy · #60K35 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #math.PR #msc:60K35

paper · pdf · doi:10.48550/arxiv.math/0305400

12 pages

arxiv created 2003/05/28 · openalex publication_date 2003/05/28 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a branching random walk with binary state space and index set T^k, the infinite rooted tree in which each node has k children (also known as the model of "broadcasting on a tree"). The root of the tree takes a random value 0 or 1, and then each node passes a value independently to each of its children according to a 2x2 transition matrix P. We say that "reconstruction is possible" if the values at the d'th level of the tree contain non-vanishing information about the value at the root as d→∞. Adapting a method of Brightwell and Winkler, we obtain new conditions under which reconstruction is impossible, both in the general case and in the special case p₁₁=0. The latter case is closely related to the "hard-core model" from statistical physics; a corollary of our results is that, for the hard-core model on the (k+1)-regular tree with activity λ=1, the unique simple invariant Gibbs measure is extremal in the set of Gibbs measures, for any k.

Related

• The branching-ruin number and the critical parameter of once-reinforced random walk on trees
• The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations
• Broadcasting on trees near criticality
• Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
• The branching-ruin number as critical parameter of random processes on\n trees