OAI.ThreeState.TreeClauses.Tree.poisson_reconstructs_above_KS

The theorem states that, for any nonnegative real d and any real lam in the admissible range -1/2 ≤ lam ≤ 1, if the Kesten–Stigum-type inequality 1 < d·lam² holds, then the Poisson(d) offspring distribution reconstructs. Here the model is a Galton–Watson tree whose root has a spin uniformly distributed on three states, and each child's spin is obtained through a channel that keeps the parent's spin with probability (1+2lam)/3 and moves to each other spin with probability (1−lam)/3. The number of children of each vertex is drawn from the offspring law, which here is the Poisson distribution with mean d, with weights e^{-d} d^k / k!. At depth ℓ, the observation is the nested multiset of the spins of descendants, with the leaves at depth ℓ recorded as spins. The posterior of the root spin given an observation is computed from the uniform prior and the observation law, and the advantage at depth ℓ is the expected total variation distance (half the sum of absolute deviations) between this posterior and the uniform distribution on three spins. Reconstructs means that the advantage converges, as ℓ tends to infinity, to some strictly positive limit a.