Robust reconstruction on trees is determined by the second eigenvalue. (Q1889794): Difference between revisions

Consider a process on a tree \(T\) in which information is transmitted from the root of the tree to all the nodes of the tree. Each node inherits information from its parent with some probability of error. The transmisson process is assumed to have identical distribution on all the edges, and different edges of the tree are assumed to act independently. The basic reconstruction question is: does the configuration obtained at level \(n\) of \(T\) typically contain significant information on the root variable? The problem of robust reconstruction is studied. Roughly speaking, the reconstruction problem is robust-solvable if for any noise-rate and for all \(n\), the \(n\)th level of the tree contains a non vanishing amount of information on the root of the tree. It is proven that the reconstruction problem for a \(B\)-ary tree is not robust-solvable if \(B| \lambda_2| ^2<1,\) where \(\lambda_2\) is the second largest (in absolute value) eigenvalue of the Markov transition rule matrix. A similar result is proven for general bounded degree trees, where \(B\) is replaced by the branching number of the tree br\((T).\)