Paper detail

Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators

Consider a Markov chain $(ξ_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 $λ$ with corresponding real eigenvector $ν\neq 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: \begin{equation*} S_n = (bλ)^{-n} \sum_{x\in L_n} σ_x. \end{equation*} As noted by Mossel and Peres, when $bλ^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_n^2$ when $bλ^2 > 1$. Our results have implications for the inference of evolutionary trees.