2004/06/30 by Svante Janson, Elchanan Mossel · 4 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Mathematical Analysis and Transform Methods #Random Matrices and Applications #math.CO #math.PR #math.SP #math.ST #msc:60J80 #msc:60K35 #msc:82B26 #stat.TH
paper · pdf · doi:10.1214/009117904000000153
published as Annals of Probability 2004, Vol. 32, No. 3, 2630-2649 · 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)
openalex publication_date 2004/07/01 · arxiv created 2005/03/30 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/31
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∈ V∈ \mathcal AV, where \mathcal A is some finite set. Let μjn 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∈ \mathcal AdTV(μin,μjn), where dTV denotes total variation distance, we say that the reconstruction problem is solvable if lim inf n→∞α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→∞. In this paper we study the problem of robust reconstruction. Let ν be a nondegenerate distribution on \mathcal A" and ɛ>0. Let σ be chosen according to μjn 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 μjn[ν,ɛ] the resulting measure on σ'. The measure μjn[ν,ɛ] is a perturbation of the measure μjn. Letting αn(ν,ε )=max_i,j∈ \mathcal AdTV(μin[ν,ε ],μjn[ν,ε ]), we say that the reconstruction problem is ν-robust-solvable if lim inf n→∞αn(ν,ɛ)>0 for all 0<ɛ<1. Roughly speaking, the reconstruction problem is robust-solvable if for any noise-rate and for all n, the nth level of the tree contains a nonvanishing amount of information on the root of the tree. Standard techniques imply that if T is the rooted B-ary tree (where each node has B children) and if B|λ2(M)|2>1, where λ2(M) is the second largest eigenvalue of M (in absolute value), then for all nondegenerate ν, the reconstruction problem is ν-robust-solvable. We prove a converse and show that the reconstruction problem is not ν-robust-solvable if B|λ2(M)|2<1. This proves a conjecture by the second author and Y. Peres. We also consider other models of noise and general trees.