Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators

Consider a Markov chain \(({\xi }_v)_{v\in V}\in [k]_V\) on the infinite \(b\)-ary tree \(T=(V,E)\) with irreducible edge transition matrix \(M\), where \(b\geq 2\), \(k\geq 2\) and \([k]={1,…,k}\). We denote by \(L_n\) the level-\(n\) vertices of \(T\). Assume \(M\) has a real second-largest (in absolute value) eigenvalue \(\lambda\) with corresponding real eigenvector \(\nu \neq 0\). Letting \({\sigma }_v={\nu }_{{\xi }_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{\lambda }_2>1\) (the so-called Kesten-Stigum reconstruction phase) the quantity \(S_n\) has uniformly bounded variance. Here, we give bounds on the moment-generating functions of \(S_n\) and \(S_2^n\) when \(b{\lambda }_2>1\). Our results have implications for the inference of evolutionary trees.

Opens in a new tab