OAI.ThreeState.TreeClauses.Tree.regular_reconstructs_above_KS

The theorem states that, for any natural number b and real number lam in the admissible range -1/2 ≤ lam ≤ 1, if b·lam² > 1, then the three-state broadcast process on a tree whose offspring law is the point mass at b (every vertex has exactly b children) reconstructs. Here the root spin is uniform on three states {0,1,2}, and each edge passes the spin through a channel that keeps it with probability (1+2·lam)/3 and moves it to each other state with probability (1−lam)/3. The observation at depth ℓ is a nested multiset of the spins at that depth, built recursively from the children's observations, and the advantage at depth ℓ is the expected half-L1 distance between the posterior of the root spin given the observation and the uniform distribution on three states, namely the average over observations of half the sum over states of |posterior − 1/3|. Reconstructs means that there is a real a>0 such that this advantage converges to a as ℓ tends to infinity.