Robust reconstruction on trees is determined by the second Eigenvalue

• 成果类型: Article
• 署名作者: Janson, S; Mossel, E
• 署名单位: Uppsala University; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/0091179040000000153
• 发表日期: 2004
• 页码: 2630-2649
• 关键词: ising-model; phase-transitions; bethe lattice; percolation; state

摘要

Consider a Markov chain on an infinite tree T = (V, E) rooted at rho. In such a chain, once the initial root state a(p) 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 mu(j) denote the resulting measure for sigma(rho) = j. The resulting measure mu(j) is defined on configurations sigma = (sigma(x))(xis an element ofV) is an element of A(V), where A is some finite set. Let mu(j)(n) denote the restriction of mu to the sigma-algebra generated by the variables sigma(x), where x is at distance exactly n from rho. Letting alpha(n) = max(i,jis an element ofA) d(TV)(mu(i)(n), mu(j)(n)), where d(TV) denotes total variation distance, we say that the reconstruction problem is solvable if lim inf(n-->infinity) alpha(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 --> infinity. In this paper we study the problem of robust reconstruction. Let v be a nondegenerate distribution on A and epsilon > 0. Let sigma be chosen according to mu(j)(n) and sigma' be obtained from sigma by letting for each node independently, sigma(v) = sigma'(v) with probability 1 - epsilon and sigma'(v) be an independent sample from v otherwise. We denote by mu(j)(n)[v, epsilon] the resulting measure on sigma'. The measure mu(j)(n)[v, epsilon] is a perturbation of the measure mu(j)(n). Letting alpha(n)(v, epsilon) max(i,jis an element ofA) d(TV) (mu(i)(n),[v, epsilon], mu(j)(n)[v, epsilon]), we say that the reconstruction problem is v-robust-solvable if lim inf(n-->infinity) alpha(n) (v, epsilon) > 0 for all 0 < epsilon < 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\lambda(2) (M)\(2) > 1, where lambda(2)(M) is the second largest eigenvalue of At (in absolute value), then for all nondegenerate v, the reconstruction problem is v-robust-solvable. We prove a converse and show that the reconstruction problem is not v-robust-solvable if B\lambda(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.