Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators

Consider a Markov chain (ξv)v∈V∈[k]V on the infinite b-ary tree T=(V,E) with irreducible edge transition matrix M, where b≥2, k≥2 and [k]={1,...,k}. We denote by Ln the level-n vertices of T. Assume M has a real second-largest (in absolute value) eigenvalue λ with corresponding real eigenvector ν≠0. Letting σv=νξv, we consider the following root-state estimator, which was introduced by Mossel and Peres (2003) in the context of the “recontruction problem” on trees:

As noted by Mossel and Peres, when bλ2>1 (the so-called Kesten-Stigum reconstruction phase) the quantity Sn has uniformly bounded variance. Here, we give bounds on the moment-generating functions of Sn and S2n when bλ2>1. Our results have implications for the inference of evolutionary trees.