Reconstruction on trees: Beating the second eigenvalue

We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T. We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an independent copy of some c hannel (Markov chain) M, where M is irreducible and aperiodic on A. The goa l is to reconstruct the symbol at the root from the symbols at the nth leve l of the tree. This model has been studied in information theory, genetics and statistical physics. The basic question is: is it possible to reconstru ct (some information on) the root? In other words, does the probability of correct reconstruction tend to 1/\A \ as n --> infinity? It is known that reconstruction is possible if d lambda (2)(2)(M) > 1, wher e lambda (2)(M) is the second eigenvalue of M. Moreover, in this case it is possible to reconstruct using a majority algorithm which ignores the locat ion of the data at the boundary of the tree. When M is a symmetric binary c hannel, this threshold is sharp. In this paper we show that, both for the b inary asymmetric channel and for the symmetric channel on many symbols, it is sometimes possible to reconstruct even when d lambda (2)(2)(M) < 1. This result indicates that, for many (maybe most) tree-indexed Markov chains, t he location of the data on the boundary plays a crucial role in reconstruct ion problems.