Consider a rooted tree in which every vertex carries one of four colors.
Each edge transmits the parent color to its child through a fixed noisy
channel with parameter lambda in [0,1]:
P_lambda(j | i) = lambda * 1_{i = j} + (1 - lambda)/4, i, j in {1,2,3,4}.
Lambda = 1 copies the parent perfectly, lambda = 0 forgets everything, and
lambda >= 0 is the ferromagnetic regime in which copying is never
discouraged. Trees under study are the d-ary tree with d children at every
vertex (d >= 2) and the Galton-Watson tree with independent Poisson(d)
offspring counts (mean d > 0). The root spin sigma_rho is uniform on the
four colors. The observer is shown the whole tree T together with every
spin on level L_n = { v : dist(v, rho) = n }, and afterward infers the
root's color. Denote the resulting posterior probabilities by p_i.
Non-reconstruction means that, in expectation, the posterior concentrates
on the uniform prior:
a_n(d, lambda) = E[ (1/2) sum_{i=1}^4 | p_i - 1/4 | ] -> 0.
In the Poisson model the expectation averages over the tree as well,
without conditioning on survival, and an empty level L_n gives
p = (1/4,1/4,1/4,1/4). The framework and its normalizations are in Mezard
and Montanari, Reconstruction on trees and spin glass transition,
J. Stat. Phys. 124 (2006) 1317-1350.
./pdfs/mm2006.pdf
The main result is an exact threshold.
THEOREM. Suppose d lambda^2 <= 1. Then a_n(d, lambda) -> 0 in both the
d-ary and Poisson(d) families. The critical case d lambda^2 = 1 is
included.
The matching reconstruction direction for d lambda^2 > 1 follows from the
branching-process criterion of Kesten and Stigum, Additional limit theorems
for indecomposable multidimensional Galton-Watson processes, Ann. Math.
Statist. 37 (1966) 1463-1481, doi:10.1214/aoms/1177699139; the tree-branching
formulation on Galton-Watson trees is Lyons, Random walks and percolation
on trees, Ann. Probab. 18 (1990) 931-958, doi:10.1214/aop/1176990730.
Together with the main theorem, this makes the second-moment criterion an
exact statement. For the symmetric binary channel the boundary was
resolved by Bleher, Ruiz, and Zagrebnov, On the purity of the limiting
Gibbs state for the Ising model on the Bethe lattice, J. Stat. Phys. 79
(1995) 473-482, doi:10.1007/BF02179399, and by Evans, Kenyon, Peres, and
Schulman, Broadcasting on trees and the Ising model, Ann. Appl. Probab. 10
(2000) 410-433, doi:10.1214/aoap/1019487349. The general tree analysis in
Mossel and Peres, Information flow on trees, Ann. Appl. Probab. 13 (2003)
817-844, doi:10.1214/aoap/1060202828, extends this to the branching-number
regime.
./pdfs/lyons1990.pdf
./pdfs/mp2003.pdf
Whether the second-moment criterion is sharp for non-reconstruction
depends on the channel. Mossel, Reconstruction on trees: beating the
second eigenvalue, Ann. Appl. Probab. 11 (2001) 285-300,
doi:10.1214/aoap/998926994, showed that it need not be necessary; the
Potts channel makes this decisive as the number of states grows. For
Potts models, Sly, Reconstruction for the Potts model, Ann. Probab. 39
(2011) 1365-1406, established sharpness for the three-state model on
regular trees of sufficiently large degree and failure of sharpness for
five or more states.
./pdfs/sly2011.pdf
The four-state ferromagnetic model lies at the boundary between these
two regimes. Non-reconstruction at criticality on Galton-Watson trees of
sufficiently large mean degree, under hypotheses that cover both regular
and Poisson offspring, was proved by Mossel, Sly, and Sohn, Exact phase
transitions for stochastic block models and reconstruction on trees, Ann.
Probab. 53 (2025) 967-1018. The four-state critical behavior had earlier
been predicted by cavity methods; the typology in Ricci-Tersenghi,
Semerjian, and Zdeborova, Typology of phase transitions in Bayesian
inference problems, Phys. Rev. E 99 (2019) 042109,
doi:10.1103/PhysRevE.99.042109, covers those predictions.
./pdfs/mss2025.pdf
./pdfs/rtsz2019.pdf
Why is d lambda^2 the threshold, and why is the boundary case subtle?
The quadratic information of p is
A(p) = 4 sum_{i=1}^4 (p_i - 1/4)^2 = | L p |^2,
where L is the 3x4 matrix with rows (1,1,-1,-1), (1,-1,1,-1),
(1,-1,-1,1). Then A(u) = 0 at the uniform vector, A(e_i) = 3 at each
point mass, and hence A(p) in [0,3]. A channel edge acts by
C_lambda(p) = u + lambda (p - u),
which scales the deviation linearly, so A(C_lambda(p)) = lambda^2 A(p).
Concatenating d independent branches multiplies the mean of A by
d lambda^2. When d lambda^2 < 1 the mean decays geometrically; when
d lambda^2 > 1 it can persist on trees of positive survival probability.
At d lambda^2 = 1 the mean is conserved at leading order, and decay must
come from a genuinely nonlinear effect.
The relevant object is not an individual posterior vector but the law of
such vectors. An experiment is a uniform input I in {1,2,3,4} together
with an observation Y. Write kappa_i for the conditional law of Y given
I = i, and kappa = (1/4) sum_i kappa_i. The posterior vector satisfies
p_i(y) = (1/4) (d kappa_i / d kappa)(y),
and the law mu of p(Y) has barycenter integral p_i dmu = 1/4.
Conversely every probability law on the simplex Delta_4 with that
barycenter arises from some experiment. Call mu symmetric if it is
invariant under coordinate permutations. Three operations act on
symmetric posterior laws. A channel edge pushes mu forward by C_lambda,
which preserves symmetry and multiplies A by lambda^2. A Bayes product
combines two conditionally independent experiments about the same input:
for p, q in Delta_4 set U_i = 4 p_i q_i, z = sum_i U_i, and P = U/z when
z > 0, P = u when z = 0. The product law mu star nu is characterized by
integral f(r) d(mu star nu)(r)
= integral z(p,q) f(P(p,q)) dmu(p) dnu(q)
for every bounded measurable f, and it is symmetric when mu and nu are.
The definition uses p and q as independent with laws mu, nu before
multiplying by the density z, which is exactly what makes nonlinear
statistics tractable. An observed mixture is a third operation: if an
observed index S independent of the input has conditional posterior law
mu_s, the mixed posterior law is integral mu_s dPr(S=s). Symmetry and any
linear inequality in the law are preserved by such mixtures. This is
Bayes' rule in posterior-vector notation; an extended treatment on trees
is in Mezard and Montanari (2006).
./pdfs/mm2006.pdf
A higher statistic is required at the critical line. Define
B(p) = x_1 x_2 x_3, C(p) = x_1^2 x_2^2 + x_1^2 x_3^2 + x_2^2 x_3^2,
with x = L p. Each of A, B, C is invariant under coordinate permutation,
because a permutation acts on x by permuting coordinates and changing an
even number of signs. Fix three further permutation-invariant
polynomials H, F, G by their coefficient tables, whose entries are in
thousandths:
polynomial | 1 A B A^2 C AB A^3 AC B^2
-----------+--------------------------------------------------------------------
H | 0 0 +1000 -100 -150 +300 -20 +70 -510
F | 0 +4000 -3000 +700 -4000 -800 0 0 0
G |+1000 -1610 -3100 +773 +4000 -3980 0 0 0
For example,
H = B - A^2/10 - 3C/20 + 3AB/10 - A^3/50 + 7AC/100 - 51B^2/100.
Pointwise, H can be negative: for p = (1/2,1/2,0,0) one finds
H(p) = -3/25. The proof will use only the average of H over a posterior
law, not its pointwise sign. For p, q in Delta_4 and a permutation pi of
four letters, set
U^pi_i = 4 p_i q_{pi(i)}, z_pi = sum_i U^pi_i, P^pi = U^pi / z_pi,
with P^pi = u when z_pi = 0. For a continuous phi on Delta_4, the Sym_4
average is
[z phi(P)](p,q) = (1/24) sum_{pi in Sym_4} z_pi phi(P^pi).
Finally set D_0(p,q) = A(p) A(q) (A(p) + A(q)) / 1000.
PROPOSITION 1 (polynomial inequalities). For every p, q in Delta_4,
F(p) >= 0, G(p) >= 0, H(p) >= -1/2,
and for 0 <= t <= 1 and x = L p,
H(t x) >= t^3 H(x).
Moreover
[z A(P)](p,q) <= A(p) + A(q) - H(p) F(q) - F(p) H(q) - D_0(p,q), (i)
[z H(P)](p,q) >= H(p) G(q) + G(p) H(q). (ii)
The single-posterior inequalities come from a positive-coefficient
certificate on an ordered simplex; the two-posterior inequalities come
from a signed-coefficient certificate on a finite subdivision. Both are
exact computations. Prior exact-computation methods for the same
non-reconstruction problem are the survey method of Bhatnagar and Maneva,
A computational method for bounding the probability of reconstruction on
trees, SIAM J. Discrete Math. 25 (2011) 854-871, doi:10.1137/090751244,
and the population-dynamics method of Gu, Exact reconstruction thresholds
on hypertrees over a symmetric binary alphabet, arXiv:2606.21699 (2026);
neither covers the low-degree four-state case.
./pdfs/bm2011.pdf
./pdfs/gu2026.pdf
The proof uses a linear condition on the posterior law. Let C be the
class of symmetric posterior laws mu with E_mu[H] >= 0. The condition is
linear in mu and does not demand H(p) >= 0 pointwise. Both boundary laws
lie in C:
H(e_i) = 13/100 for i = 1,2,3,4, H(u) = 0.
PROPOSITION 2 (closure and moment saving). The class C is preserved by
channel steps with lambda in [0,1], by Bayes products of conditionally
independent experiments, and by observed mixtures whose mixing label is
independent of the input. If mu, nu are in C, then
E_{mu star nu}[A] <= E_mu[A] + E_nu[A]
- ( E_mu[A^2] E_nu[A] + E_mu[A] E_nu[A^2] ) / 1000.
In particular, when E_mu[A] = E_nu[A] = b the subtracted term is at least
2 b^3 / 1000.
Proof. For a channel step, x = L p is scaled by lambda. The scaling
inequality of Proposition 1 gives E[H(lambda x)] >= lambda^3 E[H(x)] >= 0,
and symmetry is automatic. For a Bayes product, symmetry of nu allows
replacing z phi(P) by its Sym_4 average, so (ii) integrates to
E_{mu star nu}[H] >= E_mu[H] E_nu[G] + E_mu[G] E_nu[H]; the right side is
nonnegative because G >= 0 pointwise and both H-expectations are
nonnegative. Integration of (i) gives
E_{mu star nu}[A] <= E_mu[A] + E_nu[A] - E_mu[H] E_nu[F]
- E_mu[F] E_nu[H] - E[D_0],
and the two F-terms are discarded because F >= 0 and mu, nu in C.
Expanding E[D_0] and using A >= 0 with Jensen's inequality
E_mu[A^2] >= (E_mu[A])^2 and E_nu[A^2] >= (E_nu[A])^2 gives the stated
bound. For an observed mixture, conditioning on an independent observed
label leaves the uniform prior unchanged, so both symmetry and the linear
inequality E[H] >= 0 pass through. QED.
Earlier entropy-based non-reconstruction criteria for Galton-Watson trees
are in Formentin and Kulske, A symmetric entropy bound on the
non-reconstruction regime of Markov chains on Galton-Watson trees,
Electron. Commun. Probab. 14 (2009) 587-596, doi:10.1214/ECP.v14-1516.
Second moment at the level of expectations is used instead; the retained
polynomial constraint replaces an entropy inequality at the critical line.
./pdfs/fk2009.pdf
The tree is now analysed by tracking the mean of A at successive levels.
Order the children at every vertex. In the Poisson tree, sample the
offspring independently at each vertex and number the children
1, ..., D_v; erasing the order recovers the unlabelled tree. Let T_hat
be the ordered tree, T_hat_{<= n} its truncation at depth n,
Y_n = (T_hat_{<= n}, (sigma_v)_{v in L_n}), and p^(n)_i = Pr(sigma_rho = i
| Y_n). Set mu_n = law of p^(n) and m_n = E_mu_n[A]. Two information
comparisons are needed. Conditional on the truncated tree, the part of
the tree below depth n is independent of the root and of Y_n, so revealing
the full ordered tree does not change the posterior:
Pr(sigma_rho = i | T_hat, sigma_{L_n}) = p^(n)_i almost surely.
Forgetting the order cannot increase expected total variation. If
observation sigma-fields satisfy F_1 subset F_2, the posterior given F_1
is the conditional expectation of the posterior given F_2, and the
total-variation norm is convex; therefore
a_n(d, lambda) <= (1/2) E[ sqrt(A(p^(n))) ] <= (1/2) sqrt(m_n).
The problem reduces to m_n -> 0.
PROPOSITION 3 (moment recursion). In either tree family, mu_n is
symmetric and E_mu_n[H] >= 0 for every n >= 0. If D is the offspring
count (equal to d in the regular tree, Poisson(d) in the Galton-Watson
tree), then
m_{n+1} <= d lambda^2 m_n - (2/1000) Pr(D >= 2) (lambda^2 m_n)^3.
Proof. At depth zero the informative law places mass 1/4 on each of the
four point masses, is symmetric, and has H-expectation 13/100 > 0.
Assume mu_n in C. Conditional on D = k, each child contributes the
branch law (C_lambda)_* mu_n, which is in C with mean A equal to
b = lambda^2 m_n. Combining the first two branches by the Bayes product
preserves C and gives mean A at most 2 b - 2 b^3/1000 by the moment
saving. Each further branch adds at most b, and the degenerate cases
k = 0, 1 give mean A equal to 0, b. Mixing over D preserves C. The
claim follows by linearity. QED.
Proof of the theorem. For lambda = 0 the branch observation is
independent of the root and m_n = 0 for n >= 1. Assume lambda > 0 and
d lambda^2 <= 1. In the d-ary family Pr(D >= 2) = 1 and d >= 2, so
0 <= m_{n+1} <= m_n - (2 lambda^6 / 1000) m_n^3.
The sequence m_n is nonincreasing and nonnegative, so it converges to
some ell >= 0. Passing to the limit gives ell <= ell - 2 lambda^6 ell^3 /
1000, hence ell = 0. In the Poisson(d) family
Pr(D >= 2) = 1 - (1+d) e^{-d}, which is strictly positive for every d > 0,
so the same argument applies with the positive coefficient
2 lambda^6 (1 - (1+d) e^{-d}) / 1000. The critical case d lambda^2 = 1
is thus included; the cubic term, absent from the linear approximation,
forces the decay. Finally a_n <= (1/2) sqrt(m_n) tends to 0. QED.
It remains to prove Proposition 1.
The single-posterior inequalities are checked on the ordered simplex
S = { p in Delta_4 : p_1 >= p_2 >= p_3
>= p_4 }, with vertices S_i = (e_1 + ... + e_{i+1})/(i+1) for i = 0, 1,
2, 3. In barycentric coordinates X_i = (i+1)(p_{i+1} - p_{i+2}), with
p_5 = 0, every p in S is sum_i X_i S_i with X_i >= 0 and sum_i X_i = 1.
A coordinate permutation acts on x = L p by permuting coordinates and
changing an even number of signs, so A, B, C and hence H, F, G are
permutation-invariant. It is enough to prove the single-posterior
inequalities on S.
Coefficient positivity is the criterion. For r >= 0, let I_r = { I in (Z_{>=0})^4 :
|I| = r }, X^I = prod_i X_i^{I_i}, and W_r = (sum_i X_i)^r. A polynomial
of degree at most r is homogenized to degree r by multiplying each
degree-s monomial by W_{r-s}. Its values on the simplex are unchanged,
and if every ordinary homogeneous coefficient is nonnegative, the
polynomial is nonnegative on the simplex. The simplicial Bernstein
coefficients equal the ordinary homogeneous coefficients times positive
multinomial factors, so their sign pattern agrees; this is the
coefficient-certificate principle behind simplicial Bernstein bounds and
their refinement by subdivision, due to Leroy, Convergence under
subdivision and complexity of polynomial minimization in the simplicial
Bernstein basis, Reliable Computing 17 (2012) 11-21.
On S the coordinate map is
L (sum_i X_i S_i) = ( X_0 + X_1 + X_2/3, X_0 + X_2/3, X_0 - X_2/3 ),
linear in (X_0, X_1, X_2). A degree-e monomial in x becomes, after
homogenization, a degree-e polynomial in (X_0, X_1, X_2, X_3). The four
target polynomials on S are H + 1/2 (degree 6), F (degree 5), G
(degree 14), and (3 - E)H (degree 6), where E = sum_{j=1}^3 x_j d/dx_j is
the Euler operator. Coefficient expansion gives the following exact
minima over S:
polynomial degree coefficients minimum
---------------+--------+-------------+---------
H + 1/2 | 6 | 84 | 19/50
F | 5 | 56 | 0
G | 14 | 680 | 87/1000
(3 - E) H | 6 | 84 | 0
The first three lines give H + 1/2 >= 0, F >= 0, G >= 0 on Delta_4 by
permutation invariance. The fourth gives (3 - E)H >= 0 on L Delta_4.
For x in L Delta_4 and 0 < ell <= 1 the point ell x is also in L Delta_4
(it corresponds to ell p + (1 - ell) u), and therefore
d/d ell ( ell^{-3} H(ell x) ) = ell^{-4} (E - 3) H(ell x) <= 0.
Comparing with ell = 1 gives H(ell x) >= ell^3 H(x), and at ell = 0 this
is H(0) = 0. This proves all four single-variable inequalities and the
scaling inequality.
For a pair of posterior vectors p, q, each of the two-posterior inequalities is
equivalent to R >= 0 with
R = K + sum_{pi in Sym_4} N_pi / z_pi^k,
where the row data (k, N_pi, m) are, for the first and second row of
Proposition 1 under the change of variables U^pi_v = 4 p_v q_{pi(v)},
z_pi = sum_v U^pi_v, P^pi = U^pi/z_pi,
row k N_pi m
---- -- --------------------------- ----
a 1 -sum_{j=1}^3 (L U^pi)_j^2 3
b 5 z_pi^6 H(U^pi / z_pi) 1/2
with K_a = 24(A(p) + A(q) - H(p)F(q) - F(p)H(q) - D_0(p,q)) and
K_b = -24(H(p)G(q) + G(p)H(q)). The sum runs over the 24 permutations.
Because A(P^pi) and H(P^pi) are bounded on Delta_4, each summand
N_pi / z_pi^k tends to 0 as z_pi -> 0, so R has a continuous extension
across the apparent singularity.
The certificates operate on a product of subsimplices. Take nondegenerate
subsimplices of S with vertex lists a = (a_0, a_1, a_2, a_3) and
b = (b_0, b_1, b_2, b_3) and substitute
p = sum_i X_i a_i, q = sum_j Y_j b_j, X, Y in Delta_4.
The coefficients of U^pi_v in the monomial basis X^I Y^J are
4 (a_i)_v (b_j)_{pi(v)}, hence nonnegative, so the coefficients of z_pi
are nonnegative. A full-dimensional four-vertex simplex cannot lie in a
coordinate face of Delta_4, so every z_pi is strictly positive in the
interior of the subsimplex product.
The type-T certificate uses the Taylor expansion of z^{-k}. Define
t_k(z) = sum_{i=0}^5 binom(-k, i)(z - 1)^i.
Taylor's theorem gives, for every z > 0,
z^{-k} - t_k(z) = (k(k+1)...(k+5)/6!) xi^{-k-6} (z - 1)^6 >= 0,
with xi between 1 and z; at z = 1 both sides vanish. On row a, A(P) <= 3,
so N_pi + m z_pi^{k+1} >= 0 with m = 3. On row b, H(P) >= -1/2 by the
single-posterior inequality, so N_pi + m z_pi^{k+1} >= 0 with m = 1/2.
In either row, multiply by t_k and subtract m z_pi:
N_pi / z_pi^k >= (N_pi + m z_pi^{k+1}) t_k(z_pi) - m z_pi.
Summing over pi gives R >= T with
T = K + sum_pi ( (N_pi + m z_pi^{k+1}) t_k(z_pi) - m z_pi ).
If T has no negative homogeneous coefficient in bidegree (k+6, k+6), then
R >= 0 on the product subsimplex.
The type-P certificate uses interpolation. Choose bihomogeneous J_pi of
bidegree (3,3). On the
relative interior of the product, N_pi / z_pi^k >= J_pi - c_pi is
equivalent to N_pi - z_pi^k J_pi + c_pi z_pi^k >= 0. Form, in
bidegree (k+3, k+3),
O_pi = W_2 N_pi - z_pi^k J_pi, Q_pi = z_pi^k W_3.
Every coefficient of Q_pi is nonnegative. Fix M = 2^32, and if a negative
coefficient (O_pi)_{IJ} occurs where (Q_pi)_{IJ} = 0, declare failure;
otherwise set
c_pi = (1/M) max( {0} union { ceil(-M (O_pi)_{IJ} / (Q_pi)_{IJ})
: (O_pi)_{IJ} < 0 } ).
By construction O_pi + c_pi Q_pi has nonnegative coefficients. On the
interior,
N_pi / z_pi^k = J_pi - c_pi + (O_pi + c_pi Q_pi)/z_pi^k
>= J_pi - c_pi.
If K + sum_pi (J_pi - c_pi W_3) has nonnegative homogeneous coefficients
in bidegree (6,6), then R >= 0 on the product subsimplex.
The interpolation uses degree-three cardinal polynomials. For I in I_3
with |I| = 3, define
ell_I(X) = prod_{i=0}^3 binom(3 X_i, I_i),
binom(t,j) = t(t-1)...(t-j+1)/j!, binom(t,0) = 1.
At the lattice point J/3 with J in I_3, ell_I(J/3) = 1 if I = J and 0
otherwise, so these interpolate any degree-three polynomial on the
three-dimensional simplex. In coefficient arrays each linear factor
3 X_i - h is written as 3 X_i - h sum_j X_j, giving the homogeneous
degree-three forms. Let trunc_M denote truncation toward zero to a
multiple of 1/M, and set
J_pi(X, Y) = sum_{I, J in I_3} trunc_M( N_pi(I/3, J/3) /
z_pi(I/3, J/3)^k )
ell_I(X) ell_J(Y).
At every rational vertex list in the subdivision, N_pi / z_pi^k takes rational values
(zero where z_pi = 0), so the coefficients of J_pi are exact rationals.
The type-P lemma does not estimate interpolation error; it certifies the
actual interpolant.
The finite subdivision covers S x S by cells. A cell is a pair (a, b) of
affinely independent four-vertex lists in S, with domain conv(a) x
conv(b). Start at a = b = (S_0, S_1, S_2, S_3). On a cell substitute
p = sum_i X_i a_i and
q = sum_j Y_j b_j. Replacing a single vertex a_i by (a_i + a_j)/2 with
i != j, and leaving all other vertices fixed, produces one child; the
analogous replacement for a_j produces the other child. For an ordinary
homogeneous coefficient indexed by I in I_r, its contributions to the new
coefficients are indexed by
I + t e_i - t e_j, 0 <= t <= I_j, multiplier 2^{-I_i - t} binom(I_j, t).
The two children cover the parent cell because the barycentric change of
variables X_i = X_i'/2, X_j = X_j' + X_i'/2 has nonzero determinant. The
same construction applies with b in place of a.
At each cell: (1) run the type-T test of the row; accept on success.
(2) If neither a nor b contains u = (1/4,1/4,1/4,1/4), run the
type-P test with M = 2^32; accept on success, abort on undefined
c_pi. (3) If neither test succeeds and the depth equals 24, abort.
(4) Otherwise choose the pair (y in {0,1}, i > j) maximizing
lexicographically
( w(i,j), y, i, j ), w(i,j) = |c_i - c_j|^2 * (16 if c_i = u or
c_j = u else 1),
where c = a for y = 0 and c = b for y = 1, and c_i, c_j are treated as
rational vectors. Replace vertex j of c by the midpoint (c_i + c_j)/2
and recurse; then replace vertex i by the midpoint and recurse on the
sibling. The uniform vertex u is detected exactly as the unique point of
S whose fourth coordinate equals 1/4.
The exact-rational check, run once per row, terminates without failure
and returns the counts
row cells visited max depth type-T leaves type-P leaves unresolved
---- ------------- --------- ------------- ------------- ----------
a 4479 19 166 2074 0
b 1935 20 97 871 0
Each terminal cell is accepted by the type-T or type-P test, and the
subdivision covers S x S. Hence R >= 0 on S x S in both rows. Combined
with the single-posterior coefficient checks, this proves Proposition 1.
Together with the moment recursion, it settles the exact reconstruction
threshold in both families of the theorem.