Reconstruction on Trees: Beating the Second Eigenvalue
Reconstruction on Trees: Beating the Second Eigenvalue
复制标题
树的重建：击败第二特征值
DOI：
10.1214/aoap/998926994
复制
发表时间：
2001
影响因子：
1.8
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
Elchanan Mossel
我们考虑一个过程，在这个过程中，信息从一个有噪声的辅助树网络T上的一个给定的根节点被传输。我们从一个取自字母表\(数学{A}\)的统一符号开始。树的每条边都是某个通道(马尔可夫链)M的独立副本，其中M是不可约的，且在数学上是非周期的。目标是根据树的第n级符号在根部重建符号。这个模型已经在信息论、遗传学和统计物理学中得到了研究。基本的问题是：有可能重建根(关于根的一些信息)吗？换言之，正确重建的概率是否趋向于n→∞？众所周知，如果dλ22(M)和gt；1，其中λ2(M)是M的第二个特征值，则重建是可能的。此外，在这种情况下，可以使用忽略数据在树边界的位置的多数算法进行重建。当M是对称的二进制通道时，该阈值是尖锐的。在这篇文章中，我们证明了，无论是对于二元非对称信道还是对于许多符号上的对称信道，有时甚至当dλ22(M)和lt；1时也是可能的。这一结果表明，对于许多(可能大多数)树索引马尔可夫链，数据在边界上的位置在重建问题中起着至关重要的作用。
We consider a process in which information is transmitted from a given root node on a noisy -dary tree network T. We start with a uniform symbol taken from an alphabet \(\mathcal{A}\). Each edge of the tree is an independent copy of some channel (Markov chain) M, where M is irreducible and aperiodic on \(\mathcal{A}\). The goal is to reconstruct the symbol at the root from the symbols at the nth level of the tree. This model has been studied in information theory, genetics and statistical physics. The basic question is: is it possible to reconstruct (some information on)the root? In other words, does the probability of correct reconstruction tend to \(1 /{\mathcal{A}}\) as n →∞?It is known that reconstruction is possible if dλ22(M) > 1, where λ2(M) is the second eigenvalue of M. Moreover,in this case it is possible to reconstruct using a majority algorithm which ignores the location of the data at the boundary of the tree. When M is a symmetric binary channel, this threshold is sharp. In this paper we show that, both for the binary asymmetric channel and for the symmetric channel on many symbols, it is sometimes possible to reconstruct even when dλ22(M) < 1. This result indicates that, for many (maybe most) tree-indexed Markov chains, the location of the data on the boundary plays a crucial role in reconstruction problems.