THE RECONSTRUCTION THRESHOLD FOR THE FERROMAGNETIC FOUR-STATE POTTS MODEL
A complete proof written to be read by high-school students
HOW TO READ THIS
This paper answers one yes/no question about a tree of random colors. The
question is: if you see the colors far away from the root, can you still tell
what color the root had? The answer changes sharply at
d * lambda^2 = 1.
Here d is the number of children per vertex (or the average number), and
lambda measures how faithfully a child copies its parent. This paper proves
that at and below the line d * lambda^2 = 1, the answer is no: the root
information fades away. Above the line, a classical theorem says the answer
is yes. So the line is exact.
The proof has two parts. Part I is probability. It is written out completely
in ordinary language and equations. Part II is a finite exact calculation.
That calculation checks a few polynomial inequalities. It uses only integer
and rational arithmetic, never floating point. A high-school reader can skip
Part II on a first reading, but the paper is complete only with it.
You do not need to know any advanced probability to start. Every symbol is
defined below, and there is a glossary at the end.
PART I. THE MODEL, THE RESULT, AND THE PROBABILISTIC PROOF
1. WHAT IS THE MODEL?
Let [4] = {1,2,3,4}. Think of these four numbers as four colors.
A rooted tree has a top vertex, called the root. Every vertex has some number
of children. Level n means the vertices exactly n steps below the root. We
use two kinds of trees.
Regular d-ary tree: every vertex has exactly d children. Here d >= 2.
Poisson(d) Galton-Watson tree: every vertex independently has k children
with probability
Pr(D = k) = e^(-d) * d^k / k!, k = 0,1,2,...
Here D is the number of children of a vertex, and d > 0 is the mean.
The root spin is a color chosen uniformly from [4]. Each edge independently
passes the parent color to the child by the channel
P_lambda(j | i) = lambda * 1_{i=j} + (1 - lambda)/4, i,j in [4].
The parameter lambda lies in [0,1]. If the parent color is i, then the child
color is i with probability
lambda + (1 - lambda)/4 = (1 + 3 lambda)/4,
and each of the other three colors with probability (1 - lambda)/4. Thus
lambda = 1 is a perfect copy, and lambda = 0 is completely random. The word
"ferromagnetic" means lambda >= 0, so copying is never discouraged.
The observer is given the whole tree T and all spins on level n,
written sigma_{L_n}. We want to know how much this tells the observer about
the root spin sigma_rho. The posterior probability of root color i is
p_i = Pr(sigma_rho = i | T, sigma_{L_n}).
The advantage is
a_n(d,lambda)
= E[ (1/2) * sum_{i=1}^4 | p_i - 1/4 | ].
The absolute value measures how far the posterior is from the uniform guess
1/4. The factor 1/2 makes the largest possible value equal to 1 - 1/4 = 3/4.
If a_n tends to 0, the root information is lost. That is called
nonreconstruction. If a_n does not tend to 0, it is called reconstruction.
For the Poisson tree, the observer sees the whole unlabelled tree T. The
expectation in a_n averages over the random tree as well as the random spins.
It is not conditioned on the tree surviving forever. If level n is empty,
then there are no observed spins, and the posterior is exactly uniform.
2. THE MAIN THEOREM
Theorem 1 (exact threshold). For the channel above, if
d * lambda^2 <= 1,
then
lim_{n -> infinity} a_n(d,lambda) = 0
in both models:
(a) the regular d-ary tree, for every integer d >= 2;
(b) the Poisson(d) Galton-Watson tree, for every real d > 0.
The equality case d * lambda^2 = 1 is included.
In this statement, d is the number of children or the mean number of
children. It is not the total undirected degree.
For d * lambda^2 > 1, the Kesten-Stigum theorem gives reconstruction. Thus
Theorem 1 supplies the missing nonreconstruction half and makes the threshold
exact. The theorem is computer assisted only in the polynomial-checking
part. Every probabilistic step is proved in the text below.
Why is the four-state case interesting? For the two-state (Ising) model the
threshold is classical. For the three-state model Sly proved sharpness for
large enough d. For five or more states sharpness can fail. The four-state
ferromagnetic model is the boundary case. Mossel, Sly, and Sohn proved
nonreconstruction for large mean degree. Theorem 1 removes the large-degree
restriction for the regular and Poisson families.
3. WHY THE LINE IS d * lambda^2 = 1
First forget the tree and look at one experiment. An experiment has a uniform
input I in [4] and an observation Y. Let mu be the probability law of the
posterior vector p(Y). Define
A(p) = 4 * sum_{i=1}^4 p_i^2 - 1.
This number is zero exactly at the uniform vector u = (1/4,1/4,1/4,1/4).
It is largest when p is a point mass, where A = 3. Also
A(p) = 4 * sum_{i=1}^4 (p_i - 1/4)^2,
so A is a quadratic measure of information.
If an experiment is passed through one channel edge, the posterior vector
changes by
C_lambda(p) = u + lambda * (p - u).
Therefore
A(C_lambda(p)) = lambda^2 * A(p).
If d independent branches are combined, the linear effect is to multiply the
expected A by d * lambda^2. So one expects information to die when
d * lambda^2 < 1 and to survive when d * lambda^2 > 1. At equality the linear
effect is exactly neutral, and a second-order effect decides the answer.
The main work of this paper is to prove that at equality the second-order
effect is a strict cubic saving. That saving forces the information to zero.
There is a second useful measure. Let
L =
[ 1 1 -1 -1 ]
[ 1 -1 1 -1 ]
[ 1 -1 -1 1 ]
and put x = L p. Then
A(p) = |x|^2 = x_1^2 + x_2^2 + x_3^2.
Also
0 <= A(p) <= 3,
and
(1/2) * sum_i |p_i - 1/4| <= (1/2) * sqrt(A(p)).
The last inequality is the Cauchy-Schwarz inequality. It means that if the
average of A tends to zero, then the advantage a_n tends to zero.
4. POSTERIOR EXPERIMENTS AND TWO OPERATIONS
An experiment is a uniform input I and an observation Y. Let kappa_i be the
law of Y given I = i, and let kappa = (1/4) sum_i kappa_i. The posterior
vector is
p_i(y) = (1/4) * (d kappa_i / d kappa)(y).
The law mu of p(Y) always satisfies
integral p_i dmu(p) = 1/4 for each i.
Conversely, any probability law on the simplex
Delta4 = { p in [0,1]^4 : sum_i p_i = 1 }
with this average can be realized by some experiment. We call mu symmetric
if it is unchanged when the four coordinates of p are permuted. Symmetry is a
property of the law, not of one particular vector p.
There are two operations on experiments.
Operation 1: pass through one edge. If mu is the posterior law for the child
spin, then the posterior law for the parent spin is the pushforward of mu by
C_lambda(p) = u + lambda * (p - u).
This operation preserves symmetry, and it multiplies A by lambda^2.
Operation 2: combine two conditionally independent experiments about the same
input. If their posterior vectors are p and q, define
U_i(p,q) = 4 p_i q_i,
z(p,q) = sum_{i=1}^4 U_i(p,q),
P_i(p,q) = U_i(p,q) / z(p,q) if z(p,q) > 0.
If z(p,q) = 0, set P(p,q) = u. The combined posterior law, written mu * nu,
is defined by
integral f(r) d(mu * nu)(r)
= integral z(p,q) f(P(p,q)) dmu(p) dnu(q)
for every bounded measurable f. The right side has total mass one. This is
Bayes' formula in posterior-vector language. If mu and nu are symmetric,
then mu * nu is symmetric. In the integral, p and q are independent with
laws mu and nu before the density z is applied. They are generally not
independent under the actual combined observation law.
We also use observed mixtures. If an index S is observed, is independent of
the input, and conditional on S = s the posterior law is mu_s, then the mixed
posterior law is integral mu_s dPr(S=s). Symmetry and any linear inequality
on posterior laws survive this operation. In the tree, S is the offspring
count D.
The completely informative experiment has posterior law putting mass 1/4 on
each of the four point masses e_1,e_2,e_3,e_4. The completely uninformative
experiment has posterior law concentrated at u.
5. THE EXTRA POLYNOMIAL H
The quadratic statistic A is not enough at the critical line. We need one
higher-order statistic. Using x = L p, 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.
These, like A, are unchanged by permuting the four entries of p. Now define
three polynomials H, F, G. The following table gives their coefficients.
Every entry in the table is divided by 1000.
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,
F = 4A - 3B + 7A^2/10 - 4C - 4AB/5,
G = 1 - 161A/100 - 31B/10 + 773A^2/1000 + 4C - 398AB/100.
The polynomial H is not nonnegative for every p. For example,
p = (1/2,1/2,0,0) gives H(p) = -3/25. The proof will use only the average
of H over a posterior law, not the pointwise sign of H.
For p,q in Delta4 and a permutation pi in the symmetric group S4, put
U_i^pi = 4 p_i q_{pi(i)},
z_pi = sum_{i=1}^4 U_i^pi,
P^pi = U^pi / z_pi if z_pi > 0.
For a continuous function phi on Delta4, define the permutation average
[z phi(P)](p,q)
= (1/24) * sum_{pi in S4} z_pi phi(P^pi),
with a summand set to zero when z_pi = 0. The average over S4 is present
because the law of q is symmetric: relabelling the four colors of q does not
change any expectation. Finally define
D_0(p,q) = A(p) A(q) (A(p) + A(q)) / 1000.
Proposition 2 (polynomial inequalities). For every p,q in Delta4:
(i) F(p) >= 0,
(ii) G(p) >= 0,
(iii) H(p) >= -1/2.
For x = L p and 0 <= t <= 1,
(iv) H(t x) >= t^3 H(x).
Moreover,
(v) [z A(P)](p,q)
<= A(p) + A(q) - H(p) F(q) - F(p) H(q) - D_0(p,q),
(vi) [z H(P)](p,q)
>= H(p) G(q) + G(p) H(q).
The rest of Part I shows how these six inequalities control the tree. Part II
proves Proposition 2 by exact arithmetic.
6. THE CONE OF GOOD POSTERIOR LAWS
Let C be the class of symmetric posterior laws mu such that
E_mu H(p) >= 0.
The condition is linear in the law mu. It does not say H(p) >= 0 for every
p. The two simplest laws belong to C. The completely informative law has
H(e_i) = 13/100 for i = 1,2,3,4,
and the completely uninformative law has
H(u) = 0.
Proposition 3 (closure and moment saving). The class C is preserved by:
(a) a channel step with lambda in [0,1];
(b) conditionally independent products of experiments;
(c) observed mixtures whose mixing label is independent of the input.
If mu and nu are in C, then their product law mu * nu satisfies
E_{mu*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, if E_mu A = E_nu A = b, then the subtracted term is at least
2 b^3 / 1000.
Proof. For a channel step, x = L p becomes lambda x. By (iv),
E H(lambda x) >= lambda^3 E H(x) >= 0.
Symmetry is preserved by C_lambda. This proves (a).
For a product, use the definition of mu * nu and Lemma 2(v). Since nu is
symmetric, we may replace z phi(P) by its S4-average. Integrating (vi) gives
E_{mu*nu} H
>= E_mu H * E_nu G + E_mu G * E_nu H >= 0,
because G >= 0 pointwise by (ii) and both H-expectations are nonnegative by
membership in C. This proves (b).
For a mixture, conditioning on an observed label independent of the input
leaves the uniform prior unchanged. The posterior law is the corresponding
mixture. Both symmetry and the linear inequality E H >= 0 are preserved.
This proves (c).
For the moment saving, integrate (v). Since F >= 0 and both H-expectations
are nonnegative, the two terms involving F can be dropped. The remaining
subtraction is exactly
E[ D_0(p,q) ]
= ( E_mu(A^2) E_nu A + E_mu A E_nu(A^2) ) / 1000.
If both means are b, then A >= 0 and Jensen's inequality gives
E_mu(A^2) >= b^2 and E_nu(A^2) >= b^2. Hence the subtraction is at least
2 b^3 / 1000. This proves Proposition 3.
7. THE RECURSION ON THE TREE
We now apply Proposition 3 to the tree. It is convenient to order the
children of every vertex. In the Poisson tree, give each vertex an
independent offspring count and number its children 1,2,... . Erasing the
numbering gives the unlabelled tree in Theorem 1. Write T_hat for the ordered
tree and T_hat_{<= n} for its truncation at depth n. Define
Y_n = ( T_hat_{<= n}, (sigma_v)_{v in L_n} ),
p_i^(n) = Pr(sigma_rho = i | Y_n).
Let mu_n be the law of p^(n), and put
m_n = integral A(p) dmu_n(p).
In the Poisson case this integral averages over the random tree as well as the
spins, without conditioning on survival.
Two information comparisons are needed. First, conditional on the truncated
tree, the part of the tree below depth n is independent of the root and of
all spins in Y_n. Therefore supplying the entire ordered tree does not
change the posterior:
Pr(sigma_rho = i | T_hat, sigma_{L_n}) = p_i^(n) almost surely.
Second, forgetting the ordering cannot increase expected total variation from
the uniform prior. Indeed, if one observation sigma-field is contained in
another, the smaller posterior is the conditional expectation of the larger
one, and the total-variation norm is convex. Combining this with the
Cauchy-Schwarz bound gives
a_n(d,lambda)
<= (1/2) E sqrt(A(p^(n)))
<= (1/2) sqrt(m_n).
So it is enough to prove m_n -> 0.
Proposition 4 (moment recursion). In either tree family, the posterior law
mu_n is symmetric and satisfies E H >= 0 for every n >= 0. Let D be the
# ^C interrupted by user!