Robust reconstruction on trees is determined by the second eigenvalue

• Svante Janson ^[1] ; Elchanan Mossel ^[2]
  1. [1] Uppsala University

     Uppsala University

     Uppsala domkyrkoförs., Suecia

     
  2. [2] University of California, Berkeley
• Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 32, Nº. 3, 2, 2004, págs. 2630-2649
• Idioma: inglés
• DOI: 10.1214/009117904000000153
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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 $\sigma=(\sigma(x))_{x\in V}\in \mathcal {A}^{V}$, 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 $\alpha_{n}=\max_{i,j\in \mathcal {A}}d_{\mathrm{TV}}(\mu_{i}^{n},\mu_{j}^{n})$, 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 $\alpha_{n}(\nu,\varepsilon )=\max_{i,j\in \mathcal {A}}d_{\mathrm{TV}}(\mu_{i}^{n}[\nu,\varepsilon ],\mu_{j}^{n}[\nu,\varepsilon ])$, 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.