Robust reconstruction on trees is determined by the second eigenvalue

Svante Janson Uppsala University Elchanan Mossel U.C. Berkeley

October 14, 2002; revised December 3, 2003

Abstract

Consider a Markov chain on an infinite tree T = (V, E) rooted at ρ. In such a chain, once the initial root state σ(ρ) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let μ_{j} denote the resulting measure for σ(ρ) = j. μ_{j} is defined on configurations σ = (σ(x))_{x∈V} ∈ A^{V}, where A is some finite set. Let μ_{j}^{n} denote the restriction of μ to the sigma-algebra generated by the variables σ(x) where x is at distance exactly n from ρ. Letting α_{n} = max_{i,j∈A} d_{T V} (μ_{i}^{n}, μ_{j}^{n}), where d_{T V} denotes total variation distance, we say that the reconstruction problem is solvable if lim inf_{n→∞} α_{n} > 0. Reconstruction solvability roughly means that the n’th level of the tree contains a non-vanishing amount of information on the root of the tree, as n → ∞.

In this paper we study the problem of robust reconstruction. Let ν be a non degenerate distribution on A and ϵ > 0. Let σ be chosen according to μ_{j}^{n} and σ′ be obtained from σ by letting for each node independently σ(v) = σ′(v) with probability 1 − ϵ and σ′(v) to be an independent sample from ν otherwise. We denote by μ_{j}^{n}[ν, ϵ] the resulting measure on σ′. The measure μ_{j}^{n}[ν, ϵ] is a perturbation of the measure μ_{j}^{n}. Letting α_{n}(ν, ϵ) = max_{i,j∈A} d_{T V} (μ_{i}^{n}[ν, ϵ], μ_{j}^{n}[ν, ϵ]), we say that the reconstruction problem is ν-robust-solvable if lim inf_{n→∞} α_{n}(ν, ϵ) > 0 for all 0 < ϵ < 1. Roughly speaking, the reconstruction problem is robust-solvable if for any noise-rate and for all n, the n’th level of the tree contains a non-vanishing amount of information on the root of the tree.

Standard techniques imply that if T is the rooted B-ary tree (where each node has B children) and if B|λ_{2}(M)|^{2} > 1, where λ_{2}(M) is the second largest eigenvalue of M (in absolute value), then for all non-degenerate ν, the reconstruction problem is ν-robust-solvable. We prove a converse and show that the reconstruction problem is not ν-robust-solvable if B|λ_{2}(M)|^{2} < 1. This proves a conjecture by the second author and Peres. We also consider other models of noise and general trees.

1 Introduction

In this paper we study the perturbative theory of reconstruction on trees, and show how it depends on the spectrum of the underlying Markov chain. In particular, we show that the threshold for “robust reconstruction” for the B-ary tree is B|λ_{2}(M)|^{2} = 1, where λ_{2}(M) denotes the eigenvalue of M which is the second largest in absolute value. In Section 3 we prove a similar threshold for general bounded degree trees, where B is replaced by the branching number of the tree br(T). We refer the reader to Subsection 1.2 and to [7, 3, 22, 21] for background.

1.1 Definitions and main results

We proceed with some formal definitions. Let T = (V, E, ρ) be a tree T with nodes V, edges E and root ρ ∈ V. We direct all edges away from the root, so that if e = (x, y) then x is on the path connecting ρ to y. Let d(·, ·) denote the graph-metric distance on T, and L_{n} = {v ∈ V : d(ρ, v) = n} be the n’th level of the tree. For x ∈ V and e = (y, z) ∈ E, we denote |x| = d(ρ, x), d(x, (y, z)) = max{d(x, y), d(x, z)} and |e| = d(ρ, e). The B-ary tree is the infinite rooted tree, where each vertex has exactly B children.

A Markov chain on the tree is a probability measure whose state space is A^{V}, where A is a finite set. Without loss of generality we assume that A = {1, …, q}. Assume first that T is finite and let M = (M_{i,j})_{i,j∈A} be a stochastic matrix. In this case the probability measure defined by M on T is given by

\overline{μ}_{ℓ}(σ) = 1_{\{σ(ρ)=ℓ\}} ∏_{(x,y)∈E} M_{σ(x),σ(y)}.  (1)

In other words in \overline{μ}_{ℓ}, the root state σ(ρ) satisfies σ(ρ) = ℓ and then each vertex iteratively chooses its state from the one of its parent by an application of the Markov transition rule given by M (and all such applications are independent). We can define the measure \overline{μ}_{ℓ} on an infinite tree too, by Kolmogorov’s extension theorem, but we will not need chains on infinite trees in this paper (see [7] for basic properties of Markov chains on trees).

Instead, for an infinite tree T, we let T_{n} = (V_{n}, E_{n}, ρ), where V_{n} = {x ∈ V : d(x, ρ) ≤ n}, E_{n} = \{e ∈ E : d(e, ρ) ≤ n\} and define \overline{μ}_{ℓ}^{n} by (1) for T_{n}. More explicitly,

\overline{μ}_{ℓ}^{n}(σ) = 1_{\{σ(ρ)=ℓ\}} ∏_{(x,y)∈E_{n}} M_{σ(x),σ(y)}.  (2)

We are particularly interested in the distribution of the states σ(x) for x ∈ L_{n}, the set of leaves in T_{n}. This distribution, denoted by μ_{k}^{n}, is the projection of \overline{μ}_{k}^{n} on A^{L_{n}} given by

μ_{k}^{n}(σ) = ∑\{\overline{μ}_{k}^{n}(\overline{σ}) : \overline{σ}|L_{n} = σ\}.  (3)

In this paper we are interested in perturbative theory of the above process. Below we give three definitions of perturbations of μ_{n}^{k} representing three different types of “noise”. We call a distribution ν on A = {1, …, q} non-degenerate, if ν(i) > 0, for all 1 ≤ i ≤ q.

In the general setting the perturbation is obtained by observing, for leaves x ∈ L_{n}, not the state σ(x) but a state (in a state space B possibly different from A) derived from σ(x) by another random choice (independently for all leaves). The extra choice can be described by a stochastic matrix N = (N_{i,j})_{i∈A,j∈B}; this defines a probability measure on A^{V_{n}} × B^{L_{n}} by

\overline{μ}[N]_{ℓ}^{n}(σ, τ) = 1_{\{σ(ρ)=ℓ\}} ∏_{(x,y)∈E_{n}} M_{σ(x),σ(y)} × ∏_{y∈L_{n}} N_{σ(y),τ(y)},  (4)

and the distribution of our observed states is the projection μ[N]_{ℓ}^{n} on B^{L_{n}} given by

μ[N]_{ℓ}^{n}(τ) = ∑_{σ} \overline{μ}[N]_{ℓ}^{n}(σ, τ).  (5)

We will mostly be interested in the following types of noise:

• Given k ≥ 0, define N = M^{k}. Here, for each leaf independently, k additional steps of the chain are performed. We write μ_{ℓ}^{n}[k] for μ_{ℓ}^{n}[N].

• Given a distribution ν on A, define N_{i,j} = (1−ϵ)1_{{i=j}}+ϵν_{j}. Here, for each leaf independently, with probability 1−ϵ, there is no noise; otherwise, the leaf state is chosen independently from anything else according to ν. We will write μ_{k}^{n}[ν, ϵ] for μ[N]_{ℓ}^{n}.

• Given 0 ≤ ϵ ≤ 1, we let N be an q × (q + 1) matrix defined by N_{i,i} = (1 − ϵ), N_{i,q+1} = ϵ and N_{i,j} = 0 otherwise. Here, for each leaf independently, the state at the leaf is deleted with probability ϵ (deletion is marked by q + 1). We write μ_{ℓ}^{n}[ϵ] for μ_{ℓ}^{n}[N].

Recall that for distributions μ and ν on the same space Ω the total variation distance between μ and ν is

D_{V} (μ, ν) = \frac{1}{2} ∑_{σ∈Ω} |μ(σ) − ν(σ)|.  (6)

Definition 1.1. • The reconstruction problem for the B-ary tree T and M is solvable if there

exist i, j ∈ A for which

lim inf_{n→∞} D_{V} (μ_{i}^{n}, μ_{j}^{n}) > 0.  (7)

• The reconstruction problem for the B-ary tree T and M is robust-solvable if for all k < ∞ there exist i, j ∈ A for which

lim inf_{n→∞} D_{V} (μ_{i}^{n}[k], μ_{j}^{n}[k]) > 0.  (8)

• Let ν be a non-degenerate distribution. The reconstruction problem for the B-ary tree T and M is ν-robust-solvable if for all ϵ < 1 there exist i, j ∈ A for which

lim inf_{n→∞} D_{V} (μ_{i}^{n}[ν, ϵ], μ_{j}^{n}[ν, ϵ]) > 0.  (9)

• The reconstruction problem for the B-ary tree T and M is erasure-robust-solvable if for all ϵ < 1 there exist i, j ∈ A for which

lim inf_{n→∞} D_{V} (μ_{i}^{n}[ϵ], μ_{j}^{n}[ϵ]) > 0.  (10)

Note that by taking ϵ = 0 in (9) or (10) we obtain the original reconstruction condition (7). The same is true if k = 0 in (8).

Let λ_{2}(M) denote the eigenvalue of M which has the second largest absolute value (λ_{2}(M) may be negative or non-real). In our main result we prove

Theorem 1.2. Consider an ergodic Markov chain on the B-ary tree such that B|λ_{2}(M)|^{2} < 1. Then

• The reconstruction problem is not robust-solvable. Moreover, there exists k^{∗} such that for all

k > k^{∗}

max_{i,j} lim_{n→∞} D_{V} (μ_{i}^{n}[k], μ_{j}^{n}[k]) = 0.  (11)

• For all non-degenerate ν, the reconstruction problem is not ν-robust-solvable. Moreover, for all non-degenerate ν, there exists ϵ^{∗} < 1 such that for all ϵ > ϵ^{∗},

max_{i,j} lim_{n→∞} D_{V} (μ_{i}^{n}[ν, ϵ], μ_{j}^{n}[ν, ϵ]) = 0.  (12)

• If all the entries of M are non-zero, then the reconstruction problem is not erasure-robust-solvable. Moreover, there exists an ϵ^{∗} < 1 such that for all ϵ > ϵ^{∗},

max_{i,j} lim_{n→∞} D_{V} (μ_{i}^{n}[ϵ], μ_{j}^{n}[ϵ]) = 0.  (13)

It is easy to see that the total variation distances in (11), (12) and (13) are monotone decreasing in k, ϵ and ϵ respectively

The following proposition follows immediately from [12] or from the proofs in [22]. Together with Theorem 1.2, it shows that the threshold for robust reconstruction is given by B|λ_{2}(M)|^{2} = 1.

Proposition 1.3. Consider an ergodic Markov chain on the B-ary tree where B|λ_{2}(M)|^{2} > 1. Then

• The reconstruction problem is robust-solvable,

• For all non-degenerate ν the reconstruction problem is ν-robust-solvable and

• The reconstruction problem is erasure-robust-solvable.

1.2 Discussion

The reconstruction problem was first studied in statistical physics [28, 9], where the problem was phrased in terms of extremality of the free measure for the Ising model on the (B + 1)-regular tree (Bethe lattice). It is not too hard to see (e.g. [3]) that the measure is non-extremal if and only if the reconstruction problem is solvable for the Markov chain on the B-ary tree with transition

probabilities given by the binary symmetric Markov chain: (\begin{matrix}1 − δ & δ \\ δ & 1 − δ \end{matrix}). δ is related to the

“inverse temperature” β by 1 − 2δ = tanh(2β). The equivalence between non-extremality of the free measure of a random field and reconstruction solvability of an associated Markov chain on the same tree holds under mild non-degeneracy conditions (see e.g. [18]).

In the past decade, the reconstruction problem re-appeared in many applications: In communication networks (see [3] and the references there), in noisy computation (a model introduced by von Neumann in [29], see [8, 4]) and in phylogeny (molecular evolution, see [5, 26] for general background) [27]. Most recently, it is shown that the reconstruction problem is of crucial importance to basic questions in phylogeny [20, 19, 23]. In all of these applications the interest is to find when is it possible to reconstruct some information on the root state from states at the leaves of a finite tree. In many of the applications it is natural to consider robust-reconstruction as the observed data goes via additional “noise mechanism”.

Solvability of the reconstruction problem is also closely related to mixing rate of Glauber dynamics on the tree. See [1, 16] where it is shown that non-solvability roughly corresponds to rapid mixing dynamics on the tree.

Determining if the reconstruction problem is solvable or not turns out to be very hard. Binary symmetric Markov chains is the only family for which the threshold for reconstruction solvability is known. Even here there is a generation gap between the proof of the lower-bound [9] and proofs of the upper bound [2] (see also [10] for a different proof, [3] for the result on a general trees and [24] for the critical case on general trees). For binary symmetric Markov chains on the B-ary tree the threshold for the reconstruction problem is given by B(1 − 2δ)^{2} = 1, or equivalently Bλ_{2}(M)^{2} = 1. For all other families of Markov chain, including q-ary symmetric Markov chain for q > 2 and general 2 × 2 Markov chains only bounds are known [22, 15, 16].

The threshold B|λ_{2}(M)|^{2} = 1 is also the threshold for “census-solvability” [22], where different nodes of L_{n} are indistinguishable (in other words, we only observe the “census” of level n). However, in general, it is not the threshold for reconstruction. Indeed, except for the binary symmetric channel we know of no family of chains for which B|λ_{2}(M)|^{2} = 1 is the threshold for reconstruction. Moreover, [18] shows that for asymmetric binary Markov chains (general stochastic 2 by 2 matrices) or symmetric Markov chains for q > 2 (where M_{i,j} = (1 − δ)1_{\{i=j\}} + \frac{δ}{q−1}1_{\{i≠j\}} for i, j ∈ \{1, …, q\}) the reconstruction problem is sometimes solvable even when B|λ_{2}(M)|^{2} < 1. In [18] there is also a construction of M with λ_{2}(M) = 0 for which the reconstruction problem is solvable for large B.

Why is determining the threshold for reconstruction hard? From the technical point of view a Markov chain on the tree corresponds to a recursion in some random variables ([2, 24, 16]). A natural way to analyze these recursions is to use a perturbative argument around the stationary distribution of the chain. The main problem is that the random variables we start with are atoms - far from the stationary distribution and that in general the recursions lack any convexity. For “robust-reconstruction” the problem is easier - as the recursions begin close to the stationary distribution.

Our proof is based on a new measure of discrepancy for a vector of distributions which is a weighted variant of the χ^{2} distance. We show that an application of the chain M contracts the discrepancy by a |λ_{2}(M)|^{2} factor, and that if the discrepancy is smaller than δ, then tensoring B copies of the distributions increases the discrepancy by a factor of at most B(1 + ϵ(δ)), where ϵ(δ) → 0, as δ → 0.

It is interesting to compare our results with the results of [25]. In [25] Pemantle and Steif study robust phase transition on trees. For a Gibbs measure on a tree we say that a robust phase transition occurs if the boundary conditions on a cutset have a non-vanishing effect on the root even when the interactions along the cutsets are made arbitrarily small but fixed (see [25] for exact definition). The main results of [25] give the exact threshold for robust phase transitions for general (bounded degree) trees for Potts and Heisenberg models in terms of the underlying model and the branching number (see [14]) of the tree.

Both in our result and in the results of [25], it is easier to analyze the “robust” problem than it is the original problem for similar reasons. In both cases the “non-robust” problem is hard to control without some convexity assumption, while the solution of “robust” problem allows the use of “local” arguments.

Moreover, like robust phase transition, robust reconstruction is a geometric property, i.e. for general bounded degree T, the threshold for robust-reconstruction depends only br(T) and |λ_{2}(M)|. Indeed, the proof of Theorem 3.3 combines the analysis of the new discrepancy measure introduced here, with some of the techniques developed in [25] for controlling recursions on general trees.

A natural open problem is to determine the behavior of robust-solvability in the critical case, where B|λ_{2}(M)|^{2} = 1. Our techniques shed no light on this problem. It is also interesting to try and remove the restriction that the entries of M are positive for (13) – see also Remark 2.10. Finally, in the proof presented for Theorem 3.3, for fixed M and ν, the bounds on ϵ and k are becoming weaker as br(T)|λ_{2}(M)|^{2} approaches 1 (i.e., ϵ → 1 and k → ∞). It is natural to ask if for given M, ν and K, there exist ϵ and k for which the result holds uniformly for all infinite trees T with br(T)|λ_{2}(M)|^{2} < 1.

Acknowledgment. This research was carried out during a visit to the Computation, Combinatorics and Probability program at the Isaac Newton Institute for Mathematical Sciences in Cambridge, U.K. The second author is supported by a Miller fellowship at U.C. Berkeley. We thank Yuval Peres for suggesting the 3rd open problem above.

2 Proof

Recall that we denote by M the transition matrix. In this section we will often multiply M from the right by a vector of functions / from the left by a vector of measures – in which case the resulting vector would also be a vector of functions / vector of measures.

Let 1 = (1, …, 1)^{t}, then clearly M1 = 1. Let v_{i} be the stationary probability of state i, and v = (v_{1}, …, v_{q}) the stationary distribution, so that vM = v. In the remainder of this section we will use a, b, c, … for column vectors, and u, v, w, … for row vectors. v will always denote the stationary distribution.

Note that if b is a column vector such that vb = 0, then vMb = vb = 0. In other words, the linear space v^{⊥} = {b ∈ ℝ^{q} : vb = 0} is invariant under M.

Lemma 2.1. Let b = (b_{1}, …, b_{q})^{t} be a vector such that b_{i} > 0 for all i. Then

∑_{i=1}^{q} \frac{v_{i}}{(Mb)_{i}} ≤ ∑_{i=1}^{q} \frac{v_{i}}{b_{i}} .

Proof. By Jensen,

\frac{1}{(Mb)_{i}} = \frac{1}{∑_{j} m_{i,j}b_{j}} ≤ ∑_{j} m_{i,j} \frac{1}{b_{j}} .

Hence,

∑_{i} \frac{v_{i}}{(Mb)_{i}} ≤ ∑_{i} ∑_{j} v_{i}m_{i,j} \frac{1}{b_{j}} = ∑_{j}(∑_{i} v_{i}m_{i,j})\frac{1}{b_{j}} = ∑_{j} \frac{v_{j}}{b_{j}} ,

as needed. ■

By looking at the Jordan form of M it is easy to see that

Lemma 2.2. Given ϵ > 0, there exists an Euclidean norm ∥ ∥ on v^{⊥} such that ∥Mb∥ ≤ (|λ_{2}(M)|+ ϵ)∥b∥ for all b ∈ v^{⊥}. ■

Let Q be the projection onto v^{⊥} defined by Qb = b − (vb)1 (note that vQb = vb − (vb)(v1) = 0 for all b).

Definition 2.3. Let ∥ ∥ be a Euclidean norm on v^{⊥}. Let ν = (ν_{1}, …, ν_{q}) be a vector of distributions on a common space. Let f = (f_{1}, …, f_{q}) be the vector of density functions with respect to a σ-finite measure μ, such that ν_{i} ≪ μ for every i. In other words, dν_{i} = f_{i}dμ for all i. We then define the discrepancy of the vector by

D_{∥ ∥}^{μ}(f) = ∫ ∥Qf∥^{2} ∑_{i=1}^{q} \frac{v_{i}}{f_{i}} dμ.

We also write D(ν) and D(f) for the discrepancy, without explicitly indicating the norm and reference measure.

Note the similarity between the discrepancy and the χ^{2}-distance. The χ^{2}-distance is known to be well behaved with respect to ℓ_{2} norms. Note that if f_{1} = … = f_{q}, then Qf = fQ1 = 0. Thus, Q projects into the orthogonal complement of the space where the discrepancy should be 0.

Lemma 2.4. D(ν) is independent of the reference measure μ; i.e., if f = (f_{1}, …, f_{q}) and g = (g_{1}, …, g_{q}) are such that dν_{i} = f_{i} dμ = g_{i} dμ̃ for all i, then D_{∥ ∥}^{μ}(f) = Dμ̃ ; ∥ ∥(g).

Proof. Assume that μ̃ ≪ μ. The general case then follows by considering the three reference measures μ, μ + μ̃, μ̃.

Since Q is linear and ∥ ∥ is Euclidean, we may write ∥Qb∥^{2} = ∑_{i,j=1}^{q} t_{i,j}b_{i}b_{j} for some t_{i,j} ∈ ℝ. Now

D^{μ}(f) = ∑_{r,i,j=1}^{q} v_{r}t_{i,j} ∫ \frac{f_{i}f_{j}}{f_{r}} dμ = ∑_{r,i,j=1}^{q} v_{r}t_{i,j} ∫ \frac{g_{i}g_{j} (\frac{dμ̃}{dμ})^{2}}{g_{r} \frac{dμ̃}{dμ}} dμ = ∑_{r,i,j=1}^{q} v_{r}t_{i,j} ∫ \frac{g_{i}g_{j}}{g_{r}} dμ̃ = Dμ̃(g).

■

Lemma 2.5. Let the norm ∥ ∥ on v^{⊥} satisfy ∥Mb∥ ≤ α∥b∥ for all b ∈ v^{⊥} and some constant α. Then D(Mf) ≤ α^{2}D(f) for all f as in Definition 2.3.

Proof. For all b,

MQb = M(b − (vb)1) = Mb − (vb)M1 = Mb − (vb)1 = Mb − (vMb)1 = QMb.

Therefore we have pointwise that

∥QMf∥^{2} = ∥MQf∥^{2} ≤ α^{2}∥Qf∥^{2}.  (14)

Now

D(Mf) = ∫ ∥QMf∥^{2} ∑_{i=1}^{q} \frac{v_{i}}{(Mf)_{i}} dμ

≤ α^{2} ∫ ∥Qf∥^{2} ∑_{i=1}^{q} \frac{v_{i}}{(Mf)_{i}} dμ  (15)

≤ α^{2} ∫ ∥Qf∥^{2} ∑_{i=1}^{q} \frac{v_{i}}{f_{i}} dμ = α^{2}D(f),  (16)

where (15) follows from (14), and (16) follows by Lemma 2.1. ■

Lemma 2.6. For every Euclidean norm ∥ ∥ on v^{⊥}, there exists a constant C = C(∥ ∥), such that

|∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1| ≤ CD(f),  (17)

for all i, j, k, where f and μ are as in Definition 2.3.

Proof. By Cauchy–Schwartz,

|∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1| = |∫ \frac{(f_{i} − f_{k})(f_{j} − f_{k})}{f_{k}} dμ| ≤ \sqrt{∫ \frac{|f_{i} − f_{k}|^{2}}{f_{k}} dμ}\sqrt{∫ \frac{|f_{j} − f_{k}|^{2}}{f_{k}} dμ}.

Therefore in order to prove the lemma, it suffices to prove that there exists a constant C such that for all i, j, k it holds that

∫ \frac{|f_{i} − f_{j}|^{2}}{f_{k}} dμ ≤ CD(f).  (18)

Note that

(Qb)_{i} − (Qb)_{j} = (b − (vb)1)_{i} − (b − (vb)1)_{j} = b_{i} − b_{j}.

Therefore for all b, it holds that, for some constant C_{ij},

|b_{i} − b_{j}| = |(Qb)_{i} − (Qb)_{j}| ≤ C_{ij}∥Qb∥.

Hence

∫ \frac{|f_{i} − f_{j}|^{2}}{f_{k}} dμ ≤ C_{ij}^{2} ∫ \frac{∥Qf∥^{2}}{f_{k}} ≤ \frac{C_{ij}^{2}}{v_{k}} D(f).

Now (18) follows by taking C = sup_{i,j,k} \frac{C_{ij}^{2}}{v_{k}}. ■

Given a σ-finite measure μ on a space X, we denote by μ^{⊗B} the product measure on X^{B} with marginals μ. Similarly, if f_{i} is a density of ν_{i} with respect to μ, write f_{i}^{⊗B} for the density of ν_{i}^{⊗B} with respect to μ^{⊗B}. Finally for f = (f_{1}, …, f_{q}), write f^{⊗B} = (f_{1}^{⊗B}, …, f_{q}^{⊗B}), and for ν = (ν_{1}, …, ν_{q}), write ν^{⊗B} = (ν_{1}^{⊗B}, …, ν_{q}^{⊗B}). We similarly use ⨂_{r=1}^{B} ν^{r} for the componentwise product of several vectors ν^{r} of measures.

Lemma 2.7. Let ∥ ∥ be an Euclidean norm on v^{⊥}, B ≥ 1 an integer and ϵ > 0. Then there exists a δ > 0 such that if ν^{1} = (ν_{1}^{1}, …, ν_{q}^{1}), …, ν^{B} = (ν_{1}^{B}, …, ν_{q}^{B}), satisfy D(ν^{i}) ≤ δ for 1 ≤ i ≤ B, then

D(⨂_{r=1}^{B}ν^{r}) ≤ (1 + ϵ)(D(ν^{1}) + ⋯ + D(ν^{B})).

In particular, given ϵ > 0, there exists a δ > 0 such that if ν = (ν_{1}, …, ν_{q}) satisfies D(ν) ≤ δ, then D(ν^{⊗B}) ≤ (1 + ϵ)BD(ν).

Proof. The second part of the lemma immediately follows from the first part. Choose a reference measure μ with ν_{i}^{r} ≪ μ for every i and r, and let f_{i}^{r} be the density dν_{i}^{r}/dμ.

As in Lemma 2.4, we may write ∥Qb∥^{2} = ∑_{i,j} t_{i,j}b_{i}b_{j}. Moreover, since ∥Q1∥^{2} = ∥0∥^{2} = 0, it follows that ∑_{i,j} t_{i,j} = 0. Hence

D(f) = ∫ ∥Qf∥^{2} ∑_{k=1}^{q} \frac{v_{k}}{f_{k}} dμ = ∑_{i,j,k} v_{k}t_{i,j} ∫ \frac{f_{i}f_{j}}{f_{k}} dμ = ∑_{i,j,k} v_{k}t_{i,j} (∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1) .  (19)

Substituting ⨂_{r=1}^{B} f^{r} in (19) we obtain, using the reference measure μ^{⊗B},

D (⨂_{r=1}^{B} f^{r}) = ∑_{i,j,k} v_{k}t_{i,j} (∫ \frac{⨂_{r=1}^{B} f_{i}^{r} ⨂_{r=1}^{B} f_{j}^{r}}{⨂_{r=1}^{B} f_{k}^{r}} dμ^{⊗B} − 1)  (20)

= ∑_{i,j,k} v_{k}t_{i,j} (∏_{r=1}^{B} (∫ \frac{f_{i}^{r}f_{j}^{r}}{f_{k}^{r}} dμ) − 1) .

Let C be chosen to satisfy (17) in Lemma 2.6, and C̃ = C ∑_{i,j} |t_{i,j}|. Let δ be chosen such that for all (x_{1}, …, x_{B}) ∈ [1 − Cδ, 1 + Cδ]^{B} it holds that

|∏_{r=1}^{B} x_{r} − 1 − ∑_{r=1}^{B}(x_{r} − 1)| ≤ \frac{ϵ ∑_{r=1}^{B} |x_{r} − 1|}{C̃}.  (21)

By Lemma 2.6, it follows that if D(f) ≤ δ, then for all i, j, k,

|∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1| ≤ CD(f) ≤ Cδ.

Therefore, it follows from (20) and (21) that

D (⨂_{r=1}^{B} f^{r}) ≤ ∑_{i,j,k,r} v_{k}t_{i,j} (∫ \frac{f_{i}^{r}f_{j}^{r}}{f_{k}^{r}} dμ − 1) + \frac{ϵ}{C̃} ∑_{i,j,k,r} v_{k}|t_{i,j}| |∫ \frac{f_{i}^{r}f_{j}^{r}}{f_{k}^{r}} dμ − 1|

= ∑_{r} D(f^{r}) + \frac{ϵ}{C̃} ∑_{i,j,k,r} v_{k}|t_{i,j}| |∫ \frac{f_{i}^{r}f_{j}^{r}}{f_{k}^{r}} dμ − 1|
≤ ∑_{r} D(f^{r}) + \frac{ϵ}{C̃} ∑_{i,j,k,r} v_{k}|t_{i,j}|CD(f^{r})  (22)
= (1 + ϵ) ∑_{r} D(f^{r}),

where inequality (22) follows from Lemma 2.6. ■

Lemma 2.8. Given a Euclidean norm ∥ ∥ on v^{⊥}, there exists a constant C(∥ ∥) < ∞ such that for any vector ν = (ν_{i})_{i=1}^{q} = (f_{i}dμ)_{i=1}^{q} of distributions we have

sup_{i,j} d_{T V} (ν_{i}, ν_{j}) = sup_{i,j} ∫ |f_{i} − f_{j}| dμ ≤ C\sqrt{D(f)},  (23)

where f = (f_{1}, …, f_{q}).

Proof. By Cauchy–Schwartz,

∫ |f_{i} − f_{j}| dμ ≤ \sqrt{∫ \frac{|f_{i} − f_{j}|^{2}}{f_{i}} dμ}\sqrt{∫ f_{i} dμ} = \sqrt{∫ \frac{|f_{i} − f_{j}|^{2}}{f_{i}} dμ},

and (23) follows from Lemma 2.6. ■

Lemma 2.9. • Let ∥ ∥ be a Euclidean norm on v^{⊥}. Let μ be a probability distribution on 1, …, q such that μ(i) > 0 for all i. Then for all δ > 0, there exists an ϵ^{∗} = ϵ^{∗}(δ) < 1 such that for any vector ν′ = (ν′_{1}, …, ν′_{q}) of probability distributions on 1, …, q and for all ϵ > ϵ^{∗}, if

ν = (1 − ϵ)(ν′_{1}, …, ν′_{q}) + ϵ(μ, …, μ),

then D(ν) ≤ δ.

• Let ∥ ∥ be a Euclidean norm on v^{⊥}. Let ν_{ℓ}^{(r)} be denote the ℓ’th row of M^{r}, i.e., the distribution of the chain given by M^{r}, after r steps starting at ℓ, and ν^{(r)} = (ν_{1}^{(r)}, …, ν_{q}^{(r)}). Then for all δ > 0, there exists an r^{∗} = r^{∗}(δ) such that if r ≥ r^{∗} then D(ν^{(r)}) ≤ δ.

• Let ∥ ∥ be an Euclidean norm on v^{⊥}. Let ν = (ν_{1}, …, ν_{q}) be a vector of probability measures such that for all 1 ≤ i, j ≤ q it holds that ν_{i}(j) > 0. Let ν^{ϵ} = (ν_{1}^{ϵ}, …, ν_{q}^{ϵ}) be a collection of probability measures on {1, …, q + 1} such that ν_{i}^{ϵ} = (1 − ϵ)ν_{i} + ϵν′, where ν′ is the delta measure on q + 1. Then for all δ > 0, there exists an ϵ^{∗} = ϵ^{∗}(δ) < 1 such that if ϵ > ϵ^{∗}, then D(ν^{ϵ}) ≤ δ.

Proof. For the first part of the lemma we use the representation of D(ν) as in (19) with respect to the measure μ. Let m = min{μ(1), …, μ(q)}, and observe that if dν_{i} = f_{i} dμ, then

f_{i} = \frac{dν_{i}}{dμ} = ϵ + (1 − ϵ)\frac{dν′_{i}}{dμ} ,

so

ϵ ≤ f_{i} ≤ ϵ + (1 − ϵ)/m,

and for all i, j, k,

\frac{f_{i}f_{j}}{f_{k}} ≤ \frac{(ϵ + (1 − ϵ)/m)^{2}}{ϵ} .

Hence by (19)

D(ν) ≤ (\frac{(ϵ + (1 − ϵ)/m)^{2}}{ϵ} − 1) ∑_{i,j} |t_{i,j}|,  (24)

and the right hand side of (24) converges to 0 as ϵ → 1.

The second part of the lemma follows from the first one as the ergodicity of M implies that for all i, ν_{i}^{(m)} converges to the stationary distribution of the chain as m → ∞.

The third part of the lemma is proven similarly to the first part. Let m = min_{i,j∈A} ν_{i}(j) and

μ^{ϵ} = ϵν′ + \frac{(1 − ϵ)}{q} ∑_{i=1}^{q} ν_{i}.

Note that if dν_{i}^{ϵ} = f_{i} dμ^{ϵ}, then m ≤ f_{i}(ℓ) ≤ q for 1 ≤ ℓ ≤ q and all i, and f_{i}(q + 1) = 1 for all i. It follows that for all i, j, k and 1 ≤ ℓ ≤ q,

\frac{m^{2}}{q} ≤ \frac{f_{i}(ℓ)f_{j}(ℓ)}{f_{k}(ℓ)} ≤ \frac{q^{2}}{m} and \frac{f_{i}(q+1)f_{j}(q+1)}{f_{k}(q+1)} = 1.

Moreover μ^{ϵ}(q + 1) = ϵ and μ^{ϵ}({1, …, q}) = 1 − ϵ, so for all i, j and k,

∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1 = ∫ (\frac{f_{i}f_{j}}{f_{k}} − 1) dμ ≤ (\frac{q^{2}}{m} − 1)(1 − ϵ).

Hence by (19)

D(ν^{ϵ}) = ∑_{i,j,k} v_{k}t_{i,j} (∫ \frac{f_{i}f_{j}}{f_{k}} dμ − 1) ≤ (\frac{q^{2}}{m} − 1)(1 − ϵ) ∑_{i,j} |t_{i,j}|  (25)

and the right hand side of (25) converges to 0 as ϵ → 1. ■

Proof of Theorem 1.2. The basic idea of the proof is that if μ[N]^{n} is the vector of probability measures (μ[N]_{1}^{n}, …, μ[N]_{q}^{n}) defined in (5), then we may write μ[N]^{n+1} in terms of μ[N]^{n} using the operator M and tensoring. This will allow us to bound discrepancies recursively. Let ρ_{1}, …, ρ_{B} be the B children of ρ in the B-ary tree. Write E_{n+1}(s) for the edges in E_{n+1} that are on the subtree rooted in ρ_{s} (formally, these are the edges of E_{n+1} that are connected to ρ only by paths going via ρ_{s}). Define L_{n+1}(s) similarly. Finally, for a configuration σ of the vertices at the first n level of the tree, let σ_{1}, …, σ_{B} denote the configurations restricted to the subtrees rooted at ρ_{1}, …, ρ_{B}. Then by (4) and (5)

μ[N]_{ℓ}^{n+1}(τ) = ∑_{σ} 1_{{σ(ρ)=ℓ}} ∏_{(x,y)∈E_{n+1}} M_{σ(x),σ(y)} ∏_{y∈L_{n+1}} N_{σ(y),τ(y)}

= ∏_{s=1}^{B} (∑_{ℓ′=1}^{q} M_{ℓ,ℓ′} ∑_{σ_{s}} 1_{{σ_{s}(ρ_{s})=ℓ′}} ∏_{(x,y)∈E_{n+1}(s)} M_{σ_{s}(x),σ_{s}(y)} ∏_{y∈L_{n+1}(s)} N_{σ_{s}(y),τ_{s}(y)})

= ∏_{s=1}^{B} (∑_{ℓ′=1}^{q} M_{ℓ,ℓ′}μ[N]_{ℓ′}^{n}(τ|L_{n+1}(s))) .  (26)

Note that the expression in the parenthesis in (26) is given by (M(μ[N]^{n}))_{ℓ}(τ|L_{n+1}(s)), the ℓ’th coordinate of the vector M(μ[N]^{n}). It is now easy to see that

μ[N]^{n+1} = (M(μ[N]^{n}))^{⊗B}.  (27)

We use (27) in order to bound discrepancies recursively.

The assumption B|λ_{2}(M)|^{2} < 1, implies by Lemma 2.2 that there exists an ϵ > 0 and a norm ∥ ∥ on v^{⊥} such that for all b ∈ v^{⊥}, it holds that ∥Mb∥ ≤ α∥b∥, where B(1 + ϵ)α^{2} ≤ 1 − ϵ. Let δ be chosen as to satisfy Lemma 2.7, so that if D(f) ≤ δ, then D(f^{⊗B}) ≤ B(1 + ϵ)D(f).

By Lemma 2.9 it follows that there exist a k^{∗} such that μ^{0} = (μ_{1}^{0}[k], …, μ_{q}^{0}[k]) satisfies D(μ^{0}) ≤ δ for all k ≥ k^{∗}. Write μ^{n} for (μ_{1}^{n}[k], …, μ_{q}^{n}[k]). Thus (27) implies that μ^{n+1} = (Mμ^{n})^{⊗B}. It now follows by Lemmas 2.7 and 2.5 that

D(μ^{n+1}) ≤ B(1 + ϵ)α^{2}D(μ^{n}) ≤ (1 − ϵ)D(μ^{n}).

Hence lim_{n→∞} D(μ^{n}) = 0. We therefore conclude from Lemma 2.8 that

lim_{n→∞} max_{i,j} d_{T V} (μ_{i}^{n}[k], μ_{j}^{n}[k]) = 0,

and (11) follows.

In order to prove (12), let ν be a non-degenerate measure and note that by Lemma 2.9 it follows that there exist a ϵ^{∗} < 1 such that μ^{0} = (μ_{1}^{0}[ν, ϵ], …, μ_{q}^{0}[ν, ϵ]) satisfies D(μ^{0}) ≤ δ for all ϵ > ϵ^{∗}. Now (12) follows similarly to (11).

The proof of (13) is similar. We look at μ^{1} = (μ_{1}^{1}[ϵ], …, μ_{q}^{1}[ϵ]). Note that (27) implies that μ^{1} = (Mμ^{0})^{⊗B}. Let ν = Mμ^{0}. Note that the vector ν satisfies for all i that ν_{i}(q + 1) = ϵ and ν_{i}(j) = (1 − ϵ)M_{i,j} otherwise.

Since all the entries of M are positive, it follows from Lemma 2.9 that for every δ′ > 0 there exists an ϵ^{∗} < 1 such that if ϵ > ϵ^{∗} then D(ν) ≤ δ′. We may now apply Lemma 2.7 and choose δ′ > 0 in such a way that

D(μ^{1}) = D(ν^{⊗B}) ≤ δ.

The rest of the proof is identical. ■

Remark 2.10. It is an interesting goal to extend (13) to general ergodic chains (where some of the entries of M may be zero). Above we proved this for the case where all the entries of M are positive.

The proof of Lemma 2.9 can easily be extended to the case when there exists an n such that the measures μ_{1}^{n}, …, μ_{q}^{n} all have the same support (in such a case one can prove that there exists a value of ϵ < 1 such that D(μ^{n}) ≤ δ by showing that for ϵ sufficiently large the measures μ_{i}^{n} have most of their mass on the atom (q + 1, …, q + 1) and bounded relative densities elsewhere). However, we do not know any simple characterizations of the matrices M for which this holds (it evidently depends only on the set of zero entries of M); nor we do believe that this property is necessary for non-erasure-robust-solvability.

3 General trees

Our result readily extend to general infinite bounded degree trees, where B is replaced by br(T), the branching number of the tree. In [6], Furstenberg introduced the notion of the Hausdorff dimension of a tree. Later, Lyons [13, 14] showed how many of the probabilistic properties of the tree are determined by this number which he named the branching number.

For our purposes it is best to define the branching number via cutsets. A cutset S for a tree T rooted at ρ, is a finite set of vertices separating ρ from ∞. In other words, a finite set S is a cutset, if every infinite self avoiding path from ρ intersects S. An antichain is a cutset that does not have any proper subset which is also a cutset.

We follow the notation of [25] and for a cutset S, write Ins(S) for the inside of S (the finite component of T \ S, containing the root ρ), Ins_{E}(S) for edges inside S (those edges (x, y) having x ∈ Ins(S)) and Out(S) for the outside of S (Out(S) = T \ (S ∪ Ins(S))).

Definition 3.1. The branching number of T is defined as

br(T) = inf{λ > 0 : inf_{cutsets S} ∑_{x∈S} λ^{−|x|} = 0}.

Note that

br(T) = inf{λ > 0 : inf_{antichains S} ∑_{x∈S} λ^{−|x|} = 0}.

By Min-Cut-Max-Flow, br(T) is also the supremum of the real numbers λ > 0, such that T admits a positive flow from the root to infinity, where on every edge e of T, the flow is bounded by λ^{−|e|}. It is shown in [14] that br(T)^{−1} is the critical probability for Bernoulli percolation on T. See [14] and [3] for equivalent definitions of br(T) in terms of percolation, cutset sums and electrical conductance. We note that br(T_{B}) = B for the B-ary tree T_{B}.

As in Section 1, the Markov chain on T is described by an |A|×|A| stochastic matrix M and the perturbations by an |A| × |B| stochastic matrix N. For B-ary trees we observed the process on the special antichains L_{n}; for general trees it seems more natural to consider arbitrary antichains. The distribution μ[N]_{ℓ}^{S} of the observed (perturbed) states on an antichain S in T is given by, extending (4) and (5),

μ[N]_{ℓ}^{S}(τ) = ∑_{σ} 1_{{σ(ρ)=ℓ}} ∏_{(x,y)∈Ins_{E}(S)} M_{σ(x),σ(y)} × ∏_{y∈S} N_{σ(y),τ(y)}.  (28)

We proceed by defining μ_{ℓ}^{S}, the measure μ_{ℓ}^{S}[k] for k ≥ 0, the measure μ_{ℓ}^{S}[ν, ϵ] for ϵ > 0 and nondegenerate distribution ν on A and μ_{ℓ}^{S}[ϵ]. This is done in exactly the same way as in the case of the B-ary tree, by choosing appropriate N’s in (28).

We say that the reconstruction problem is solvable if there exists i, j ∈ A for which

inf_{S antichain} D_{V} (μ_{i}^{S}, μ_{j}^{S}) > 0,

where μ_{ℓ}^{S} denotes the conditional distribution on σ_{S} given that σ(ρ) = ℓ. We similarly define the notions of robust-solvable, ν-robust-solvable and erasure-robust-solvable.

Remark 3.2. The definitions of solvability for general trees and B-ary tree are not compatible. If T is the B-ary tree, then solvability by Definition 1.1 involves only cutsets S = L_{n} and is therefore a weaker condition than solvability defined here which involves all antichains (same for robustsolvable etc.). However we will obtain the same threshold for robust-reconstruction under both definitions.

The proof of our main result extends to show that

Theorem 3.3. Consider an ergodic Markov chain on a rooted tree T such that br(T)|λ_{2}(M)|^{2} < 1. Then

• The reconstruction problem is not robust-solvable.

• For all non-degenerate ν, the reconstruction problem is not ν-robust-solvable.

• If all the entries of M are non-zero, then the reconstruction problem is not erasure-robust-solvable.

This proves that the threshold for robust reconstruction is given by br(T)|λ_{2}(M)|^{2} = 1 as the proof of Theorem 1.4 in [22] immediately generalizes to show that

Proposition 3.4. Consider an ergodic Markov chain on a tree T such that br(T)|λ_{2}(M)|^{2} > 1. Then the reconstruction problem is robust-solvable, for all non-degenerate ν the reconstruction problem is ν-robust-solvable and the reconstruction problem is erasure-robust-solvable.

We now turn to the proof of Theorem 3.3. The proof generalizes the proof of Theorem 1.2. For a vertex x of the rooted tree T we write T (x) for the subtree rooted at x, i.e. the subtree consisting of x and all of its descendents. We will use the following lemma from Pemantle and Steif [25].

Lemma 3.5 ([25, Lemma 3.3]). Assume that br(T) < g. Then for all ϵ > 0 there exists an anitchain S such that

∑_{x∈S} (\frac{1}{g})^{|x|} ≤ ϵ,  (29)

and for all y ∈ S ∪ Ins(S),

∑_{x∈S∩T (v)} (\frac{1}{g})^{|x|−|y|} ≤ 1.  (30)

Proof of Theorem 3.3. We will show that under the conditions of Theorem 3.3 the reconstruction problem is not robust-solvable.

Let S be an antichain and y ∈ S ∪ Ins(S). Consider the Markov chain on the subtree T (y), starting with state ℓ at y, and let μ[N]_{ℓ}^{y,S} be the distribution of the observed states on T (y) ∩ S. Thus,

μ[N]_{ℓ}^{y,S}(τ) = ∑_{σ} 1_{{σ(y)=ℓ}} ∏_{(x,z)∈Ins_{E}(S),x∈T (y),z∈T (y)} M_{σ(x),σ(z)} × ∏_{z∈T (y)∩S} N_{σ(z),τ(z)}.  (31)

We write μ[N]^{y,S} for (μ[N]_{1}^{y,S}, …, μ[N]_{q}^{y,S}). Note that μ[N]^{S} = μ[N]^{ρ,S} for any antichain S.

The proof of Theorem 1.2 easily extends to show that if y ∈ Ins(S) and z_{1}, …, z_{B} are the children of y then

μ^{y,S}[N] = ⨂_{r=1}^{B}(Mμ^{z_{r},S}[N]).  (32)

We will prove the theorem by recursively analyzing discrepancies via (32). We will prove the result for robust-solvability and indicate the modifications needed for other cases at the end of the proof.

Below, we will write μ^{y,S}[k] for the measure μ^{y,S}[N], where N = M^{k}. Note that if S is an antichain and v ∈ S, then the measure μ^{y,S} is a measure on a single node. We may therefore apply Lemma 2.9 and conclude that for all δ > 0 there exists a k^{∗} such that for k ≥ k^{∗}, for all antichains S and y ∈ S it holds that

D(μ^{y,S}[k]) ≤ δ.  (33)

Since br(T)|λ_{2}(M)|^{2} < 1, there exists by Lemma 2.2 an ϵ > 0 and a norm ∥ ∥ on v^{⊥} such that for all b ∈ v^{⊥}, it holds that ∥Mb∥ ≤ α∥b∥, where (1 + ϵ)br(T)α^{2} ≤ 1 − ϵ. Recall that there is a uniform bound K on the number of children of vertices of T. Let δ be chosen as to satisfy Lemma 2.7 for every B ≤ K, so that if D(f^{r}) ≤ δ for r = 1, …, B, and B ≤ K, then D(⨂_{r=1}^{B} f^{r}) ≤ (1 + ϵ) ∑_{r=1}^{B} D(f^{r}).

Lemma 3.5 implies that there exists a sequence of antichains S_{n} such that

lim_{n→∞} ∑_{x∈S_{n}}[(1 + ϵ)α^{2}]^{|x|} = 0,  (34)

and that for all n and y ∈ S_{n} ∪ Ins(S_{n}),

∑_{x∈S_{n}∩T (y)}[(1 + ϵ)α^{2}]^{|x|−|y|} ≤ 1.  (35)

We will now show by induction (on s−|y|, where s = max_{x∈S} |x|), that for all antichains S = S_{n} and all y ∈ S ∪ Ins(S), for k ≥ k^{∗},

D(μ^{y,S}[k]) ≤ δ ∑_{x∈S∩T (y)}[(1 + ϵ)α^{2}]^{|x|−|y|}.  (36)

The case where y ∈ S follows from (33). This also proves the base of the induction. For the induction step, it therefore suffices to consider y ∈ Ins(S) such that the children of v denoted z_{1}, …, z_{B} satisfy the induction hypothesis. By Lemma 2.5 and the induction hypothesis, for all r,

D(Mμ^{z_{r},S}[k]) ≤ α^{2}D(μ^{z_{r},S}[k]) ≤ δα^{2} ∑_{x∈S∩T (z_{r})}[(1 + ϵ)α^{2}]^{|x|−|z_{r}|}.  (37)

The right hand side of (37) is bounded by δ by (35), since α < 1. Therefore we may apply Lemma 2.7 with (32) and (37) to obtain

D(μ^{y,S}[k]) ≤ (1 + ϵ) ∑_{r=1}^{B} D(Mμ^{z_{r},S})  (38)

≤ (1 + ϵ)δα^{2} ∑_{r=1}^{B} ∑_{x∈S∩T (z_{r})}[(1 + ϵ)α^{2}]^{|x|−|z_{r}|}
= δ ∑_{x∈S∩T (y)}[(1 + ϵ)α^{2}]^{|x|−|y|}

proving (36).

Applying (36) for the root ρ and S_{n} we get by (34), taking n → ∞,

lim sup_{n→∞} D((μ_{1}^{ρ,S_{n}}[k], …, μ_{q}^{ρ,S_{n}}[k])) ≤ δ lim_{n→∞} ∑_{x∈S_{n}}[(1 + ϵ)α^{2}]^{|x|} = 0,

which implies by Lemma 2.8 that

max_{i,j} lim_{n→∞} D_{T V} (μ_{i}^{ρ,S_{n}}[k], μ_{j}^{ρ,S_{n}}[k]) = 0,

as needed.

The proofs for ν-robust-solvability is exactly the same. The proof for erasure-robust solvability requires the following modification.

First, as in the proof of Theorem 1.2, we may find ϵ^{∗} < 1 such that if ϵ > ϵ^{∗} and B ≤ K, then for all y which have B children z_{1}, …, z_{B} in a cutset S, it holds that D(μ^{y,S}[ϵ]) < δ (with δ as above).

If S is an antichain, let S′ denote the set of children of S. Note that S′_{n} is an antichain for all n. We prove by induction that for all antichains S = S_{n} and all y ∈ S ∪ Ins(S), for ϵ > ϵ^{∗},

D(μ^{y,S′}[ϵ]) ≤ δ ∑_{x∈S∩T (y)}[(1 + ϵ)α^{2}]^{|x|−|y|}.  (39)

The proof is again by induction on s − |y|, where s = max_{x∈S} |x|. The only difference is in that for y ∈ S, we use the estimate D(μ^{y,S′}[ϵ]) < δ. The remainder of the proof is the same. ■

References

[1] N. Berger, C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. Submitted. Extended abstract by Kenyon, Mossel and Peres appeared in [11], 2003.

[2] P. M. Bleher, J. Ruiz, and V. A. Zagrebnov. On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys., 79(1-2):473–482, 1995.

[3] W. S. Evans, C. Kenyon, Y. Peres, and L. J. Schulman. Broadcasting on trees and the Ising model. Ann. Appl. Probab., 10(2):410–433, 2000.

[4] W. S. Evans and L. J. Schulman. Signal propagation and noisy circuits. IEEE Trans. Inform. Theory, 45(7):2367–2373, 1999.

[5] J. Felsenstein. Inferring Phylogenies. Sinauer, New York, New York, 2003.

[6] H. Furstenberg. Intersections of Cantor sets and transversality of semigroups. In Problems in analysis (Sympos. Salomon Bochner, Princeton Univ., Princeton, N.J., 1969), pages 41–59. Princeton Univ. Press, Princeton, N.J., 1970.

[7] H. O. Georgii. Gibbs measures and phase transitions, volume 9 of de Gruyter Studies in Mathematics. Walter de Gruyter & Co., Berlin, 1988.

[8] B. Hajek and T. Weller. On the maximum tolerable noise for reliable computation by formulas. IEEE Transactions on Information theory, 37:388–291, 1991.

[9] Y. Higuchi. Remarks on the limiting Gibbs states on a (d + 1)-tree. Publ. Res. Inst. Math. Sci., 13(2):335–348, 1977.

[10] D. Ioffe. On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys., 37(2):137–143, 1996.

[11] C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. In Proceedings of the Forty-Second Annual Symposium on on Foundations of Computer Science, pages 568–578, 2001.

[12] H. Kesten and B. P. Stigum. Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Statist., 37:1463–1481, 1966.

[13] R. Lyons. The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys., 125(2):337–353, 1989.

[14] R. Lyons. Random walks and percolation on trees. Ann. Probab., 18(3):931–958, 1990.

[15] J. Martin. Reconstruction thresholds on regular trees. In C. Banderier and C. Krattenthaler, editors, Discrete Random Walks, Discrete Math. Theoret. Comput. Sci., pages 191–204. 2003.

    Availible at http://dmtcs.loria.fr/proceedings/dmACind.html.

[16] F. Martinelli, A. Sinclair, and D. Weitz. The ising model on trees: Boundary conditions and mixing time. Submitted to communication in mathematical physics. Extended abstarct appeared in [17], 2003.

[17] F. Martinelli, A. Sinclair, and D. Weitz. The ising model on trees: Boundary conditions and mixing time. In Proceedings of the Forty Fourth Annual Symposium on Foundations of Computer Science, pages 628–639, 2003.

[18] E. Mossel. Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Probab., 11(1):285–300, 2001.

[19] E. Mossel. On the impossibility of reconstructing ancestral data and phylogenies. Jour. Comput. Bio., 10(5):669–678, 2003.

[20] E. Mossel. Phase transitions in phylogeny. To appear in Trans. of AMS., 2003.

[21] E. Mossel. Survey: Information flow on trees. To appear, 2003.

[22] E. Mossel and Y. Peres. Information flow on trees. Ann. Appl. Probab., 13(3):817–844, 2003.

[23] E. Mossel and M. Steel. A phase transition for a random cluster model on phylogenetic trees. Submitted to Mathematical Biosciences, 2003.

[24] R. Pemantale and Y. Peres. Recursions on trees and the ising model at critical temperatures. Unpublished manuscript, 1995.

[25] R. Pemantle and J. E. Steif. Robust phase transitions for Heisenberg and other models on general trees. Ann. Probab., 27(2):876–912, 1999.

[26] C. Semple and M. Steel. Phylogenetics, volume 22 of Mathematics and its Applications series. Oxford University Press, 2003.

[27] E. Sober and M. A. Steel. Testing the hypothesis of common ancestry. Jour. Theor. Bio., 218:395–408, 2002.

[28] F. Spitzer. Markov random fields on an infinite tree. Ann. Probability, 3(3):387–398, 1975.

[29] J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata studies, Annals of mathematics studies, no. 34, pages 43–98. Princeton University Press, Princeton, N. J., 1956.

Svante Janson Department of Mathematics, Uppsala University P.O. Box 480 SE-751 06 Uppsala, Sweden

svante.janson@math.uu.se
http://www.math.uu.se/~svante

Elchanan Mossel Department of Statistics Evans Hall, University of California Berkeley, CA 94720-1776, U.S.A

mossel@stat.berkeley.edu
http://www.stat.berkeley.edu/~mossel