Broadcasting on Bounded Degree DAGs
Anuran Makur∗ , Elchanan Mossel† , and Yury Polyanskiy∗

arXiv:1803.07527v1 [cs.IT] 20 Mar 2018

Abstract
We study the following generalization of the well-known model of broadcasting on trees. Consider
an infinite directed acyclic graph (DAG) with a unique source node X. Let the collection of nodes at
distance k from X be called the kth layer. At time zero, the source node is given a bit. At time k ≥ 1,
each node in the (k − 1)th layer inspects its inputs andsends a bit to its descendants in the kth layer.
Each bit is flipped with a probability of error δ ∈ 0, 12 in the process of transmission. The goal is to
be able to recover the original bit with probability of error better than 12 from the values of all nodes at
an arbitrarily deep layer k.
Besides its natural broadcast interpretation, the DAG broadcast is a natural model of noisy computation. Some special cases of the model represent information flow in biological networks, and other cases
represent noisy finite automata models.
We show that there exist DAGs with bounded degree and layers of size ω(log(k)) that permit recovery
provided δ is sufficiently small and find the critical δ for the DAGs constructed. Our result demonstrates
a doubly-exponential advantage for storing a bit in bounded degree DAGs compared to trees. On the
negative side, weshow that if the DAG is a two-dimensional regular grid, then recovery is impossible
for any δ ∈ 0, 21 provided all nodes use either AND or XOR for their processing functions.

C ONTENTS
I

Introduction and Main Results
I-A
Motivation . . . . . . . . . . . . . . . . . .
I-B
Random DAG Model . . . . . . . . . . . .
I-C
Results on Random DAG Models . . . . .
I-D
Deterministic 2D Grid Model . . . . . . . .
I-E
Results on Deterministic 2D Grids . . . . .
I-F
Further Discussion on Impossibility Results

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2
. 2
. 3
. 5
. 7
. 8
. 10

II

Analysis of Majority Rule Processing in Random DAG Model

12

III

Analysis of AND-OR Rule Processing in Random DAG Model

17

IV

Analysis of Deterministic AND 2D Grid

23

V

Analysis of Deterministic XOR 2D Grid

27

Appendix A: Miscellaneous Proofs

32

References

34

∗

A. Makur and Y. Polyanskiy are with the Department of Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, Cambridge, MA 02139, USA (e-mail: a makur@mit.edu; yp@mit.edu).
The research was supported in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center,
under grant agreement CCF-09-39370, by the NSF CAREER award CCF-12-53205, and by Schneider Electric, Lenovo Group
(China) Limited and the Hong Kong Innovation and Technology Fund (ITS/066/17FP) under the HKUST-MIT Research Alliance
Consortium.
†
E. Mossel is with the Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
(e-mail: elmos@mit.edu).
The research was supported in part by the NSF grants CCF-1665252 and DMS-1737944, and the DOD ONR grant N0001417-1-2598.

1

I. I NTRODUCTION AND M AIN R ESULTS
In this paper, we study a generalization of the well-known problem of broadcasting on trees [EKPS00].
In the broadcasting on trees problem, we are given a noisy tree T whose nodes are Bernoulli random
variables and edges
are independent binary symmetric channels (BSCs) with common crossover proba
bility δ ∈ 0, 12 . Given that the root is an unbiased random bit, the objective is to decode the bit at the
root from the bits at the k th layer of the tree. The authors of [EKPS00] characterize the sharp threshold
for when such reconstruction is possible:
1
• If (1 − 2δ)2 br(T ) < 1, then the minimum probability of error in decoding tends to 2 as k → ∞,
• If (1 − 2δ)2 br(T ) > 1, then the minimum probability of error in decoding is bounded away from
1
2 for all k ,
where br(T ) denotes the branching number of the tree. A consequence of this result is that reconstruction
is impossible for trees with sub-exponentially many vertices at each layer. Indeed, if Lk denotes the
number of vertices at layer k and limk→∞ log(Lk )/k = 0, then it is straightforward to show that br(T ) ≤
1, which in turn implies that (1 − 2δ)2 br(T ) < 1.
This result on reconstruction on trees generalizes results from statistical physics that hold for regular
trees [BRZ95], and have had numerous extensions and further generalizations including [Iof96a], [Iof96b],
[Mos98], [Mos01], [PP10], [Sly09], [Sly11], [JM04], [BVVW11]. Reconstruction on trees plays a crucial
role in understanding phylogenetic reconstruction, see e.g. [Mos03], [Mos04], [DMR06], [Roc10]. It also
plays a crucial role in understanding phase transitions for random constraint satisfaction problems, see
e.g. [MM06], [KMRT+ 07], [GM07], [MRT11] and follow-up work.
Instead of analyzing trees, we consider the problem of broadcasting on bounded degree directed acyclic
graphs (DAGs). As in the setting of trees, all nodes in our graphs are Bernoulli random variables and
all edges are independent BSCs. Furthermore, variables located at nodes with indegree 2 or more are the
values of a function on their noisy inputs.
Notice that compared to the setting of trees, broadcasting on DAGs has two principal differences: (a)
in trees, layer sizes scale exponentially in depth, while in DAGs they are polynomial; (b) in trees, the
indegree of each node is 1, while in DAGs each node has several incoming signals. The latter enables
the possibility of information fusion at the nodes and our main goal is to understand whether the benefits
of (b) overpower the harm of (a).
This paper contains two results. First, by a probabilistic argument, we demonstrate the existence of
bounded degree DAGs with Lk = ω(log(k)) which permit recovery of the root bit for sufficiently low
δ ’s. This implies that in terms of economy of storing information, DAGs are doubly-exponentially more
efficient than trees. Second, we show that no such recovery is possible on a two-dimensional (2D) grid
if all intermediate nodes with indegree 2 use logical AND as the processing function, or all use XOR as
the processing function. (This leaves only NAND as the remaining symmetric processing function.)
A. Motivation
The problem of broadcasting on trees is closely related to the problem of noisy computation [vN56],
[ES99]. Indeed it can be thought of in the following way: suppose we want to remember a bit in a noisy
circuit of depth k . How big should the circuit be? Von Neumann [vN56] asked this question assuming
we take multiple clones of the original bit and recursively apply gates in order to reduce the noise. The
broadcasting on trees perspective is to start from a single bit and repeatedly clone it so that one can
recover it well from the nodes at depth k . The model we consider here again starts from a single bit but
we are allowed to use bounded degree gates to reduce noise as well as to duplicate. This leads to much
smaller circuits than the tree circuits.
As mentioned earlier, the broadcasting process on trees plays a fundamental role in phylogenetic
reconstruction. The positive results obtained here suggest it might be possible to reconstruct other
biological networks, such as phylogenetic networks (see e.g. [HRS10]) or pedigrees (see e.g. [Tho86],
2

[SH06]), even if the growth of the network is very mild. It is interesting to explore if there are also
connections between broadcasting on DAGs and random constraint satisfaction problems. Currently, we
are not aware that such connections have been established.
Another motivation for this problem is to understand whether it is possible to propagate information
in regular grids starting from the root–see Figure 1 for a 2D example. Our conjecture is that such
propagation is possible for sufficiently low noise δ in 3 and more dimensions, and impossible for a 2D
grid regardless of the noise level and of the choice of processing function (which is the same for every
node). The conjecture is inspired by the work on 1D cellular automata [Gra01]. Indeed, the existence of
a 2D grid (with a choice of processing function) which remembers its initial state (bit) for infinite time
would suggest the existence of non-ergodic infinite 1D cellular automata consisting of 2-input binary-state
cells. Known constructions, however, require a lot more states [Gác01], or are non-uniform in time and
space [Cir78].
In this paper, we take some first steps towards establishing this conjecture. The next few subsections
formally define the random DAG and deterministic 2D grid models, and present our main results. After
stating each result, we also provide a brief outline of the main technique or intuition used in the proof.
The subsequent sections contain the proofs and auxiliary results.
B. Random DAG Model
A random DAG model consists of an infinite DAG with fixed vertices that are Bernoulli ({0, 1}-valued)
random variables and randomly generated edges which are independent BSCs. We first define the vertex
structure of this model, where each vertex is identified with the corresponding random variable. Let the
root random variable be X0,0 ∼ Bernoulli 21 . Furthermore, we define Xk = (Xk,0 , . . . , Xk,Lk −1 ) as the
vector of node random variables at distance (i.e. length of shortest path) k ∈ N , {0, 1, 2, . . . } from the
root, where Lk ∈ N denotes the number of nodes at distance k . In particular, we have X0 = (X0,0 ) and
L0 = 1.
We next define the edge structure of the random DAG model. For any k ∈ N\{0} and any j ∈ [Lk ] ,
{0, . . . , Lk − 1}, we independently and uniformly select d ∈ N\{0} vertices Xk−1,i1 , . . . , Xk−1,id from
Xk−1 (i.e. i1 , . . . , id are i.i.d. uniform on [Lk−1 ]), and then construct d directed edges: (Xk−1,i1 , Xk,j ), . . . ,
(Xk−1,id , Xk,j ). (Here, i1 , . . . , id are independently chosen for each Xk,j .) This random process generates
the underlying DAG structure. In the sequel, we will let G be a random variable representing this
underlying (infinite) random DAG, i.e. G encodes the random configuration of the edges between the
vertices.
To define a Bayesian network (or directed graphical model) on this random DAG, we fix some sequence
of Boolean functions fk : {0, 1}d → {0, 1} for k ∈ N\{0} (that depend on the level index k , but not on
the realization of G), and some crossover probability δ ∈ 0, 21 (since this is the interesting regime of
δ ). Then, for any k ∈ N\{0} and j ∈ [Lk ], given i1 , . . . , id and Xk−1,i1 , . . . , Xk−1,id , we define:1
Xk,j = fk (Xk−1,i1 ⊕ Zk,j,1 , . . . , Xk−1,id ⊕ Zk,j,d )

(1)

where ⊕ denotes addition modulo 2, and {Zk,j,i : k ∈ N\{0}, j ∈ [Lk ], i ∈ {1, . . . , d}} are i.i.d
Bernoulli(δ) random variables that are independent of everything else. This means that each edge is
a BSC with parameter δ (denoted BSC(δ)). Moreover, (1) characterizes the conditional distribution of
Xk,j given its parents.
Note that although we will analyze this model for convenience, as stated, our underlying graph is really
a directed multigraph rather than a DAG, because we select the parents of a vertex with replacement.
It is straightforward to construct an equivalent model where the underlying graph is truly a DAG. For
1

In this model, the Boolean processing function used at a node Xk,j depends only on the level index k. A more general
model can be defined where each node Xk,j has its own Boolean processing function fk,j : {0, 1}d → {0, 1} for k ∈ N\{0}
and j ∈ [Lk ], but we will only analyze instances of the simpler model in this paper.

3

i :
each vertex Xk,j with k ∈ N\{0} and j ∈ [Lk ], we first construct d intermediate parent vertices {Xk,j
i
i = 1, . . . , d} that live between layers k and k − 1, where each Xk,j has a single edge pointing to Xk,j .
i , we independently and uniformly select a vertex from layer k − 1, and construct a
Then, for each Xk,j
i . This defines a valid (random) DAG. As a result, every realization
directed edge from that vertex to Xk,j
of G can be perceived as either a directed multigraph or its equivalent DAG. Furthermore, the Bayesian
network on this true DAG is defined as follows: each Xk,j is the output of a Boolean processing function
i : i = 1, . . . , d}, and each X i is the output of a BSC whose input is the unique
fk with inputs {Xk,j
k,j
i in layer k − 1.
parent of Xk,j
Finally, we define the “empirical probability of unity” at level k ∈ N as:

σk ,

Lk −1
1 X
Xk,m
Lk

(2)

m=0

where σ0 = X0,0 is just the root node. Observe that given σk−1 = σ , Xk−1,i1 , . . . , Xk−1,id are i.i.d.
Bernoulli(σ), and as a result, Xk−1,i1 ⊕ Z1 , . . . , Xk−1,id ⊕ Zd are i.i.d. Bernoulli(σ ? δ), where σ ? δ ,
σ(1 − δ) + δ(1 − σ) is the convolution of σ and δ . Therefore, Xk,j is the output of fk upon inputting a
d-length i.i.d. Bernoulli(σ ? δ) string.
Under this setup, our objective is to determine whether or not the value at the root σ0 = X0,0 can
be decoded from the observations Xk as k → ∞. Since Xk is an exchangeable sequence of random
variables given σ0 , for any x0,0 , xk,0 , . . . , xk,Lk −1 ∈ {0, 1} and any permutation π of [Lk ], we have
P k −1
PXk |σ0 (xk,0 , . . . , xk,Lk −1 |x0,0 ) = PXk |σ0 (xk,π(0) , . . . , xk,π(Lk −1) |x0,0 ). Letting σ = L1k L
j=0 xk,j , we
can factorize PXk |σ0 as:


Lk −1
PXk |σ0 (xk,0 , . . . , xk,Lk −1 |x0,0 ) =
Pσk |σ0 (σ|x0,0 ) .
(3)
Lk σ
Using the Fisher-Neyman factorization theorem [Kee10, Theorem 3.6], this implies that σk is a sufficient
statistic of Xk for performing inference about σ0 . Therefore, we restrict our attention to the Markov
chain {σk : k ∈ N}. Given σk , inferring the value of σ0 is a binary hypothesis testing problem with
minimum achievable probability of error:

 1

k
(4)
1 − Pσ+k − Pσ−k TV
P fML
(σk ) 6= σ0 =
2
k
where fML
: {m/Lk : m = 0, . . . , Lk } → {0, 1} is the maximum likelihood (ML) decision rule at
level k in the absence of knowledge of the random DAG realization G, Pσ+k and Pσ−k are the conditional
distributions of σk given σ0 = 1 and σ0 = 0 respectively, and for any two probability measures P and
Q on the same measurable space (Ω, F), their total variation (TV) distance is defined as:
kP − QkTV , sup |P (A) − Q(A)| .

(5)

A∈F

We say that reconstruction of the root bit σ0 is possible when:

 1
k
lim sup P fML
(σk ) 6= σ0 <
⇔ lim inf Pσ+k − Pσ−k TV > 0 ,
(6)
k→∞
2
k→∞
and is impossible when:

 1
k
lim P fML
(σk ) 6= σ0 =
(7)
⇔
lim Pσ+k − Pσ−k TV = 0 .
k→∞
k→∞
2
In the sequel, to simplify our analysis when proving that reconstruction is possible, we will often use
other (sub-optimal) decision rules rather than the ML decision rule. On the other hand, when proving
that reconstruction is impossible, we will prove the stronger impossibility result:
h 
i 1
h
i
k
(σk , G) 6= σ0 G =
lim E P fML
⇔
lim E Pσ+k |G − Pσ−k |G
=0
(8)
k→∞
k→∞
2
TV
4

k (·, G) : {m/L : m = 0, . . . , L } → {0, 1} is the ML decision rule at level k given knowledge
where fML
k
k
of the random DAG realization G (based on σk , not the full k -layer state Xk ), and Pσ+k |G and Pσ−k |G
denote the conditional distributions of σk given {σ0 = 1, G} and {σ0 = 0, G}, respectively. Note that
applying Jensen’s inequality to the TV distance condition in (8) establishes the weaker impossibility
result in (7).

C. Results on Random DAG Models
We prove two main results on the random DAG model. The first considers the setting where the
indegree of each node (except the root) is d = 3. In this scenario, taking a majority vote of the inputs
at each node intuitively appears to have good “local error correction” properties. So, we fix all Boolean
functions in the random DAG model to be the majority rule, and prove that this model exhibits a phase
transition phenomenon around a critical threshold
, 61 . Indeed, the theorem below illustrates that for
 δmaj
δ < δmaj , the majority decision rule Ŝk , 1 σk ≥ 12 can asymptotically decode σ0 , but for δ > δmaj ,
the ML decision rule cannot asymptotically decode σ0 .
Theorem 1 (Phase Transition in Random DAG Model with Majority Rule Processing). For a random
DAG model with d = 3 and majority processing functions, the following phase transition phenomenon
occurs around δmaj :
1) If δ ∈ (0, δmaj ), and the number of vertices per level satisfies Lk = ω(log(k)), then reconstruction
is possible in the sense that:
1
lim sup P(Ŝk 6= σ0 ) < .
2
k→∞
k 


2
, then recon2) If δ ∈ δmaj , 12 , and the number of vertices per level satisfies Lk = o 3(1−2δ)
struction is impossible in the sense of (8):
h
i
lim E Pσ+k |G − Pσ−k |G
= 0.
k→∞

TV

Theorem 1 is proved in section II. Intuitively, the proof considers the conditional expectation function
σ 7→ E[σk |σk−1 = σ] which provides the approximate value of σk given the value of σk−1 for large k .
This function
 turns out to have three fixed points when δ ∈ (0, δmaj ), and only one fixed point when
δ ∈ δmaj , 12 . In the former case, σk “moves” to the largest fixed point when σ0 = 1, and to the smallest
fixed point when σ0 = 0. In the latter case, σk “moves” to the unique fixed point of 12 regardless of
the value of σ0 .2 This provides the guiding
intuition for why we can asymptotically decode σ0 when

δ ∈ (0, δmaj ), but not when δ ∈ δmaj , 21 .
It is worth comparing Theorem 1 with Von Neumann’s results in [vN56, Section 8], where the threshold
of 16 is also significant. In [vN56, Section 8], Von Neumann demonstrates the possibility of reliable
computation by constructing a circuit with successive layers of computation and local error correction
using 3-input noisy majority gates. Note that in this model, the gates are noisy (i.e. the gates independently
make errors with probability δ ), while in our model, the edges (or wires) are noisy.3 In his analysis, Von
Neumann first derives a simple recursion that captures the effect on the probability of error after applying
a single noisy majority gate. Then, he uses a “heuristic” fixed point argument to show that as the depth
of the circuit grows, the probability of error asymptotically stabilizes at a fixed point value less than 12
if δ < 61 , and the probability of error tends to 12 if δ ≥ 61 . Furthermore, he is able to rigorously prove
that reliable computation is possible for δ < 0.0073.
2

Note, however, that σk → 12 almost surely as k → ∞ does not imply the impossibility of reconstruction in the sense of (7),
let alone (8). So, a different argument is required to establish such impossibility results.
3
See [DO77] for the relation between gate noise and edge noise.

5

As we mentioned in subsection I-A, Von Neumann’s approach to remembering a random initial bit
entails using multiple clones of the initial bit as inputs to a noisy circuit with one output, where the output
equals the initial bit with probability greater than 12 for “good” choices of noisy gates. It is observed in
[HW91, Section 2] that a balanced ternary tree circuit, with k layers of 3-input noisy majority gates and 3k
inputs that are all equal to the initial bit, can be used to remember the initial bit. In fact, Von Neumann’s
heuristic fixed point argument that yields a critical threshold of 16 for reconstruction is accurate in this
scenario. Moreover, Hajek and Weller also prove the stronger impossibility result that reliable computation
is impossible for formulas (i.e. circuits where the output of each intermediate gate is the input of one
other gate) with general 3-input gates when δ ≥ 61 [HW91, Proposition 2].
In the brief intuition for our proof of Theorem 1 given above, the recursion given by the repeated
composition of σ 7→ E[σk |σk−1 = σ] seems similar to Von Neumann’s recursion in [vN56, Section 8]
since both analyze majority gates and yield the same critical threshold of 16 . However, our recursion is
also quite different in two crucial ways: (a) We prove the 16 threshold for a model where errors occur
on the edges rather than at the gates (as mentioned earlier). (b) Since our recursion is defined on the
proportion of 1’s in a layer via conditional expectations, our proof requires exponential concentration
inequalities to formalize the intuition provided by the fixed point analysis.
We now make some pertinent remarks about Theorem 1. Firstly, reconstruction is possible in the sense
of (6) when δ ∈ (0, δmaj ) since the ML decision rule achieves lower probability of errorthan the majority
decision rule,4 and reconstruction is impossible in the sense of (7) when δ ∈ δmaj , 12 (as explained at
the end of subsection I-B). Secondly, in the δ ∈ (0, δmaj ) regime, reconstruction is in fact possible
under the weaker assumption that Lk ≥ h(δ) log(k) for some constant h(δ) (that depends on δ ) and all
sufficiently large k ; we will briefly explain this after presenting the proof of Theorem 1 in section II.
k (σ ) is only optimal in the absence of knowledge of the particular graph
Thirdly, the ML decoder fML
k
realization G. If the decoder knows the graph G, then it can do better and possibly beat the δmaj = 16
threshold. We do note, however, that (except for a vanishing fraction of DAGs) this would require using
k (σ , G) does not beat the δ
the full k -layer state Xk , not just σk (since the decoder fML
maj threshold
k
on average). Fourthly, the following conjecture is still open: In the random DAG model with d = 3
and Lk = O(log(k)), reconstruction is impossible for all choices of Boolean processing functions when
δ > δmaj . (A consequence of this conjecture is that majority processing functions are optimal, i.e. they
achieve the δmaj reconstruction threshold.) Lastly, it is worth mentioning that for any fixed graph with
indegree d = 3 and sub-exponential Lk , for any choice of Boolean processing functions, and any choice
1
of decoder, it is impossible to reconstruct the root bit when δ > 12 − 2√
= 0.21132.... This follows from
3
Evans and Schulman’s result in [ES99], which we will discuss in subsection I-F.
We next present an immediate corollary of Theorem 1 which states that there exist constant indegree
(deterministic) DAGs with Lk = ω(log(k)) such that reconstruction of the root bit is possible. Formally,
we have the following result which is proved in Appendix A.

Corollary 1 (Existence of DAGs where Reconstruction is Possible). For any δ ∈ 0, 16 , there exists a
DAG G with d = 3 and any Lk = ω(log(k)) such that if we use majority rules as our Boolean processing
functions, then there exists  > 0 such that the probability of error in ML decoding is bounded away
from 21 − :

 1
∀k ∈ N, P hkML (Xk , G) 6= X0 ≤ − 
2
where hkML (·, G) : {0, 1}Lk → {0, 1} denotes the ML decision rule at level k of G based on the full
k -layer state Xk .
4

It can be seen from monotonicity and symmetry considerations that without knowledge of the random DAG realization G,
k
the ML decision rule fML
(σk ) is equal to the majority decision rule Ŝk . On the other hand, with knowledge of the random DAG
k
realization G, the ML decision rule fML
(σk , G) is not the majority decision rule.

6

Until now, we have restricted ourselves to the d = 3 case of the random DAG model, because we can
always neglect d−3 inputs at each processing function if d > 3. However, this restriction has only allowed
us to prove the existence of DAGs (where reconstruction is possible) when δ < 16 . It can in fact be shown
that for every δ ∈ 0, 21 , there exists a DAG with some d ≥ 3 (that depends on δ ), Lk = ω(log(k)), and
all d-input majority Boolean processing functions such that reconstruction is possible based on the full
k -layer state Xk .
Our second result considers the setting where the indegree of each node (except the root) is d = 2,
because it is not immediately obvious that deterministic DAGs (for which reconstruction is possible)
exist for d = 2. Indeed, it is not entirely clear which Boolean processing functions are good for “local
error correction” in this scenario. We choose to fix all Boolean functions at even levels of the random
DAG model to be the AND rule, and all Boolean functions at odd levels of the model to be the OR
rule. We then prove that this random
√ DAG model also exhibits a phase transition phenomenon around
3− 7
a critical threshold of δandor , 4 . As before, the next theorem illustrates that for δ < δandor , the
“biased” majority decision rule, T̂k , 1{σk ≥ t} where t ∈ (0, 1) is defined in (52) in section III, can
asymptotically decode σ0 , but for δ > δandor , the ML decision rule cannot asymptotically decode σ0 . For
simplicity, we only analyze this model at even levels.
Theorem 2 (Phase Transition in Random DAG Model with AND-OR Rule Processing). Let C(δ) be the
constant defined in (48) in section III. For a random DAG model with d = 2, AND processing functions
at even levels, and OR processing functions at odd levels, the following phase transition phenomenon
occurs around δandor :
1) If δ ∈ (0, δandor ), and the number of vertices per level satisfies Lk = ω(log(k)), then reconstruction
is possible in the sense that:
1
lim sup P(T̂2k 6= σ0 ) < .
2
k→∞

k
2) If δ ∈ δandor , 21 , and the number of vertices per level satisfies Lk = o (C(δ) + )− 2 for some
 ∈ (0, 1 − C(δ)) (that can depend on δ ), then reconstruction is impossible in the sense of (8):
i
h
−
+
= 0.
lim E Pσ2k |G − Pσ2k |G
k→∞

TV

Theorem 2 is proved in section III, and many of the remarks pertaining to Theorem 1 as well as the
general intuition for Theorem 1 also hold for Theorem 2. Furthermore, a corollary analogous to Corollary
1 also holds here.
D. Deterministic 2D Grid Model
We now turn to deterministic DAG models. As we mentioned earlier, all deterministic DAGs we will
analyze will have the structure of a regular 2D grid. A deterministic 2D grid consists of a deterministic
DAG whose vertices are also Bernoulli random variables and whose edges are independent
BSC(δ)’s.

As with random DAG models, there is a root random variable X0,0 ∼ Bernoulli 12 , and we let Xk =
(Xk,0 , . . . , Xk,k ) be the vector of node random variables at distance k ∈ N from the root. So, there
are k + 1 nodes at distance k . Furthermore, the 2D grid contains the (deterministic) directed edges
(Xk,j , Xk+1,j ) and (Xk,j , Xk+1,j+1 ) for every k ∈ N and every j ∈ [k + 1]. The underlying graph of
such a 2D grid is shown in Figure 1.
To define
 the Bayesian network on a deterministic 2D grid, we again fix some crossover probability
δ ∈ 0, 12 , and two Boolean functions f1 : {0, 1}2 → {0, 1} and f2 : {0, 1} → {0, 1}. Then, for any
k ∈ N\{0, 1} and j ∈ {1, . . . , k − 1}, we define:5
Xk,j = f1 (Xk−1,j−1 ⊕ Zk,j,1 , Xk−1,j ⊕ Zk,j,2 )
5

(9)

As mentioned subsection I-B, we can define a more general model where every node Xk,j has its own Boolean processing
function fk,j , but we will only analyze instances of the simpler model presented here.

7

Fig. 1. Illustration of a deterministic
2D grid. In this 2D grid, each node is a Bernoulli random variable and each edge is a BSC

with parameter δ ∈ 0, 12 . Moreover, each node uses a Boolean processing function to combine its (possibly flipped) input bits.

and for any k ∈ N\{0}, we define:
Xk,0 = f2 (Xk−1,0 ⊕ Zk,0,2 ) and Xk,k = f2 (Xk−1,k−1 ⊕ Zk,k,1 )

(10)

where {Zk,j,i : k ∈ N\{0}, j ∈ [k + 1], i ∈ {1, 2}} are i.i.d Bernoulli(δ) random variables that are
independent of everything else. Together, (9) and (10) characterize the conditional distribution of any
Xk,j given its parents.
As before, we have a Markov chain {Xk : k ∈ N}, and our goal is to determine whether or not the
value at the root X0 can be decoded from the observations Xk as k → ∞. In all the cases that we will
consider in this paper, we will prove that reconstruction is impossible in the sense that:
lim

k→∞

PX+k − PX−k

TV

=0

(11)

where PX+k and PX−k are the conditional distributions of Xk given X0 = 1 and X0 = 0, respectively.
The condition in (11) is of course equivalent to the ML decision rule failing to decode X0 from Xk as
k → ∞.
E. Results on Deterministic 2D Grids
Deterministic 2D grids are much harder to analyze than random DAG models due to the dependence
between adjacent nodes in a given layer. As mentioned earlier, we analyze the setting where all Boolean
processing functions in the 2D grid with two inputs are the same, and all Boolean processing functions
in the 2D grid with
 one input are the identity rule. Our first result shows that reconstruction is impossible
for all δ ∈ 0, 21 when AND processing functions are used.

Theorem 3 (Deterministic AND 2D Grid). If δ ∈ 0, 12 , and all Boolean processing functions with two
inputs in the deterministic 2D grid are the AND rule, then reconstruction is impossible in the sense of
(11), i.e. limk→∞ PX+k − PX−k TV = 0.
Theorem 3 is proved in section IV. The proof couples the 2D grid starting at X0,0 = 0 with the 2D
grid starting at X0,0 = 1, and “runs” them together. Using a phase transition result concerning bond
percolation on 2D grids, we show that we eventually reach a layer where the values of all nodes in the
first grid equal the values of the corresponding nodes in the second grid. So, the two 2D grids “couple”
almost surely regardless of their starting state. This implies that we cannot decode the starting state by
looking at nodes in layer k as k → ∞. We note that in order to prove that the two 2D grids “couple,”
we have to consider two different regimes of δ and provide separate arguments for each. The details of
these arguments are presented in section IV.

Our second result shows that reconstruction is impossible for all δ ∈ 0, 21 when XOR processing
functions are used.
8


Theorem 4 (Deterministic XOR 2D Grid). If δ ∈ 0, 21 , and all Boolean processing functions with two
inputs in the deterministic 2D grid are the XOR rule, then reconstruction is impossible in the sense of
(11), i.e. limk→∞ PX+k − PX−k TV = 0.
Theorem 4 is proved in section V. In the XOR 2D grid, every node at level k can be written as a
(binary) linear combination of the root bit and all the BSC noise random variables in the grid up to level
k . This linear relationship can be captured by a binary matrix. The main idea of the proof is to perceive
this matrix as a parity check matrix of a linear code. The problem of inferring X0,0 from Xk turns out
to be equivalent to decoding the first bit of a codeword drawn uniformly from this code after observing
a noisy version of the codeword. Basic facts from coding theory can then be used to complete the proof.
We remark that Theorems 3 and 4 seem intuitively obvious from the random DAG model perspective.
For example, consider the random DAG model with d = 2, Lk = k + 1, and all AND processing
functions. Then, the conditional expectation
function σ 7→ E[σk |σk−1 = σ] has only one fixed point

1
regardless of the value of δ ∈ 0, 2 , and we intuitively expect σk to tend to this fixed point (which
roughly captures the equilibrium between AND gates killing 1’s and BSC(δ)’s producing new 1’s) as
k → ∞. So, reconstruction is impossible in this random DAG model, which suggests that reconstruction
is also impossible in the deterministic 2D AND grid. Although Theorems 3 and 4 are intuitively easy to
understand in this way, we emphasize that they are nontrivial to prove–see sections IV and V.
The impossibility of reconstruction in Theorems 3 and 4 also seems intuitively plausible due to the
ergodicity results for numerous 1D (probabilistic) cellular automata–see e.g. [Gra82] and the references
therein. However, there are two key differences between deterministic 2D grids and 1D cellular automata.
Firstly, the main question in the study of 1D cellular automata is whether a given automaton is ergodic,
i.e. whether the Markov process defined by it converges to a unique invariant probability measure on
the configuration space for all initial configurations. This question of ergodicity is typically addressed
by considering the convergence of finite-dimensional distributions over the sites (i.e. weak convergence).
Hence, for many 1D cellular automata that have special characteristics (such as translation invariance,
finite range, positivity, and attractiveness/monotonicity, cf. [Gra82]), it suffices to consider the convergence
of distributions on finite intervals (e.g. marginal distribution at a given site). In contrast to this setting,
we are concerned with the stronger notion of convergence in TV distance. Indeed, Theorems 3 and 4
show that the TV distance between PX+k and PX−k vanishes as k → ∞.
Secondly, since a 1D cellular automaton has infinitely many sites, the problem of remembering a
bit in a cellular automaton corresponds to distinguishing between the “all zeros” and “all ones” initial
configurations. On the other hand, a deterministic 2D grid can be construed as a 1D cellular automaton
with boundary conditions; each level k corresponds to an instance in (discrete) time, and there are Lk
sites at time k . Moreover, its initial configuration has only one copy of the initial bit as opposed to
infinitely many copies. As a result, compared a deterministic 2D grid, a 1D cellular automaton (without
boundary conditions) intuitively appears to have a stronger separation between the two initial states as
time progresses. The aforementioned boundary conditions form another barrier to translating results from
the 1D cellular automata literature to deterministic 2D grids.
It is also worth mentioning that most results on 1D cellular automata pertain to the continuous time
setting–see e.g. [Lig78], [Gra82] and the references therein. This is because sites are updated one by
one in a continuous time automaton, but they are updated in parallel in a discrete time automaton. So,
the discrete time setting is often harder to analyze. (One of the only known discrete time 1D cellular
automaton ergodicity results, for the 3-input majority vote model, is outlined in [Gra87, Section 3].)
This is another reason why results from the 1D cellular automata literature cannot be easily used for our
model.

9

F. Further Discussion on Impossibility Results
In this subsection, we present and discuss two impossibility results pertaining to both deterministic
and random DAG models (where the former correspond to Bayesian networks on specific realizations
of G as defined in subsection I-B). The first result illustrates that if Lk ≤ log(k)/(d log(1/(2δ))) for
every sufficiently large k (i.e. Lk grows very “slowly”), then reconstruction is impossible regardless of
the choice of Boolean processing functions and the choice of decision rule.
Proposition 1 (Slow Growth of Layers). Suppose that the number of vertices per level satisfies:
∃K ∈ N, ∀k ≥ K, Lk ≤

Then, reconstruction is impossible and we have:
1) for a deterministic DAG:
lim PX+k − PX−k
k→∞

2) for a random DAG:

log(k)

1 .
d log 2δ

TV

h
lim E PX+k |G − PX−k |G

k→∞

= 0.

i
TV

= 0.

This proposition is proved in Appendix A. In part 2 of Proposition 1, PX+k |G and PX−k |G denote
the conditional distributions of Xk given {X0 = 1, G} and {X0 = 0, G} respectively, which shows
that reconstruction is impossible for random DAGs even if the particular DAG realization G is known
and the decoder can access the entire k -layer state Xk . Furthermore, part 2 also clearly implies that
reconstruction is impossible in the sense of (8). Therefore, Proposition 1 illustrates that our assumption
that Lk = ω(log(k)) (or as we mentioned earlier, the weaker assumption that Lk ≥ h(δ) log(k) for some
constant h(δ) and all sufficiently large k ) for reconstruction to be possible in Theorems 1 and 2 is in
fact necessary. In contrast, consider a deterministic DAG with no restrictions (i.e. no bounded indegree
assumption) except for the size of Lk . Then, each node at level k is connected to all Lk−1 nodes at
level k − 1. In this scenario, the proof technique of part p
1 of Proposition 1 in Appendix A can be used
to show that reconstruction is impossible
when
L
≤
log(k)/ log(1/(2δ)) for all sufficiently large
k
p

k . Moreover, this scaling of Lk = O log(k) is tight, because if we let every Boolean processing
function be the majority vote, then the proof of part 1 of Theorem 1 in section
II can be executed
mutatis
p


mutandis to show that reconstruction is possible for every δ ∈ 0, 21 when Lk = Ω log(k) and
lim supk→∞ Lk /Lk−1 < +∞.
The second impossibility result we present is an important result from the noisy circuits literature
due to Evans and Schulman [ES99]. Evans and Schulman studied Von Neumann’s noisy computation
model (which we briefly discussed in subsection I-C), and established general conditions under which
reconstruction is impossible in deterministic DAGs due to the decay of mutual information between X0
and Xk . Recall that for two discrete random variables X ∈ X and Y ∈ Y (where |X |, |Y| < ∞), with
joint probability mass function PX,Y and marginals PX and PY respectively, the mutual information (in
bits) between them is defined as:


XX
PX,Y (x, y)
I(X; Y ) ,
PX,Y (x, y) log2
(12)
PX (x)PY (y)
x∈X y∈Y
 

where log2 (·) is the binary logarithm, and we assume that 0 log2 0q = 0 for any q ≥ 0, and p log2 p0 =
∞ for any p > 0 (due to continuity considerations). We present a specialization of [ES99, Lemma 2]
for our setting as Proposition 2 below. This proposition portrays that if Lk is sub-exponential and the
parameters δ and d satisfy (1 − 2δ)2 d < 1, then reconstruction is impossible in deterministic DAGs
regardless of the choice of Boolean processing functions and the choice of decision rule.
10

Proposition 2 (Decay of Mutual Information [ES99, Lemma 2]). For any deterministic DAG model, we
have:
k
I(X0 ; Xk ) ≤ Lk (1 − 2δ)2 d
where Lk dk is the total number of paths from X0 to layer Xk , and (1 − 2δ)2k can be construed as
the overall contraction
of mutual information along each path. Therefore, if (1 − 2δ)2 d < 1 and Lk =

2
k
o 1/((1 − 2δ) d) , then limk→∞ I(X0 ; Xk ) = 0, which implies that limk→∞ PX+k − PX−k TV = 0.
We make some pertinent remarks about this result. Firstly, Evans and Schulman’s original analysis
assumes that gates are noisy as opposed to edges (in accordance with Von Neumann’s setup), but the
re-derivation of [ES99, Lemma 2] in [PW17b, Corollary 7] illustrates that the result also holds for our
model. In fact, the site percolation analysis in [PW17b, Section 3] (which we will briefly delineate later)
improves upon Evans and Schulman’s estimate. Furthermore, this analysis illustrates that the bound in
Proposition 2 also holds for all choices of random Boolean processing functions.
Secondly, while Proposition 2 holds for deterministic DAGs, we can easily extend it for random DAG
models. Indeed, the random DAG model inherits the inequality in Proposition 2 pointwise:
k
I(X0 ; Xk |G = G) ≤ Lk (1 − 2δ)2 d
(13)
for every realization of the random DAG G = G , where I(X0 ; Xk |G = G) is the mutual information
between X0 and Xk computed using the joint distribution of X0 and Xk given G = G . Taking expectations
with respect to G, we get:
k
(14)
I(σ0 ; σk ) = I(X0 ; Xk ) ≤ I(X0 ; Xk |G) ≤ Lk (1 − 2δ)2 d
where I(X0 ; Xk |G) is the conditional mutual information (i.e. the expected value of I(X0 ; Xk |G = G)
with respect to G), the equality holds because σk is a sufficient statistic of Xk for performing inference
about σ0 (cf. [PW17a, Section 3.1]), and the first inequality follows from the chain rule for mutual
information and the fact that X0 is independent of G. Hence, if Lk is sub-exponential and (1−2δ)2 d < 1,
then reconstruction is impossible in the sense of (7) in the random DAG model regardless of the choice
of Boolean processing functions and the choice of decision rule. (It is straightforward to see from the
previous discussion that reconstruction is also impossible in the sense of (8).)
Thirdly, Evans and Schulman’s result in Proposition 2 provides an upper bound on the critical threshold
of δ above which reconstruction of the root bit is impossible. Indeed, the condition, (1 − 2δ)2 d < 1,
under which mutual information decays can be rewritten as (cf. the discussion in [ES99, p.2373]):
1
1
1
δES (d) , − √ < δ <
(15)
2 2 d
2
and reconstruction is impossible for deterministic or random DAGs in this regime of δ provided Lk is
sub-exponential. As a sanity check, we can verify that δES (2) = 0.14644... > 0.08856... = δandor in the
context of Theorem 2, and δES (3) = 0.21132... > 0.16666... = δmaj in the context of Theorem 1 (as
mentioned in subsection I-C). Although δES (d) is a general upper bound on the critical threshold for
reconstruction, in this paper, it is not particularly useful because we analyze explicit processing functions
and decision rules, and derive specific bounds that characterize the corresponding thresholds.
Fourthly, it is worth comparing δES (d) (which comes from a site percolation argument, cf. [PW17b,
Section 3]) to an upper bound on the critical threshold for reconstruction derived from bond percolation.
To this end, consider the random DAG model, and recall that the BSC(δ)’s along each edge generate
independent bits with probability 2δ (as shown in the proof of Proposition 1 in Appendix A). So, we can
perform bond percolation so that each edge is independently “removed” with probability 2δ . It can be
1
< δ < 12 .
shown by analyzing this bond percolation process that reconstruction is impossible when 21 − 2d
Therefore, the Evans-Schulman upper bound of δES (d) is tighter than the bond percolation upper bound:
1
δES (d) < 12 − 2d
.
11

Finally, we briefly delineate how the site percolation approach in [PW17b, Section 3] allows us to prove
that reconstruction is impossible in the random DAG model for the (1−2δ)2 d = 1 case as well. Consider a
site percolation process where each node Xk,j (for k ∈ N\{0} and j ∈ [Lk ]) is independently “open” with
probability (1 − 2δ)2 , and “closed” with probability 1 − (1 − 2δ)2 . (Note that X0,0 is open almost surely.)
For every k ∈ N\{0}, let pk denote the probability that there is an “open connected path” from X0 to
Xk (i.e. there exist j1 ∈ [L1 ], . . . , jk ∈ [Lk ] such that (X0,0 , X1,j1 ), (X1,j1 , X2,j2 ), . . . , (Xk−1,jk−1 , Xk,jk )
are directed edges in the random DAG G and X1,j1 , . . . , Xk,jk are all open). It can be deduced from
[PW17b, Theorem 5] that for any k ∈ N\{0}:
I(X0 ; Xk |G) ≤ pk .

(16)

Next, for each k ∈ N, define the random variable:
1 X
λk ,
1{Xk,j is open and connected}
Lk

(17)

j∈[Lk ]

which is the proportion of open nodes at level k that are connected to the root by an open path. (Note
that λ0 = 1.) It is straightforward to verify (using Bernoulli’s inequality) that for any k ∈ N\{0}:


E[λk |λk−1 ] = (1 − 2δ)2 1 − (1 − λk−1 )d ≤ (1 − 2δ)2 dλk−1 .
(18)
Observe that by Markov’s inequality and the recursion from (18), E[λk ] ≤ (1 − 2δ)2 d E[λk−1 ], we have:


k
1
pk = P λk ≥
≤ Lk E[λk ] ≤ Lk (1 − 2δ)2 d
(19)
Lk
which recovers Evans and Schulman’s result (Proposition 2)in the context of the random DAG model.
Indeed, if (1 − 2δ)2 d < 1 and Lk = o 1/((1 − 2δ)2 d)k , then limk→∞ pk = 0, and as a result,
limk→∞ I(X0 ; Xk |G) = 0 by (16). On the other hand, when (1 − 2δ)2 d = 1, taking expectations
and applying Jensen’s inequality to the equality in (18) produces:


E[λk ] ≤ (1 − 2δ)2 1 − (1 − E[λk−1 ])d .
(20)
This implies that E[λk ] ≤ RF −1 (k) for every k ∈ N using the estimate in [PW16, Appendix A], where
1 1
2
d
F : [0, 1] → R+ , F (t) = t f (τ
) dτ with f : [0, 1] → [0, 1], f (t) = t − (1 − 2δ) 1 − (1 − t) , and
2
F −1 : R+ → [0, 1] is well-defined. Since f (t) ≥ d−1
2 t for all t ∈ [0, 1], it is straightforward to show
that:
2
E[λk ] ≤ F −1 (k) ≤
.
(21)
(d − 1)k
Therefore, the Markov’s inequality argument in (19) illustrates that if (1−2δ)2 d = 1 and Lk = o(k), then
limk→∞ pk = 0 and reconstruction is impossible in the random DAG model due to (16). Furthermore,
the condition on Lk can be improved to Lk = O(k log(k)) using a more sophisticated Borel-Cantelli
type of argument.
II. A NALYSIS OF M AJORITY RULE P ROCESSING IN R ANDOM DAG M ODEL
In this section, we prove Theorem 1. To this end, we first make some pertinent observations. Recall
that we have a random DAG model with d = 3, and all Boolean functions are the majority rule, i.e.
fk (x1 , x2 , x3 ) = majority(x1 , x2 , x3 ) for every k ∈ N\{0}. Suppose we are given that σk−1 = σ . Then,
Xk,j = majority(Bernoulli(σ?δ), Bernoulli(σ?δ), Bernoulli(σ?δ)) for three i.i.d. Bernoulli random variables
for every k ∈ N\{0} and every j ∈ [Lk ]. Since we have:
P(Xk,j = 1|σk−1 = σ) = (σ ? δ)3 + 3(σ ? δ)2 (1 − σ ? δ)
3 3

3 2

(22)
2

= −2(1 − 2δ) σ + 3(1 − 2δ) σ + 6δ(1 − δ)(1 − 2δ)σ + δ (3 − 2δ)

(23)

= E[σk |σk−1 = σ] ,

(24)
12

Xk,j are i.i.d. Bernoulli(g(σ)) for j ∈ [Lk ], and Lk σk ∼ binomial(Lk , g(σ)), where we define g : [0, 1] →
[0, 1] as:
g(σ) , (σ ? δ)3 + 3(σ ? δ)2 (1 − σ ? δ)
(25)

and its derivative g 0 : [0, 1] → R+ is:
g 0 (σ) = 6(1 − 2δ)(σ ? δ)(1 − σ ? δ) ≥ 0 .

(26)

This is a quadratic function of σ with maximum value maxσ∈[0,1] g 0 (σ) = 32 (1 − 2δ) achieved at σ = 21 .
Hence, 32 (1 − 2δ) is the Lipschitz constant of g over [0, 1].
There are two regimes
and fixed point structure
 of interest when we consider the contraction properties

of g . In the δ ∈ 0, 61 regime, the Lipschitz constant 32 (1 − 2δ) ∈ 1, 23 is greater than 1. Furthermore,
to compute the fixed points of g , notice that:
g(σ) − σ = −2(1 − 2δ)3 σ 3 + 3(1 − 2δ)3 σ 2 + (6δ(1 − δ)(1 − 2δ) − 1)σ + δ 2 (3 − 2δ)


1
= σ−
(−2(1 − 2δ)3 σ 2 + 2(1 − 2δ)3 σ − 2δ 2 (3 − 2δ))
2

(27)

which means that g has three fixed points (or the roots of g(σ) − σ ):
s
s
!
!
1
1 − 6δ
1 − 6δ
1 1
,
(28)
1+
1−
σ= ,
2 2
(1 − 2δ)3
2
(1 − 2δ)3

using the quadratic formula. When δ ∈ 0, 61 , let us define the largest fixed point of g as:
s
!
1
1 − 6δ
σ̂ ,
1+
(29)
2
(1 − 2δ)3

so that g has the fixed points σ = 1 − σ̂, 21 , σ̂ . In contrast, in the δ ∈ 61 , 12 regime, the Lipschitz constant
3
1
2 (1 − 2δ) ∈ (0, 1) is less than 1, and the only fixed point of g is σ = 2 . (We also mention that when
1
3
δ = 6 , the Lipschitz constant 2 (1 − 2δ) = 1, and g has one fixed point at σ = 12 .) We now prove
Theorem 1.

Proof of Theorem 1. We first prove that δ ∈ 0, 61 implies lim supk→∞ P(Ŝk 6= σ0 ) < 21 . To establish
this, we begin by defining a useful “monotone Markovian coupling” (see [LPW09, Chapter 5] for basic
definitions of Markovian couplings). Let {σk+ : k ∈ N} and {σk− : k ∈ N} denote versions of the Markov
chain {σk : k ∈ N} (i.e. with the same transition kernels) initialized at σ0+ = 1 and σ0− = 0, respectively.
In particular, the marginal distributions of σk+ and σk− are Pσ+k and Pσ−k , respectively. We construct the
monotone Markovian coupling {(σk+ , σk− ) : k ∈ N} between the Markov chains {σk+ : k ∈ N} and
{σk− : k ∈ N} such that for every k ∈ N, σk+ ≥ σk− almost surely. Notice that 1 = σ0+ ≥ σ0− = 0 is true
by assumption. Suppose for some k ∈ N, σk+ ≥ σk− almost surely. We define the conditional distribution
+
−
+
of (σk+1
, σk+1
) given (σk+ , σk− ) = (σ + , σ − ) as the well-known monotone coupling of Lk+1 σk+1
∼
−
+
−
+
−
binomial(Lk+1 , g(σ )) and Lk+1 σk+1 ∼ binomial(Lk+1 , g(σ )) so that σk+1 ≥ σk+1 almost surely
given (σk+ , σk− ) = (σ + , σ − ). Such a monotone coupling exists because g(σ + ) ≥ g(σ − ) since g is a
non-decreasing function and σ + ≥ σ − . This recursively generates a Markov chain {(σk+ , σk− ) : k ∈ N}
with the following properties:
1) The “marginal” Markov chains are {σk+ : k ∈ N} and {σk− : k ∈ N}.
+
2) For every j > k ≥ 1, σj+ is conditionally independent of σ0− , . . . , σk− , σ0+ , . . . , σk−1
given σk+ , and
−
+
+
−
−
−
σj is conditionally independent of σ0 , . . . , σk , σ0 , . . . , σk−1 given σk .
3) For every k ∈ N, σk+ ≥ σk− almost surely.

13

In the sequel, probabilities of events that depend on the random variables in {(σk+ , σk− ) : k ∈ N} are
defined with respect to this Markovian coupling. We next prove that there exists  > 0 such that:


+
∀k ∈ N\{0}, P σk+ ≥ σ̂ −  σk−1
≥ σ̂ − , Ak,j ≥ 1 − exp −2Lk γ()2
(30)
where γ() , g(σ̂ − ) − (σ̂ − ) > 0, and Ak,j with 0 ≤ j < k is the non-zero probability event defined
as:

{σj− ≤ 1 − σ̂ + }
, 0≤j =k−1
Ak,j ,
.
+
{σk−2
≥ σ̂ − , . . . , σj+ ≥ σ̂ − } ∩ {σj− ≤ 1 − σ̂ + } , 0 ≤ j ≤ k − 2
Since g 0 (σ̂) < 1 and g(σ̂) = σ̂ , g(σ̂ − ) > σ̂ −  for sufficiently small  > 0. Fix any such  > 0
such that γ() > 0. Recall that Lk σk ∼ binomial(Lk , g(σ)) given σk−1 = σ . This implies that for every
k ∈ N\{0} and every 0 ≤ j < k :



+
+
P σk+ < g σk−1
− γ() σk−1
= σ, Ak,j = P(σk < g(σk−1 ) − γ()|σk−1 = σ) ≤ exp −2Lk γ()2
where the equality follows from property 2 of our Markovian coupling, and the inequality follows from
(24) and Hoeffding’s inequality [Hoe63, Theorem 1]. As a result, we have:
X



+
+
+
= σ Ak,j
P σk+ < g σk−1
− γ() σk−1
= σ, Ak,j P σk−1
σ≥σ̂−

≤ exp −2Lk γ()2

P
P

σk+
σk+

<g
<g

+
σk−1

+
σk−1



−
−

+
γ(), σk−1
≥ σ̂ −  Ak,j

+
γ() σk−1 ≥ σ̂ − , Ak,j



2

≤ exp −2Lk γ()

 X


+
= σ Ak,j
P σk−1

σ≥σ̂−
+
P σk−1

≥ σ̂ −  Ak,j






≤ exp −2Lk γ()2 .

+
+
Finally, notice that σk+ < σ̂ −  = g(σ̂ − ) − γ() implies that σk+ < g(σk−1
) − γ() when σk−1
≥ σ̂ − 
+
(since g is non-decreasing and g(σk−1 ) ≥ g(σ̂ − )). This produces:


+
≥ σ̂ − , Ak,j ≤ exp −2Lk γ()2
P σk+ < σ̂ −  σk−1

which in turn establishes (30).
Now fix any τ > 0, and choose a sufficiently large value K = K(, τ ) ∈ N (that depends on  and τ )
such that:
∞
X

exp −2Lm γ()2 ≤ τ .
(31)
m=K+1

Note that such K exists because

P∞


1
exp −2Lm γ()2 ≤ 2
m

m=1 1/m

⇔

2

= π 2 /6 < +∞, and for sufficiently large m, we have:

−2Lm γ()2 ≤ −2 log(m)

⇔

log(m)
≤ γ()2
Lm

(32)

since Lm = ω(log(m)) (i.e. limm→∞ log(m)/Lm = 0). Using the continuity of probability measures,
observe that:
!
\ 
Y

+
+
−
+
P
σk ≥ σ̂ −  σK ≥ σ̂ − , σK ≤ 1 − σ̂ +  =
P σk+ ≥ σ̂ −  σk−1
≥ σ̂ − , Ak,K
k>K

k>K

≥

Y

1 − exp −2Lk γ()2



X



k>K

≥1−

k>K

≥1−τ

14

exp −2Lk γ()2

where the first inequality follows from (30), the second inequality is straightforward to establish using
induction, and the final inequality follows from (31). Therefore, we have for any k > K :

+
−
P σk+ ≥ σ̂ −  σK
≥ σ̂ − , σK
≤ 1 − σ̂ +  ≥ 1 − τ .
(33)
Likewise, we can also prove mutatis mutandis that for any k > K :

+
−
P σk− ≤ 1 − σ̂ +  σK
≥ σ̂ − , σK
≤ 1 − σ̂ +  ≥ 1 − τ

(34)

where the choices of , τ , and K in (34) are the same as those in (33) without loss of generality.
We need to show that lim supk→∞ P(Ŝk 6= σ0 ) < 12 , or equivalently, that there exists λ > 0 such that
for all sufficiently large k ∈ N:
 1 
 1−λ
 1 

P Ŝk 6= σ0 = P Ŝk 6= σ0 σ0 = 1 + P Ŝk 6= σ0 σ0 = 0 ≤
2
2

 2 

1
1
⇔ P σk <
σ0 = 1 + P σk ≥
σ0 = 0 ≤ 1 − λ
2
2




1
1
−
+
− P σk ≥
≥ λ.
⇔ P σk ≥
2
2
 +
−
To this end, let E = σK
≥ σ̂ − , σK
≤ 1 − σ̂ +  , and observe that for all k > K :




 



1
1
1
1
+
−
+
−
P σk ≥
− P σk ≥
= E 1 σk ≥
− 1 σk ≥
2
2
2
2




 
1
1
−
+
− 1 σk ≥
1{E}
≥ E 1 σk ≥
2
2
 


 
1
1
+
−
= E 1 σk ≥
− 1 σk ≥
E P(E)
2
2
 



1
1
+
−
= P σk ≥
E − P σk ≥
E
P(E)
2
2


≥ P σk+ ≥ σ̂ −  E − P σk− > 1 − σ̂ +  E P(E)
≥ (1 − 2τ )P(E) , λ > 0


where the first inequality holds because 1 σk+ ≥ 12 − 1 σk− ≥ 12 ≥ 0 almost surely due to the monotonicity (property 3) of our Markovian coupling, the second inequality holds because 1− σ̂+ < 21 < σ̂−
(since  > 0 is small), and the final inequality follows from (33) and (34). This completes the proof for
the δ ∈ 0, 16 regime.

We next prove that δ ∈ 61 , 12 implies:
h
i
lim E Pσ+k |G − Pσ−k |G
= 0.
(35)
k→∞

TV

Recall that we are considering the monotone Markovian coupling {(σk+ , σk− ) : k ∈ N} such that σk+ ≥ σk−
almost surely for every k ∈ N. Then, it is also true that conditioned on an underlying random DAG G,
σk+ ≥ σk− almost surely for every k ∈ N. Now observe that given a random DAG G:





1
+
−
+
−
+
−
G ≤ Lk E σk+ − σk− G
Pσk |G − Pσk |G
≤ P σk 6= σk G = P σk − σk ≥
Lk
TV
where the first inequality follows from Dobrushin’s maximal coupling representation of TV distance
[LPW09, Chapter 4.2], the middle equality holds because the possible values of σk+ and σk− are {m/Lk :
m = 0, . . . , Lk }, and the final inequality follows from Markov’s inequality since σk+ − σk− ≥ 0 almost
surely given G. Taking expectations with respect to G, we have:
h
i


E Pσ+k |G − Pσ−k |G
≤ Lk E σk+ − σk− .
(36)
TV

15



We can bound E σk+ − σk− as follows. Firstly, we use the Lipschitz continuity of g (with Lipschitz
constant 32 (1 − 2δ)) to get:




 3
+
−
+
−
+
−
0 ≤ E σk+ − σk− σk−1
− σk−1
.
(37)
, σk−1
= g σk−1
− g σk−1
≤ (1 − 2δ) σk−1
2
Then, we notice that:


 
 +

+
−
+
−
+
−
−
0 ≤ E σk+ − σk− σk−2
, σk−2
= E E σk+ − σk− σk−1
, σk−1
, σk−2
, σk−2
σk−2 , σk−2
 
 +

+
−
−
= E E σk+ − σk− σk−1
, σk−1
σk−2 , σk−2
 +

3
−
+
−
− σk−1
σk−2
, σk−2
≤ (1 − 2δ) E σk−1
2
2


3
+
−
(1 − 2δ)
σk−2
− σk−2
≤
2
where the first equality follows from the tower property, the second equality follows from the Markov
property, and the final two inequalities both follow from (37). Therefore, we recursively have:
k


 +
3
−
(1 − 2δ)
0 ≤ E σk − σk ≤
2




where we use the facts that E σk+ − σk− σ0+ , σ0− = E σk+ − σk− and σ0+ − σ0− = 1. Finally, using (36),
we get:

k
i
h
3
−
+
≤ Lk
E Pσk |G − Pσk |G
(1 − 2δ)
2
TV
which in turn implies (35) because Lk = o((2/(3(1 − 2δ)))k ) by assumption. (It is worth mentioning
that although Lk = o((2/(3(1 − 2δ)))k ) in this regime, it can diverge to infinity because the Lipschitz
constant 23 (1 − 2δ) < 1.) This completes the proof.


We remark that in the δ ∈ 0, 61 regime, we can see from (32) that Lk ≥ log(k)/γ()2 for all
sufficiently large k suffices for the proof to hold, where a sufficiently small  = (δ) > 0 is fixed that
depends on δ and ensures that γ() > 0. So, the condition that Lk = ω(log(k)) can be relaxed.
In the next proposition, we show that if Lk = ω(log(k)), then the Markov chain {σk : k ∈ N}
converges almost surely.

Proposition 3 (Majority Random DAG Model Almost Sure Convergence). If δ ∈ δmaj , 12 and Lk =
ω(log(k)), then limk→∞ σk = 21 almost surely.
Proof. Recall that Lk σk ∼ binomial(Lk , g(σ)) given σk−1 = σ . This implies via Hoeffding’s inequality
and (24) that for every k ∈ N\{0} and k > 0:

P(|σk − g(σk−1 )| > k |σk−1 = σ) ≤ 2 exp −2Lk 2k
where we can take expectations with respect to σk−1 to get:

P(|σk − g(σk−1 )| > k ) ≤ 2 exp −2Lk 2k .

(38)

Now fix any τ > 0, and choose a sufficiently large integer K ∈ N (that depends on τ ) such that:
P(∃k > K, |σk − g(σk−1 )| > k ) ≤

∞
X

P(|σk − g(σk−1 )| > k ) ≤ 2

k=K+1

where we use the union bound, and let k =
implies that for any τ > 0:

p

∞
X


exp −2Lk 2k ≤ τ

k=K+1


log(k)/Lk (or equivalently, exp −2Lk 2k = 1/k 2 ). This

P(∀k > K, |σk − g(σk−1 )| ≤ k ) ≥ 1 − τ .
16

(39)

Since for every k > K , |σk − g(σk−1 )| ≤ k , we can recursively obtain the following relation:
∀k ∈ N\[K + 1],

k
X

σk − g (k−K) (σK ) ≤

ck−m m

(40)

m=K+1


where g (k−K) denotes g composed with itself k − K times, and c = 32 (1 − 2δ) ∈ (0, 1) (since δ ∈ 61 , 12 )
denotes the Lipschitz constant of g on [0, 1]. Since Lm = ω(log(m)), for any  > 0, we can take
K = K(, τ ) (which depends on both  and τ ) to be sufficiently large so that supm>K m ≤ (1 − c).
Now observe that we have:

X


k
∞
X
1
k−m
j
∀k ∈ N\[K + 1],
c
m ≤ sup m
c = sup m
≤ .
1−c
m>K
m>K
j=0

m=K+1

g (m) (σ

1
2

by the fixed point theorem [Rud76, Chapter 5, Exercise
Moreover, notice that limm→∞
K) =
22(c)] (recalling that σ = 21 is the only fixed point of g when δ ∈ 61 , 12 ). As a result, for any τ > 0
and any  > 0, there exists K = K(, τ ) ∈ N such that:


P ∀k > K, σk − g (k−K) (σK ) ≤  ≥ 1 − τ
which implies, after letting k → ∞, that:


1
1
−  ≤ lim inf σk ≤ lim sup σk ≤ +  ≥ 1 − τ .
P
k→∞
2
2
k→∞
Lastly, we can first let  → 0 and employ the continuity of P, and then let τ → 0 to obtain:


1
P lim σk =
= 1.
k→∞
2
This completes the proof.



Proposition 3 can be construed as a “weak” impossibility result since it demonstrates that the average
number of 1’s tends to 12 in the δ ∈ 16 , 12 regime regardless of initial state of the Markov chain
{σk : k ∈ N}.
III. A NALYSIS OF AND-OR RULE P ROCESSING IN R ANDOM DAG M ODEL
In this section, we prove Theorem 2. As before, we begin by making some pertinent observations.
Recall that we have a random DAG model with d = 2, and all Boolean functions at even levels are the
AND rule, and all Boolean functions at odd levels are the OR rule, i.e. fk (x1 , x2 ) = x1 ∧ x2 for every
k ∈ 2N\{0}, and fk (x1 , x2 ) = x1 ∨ x2 for every k ∈ N\2N. Suppose we are given that σk−1 = σ . Then,
for every k ∈ N\{0} and every j ∈ [Lk ]:

Bernoulli(σ ? δ) ∧ Bernoulli(σ ? δ) , if k even
Xk,j =
(41)
Bernoulli(σ ? δ) ∨ Bernoulli(σ ? δ) , if k odd
for two i.i.d. Bernoulli random variables. Since we have:

(σ ? δ)2
, if k even
P(Xk,j = 1|σk−1 = σ) =
2
1 − (1 − σ ? δ) , if k odd
= E[σk |σk−1 = σ] ,

(42)
(43)

Xk,j are i.i.d. Bernoulli(gk (mod 2) (σ)) for j ∈ [Lk ], and Lk σk ∼ binomial(Lk , gk (mod 2) (σ)), where we
define g0 : [0, 1] → [0, 1] as g0 (σ) , (σ ? δ)2 , and g1 : [0, 1] → [0, 1] as g1 (σ) , 1 − (1 − σ ? δ)2 =
2(σ ? δ) − (σ ? δ)2 . The derivatives of g0 and g1 are:
g00 (σ) = 2(1 − 2δ)(σ ? δ) ≥ 0 ,

(44)

g10 (σ)

(45)

= 2(1 − 2δ)(1 − σ ? δ) ≥ 0 .

17

Consider the composition of g0 and g1 , g , g0 ◦ g1 : [0, 1] → [0, 1], g(σ) =
which has derivative g 0 : [0, 1] → R+ given by:

 2
2(σ ? δ) − (σ ? δ)2 ? δ ,

g 0 (σ) = g00 (g1 (σ))g10 (σ)
= 4(1 − 2δ)2 (g1 (σ) ? δ)(1 − σ ? δ) ≥ 0 .

This is a cubic function of σ with maximum value:
 


q
√ i
9− 33
1−δ
 g 0 1−δ −
,
δ
∈
0,
3
1−2δ
3(1−2δ)
 √ 12 
C(δ) , max g 0 (σ) =
 g 0 (0)
σ∈[0,1]
, δ ∈ 9−12 33 , 12
 

3
√ i
9− 33
 4(1−δ)(1−2δ) 2
,
δ
∈
0,
3
 √ 12 
=
 4δ(1 − δ)2 (1 − 2δ)2 (3 − 2δ) < 1 , δ ∈ 9− 33 , 1
12
2

(46)

(47)

(48)

which follow from standard calculus and algebraic manipulations, and Wolfram Mathematica computations. Hence,
√ is the Lipschitz constant of g over [0, 1]. Since
√ 4(1 − δ)(1 − 2δ)/3 ∈ (0, 1) ⇔
√ C(δ) in (48)
δ ∈ ((3 − 7)/4, (9 − 33)/12]
, C(δ) < 1 if and only if δ ∈ ((3√− 7)/4, 1/2). Moreover, C(δ) > 1
√
if and only if δ ∈ (0, (3 − 7)/4) (and C(δ) = 1 when δ = (3 − 7)/4).
We next summarize the fixed point structure of g . Solving the equation g(σ) = σ in Wolfram
Mathematica produces:
√
√
1 − 6δ + 4δ 2 ± 1 − 12δ + 8δ 2 3 − 6δ + 4δ 2 ± 5 − 12δ + 8δ 2
,
(49)
σ=
2(1 − 2δ)2
2(1 − 2δ)2
√
where the first pair is real when δ ∈ [0, (3 − 7)/4], and the second pair is always real. From these
solutions, it is straightforward to verify that the only fixed points of g in the interval [0, 1] are:
p
√ 

2(1 − δ)(1 − 2δ) − 1 − 4(1 − δ)(1 − 2δ) − 3
3− 7
t0 ,
(valid when δ ∈ 0,
)
(50)
2(1 − 2δ)2
4
p
√


2(1 − δ)(1 − 2δ) − 1 + 4(1 − δ)(1 − 2δ) − 3
3− 7
(valid
when
δ
∈
0,
)
(51)
t1 ,
2(1 − 2δ)2
4
p
2(1 − δ)(1 − 2δ) + 1 − 4(1 − δ)(1 − 2δ) + 1
t,
(52)
2(1 − 2δ)2
√
which satisfy t0 = t1 = t when δ = (3 − 7)/4, and t0 = 0, t1 = 1 when δ = 0. Furthermore, observe
that:
√
√
√
√
a+ a+4−2
a− a+4+2
t1 − t =
> 0 and t − t0 =
>0
(53)
2(1 − 2δ)2
2(1 − 2δ)2
√
√
where a = 4(1 − δ)(1√− 2δ)√− 3 > 0 for δ ∈ (0, (3 − 7)/4), t1 − t >√ 0 because x 7→ x is
strictly
increasing
x 7→ x is strictly subadditive
√ (⇒ a + a + 4 > 2), and t − t0 > 0 because √
√
(⇒ a + 2 > a + 4). Hence, 0 < t0 < t < t1 < 1 when δ ∈ (0, (3 − 7)/4)√
.
Therefore, there are again two regimes of interest. In the regime δ ∈ (0, (3 − √7)/4), g has three fixed
points 0 < t0 < t < t1 < 1, and C(δ) > 1. In contrast, in the regime δ ∈ ((3 − 7)/4, 1/2), g has only
one fixed point at t ∈ (0, 1), and C(δ) < 1. We now prove Theorem 2.
Proof of Theorem 2. The proof √
of this result closely resembles the proof of Theorem 1 in section II.
We first prove that δ ∈ 0, (3 − 7)/4 implies lim supk→∞ P(Ŝ2k 6= σ0 ) < 21 . As before, since g0 and
g1 are non-decreasing functions, we can construct a monotone Markovian coupling {(σk+ , σk− ) : k ∈ N}
between {σk+ : k ∈ N} and {σk− : k ∈ N}, which are versions of the Markov chain {σk : k ∈ N} initialized
at σ0+ = 1 and σ0− = 0, respectively. This Markovian coupling satisfies the following properties:
18

1) The “marginal” Markov chains are {σk+ : k ∈ N} and {σk− : k ∈ N}.
+
2) For every j > k ≥ 1, σj+ is conditionally independent of σ0− , . . . , σk− , σ0+ , . . . , σk−1
given σk+ , and
−
σj− is conditionally independent of σ0+ , . . . , σk+ , σ0− , . . . , σk−1
given σk− .
+
−
3) For every k ∈ N, σk ≥ σk almost surely.
We next prove that there exists  > 0 such that:



(L2k ∧ L2k−1 )γ()2
+
+
(54)
∀k ∈ N\{0}, P σ2k ≥ t1 −  σ2k−2 ≥ t1 − , Ak,j ≥ 1 − 4 exp −
8
where γ() , g(t1 − ) − (t1 − ) > 0, and Ak,j with 0 ≤ j < k is the non-zero probability event defined
as:

−
{σ2j
≤ t0 + }
, 0≤j =k−1
Ak,j ,
.
+
+
+
−
{σ2k−4 ≥ t1 − , σ2k−6 ≥ t1 − , . . . , σ2j ≥ t1 − } ∩ {σ2j ≤ t0 + } , 0 ≤ j ≤ k − 2
Since g 0 (t1 ) = 4δ(3 − 2δ) < 1 and g(t1 ) = t1 , g(t1 − ) > t1 −  for sufficiently small  > 0. Fix any
such  > 0 such that γ() > 0. Observe that for every k ∈ N\{0} and ξ > 0, we have:
P(|σ2k − g(σ2k−2 )| > ξ|σ2k−2 = σ)
≤ P(|σ2k − g0 (σ2k−1 )| + |g0 (σ2k−1 ) − g0 (g1 (σ2k−2 ))| > ξ|σ2k−2 = σ)
≤ P(|σ2k − g0 (σ2k−1 )| + 2(1 − δ)(1 − 2δ)|σ2k−1 − g1 (σ2k−2 )| > ξ|σ2k−2 = σ)
 



ξ
ξ
∪ 2(1 − δ)(1 − 2δ)|σ2k−1 − g1 (σ2k−2 )| >
σ2k−2 = σ
≤P
|σ2k − g0 (σ2k−1 )| >
2
2




ξ
ξ
≤ P |σ2k − g0 (σ2k−1 )| > σ2k−2 = σ + P |σ2k−1 − g1 (σ2k−2 )| >
σ2k−2 = σ
2
4(1 − δ)(1 − 2δ)




 
ξ
L2k−1 ξ 2
≤ E P |σ2k − g0 (σ2k−1 )| > σ2k−1 σ2k−2 = σ + 2 exp −
2
8(1 − δ)2 (1 − 2δ)2




L2k ξ 2
L2k−1 ξ 2
≤ 2 exp −
+ 2 exp −
2
8(1 − δ)2 (1 − 2δ)2


(L2k ∧ L2k−1 )ξ 2
≤ 4 exp −
(55)
8

where the first inequality follows from the triangle inequality and the fact that g = g0 ◦ g1 , the second inequality holds because the Lipschitz constant of g0 on [0, 1] is maxσ∈[0,1] g00 (σ) = g00 (1) =
2(1 − δ)(1 − 2δ) using (44), the fourth inequality follows from the union bound, the fifth and sixth
inequalities follow from the Markov property and Hoeffding’s inequality (as well as the fact that Lk σk ∼
binomial(Lk , gk (mod 2) (σ)) given σk−1 = σ ), the final inequality holds because (1 − δ)2 (1 − 2δ)2 ≤ 1,
and ∧ denotes the minimum operation. Hence, for any k ∈ N\{0} and any 0 ≤ j < k , we have:


+
+
+
P σ2k
< g σ2k−2
− γ() σ2k−2
= σ, Ak,j = P( σ2k < g(σ2k−2 ) − γ() | σ2k−2 = σ)
≤ P(|σ2k − g(σ2k−2 )| > γ()|σ2k−2 = σ)


(L2k ∧ L2k−1 )γ()2
≤ 4 exp −
8

where the first equality follows from property 2 of the Markovian coupling, and the final inequality
follows from (55). As shown in the proof of Theorem 1, this produces:




(L2k ∧ L2k−1 )γ()2
+
+
+
P σ2k < g σ2k−2 − γ() σ2k−2 ≥ t1 − , Ak,j ≤ 4 exp −
8



(L2k ∧ L2k−1 )γ()2
+
+
P σ2k < t1 −  σ2k−2 ≥ t1 − , Ak,j ≤ 4 exp −
8
19

+
where the second inequality follows from the first because σ2k
< t1 −  = g(t1 − ) − γ() implies that
+
+
+
+
σ2k < g(σ2k−2 ) − γ() when σ2k−2 ≥ t1 −  (since g is non-decreasing and g(σ2k−2
) ≥ g(t1 − )). This
proves (54).
Now fix any τ > 0, and choose a sufficiently large even integer K = K(, τ ) ∈ 2N (that depends on
 and τ ) such that:


∞
X
(L2m ∧ L2m−1 )γ()2
exp −
≤τ.
(56)
4
8
K
m=

Note that such K exists because

2

+1

P∞

= π 2 /6 < +∞, and for sufficiently large m, we have:


(L2m ∧ L2m−1 )γ()2
1
exp −
≤ 2
8
m
m=1 1/m

2

since Lm = ω(log(m)). Using the continuity of probability measures, observe that:



Y 
\ 
+
+
−
+
+
σ2k
≥ t 1 −  σK
≥ t1 − , σK
≤ t0 +  =
P σ2k
≥ t1 −  σ2k−2
≥ t1 − , Ak, K
P
2

k> K
2

k> K
2



(L2k ∧ L2k−1 )γ()2
≥
1 − 4 exp −
8
K
k> 2


X
(L2k ∧ L2k−1 )γ()2
≥1−4
exp −
8
K
Y

k>

2

≥1−τ

where the first inequality follows from (54), and the final inequality follows from (56). Therefore, we
have for any k > K2 :

−
+
+
≤ t0 +  ≥ 1 − τ .
(57)
≥ t1 − , σK
≥ t1 −  σK
P σ2k
Likewise, we can also prove mutatis mutandis that for any k >

K
2:


−
+
−
≤ t0 +  ≥ 1 − τ
≥ t1 − , σK
≤ t0 +  σK
P σ2k

(58)

where , τ , and K in (58)
to be the same as those in (57) without loss of generality.
 +can be chosen
−
Finally, we let E = σK
≥ t1 − , σK
≤ t0 +  , and observe that for all k > K2 :


  +
 −


+
−
P σ2k
≥ t − P σ2k
≥ t ≥ E 1 σ2k
≥ t − 1 σ2k
≥ t 1{E}


+
−
= P σ2k
≥ t E − P σ2k
≥ t E P(E)


+
−
≥ P σ2k
≥ t1 −  E − P σ2k
> t0 +  E P(E)
≥ (1 − 2τ )P(E) > 0
 +
 −
where the first inequality holds because 1 σ2k
≥ t − 1 σ2k
≥ t ≥ 0 almost surely due to the monotonicity (property 3) of our Markovian coupling, the second inequality holds because t0 +  < t < t1 − 
(since  > 0 is small), and the final inequality follows from (57) and (58). As argued in the proof of
1
Theorem 1, this illustrates that lim
√ supk→∞ P(T̂2k 6= σ0 ) < 2 .
We next prove that δ ∈ ((3 − 7)/4, 1/2) implies:
h
i
lim E Pσ+2k |G − Pσ−2k |G
= 0.
(59)
k→∞

TV

20

In the regime where Lk = o(log(k)), we have the desired result due to part 2 of Proposition 1 in
subsection I-F. So, we will assume that Lk → ∞ as k → ∞ in the remaining proof. Observe that given
a random DAG G:


 +


1
+
−
−
+
−
+
−
Pσ2k |G − Pσ2k |G
G ≤ L2k E σ2k
− σ2k
≤ P σ2k 6= σ2k G = P σ2k − σ2k ≥
G
L2k
TV
+
−
where we use the monotone Markovian coupling defined earlier which ensures that σ2k
≥ σ2k
almost
surely for every k ∈ N given G, the first inequality uses the maximal coupling representation of TV
distance, and the final inequality follows from Markov’s inequality. Taking expectations with respect to
G, we have:
h
i
 +

−
E Pσ+2k |G − Pσ−2k |G
≤ L2k E σ2k
− σ2k
.
(60)
TV
 +

−
We can bound E σ2k − σ2k
as follows. Firstly, for any k ∈ N\{0}, we have:
 +

  +
 +

−
+
−
−
+
−
−
E σ2k − σ2k
σ2k−2
, σ2k−2
= E E σ2k
− σ2k
σ2k−1
, σ2k−1
σ2k−2 , σ2k−2


 +

+
−
−
= E g0 σ2k−1
− g0 σ2k−1
σ2k−2 , σ2k−2
(61)

where the first equality follows from the tower and Markov properties, and the second equality holds
because L2k σ2k ∼ binomial(L2k , g0 (σ)) given σ2k−1 = σ . Then, recalling that g0 (σ) = (σ ? δ)2 =
(1 − 2δ)2 σ 2 + 2δ(1 − 2δ)σ + δ 2 , we can compute:

 +


 + 
+
−
+
E g0 σ2k−1
σ2k−2 , σ2k−2
= E g0 σ2k−1
σ2k−2


+
+
2 + 2
= E (1 − 2δ) σ2k−1 + 2δ(1 − 2δ)σ2k−1
+ δ 2 σ2k−2


 +
2 
+
+
+
σ2k−2
+ E σ2k−1
σ2k−2
= (1 − 2δ)2 VAR σ2k−1
 +

+
+ 2δ(1 − 2δ)E σ2k−1
σ2k−2
+ δ2
2

+
+
+ 2δ(1 − 2δ)g1 σ2k−2
+ δ2
= (1 − 2δ)2 g1 σ2k−2


+
+
1 − g1 σ2k−2
g1 σ2k−2
+ (1 − 2δ)2
L2k−1


+

g σ+
1 − g1 σ2k−2
+
2 1 2k−2
(62)
= g σ2k−2 + (1 − 2δ)
L2k−1
where the first equality uses property 2 of the monotone Markovian coupling, and the fourth equality
uses the fact that L2k−1 σ2k−1 ∼ binomial(L2k−1 , g1 (σ)) given σ2k−2 = σ . Using (61) and (62), we get:
 +



+
−
+
−
−
E σ2k
− σ2k
σ2k−2
, σ2k−2
= g σ2k−2
− g σ2k−2



 !
+
+
−
−
g
σ
1
−
g
σ
−
g
σ
1
−
g
σ
1
1
1
1
2k−2
2k−2
2k−2
2k−2
+ (1 − 2δ)2
L2k−1


+
−
= g σ2k−2 − g σ2k−2

2
2  

 
+
−
+
−
g1 σ2k−2
− g1 σ2k−2
− g1 σ2k−2
− g1 σ2k−2

+ (1 − 2δ)2 
L2k−1

!
+
−


g
σ
−
g
σ
1
1
2k−2
2k−2
+
−
≤ g σ2k−2
− g σ2k−2
+ (1 − 2δ)2
L2k−1



2(1 − δ)(1 − 2δ)3
+
−
≤ C(δ) +
σ2k−2
− σ2k−2
L2k−1



2
+
−
≤ C(δ) +
σ2k−2
− σ2k−2
(63)
L2k−1
21

2
2
+
−
where the first inequality holds because g1 σ2k−2
− g1 σ2k−2
≥ 0 almost surely (since g1 is non+
−
negative and non-decreasing by (45), and σ2k−2
≥ σ2k−2
almost surely by property 3 of the monotone
+
−
Markovian coupling), the second inequality holds because σ2k−2
≥ σ2k−2
almost surely and g and g1 have
0
Lipschitz constants C(δ) and maxσ∈[0,1] g1 (σ) = 2(1 − δ)(1 − 2δ) respectively, and the final inequality
holds because (1 − δ)(1 − 2δ)3 ≤ 1.
Then, as in the proof of Theorem 1, we notice using (63) that:
 +

  +
 +

−
+
−
−
+
−
−
0 ≤ E σ2k
− σ2k
σ2k−4
, σ2k−4
= E E σ2k
− σ2k
σ2k−2
, σ2k−2
σ2k−4 , σ2k−4


 +

2
−
+
−
E σ2k−2
− σ2k−2
σ2k−4
, σ2k−4
≤ C(δ) +
L2k−1




2
2
+
−
C(δ) +
σ2k−4
− σ2k−4
≤ C(δ) +
L2k−1
L2k−3
which recursively produces:

k 
 +
 Y
2
−
0 ≤ E σ2k − σ2k ≤
C(δ) +
L2i−1
i=1
 +


 +
−
−
and σ0+ − σ0− = 1. Finally, using
σ0+ , σ0− = E σ2k
− σ2k
where we use the facts that E σ2k
− σ2k
(60), we get:

k 
i
h
Y
2
−
+
C(δ) +
≤ L2k
E Pσ2k |G − Pσ2k |G
.
(64)
L2i−1
TV
i=1
k
Recall that Lk = o (C(δ) + )− 2 for some  ∈ (0, 1 − C(δ)) (that can depend on δ ), and furthermore,
we can assume that Lk → ∞ as k → ∞. Hence, there exists K = K() ∈ N (that depends on ) such
that for all i > K , L2i−1 > 2 . This means that we can further upper bound (64) as follows:

K 
i
h
Y
2
−
+
k−K
C(δ) +
≤ L2k (C(δ) + )
∀k > K, E Pσ2k |G − Pσ2k |G
.
L2i−1
TV
i=1

Letting k → ∞ produces (59). This completes the proof.



The remarks
after the proof of Theorem 1 in section II also apply here. In particular, in the δ ∈
√
(0, (3 − 7)/4) regime, the Lk = ω(log(k)) condition can be relaxed to Lk ≥ h(δ) log(k) for all
sufficiently large k , where h(δ) is some fixed constant that depends on δ .
In the next proposition, we show that if Lk = ω(log(k)), then the Markov chain {σ2k : k ∈ N}
converges almost surely.

Proposition 4 (AND-OR Random DAG Model Almost Sure Convergence). If δ ∈ δandor , 12 and Lk =
ω(log(k)), then limk→∞ σ2k = t almost surely.
Proof. This proof is analogous to the proof of Proposition 3. For every k ∈ N\{0} and k > 0, we have
after taking expectations in (55) that:


(L2k ∧ L2k−1 )2k
P(|σ2k − g(σ2k−2 )| > k ) ≤ 4 exp −
.
(65)
8
Now fix any τ > 0, and choose a sufficiently large integer K ∈ N (that depends on τ ) such that:
∞
X
P(∃k ∈ N, k > K, |σ2k − g(σ2k−2 )| > k ) ≤
P(|σ2m − g(σ2m−2 )| > m )
m=K+1
∞
X

≤4

m=K+1

22



(L2m ∧ L2m−1 )2m
exp −
≤τ
8

p
where we use the union bound and (65), and we set m = 4 log(m)/(L2m ∧ L2m−1 ) (which ensures
that exp(−(L2m ∧ L2m−1 )2m /8) = 1/m2 ). This implies that for any τ > 0:
P(∀k ∈ N, k > K, |σ2k − g(σ2k−2 )| ≤ k ) ≥ 1 − τ .

(66)

Since for every k > K , |σ2k − g(σ2k−2 )| ≤ k , we can recursively obtain the following relation:
∀k ∈ N, k > K,

σ2k − g

(k−K)

(σ2K ) ≤

k
X

C(δ)k−m m

(67)

m=K+1

where g (k−K) denotes g composed with itself k − K times, and
√ C(δ) denotes the Lipschitz constant of
g on [0, 1] as shown in (48), which is in (0, 1) since δ ∈ ((3 − 7)/4, 1/2). Since Lm = ω(log(m)), for
any  > 0, we can take K = K(, τ ) ∈ N (which depends on both  and τ ) to be sufficiently large so
that supm>K m ≤ (1 − C(δ)). This implies that:
∀k ∈ N, k > K,

k
X

C(δ)k−m m ≤ 

m=K+1

as
δ ∈ ((3−
√ shown in the proof of Proposition 3. Moreover, since g : [0, 1] → [0, 1] is a contraction when
7)/4, 1/2), it has a unique fixed point t ∈ [0, 1] by the fixed point theorem, and limm→∞ g (m) (σK ) = t
almost surely. As a result, for any τ > 0 and any  > 0, there exists K = K(, τ ) ∈ N such that:


P ∀k ∈ N, k > K, σ2k − g (k−K) (σ2K ) ≤  ≥ 1 − τ
which implies, after letting k → ∞, that:


P t −  ≤ lim inf σ2k ≤ lim sup σ2k ≤ t +  ≥ 1 − τ .
k→∞

k→∞

Lastly, we can first let  → 0 and employ the continuity of P, and then let τ → 0 to obtain:


P lim σ2k = t = 1 .
k→∞



This completes the proof.
Much like Proposition 3, Proposition 4 can also be construed as a “weak” impossibility result.
IV. A NALYSIS OF D ETERMINISTIC AND 2D G RID

We now turn to proving Theorem 3. Recall that we are given a deterministic 2D grid where all Boolean
processing functions with two inputs are the AND rule, and all Boolean processing functions with one
input are the identity rule, i.e. f1 (x1 , x2 ) = x1 ∧ x2 and f2 (x) = x.
As in our proofs with random DAG models, we construct a “monotone” Markovian coupling of the
Markov chains {Xk+ : k ∈ N} and {Xk− : k ∈ N}, which denote versions of the Markov chain {Xk :
k ∈ N} initialized at X0+ = 1 and X0− = 0, respectively. We define the coupled 2D grid variables
−
+
{Yk,j = (Xk,j
, Xk,j
) : k ∈ N, j ∈ [k + 1]} and let the Markovian coupling be {Yk = (Yk,0 , . . . , Yk,k ) :
k ∈ N}. Recall that each edge
BSC(δ) either copies its input bit with probability 1 − 2δ , or produces

1
an independent Bernoulli 2 bit with probability 2δ (we will explicitly demonstrate this in the proof of
Proposition 1 in Appendix A). We couple {Xk+ : k ∈ N} and {Xk− : k ∈ N} so that along any edge
+
−
BSC of the 2D grid, say (Xk,j , Xk+1,j ), Xk,j
and Xk,j
are either both copied with probability 1 − 2δ ,

1
or a shared independent Bernoulli 2 bit is produced with probability 2δ that becomes the input to both
+
−
Xk+1,j
and Xk+1,j
. In other words, {Xk+ : k ∈ N} and {Xk− : k ∈ N} “run” on the same 2D grid and
have common BSCs. The Markovian coupling {Yk : k ∈ N} has the following properties:
1) The “marginal” Markov chains are {Xk+ : k ∈ N} and {Xk− : k ∈ N}.
23

+
−
2) For every k ∈ N, Xk+1
is conditionally independent of Xk− given Xk+ , and Xk+1
is conditionally
+
−
independent of Xk given Xk .
+
−
3) For every k ∈ N and every j ∈ [k + 1], Xk,j
≥ Xk,j
almost surely–this is the monotonicity in the
coupling.
+
−
The third property is straightforward to verify since X0,0
≥ X0,0
almost surely at the beginning, each
edge BSC preserves monotonicity (whether it copies its input or generates a new shared bit), and the
AND processing functions are monotonic in the sense that their outputs are non-decreasing when the
number of 1’s in their inputs increases.
Since the marginal Markov chains {Xk+ : k ∈ N} and {Xk− : k ∈ N} run on the same 2D grid with
common BSCs, we keep track of the Markov chain {Yk : k ∈ N} in a single coupled 2D grid. This 2D
grid has the same underlying graph as the deterministic 2D grid described in subsection I-D. Its nodes
−
+
are the coupled 2D grid variables {Yk,j = (Xk,j
, Xk,j
) : k ∈ N, j ∈ [k + 1]}, and we relabel the alphabet
−
+
of these variables for simplicity. So, each Yk,j = (Xk,j
, Xk,j
) ∈ Y , {0c , 1u , 1c }, where 0c = (0, 0),
1u = (0, 1), and 1c = (1, 1). (Note that we do not require a letter 0u = (1, 0) in this alphabet due to the
monotonicity in the coupling.) Furthermore, each edge of the coupled 2D grid is a channel (conditional
distribution) W between the alphabets Y and Y that captures the action of a shared BSC(δ)–we describe
W using the following row stochastic matrix:

0c
0c 1 − δ
W = 1u δ
1c
δ



1u
0
1 − 2δ
0

1c

δ
δ 
1−δ

(68)

where the (i, j)th entry gives the probability of output j given input i. It is straightforward to verify
that W describes the aforementioned Markovian coupling. Finally, the AND rule can be equivalently
described on the alphabet Y as:
x1 x2 x1 ∧ x2
0c ∗
0c
(69)
1u 1u
1u
1u 1c
1u
1c 1c
1c
where ∗ denotes any letter in Y , and the symmetry of the AND rule covers all other possible input
combinations. This coupled 2D grid model completely characterizes the Markov chain {Yk : k ∈ N},
which starts at Y0 = 1c almost surely. We next prove Theorem 3 by further analyzing this model.
Proof of Theorem 3. We first bound the TV distance between PX+k and PX−k using the maximal coupling
characterization of TV distance:


PX+k − PX−k TV ≤ P Xk+ 6= Xk− = 1 − P Xk+ = Xk− .
+
−
The events {Xk+ = Xk− } are non-decreasing, i.e. {Xk+ = Xk− } ⊆ {Xk+1
= Xk+1
} for all k ∈ N. Indeed,
+
−
+
−
suppose for any k ∈ N, the event {Xk = Xk } occurs. Since {Xk = Xk } = {Yk ∈ {0c , 1c }k+1 } =
{there are no 1u ’s in level k of the coupled 2D grid}, (68) and (69) imply that there are no 1u ’s in level
+
−
k + 1. Hence, the event {Xk+1
= Xk+1
} occurs as well. Letting k → ∞, we can use the continuity of
+
−
P with the events {Xk = Xk } to get:

lim PX+k − PX−k TV ≤ 1 − lim P Xk+ = Xk− = 1 − P(A)
k→∞

k→∞

where we define A , {∃k ∈ N, there are no 1u ’s in level k of the coupled 2D grid}. Therefore, it
suffices to prove that P(A) = 1.
24

To prove this, we recall a well-known result from [Dur84, Section 3] on oriented bond percolation
in two-dimensional lattices. Given the underlying DAG of our deterministic 2D grid from subsection
I-D, suppose we independently keep each edge “open” with some probability p ∈ [0, 1], and delete it
(“closed”) with probability 1 − p. Let Ω∞ be the event that there is an infinite open path starting at the
root. Furthermore, let Rk , sup{j ∈ [k + 1] : there is an open path from the root to the node (k, j)}
and Lk , inf{j ∈ [k + 1] : there is an open path from the root to the node (k, j)} be the rightmost and
leftmost nodes at level k ∈ N, respectively, that are connected to the root. (Here, we refer to the node
Xk,j using (k, j) as we no longer associate a random variable to it.) It is proved in [Dur84, Section 3]
that there exists a critical threshold δperc ∈ [0, 1] around which we observe the following phase transition
phenomenon:
1) If p > δperc , then Pp (Ω∞ ) > 0 and:


Rk
1 + α(p)
Lk
1 − α(p)
Pp lim
=
and lim
=
(70)
Ω∞ = 1
k→∞ k
k→∞ k
2
2
for some constant α(p) > 0, where α(p) is defined in [Dur84, Section 3, Equation (6)], and Pp is
the probability measure defined by the bond percolation process.
2) If p < δperc , then Pp (Ω∞ ) = 0.
We will use this to prove P(A) = 1 by considering two cases.
Case 1: Suppose 1−2δ < δperc (i.e. δ > (1−δperc )/2) in our coupled 2D grid. The root of the coupled
2D grid is Y0,0 = 1u almost surely, and we consider an oriented bond percolation process (as described
above) with p = 1 − 2δ . In particular, open edges correspond to BSCs that are copies (with probability
1 − 2δ ). In this context, Ωc∞ is the event that the number of nodes connected to the root via a sequence
of BSCs that are copies is finite. Suppose the event Ωc∞ occurs. Since (68) and (69) portray that a 1u
moves from level k to level k + 1 only if one of its outgoing edges is open (and the corresponding BSC
is a copy), there exists a level k such that no node at level k is a 1u . This proves that Ωc∞ ⊆ A. Using
part 2 of the phase transition in oriented bond percolation, we get P(A) = 1.
Case 2: Suppose 1 − δ > δperc (i.e. δ < 1 − δperc ) in our coupled 2D grid. Consider an oriented
bond percolation process (as described earlier) with p = 1 − δ that runs on the 2D grid, where an edge
is open when the corresponding BSC is either copying or generating a 0 as the new bit (i.e. this BSC
takes a 0c to a 0c , which happens with probability 1 − δ as shown in (68)). Let Bk for k ∈ N\{0} be
the event that the BSC from Yk−1,0 to Yk,0 generates a new bit which equals 0. Then, P(Bk ) = δ and
{Bk : k ∈ N\{0}} are mutually independent. So, the second Borel-Cantelli lemma tells us that infinitely
many of the Bk ’s occur almost surely. Furthermore, Bk ⊆ {Yk,0 = 0c } for every k ∈ N\{0}.
We next define the following sequence of random variables for all i ≥ 1:
Li , min{k ≥ Ti−1 + 1 : Bk occurs}
Ti , 1 + max{k ≥ Li : ∃j ∈ [k + 1], Yk,j is connected to YLi ,0 by an open path}

where we set T0 = 0. Note that when Ti−1 = ∞, we let Li = ∞ almost surely. Furthermore when
Ti−1 < ∞, Li < ∞ almost surely as infinitely many of the Bk ’s occur almost surely. We also note that
when Li < ∞, the set {k ≥ Li : ∃j ∈ [k + 1], Yk,j is connected to YLi ,0 by an open path} is non-empty
since YLi ,0 is always connected to itself, and Ti − Li − 1 denotes the length of the longest open path
connected to YLi ,0 (which could be infinity). Lastly, when Li = ∞, we let Ti = ∞ almost surely.
Let Fk for k ∈ N be the σ -algebra generated by the random variables (Y0 , . . . , Yk ) and all the BSCs
above level k (where we include all events determining whether these BSCs are copies, and all events
determining the independent bits they produce). Then, {Fk : k ∈ N} is a filtration. It is straightforward
to verify that Li and Ti are stopping times with respect to {Fk : k ∈ N} for all i ≥ 1. We can show
this inductively. T0 = 0 is trivially a stopping time, and if Ti−1 is a stopping time, then Li is clearly a
stopping time. So, it suffices to prove that Ti is a stopping time given Li is a stopping time. For any
25

finite m, {Ti = m} is the event that Li ≤ m − 1 and the length of the longest open path connected
to YLi ,0 is m − 1 − Li . This event is contained in Fm because Li ≤ m − 1 can be determined from
Fm−1 ⊆ Fm (since Li is a stopping time), and the length of the longest path can be determined from
Fm (rather than Fm−1 ). Hence, Ti is indeed a stopping time when Li is a stopping time.
Now observe that:
∞
X
P(∃k ≥ 2, Tk = ∞|T1 = m)P(T1 = m)
P(∃k ≥ 1, Tk = ∞) = P(T1 = ∞) +
= P(T1 = ∞) +

m=2
∞
X

P(∃k ≥ 1, Tk + m = ∞)P(T1 = m)

m=2

= P(T1 = ∞) + (1 − P(T1 = ∞))P(∃k ≥ 1, Tk = ∞) .

Here, P(∃k ≥ 1, Tk + m = ∞) = P(∃k ≥ 2, Tk = ∞|T1 = m) holds because the random variables
{(Li , Ti ) : i ≥ 2} given T1 = m have the same distribution as {(Li−1 + m, Ti−1 + m) : i ≥ 2}; in
particular, Li given T1 = m corresponds to Li−1 + m, and Ti given T1 = m corresponds to Ti−1 + m.
Moreover, the conditioning on {T1 = m} can be removed because the event {T1 = m} is in Fm since
T1 is a stopping time, and {T1 = m} is therefore independent of the events determining when BSCs
below level m are open, as well as the events Bk for k > m. Rearranging the previous equation, we get:
P(∃k ≥ 1, Tk = ∞)P(T1 = ∞) = P(T1 = ∞) .
Since P(T1 = ∞) = P(Ω∞ ) > 0 by part 1 of the phase transition in oriented bond percolation, we have:
P(∃k ≥ 1, Tk = ∞) = 1 .

(71)

right
Let Ωleft
, be the event that there exists an infinite open path connected to Yk,0 ,
k , respectively Ωk
respectively Yk,k , for k ∈ N. If {∃k ≥ 1, Tk = ∞} occurs, we can choose the smallest m such that
Tm = ∞, and for this m, there is an infinite open path connected to YLm ,0 = 0c (where YLm ,0 = 0c
because BLm occurs). Hence, using (71), we have:


left
P ∃k ≥ N, {Yk,0 = 0c } ∩ Ωk
= 1.

Likewise, we can also prove that:


P ∃k ≥ N, {Yk,k = 0c } ∩ Ωright
=1
k
which implies that:


right
P ∃k ≥ N, ∃m ∈ N, {Yk,0 = Ym,m = 0c } ∩ Ωleft
= 1.
k ∩ Ωm

(72)

right
To finish the proof, consider k, m ∈ N such that Yk,0 = Ym,m = 0c , and Ωleft
both happen.
k and Ωm
left
Let Rn = sup{j ∈ [n+1] : there is an open path from Yk,0 to Yn,j } be the rightmost node at level n >
k that is connected to Yk,0 by an open path, and Lright
= inf{j ∈ [n+1] : there is an open path from Ym,m
n
to Yn,j } be the leftmost node at level n > m that is connected to Ym,m by an open path. Using (70), we
know that:

Rnleft
Rnleft
1 + α(1 − δ)
Lright
Lright
−m
1 − α(1 − δ)
n
n
= lim
=
and lim
= lim
=
.
n→∞ n
n→∞ n − k
n→∞
n→∞
2
n
n−m
2
This implies that:
Rleft − Lright
n
lim n
= α(1 − δ) > 0
n→∞
n
lim

26

which means that for some sufficiently large level n, the rightmost open path from Yk,0 meets the leftmost
open path from Ym,m . By construction, all nodes in these two paths are equal to 0c . Furthermore, since
these two paths meet, we see from (68) and (69) (which show that AND gates and BSCs output 0c ’s or
1c ’s when the inputs are 0c ’s or 1c ’s) that every node at level n must be equal to 0c or 1c . Hence, there
exists a level n with no 1u ’s, i.e. the event A occurs. Therefore, we get P(A) = 1 using (72).
Combining the two cases completes the proof as P(A) = 1 for any δ ∈ 0, 12 .

We remark that this proof can be perceived as using the technique presented in [LPW09, Theorem 5.2].
Indeed, let T , inf{k ∈ N : Xk+ = Xk− } be a stopping time with respect to {Yk : k ∈ N} denoting the
first time that the marginal Markov chains {Xk+ : k ∈ N} and {Xk− : k ∈ N} meet. (Note that {T = ∞}
corresponds to the event that these chains never meet.) Since the events {Xk+ = Xk− } for k ∈ N form
a non-decreasing sequence of sets, {T > k} = {Xk+ 6= Xk− }. We can use this relation to obtain the
following bound on the TV distance between PX+k and PX−k :

PX+k − PX−k TV ≤ P Xk+ 6= Xk− = P(T > k) = 1 − P(T ≤ k)
(73)
where letting k → ∞ and using the continuity of P produces:
lim

k→∞

PX+k − PX−k

TV

≤ 1 − P(∃k ∈ N, T ≤ k) = 1 − P(T < ∞) .

(74)

These bounds correspond to the ones shown in [LPW09, Theorem 5.2]. Since the event A = {∃k ∈
N, T ≤ k} = {T < ∞}, our proof that A happens almost surely also demonstrates that the two marginal
Markov chains meet after a finite amount of time almost surely.
V. A NALYSIS OF D ETERMINISTIC XOR 2D G RID
In this section, we will prove Theorem 4. We let F2 = {0, 1} denote the Galois field of order 2 (i.e.
integers with addition and multiplication modulo 2), Fn2 with n ≥ 2 denote the vector space over F2 of
column vectors with n entries from F2 , and Fm×n
with m, n ≥ 2 denote the space of m × n matrices
2
with entries in F2 . (All matrix and vector operations will be performed modulo 2.) Now fix some matrix
H ∈ Fm×n
that has the following block structure:
2


1 B1
H=
(75)
0 B2
where 0 = [0 · · · 0]T ∈ Fm−1
is the zero vector (whose dimension will be understood from context in
2
1×(n−1)
(m−1)×(n−1)
the sequel), B1 ∈ F2
, and B2 ∈ F2
. Consider the following two problems:
n
1) Coding Problem: Let C , {x ∈ F2 : Hx = 0} be the linear code defined by the parity check
matrix H . Let X = [X1 X2T ]T with X1 ∈ F2 and X2 ∈ F2n−1 be a codeword drawn uniformly
T T
from C . Assume that there
 exists a codeword x = [1 x2 ] ∈ C (i.e. B1 x2 = 1 and B2 x2 = 0).
1
Then, X1 is a Bernoulli 2 random variable. We observe the codeword X through an additive noise
model and see Y1 ∈ F2 and Y2 ∈ F2n−1 :



 

Y1
Z1
X1 + Z1
=X+
=
(76)
Y2
Z2
X2 + Z2

where Z1 ∈ F2 is a Bernoulli 21 random variable, Z2 ∈ Fn−1
is a vector of i.i.d. Bernoulli(δ)
2
random variables that are independent of Z1 , and both Z1 , Z2 are independent of X . Our problem
is to decode X1 with minimum probability of error
 after observing Y1 , Y2 .
2) Inference Problem: Let X 0 ∈ F2 be a Bernoulli 21 random variable, and Z ∈ F2n−1 be a vector of
i.i.d. Bernoulli(δ) random variables that are independent of X 0 . Suppose we see the observations
S10 ∈ F2 and S20 ∈ Fm−1
through the model:
2
 0 
 0   0

S1
X
X + B1 Z
=H
=
.
(77)
S20
Z
B2 Z
27

Our problem is to decode X 0 with minimum probability of error after observing S10 , S20 .
The inference problem corresponds to our setting of reconstruction in the XOR 2D grid (as we will soon
see). The next lemma illustrates that this inference problem is “equivalent” to the aforementioned coding
problem (which admits simpler analysis).
Lemma 1 (Equivalence of Problems). The minimum probabilities of error of the coding problem in (76)
and the inference problem in (77) are equal. Moreover, if we couple the random variables in the two
problems so that X1 = X 0 and Z2 = Z almost surely (i.e. these variables are shared by the problems),
X2 is generated from a conditional distribution PX2 |X1 so that X is uniform on C , and Z1 is generated
independently, then we get S10 = B1 Y2 and S20 = B2 Y2 almost surely.
Proof. We first show that the minimum probabilities of error for the two problems are equal. The inference
problem has the following likelihoods for every s01 ∈ F2 and every s02 ∈ Fm−1
:
2
X


0
0
0
0
PS10 ,S20 |X 0 s1 , s2 0 =
PZ (z)1 B1 z = s1 , B2 z = s2
z∈Fn−1
2

X


PZ (z)1 B1 z = s01 + 1, B2 z = s02
PS10 ,S20 |X 0 s01 , s02 1 =
z∈Fn−1
2

and its prior is X 0 ∼ Bernoulli 2 . On the other hand, the coding problem has the following likelihoods
for every y1 ∈ F2 and every y2 ∈ Fn−1
:
2
1 X
PY2 |X2 (y2 |x2 )PX2 |X1 (x2 |0)
PY1 ,Y2 |X1 (y1 , y2 |0) = PY1 |X1 (y1 |0)PY2 |X1 (y2 |0) =
2
n−1

1

x2 ∈ F 2

1
=
2
=
PY1 ,Y2 |X1 (y1 , y2 |1) =

X

PZ2 (y2 − x2 )1{B1 x2 = 0, B2 x2 = 0}

x2 ∈Fn−1
2

1
|C|
1
|C|

X

2
|C|

PZ2 (z2 )1{B1 z2 = B1 y2 , B2 z2 = B2 y2 }

z2 ∈Fn−1
2

X

PZ2 (z2 )1{B1 z2 = B1 y2 + 1, B2 z2 = B2 y2 }

z2 ∈Fn−1
2


and its prior is X1 ∼ Bernoulli 21 . For the coding problem, define S1 , B1 Y2 and S2 , B2 Y2 . Due to
the Fisher-Neyman factorization theorem [Kee10, Theorem 3.6], the form of the likelihoods demonstrates
that (S1 , S2 ) is a sufficient statistic of (Y1 , Y2 ) for performing inference about X1 .
Continuing in the context of the coding problem, define the set C 0 = {x ∈ Fn−1
: B1 x = 0, B2 x = 0}
2
(which is also a linear code), and for any fixed s1 ∈ F2 and s2 ∈ Fm−1
,
define
the
set
S(s1 , s2 ) = {y1 ∈
2
n−1
F2 , y2 ∈ Fn−1
:
B
y
=
s
,
B
y
=
s
}
.
If
there
exists
y
∈
F
such
that
B
y
=
s
1 2
1
2 2
2
2
1 2
1 and B2 y2 = s2 ,
2
2
0
0
then S(s1 , s2 ) = {y1 ∈ F2 , y2 = y2 + y : y ∈ C }, which means that |S(s1 , s2 )| = 2|C 0 | = |C| (where
the final equality holds because each vector in C 0 corresponds to a codeword in C whose first letter is 0,
and we have assumed that there are an equal number of codewords with first letter 1). Hence, for every
s1 ∈ F2 and every s2 ∈ Fm−1
, the likelihood of (S1 , S2 ) given X1 = 0 is:
2
X
PS1 ,S2 |X1 (s1 , s2 |0) =
PY1 ,Y2 |X1 (y1 , y2 |0)1{B1 y2 = s1 , B2 y2 = s2 }
y1 ∈F2 ,y2 ∈Fn−1
2

|S(s1 , s2 )| X
PZ2 (z2 )1{B1 z2 = s1 , B2 z2 = s2 }
|C|
n−1
z2 ∈F2
X
=
PZ2 (z2 )1{B1 z2 = s1 , B2 z2 = s2 } .
=

z2 ∈Fn−1
2

28

Likewise, for every s1 ∈ F2 and every s2 ∈ Fm−1
, the likelihood of (S1 , S2 ) given X1 = 1 is:
2
X
PZ2 (z2 )1{B1 z2 = s1 + 1, B2 z2 = s2 } .
PS1 ,S2 |X1 (s1 , s2 |1) =
z2 ∈Fn−1
2

These likelihoods are exactly the same as the likelihoods for the inference problem we computed earlier.
So, the sufficient statistic (S1 , S2 ) in the coding problem is equivalent to the observation (S10 , S20 ) in
the inference problem in the sense that they are defined by the same probability model. As a result, the
minimum probabilities of error in these formulations must be equal.
We now assume that the random variables in the two problems are coupled as in the lemma statement.
To prove that S10 = S1 and S20 = S2 almost surely, observe that:
  0 


 
 
 

S1
X1
X1 + B1 Z2
B1 X2 + B1 Z2
B 1 Y2
S1
=
=H
=
=
=
Z2
S20
B2 Z2
B2 X2 + B2 Z2
B 2 Y2
S2
where the second equality uses (76), the third equality holds because B1 X2 = X1 and B2 X2 = 0 since
X is a codeword, and the last equality uses (77) and the fact that X1 = X 0 and Z2 = Z almost surely.
This completes the proof. (We note that this proof illustrates that (S10 , S20 ) in the inference problem is
actually a sufficient statistic for the coding problem under the coupling in the lemma statement.)

Recall that we are given a deterministic 2D grid where all Boolean processing functions with two
inputs are the XOR rule, and all Boolean processing functions with one input are the identity rule, i.e.
f1 (x1 , x2 ) = x1 ⊕ x2 and f2 (x) = x. We next prove Theorem 4 using Lemma 1.
Proof of Theorem 4. We first prove that the problem of decoding the root bit in the XOR 2D grid is
captured by the inference problem defined in (77). Let Ek denote the set of all directed edges in the 2D
grid above level k ∈ N. Furthermore, let us associate each edge e ∈ Ek with an independent Bernoulli(δ)
random variable Ze ∈ F2 . Since a BSC(δ) can be modeled as addition of an independent Bernoulli(δ) bit
(in F2 ), the random variables {Ze : e ∈ Ek } define the BSCs of the 2D grid up to level k . Furthermore,
each node at level k ≥ 1 of the XOR 2D grid is simply a sum (in F2 ) of its parent nodes and the random
variables on the edges between it and its parents. This provides a recursive formula for each node in
terms of its parent nodes that can be unwound so that each node can be represented in terms of the root
bit and all edge random variables:
 

X
k
bkj,e Ze
(78)
∀k ≥ 1, ∀j ∈ {0, . . . , k}, Xk,j =
(mod 2) X0,0 +
j
e∈Ek

where the coefficient of X0,0 can be computed by realizing that the coefficients of the nodes in the “grid
above Xk,j ” (with Xk,j as the root) are defined by the recursion of Pascal’s triangle, and bkj,e ∈ F2 are some
fixed coefficients. We do not require detailed knowledge of the values of {bkj,e : k ≥ 1, 0 ≤ j ≤ k, e ∈ Ek }
(but they can also be evaluated if desired via straightforward counting). In the remainder of this proof,
we will fix k to be a power of 2: k = 2m for m ∈ N\{0}. Then, we have:
   m 
k
2
1 , j = 0, k
≡
≡
(mod 2)
0 , j = 1, . . . , k − 1
j
j

29


since by Lucas’ theorem (see [Fin47]), the parity of kj is 0 if and only if at least one of the digits of
j in base 2 is strictly greater than the corresponding digit of k in base 2, and the base 2 representation
of k = 2m is 10 · · · 0 (with m 0’s). So, for each k , we can write (78) in the form:

 

1 — bk0,e — 
Xk,0

 Xk,1   0 — bk1,e —  X0,0

 


  ..
 | 
..
..

(79)
=




.
.
.

Z

 

e
k
 Xk,k−1   0 — bk−1,e — 
|
Xk,k
1 — bkk,e —
{z
}
|
, Hk
(k+1)×(|E |+1)

k
where Hk ∈ F2
is a binary matrix whose rows are indexed by the nodes at level k and
columns are indexed by 1 (first index) followed by the edges in Ek . The rows of Hk are made up of the
coefficients in (78), and the vector on the right hand side of (79) has first element X0,0 followed by the
random variables {Ze : e ∈ Ek } (indexed consistently with Hk ). Our problem is to decode X0,0 from
the observations (Xk,0 , . . . , Xk,k ) with minimum probability of error. Note that we can replace the last
row of Hk by the sum of the first and last rows of Hk (a row operation) to get Hk0 , and correspondingly
replace Xk,k by Xk,0 + Xk,k in (79) to get the equivalent formulation (which has the same minimum
probability of error for decoding X0,0 ):


Xk,0


X0,0


X
k,1


 | 


..

(80)

 = Hk0 
.
 Ze 




Xk,k−1
|
Xk,0 + Xk,k

where the equivalence follows from the fact that we only perform invertible operations. Since Hk0 is of
the form (75), the problem in (80) is exactly of the form of the inference problem in (77).
We next transform the XOR 2D grid problem in (79) into a coding problem. By Lemma 1, the inference
problem in (80) is equivalent to a coupled coding problem analogous to (76). In this coupled coding
problem, we generate a codeword Wk = [X0,0 — Wek — ]T uniformly from the linear code Ck defined by
the parity check matrix Hk0 , where the first element of the codeword is X0,0 and the remaining elements
are {Wek : e ∈ Ek }. We then observe Wk through the additive noise channel model:
 k 
Z0,0
 | 

Yk = Wk + 
(81)
 Ze 
|

k is an independent Bernoulli 1 random variable. Our
where {Ze : e ∈ Ek } are the BSC variables, and Z0,0
2
goal is to decode the first bit of the codeword, X0,0 , with minimum probability of error after observing
Yk . Since row operations do not change the nullspace of a matrix, we can equivalently think of Ck as
the linear code generated by the parity check matrix Hk . Moreover, without loss of generality, the ML
decoder for X0,0 based on Yk (which achieves the minimum probability of error) in the coding problem
makes an error if and only if the ML decision rule for X0,0 based on (Xk,0 , . . . , Xk,k ) in the inference
problem in (79) makes an error. This is because the coupling from Lemma 1 ensures that (Xk,0 , . . . , Xk,k )

30

is a sufficient statistic of Yk for X0,0 in the coding problem. Therefore, it suffices to study the probability
of error in ML decoding for the coding problem (81) due to Lemma 1.6
Recall that
 each BSC(δ) copies its input with probability 1 − 2δ and generates an independent
Bernoulli 21 bit with probability 2δ (as shown in the proof of Proposition 1 in Appendix A). Suppose
we know which BSCs among {Ze : e ∈ Ek } generate independent bits in (81). Then, we can perceive
each BSC in {Ze : e ∈ Ek } as an independent binary erasure channel (BEC) with erasure probability
2δ , denoted BEC(2δ), which erases its input if the corresponding BSC generates an independent bit, and
k corresponds to BEC(1) which always erases
copies its input otherwise. (Note that the BSC defined by Z0,0
its input.) We now consider observing the codeword Wk under this BEC model, where X0,0 is erased
almost surely, and the remaining bits of Wk are erased independently with probability 2δ . The minimum
probability of error in inferring X0,0 using an ML decoder for this BEC model lower bounds the minimum
probability of error in inferring X0,0 using an ML decoder under the BSC model. This is clear because
the BECs tell us which BSCs are generating independent bits, thereby providing additional information.
Moreover, the fact that a BEC(2δ) is “less noisy” than a BSC(δ) is well-known in information theory, cf.
[PW17b, Section 6, Equation (16)]. Now let Ik ⊆ Ek denote the set of indices where the corresponding
elements of Wk are not erased. It is a standard exercise to show that there exists a codeword w ∈ Ck
with first element w1 = 1 and wi = 0 for all i ∈ Ik if and only if the ML decoder (for the BEC model)
cannot recover X0,0 and has probability of error 21 ; see the discussion in [RU08, Section 3.2]. We next
find a codeword with these properties when two particular erasures occur.
Let e1 ∈ Ek and e2 ∈ Ek denote the edges (Xk−1,0 , Xk,0 ) and (Xk−1,k−1 , Xk,k ) in the 2D grid,
|E |+1
respectively. Consider the vector ω k ∈ F2 k
such that ω1k = 1 (first bit is 1), ωek1 = ωek2 = 1, and all
k
other elements are 0. Then, ω ∈ Ck because:




1 — bk0,e —
1 + bk0,e1 + bk0,e2

 bk1,e + bk1,e
 0 — bk1,e — 
2
1








.
.
.
..
..
Hk ω k =  ..
=0
 ωk = 




 0 — bkk−1,e — 
 bkk−1,e + bkk−1,e 
2
1
1 + bkk,e1 + bkk,e2
1 — bkk,e —
where we use the facts that bk0,e1 = 1, bk0,e2 = 0, bkk,e1 = 0, bkk,e2 = 1, and for any 0 < j < k , bkj,e1 = 0 and
bkj,e2 = 0 (and the value of bkj,ei for i = 0, 1 and j = 0, . . . , k is determined by checking the dependence
of node Xk,j on the variable Zei , which is straightforward because ei is an edge between the last two
layers at the side of the 2D grid). Since ω k has two 1’s at indices e1 and e2 (besides the first bit), if the
BECs corresponding to the indices e1 and e2 erase their inputs, the ML decoder (for the BEC model)
will fail to recover X0,0 with probability of error 21 .
Hence, we define Bk to be the event that the BECs corresponding to edges e1 and e2 at level k erase
their inputs (or equivalently, the BSCs at these edges generate independent bits), which has probability
P(Bk ) = (2δ)2 for every k . The events {Bk : k = 2m , m ∈ N\{0}} are mutually independent since
m
the BSCs are all independent. By
S the second Borel-Cantelli lemma, infinitely many of the B2 ’s occur
almost surely. So, letting An , nm=1 B2m for n ∈ N\{0}, the continuity of the underlying probability
6

We should remark that the equivalence between problems (80) and (81) requires the existence of a codeword of the form
|E |
[1 wT ]T , with w ∈ F2 k , in Ck (as mentioned earlier). This condition is always satisfied. Indeed, such a codeword does not
exist if and only if the first column of Hk0 (which is [1 0 · · · 0]T ) is not in the span of the remaining columns of Hk0 . So, if such
a codeword does not exist, we can decode X0,0 in the setting of (80) with zero probability of error because the observation
vector on the left hand side of (80) is in the span of the second to last columns of Hk0 if and only if X0,0 = 0. (It is worth
mentioning that in the coding problem in (81), if such a codeword does not exist, we can also decode the first codeword bit
with zero probability of error because all codewords must have the first bit equal to 0.) Since it is clear that we cannot decode
the root bit with zero probability of error in the XOR 2D grid, such a codeword always exists.

31

bk = X
b k (Xk,0 , . . . , Xk,k ) denote the ML decoder for X0,0
measure P yields limn→∞ P(An ) = 1. Let X
0,0
0,0
m
at level k = 2 under the original (BSC) model (79). From our discussion, we know that:
 m
 1
 m

2
2
b0,0
b0,0
∀m ∈ N\{0}, P X
6= X0,0 B2m = = P X
6= X0,0 Am
2
where the second equality holds because the probability of error for ML decoding is 12 at a given level
if the probability of error for ML decoding at the previous level is 12 . Finally, observe that:
 m

 m

 m

2
2
2
b0,0
b0,0
b0,0
lim P X
6= X0,0 = lim P X
6= X0,0 Am P(Am ) + P X
6= X0,0 Acm P(Acm )
m→∞
m→∞
 m

2
b0,0
= lim P X
6= X0,0 Am
m→∞

1
.
2
This completes the proof since the above condition is equivalent to (11).
=



A PPENDIX A
M ISCELLANEOUS P ROOFS
Proof of Corollary 1. This follows from applying the probabilistic method. Indeed, we know from
Theorem 1 that given δ < 16 , for the random DAG model with d = 3, Lm = ω(log(m)), and majority
processing functions, there exist  > 0 and K ∈ N such that:

 1
∀k ≥ K, P Ŝk 6= X0 ≤ − 2 .
2
Now define Pk (G) , P(hkML (Xk , G) 6= X0 |G) for k ∈ N as the conditional probability that the ML
decision rule based on the full k -layer state Xk makes an error given the random DAG G, and let Ek
for k ∈ N be the set of all DAGs G with d = 3 and Lm = ω(log(m)) such that Pk (G) ≤ 21 − . Observe
that for every k ≥ K :


h 
i
1
− 2 ≥ P Ŝk 6= X0 = E P Ŝk 6= X0 G
2
≥ E[Pk (G)]
= E[Pk (G)|G ∈ Ek ] P(G ∈ Ek ) + E[Pk (G)|G 6∈ Ek ] P(G 6∈ Ek )
≥ E[Pk (G)|G 6∈ Ek ] P(G 6∈ Ek )


1
≥
−  P(G 6∈ Ek )
2

where the first and third lines follow from the law of total expectation, the second line holds because
the ML decision rule minimizes the probability of error, the fourth line holds because the first term in
the previous line is non-negative, and the final line holds because G 6∈ Ek implies that Pk (G) > 12 − .
Then, we have for every k ≥ K :
2
P(G ∈ Ek ) ≥
> 0.
1 − 2
Since {Ek : k ∈ N} form a non-increasing sequence of sets (because Pk (G) is non-decreasing in k ), we
get via continuity:
!
\
2
P G∈
Ek = lim P(G ∈ Ek ) ≥
>0
k→∞
1 − 2
k∈N

which means that there exists a DAG G with d = 3 and Lm = ω(log(m)) such that Pk (G) ≤
all k ∈ N. This completes the proof.
32

1
2

−  for


Proof of Proposition 1. We first prove part 1, where we are given a fixed deterministic DAG G . Observe
that the BSC along each edge of this DAG produces its output bit by either copying its input bit exactly
with probability 1 − 2δ , or generating an independent Bernoulli 21 output bit with probability 2δ . This
is because the BSC transition matrix can be decomposed as:
"
#
"
#
"
#
1
1
1−δ
δ
1 0
= (1 − 2δ)
+ (2δ) 12 21 .
δ
1−δ
0 1
2
2
Now consider the events:
Ak , {all dLk edges from level k − 1 to level k generate independent output bits}

for k ∈ N\{0}, which have probabilities P(Ak ) = (2δ)dLk since the BSCs on the edges are independent.
These events are mutually independent (once again because the BSCs on the edges are independent).
Since the condition on Lk in the proposition statement is equivalent to:
∃K ∈ N, ∀k ≥ K, (2δ)dLk ≥

we must have:

∞
X

P(Ak ) ≥

k=1

∞
X

(2δ)dLk ≥

k=K

1
,
k

∞
X
1
= +∞ .
k

k=K

The second Borel-Cantelli
k : k ∈ N\{0}} occur
S∞ then tells us that infinitely many of the eventsS{A
T lemma
m
A
)
=
1
.
In
particular,
if
we
define
B
,
almost surely, i.e. P( ∞
m
k=1 Ak for m ∈ N\{0},
m=1 k=m k
then by continuity:
!
∞
[
(82)
lim P(Bm ) = P
Ak = 1 .
m→∞

k=1

Finally, observe that:
m
lim P(hm
ML (Xm , G) 6= X0 ) = lim P(hML (Xm , G) 6= X0 |Bm ) P(Bm )

m→∞

m→∞

c
c
+ P(hm
ML (Xm , G) 6= X0 |Bm ) P(Bm )

= lim P(hm
ML (Xm , G) 6= X0 |Bm )
m→∞

= lim P(hm
ML (Xm , G) 6= X0 |X0 = 0, Bm ) P(X0 = 0)
m→∞

+ P(hm
ML (Xm , G) 6= X0 |X0 = 1, Bm ) P(X0 = 1)
1
1
= lim P(hm
P(hm
ML (Xm , G) = 1|Bm ) +
ML (Xm , G) = 0|Bm )
m→∞ 2
2
1
(83)
=
2
Lm → {0, 1} denotes the ML decision rule at level m based on X , the second
where hm
m
ML (·, G) : {0, 1}
equality uses (82), the third equality uses the fact that X0 is independent of Bm , and the fourth equality
holds because Xm is conditionally independent of X0 given Bm . The condition in (83) is equivalent to
(11), which proves part 1.
To prove part 2, notice that part 1 yields:

lim

k→∞

PX+k |G − PX−k |G

TV

=0

which holds pointwise for every realization of the random DAG G. So, we can take expectations with
respect to G and apply the bounded convergence theorem to obtain part 2. This completes the proof. 
33

ACKNOWLEDGMENTS
A. Makur would like to thank Dheeraj Nagaraj and Ganesh Ajjanagadde for stimulating discussions.
R EFERENCES
[BRZ95]

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,” Journal of Statistical Physics, vol. 79, no. 1-2, pp. 473–482, April 1995.
[BVVW11] N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz, “Reconstruction for colorings on trees,” SIAM Journal on Discrete
Mathematics, vol. 25, no. 2, pp. 809–826, July 2011.
[Cir78]
B. S. Cirel’son, “Reliable storage of information in a system of unreliable components with local interactions,” in
Locally Interacting Systems and Their Application in Biology, ser. Lecture Notes in Mathematics, R. L. Dobrushin,
V. I. Kryukov, and A. L. Toom, Eds. Berlin, Heidelberg: Springer, 1978, vol. 653, pp. 15–30.
[DMR06]
C. Daskalakis, E. Mossel, and S. Roch, “Optimal phylogenetic reconstruction,” in Proceedings of the 38th Annual
ACM Symposium on Theory of Computing (STOC), Seattle, Washington, USA, May 21-23 2006, pp. 159–168.
[DO77]
R. L. Dobrushin and S. I. Ortyukov, “Lower bound for the redundancy of self-correcting arrangements of unreliable
functional elements,” Problemy Peredachi Informatsii, vol. 13, no. 1, pp. 82–89, 1977, in Russian.
[Dur84]
R. Durrett, “Oriented percolation in two dimensions,” The Annals of Probability, vol. 12, no. 4, pp. 999–1040,
November 1984.
[EKPS00]
W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman, “Broadcasting on trees and the Ising model,” The Annals of
Applied Probability, vol. 10, no. 2, pp. 410–433, May 2000.
[ES99]
W. S. Evans and L. J. Schulman, “Signal propagation and noisy circuits,” IEEE Transactions on Information
Theory, vol. 45, no. 7, pp. 2367–2373, November 1999.
[Fin47]
N. J. Fine, “Binomial coefficients modulo a prime,” The American Mathematical Monthly, vol. 54, no. 10, pp.
589–592, December 1947.
[Gác01]
P. Gács, “Reliable cellular automata with self-organization,” Journal of Statistical Physics, vol. 103, no. 1-2, pp.
45–267, April 2001.
[GM07]
A. Gershchenfeld and A. Montanari, “Reconstruction for models on random graphs,” in Proceedings of the 48th
Annual IEEE Symposium on Foundations of Computer Science (FOCS), Providence, Rhode Island, USA, October
20-23 2007, pp. 194–204.
[Gra82]
L. F. Gray, “The positive rates problem for attractive nearest neighbor spin systems on Z,” Zeitschrift für
Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 61, no. 3, pp. 389–404, September 1982.
[Gra87]
——, “The behavior of processes with statistical mechanical properties,” in Percolation Theory and Ergodic Theory
of Infinite Particle Systems, ser. The IMA Volumes in Mathematics and Its Applications, H. Kesten, Ed. New
York: Springer, 1987, vol. 8, pp. 131–167.
[Gra01]
——, “A reader’s guide to Gacs’s “positive rates” paper,” Journal of Statistical Physics, vol. 103, no. 1-2, pp.
1–44, April 2001.
[Hoe63]
W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical
Association, vol. 58, no. 301, pp. 13–30, March 1963.
[HRS10]
D. H. Huson, R. Rupp, and C. Scornavacca, Phylogenetic Networks: Concepts, Algorithms and Applications. New
York: Cambridge University Press, 2010.
[HW91]
B. Hajek and T. Weller, “On the maximum tolerable noise for reliable computation by formulas,” IEEE Transactions
on Infomation Theory, vol. 37, no. 2, pp. 388–391, March 1991.
[Iof96a]
D. Ioffe, “Extremality of the disordered state for the Ising model on general trees,” in Trees (Workshop in Versailles,
June 14-16 1995), ser. Progress in Probability, B. Chauvin, S. Cohen, and A. Rouault, Eds. Basel: Birkhäuser,
1996, vol. 40, pp. 3–14.
[Iof96b]
——, “On the extremality of the disordered state for the Ising model on the Bethe lattice,” Letters in Mathematical
Physics, vol. 37, no. 2, pp. 137–143, June 1996.
[JM04]
S. Janson and E. Mossel, “Robust reconstruction on trees is determined by the second eigenvalue,” The Annals of
Probability, vol. 32, no. 3B, pp. 2630–2649, July 2004.
[Kee10]
R. W. Keener, Theoretical Statistics: Topics for a Core Course, ser. Springer Texts in Statistics. New York:
Springer, 2010.
[KMRT+ 07] F. Krz̧akała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, “Gibbs states and the set of
solutions of random constraint satisfaction problems,” Proceedings of the National Academy of Sciences (PNAS),
vol. 104, no. 25, pp. 10 318–10 323, June 2007.
[Lig78]
T. M. Liggett, “Attractive nearest neighbor spin systems on the integers,” The Annals of Probability, vol. 6, no. 4,
pp. 629–636, August 1978.
[LPW09]
D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times, 1st ed. Providence, Rhode Island:
American Mathematical Society, 2009.
[MM06]
M. Mézard and A. Montanari, “Reconstruction on trees and spin glass transition,” Journal of Statistical Physics,
vol. 124, no. 6, pp. 1317–1350, September 2006.

34

[Mos98]
[Mos01]
[Mos03]
[Mos04]
[MRT11]
[PP10]
[PW16]
[PW17a]
[PW17b]

[Roc10]
[RU08]
[Rud76]
[SH06]
[Sly09]
[Sly11]
[Tho86]
[vN56]

E. Mossel, “Recursive reconstruction on periodic trees,” Random Structures and Algorithms, vol. 13, no. 1, pp.
81–97, August 1998.
——, “Reconstruction on trees: Beating the second eigenvalue,” The Annals of Applied Probability, vol. 11, no. 1,
pp. 285–300, February 2001.
——, “On the impossibility of reconstructing ancestral data and phylogenies,” Journal of Computational Biology,
vol. 10, no. 5, pp. 669–676, July 2003.
——, “Phase transitions in phylogeny,” Transactions of the American Mathematical Society, vol. 356, no. 6, pp.
2379–2404, June 2004.
A. Montanari, R. Restrepo, and P. Tetali, “Reconstruction and clustering in random constraint satisfaction
problems,” SIAM Journal on Discrete Mathematics, vol. 25, no. 2, pp. 771–808, July 2011.
R. Pemantle and Y. Peres, “The critical Ising model on trees, concave recursions and nonlinear capacity,” The
Annals of Probability, vol. 38, no. 1, pp. 184–206, January 2010.
Y. Polyanskiy and Y. Wu, “Dissipation of information in channels with input constraints,” IEEE Transactions on
Information Theory, vol. 62, no. 1, pp. 35–55, January 2016.
——, “Lecture notes on information theory,” August 2017, Lecture Notes 6.441, Department of Electrical
Engineering and Computer Science, MIT, Cambridge, Massachusetts, USA.
——, “Strong data-processing inequalities for channels and Bayesian networks,” in Convexity and Concentration,
ser. The IMA Volumes in Mathematics and its Applications, E. Carlen, M. Madiman, and E. M. Werner, Eds.
New York: Springer, 2017, vol. 161, pp. 211–249.
S. Roch, “Toward extracting all phylogenetic information from matrices of evolutionary distances,” Science, vol.
327, no. 5971, pp. 1376–1379, March 2010.
T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge: Cambridge University Press, 2008.
W. Rudin, Principles of Mathematical Analysis, 3rd ed., ser. International Series in Pure and Applied Mathematics.
New York: McGraw-Hill, Inc., 1976.
M. Steel and J. Hein, “Reconstructing pedigrees: A combinatorial perspective,” Journal of Theoretical Biology,
vol. 240, no. 3, pp. 360–367, June 2006.
A. Sly, “Reconstruction of random colourings,” Communications in Mathematical Physics, vol. 288, no. 3, pp.
943–961, June 2009.
——, “Reconstruction for the Potts model,” The Annals of Probability, vol. 39, no. 4, pp. 1365–1406, July 2011.
E. A. Thompson, Pedigree Analysis in Human Genetics, ser. Johns Hopkins Series in Contemporary Medicine and
Public Health. Baltimore: Johns Hopkins University Press, 1986.
J. von Neumann, “Probabilistic logics and the synthesis of reliable organisms from unreliable components,” in
Automata Studies, ser. Annals of Mathematics Studies, C. E. Shannon and J. McCarthy, Eds. Princeton, New
Jersey: Princeton University Press, 1956, vol. 34, pp. 43–98.

35

