Robust reconstruction on trees is determined by the second eigenvalue

Abstract

Consider a Markov chain on an infinite tree T=(V,E) rooted at ρ. In such a chain, once the initial root state σ(ρ) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let μ_j denote the resulting measure for σ(ρ)=j. The resulting measure μ_j is defined on configurations σ=(σ(x))_{x\in V}\in A^V, where A is some finite set. Let μ_j^n denote the restriction of μto the sigma-algebra generated by the variables σ(x), where x is at distance exactly n from ρ. Letting α_n=max_{i,j\in A}d_{TV}(μ_i^n,μ_j^n), where d_{TV} denotes total variation distance, we say that the reconstruction problem is solvable if lim inf_{n\to\infty}α_n>0. Reconstruction solvability roughly means that the nth level of the tree contains a nonvanishing amount of information on the root of the tree as n\to\infty. In this paper we study the problem of robust reconstruction. Let νbe a nondegenerate distribution on A and ε>0. Let σbe chosen according to μ_j^n and σ' be obtained from σby letting for each node independently, σ(v)=σ'(v) with probability 1-εand σ'(v) be an independent sample from νotherwise. We denote by μ_j^n[ν,ε] the resulting measure on σ'. The measure μ_j^n[ν,ε] is a perturbation of the measure μ_j^n.

Published at http://dx.doi.org/10.1214/009117904000000153 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (19)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• Typology of phase transitions in Bayesian inference problems
• Community detection in networks with unequal groups
• Belief propagation, robust reconstruction and optimal recovery of block models
• Quiet Planting in the Locked Constraint Satisfaction Problems
• The critical Ising model on trees, concave recursions and nonlinear capacity
• On the three state Potts model with competing interactions on the Bethe lattice
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs
• Broadcasting on Random Directed Acyclic Graphs
• Algorithmic detectability threshold of the stochastic block model
• Optimization of the dynamic transition in the continuous coloring problem
• Broadcasting on Two-Dimensional Regular Grids
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Non-robust phase transitions in the generalized clock model on trees