# An Upper Bound of the Information Flow
From Children to Parent Node on Trees

Cassius<EMAIL_ADDRESS>[ Center for Integrative
Bioinformatics Vienna, Max Perutz Labs (University of Vienna and Medical
University of Vienna),

###### Abstract

We consider the transmission of a state from the root of a tree towards its
leaves, assuming that each transmission occurs through a noisy channel. The
states at the leaves are observed, while at deeper nodes we can compute the
likelihood of each state given the observation. In this sense, information
flows from child nodes towards the parent node.

Here we find an upper bound of this children-to-parent information flow. To do
so, first we introduce a new measure of information, the memory vector, whose
norm quantifies whether all states have the same likelihood. Then we find
conditions such that the norm of the memory vector at the parent node can be
linearly bounded by the sum of norms at the child nodes.

We also describe the reconstruction problem of estimating the ancestral state
at the root given the observation at the leaves. We infer sufficient
conditions under which the original state at the root cannot be confidently
reconstructed using the observed leaves, assuming that the number of levels
from the root to the leaves is large.

60J10,

90B15,

Markov chain,

phylogenetic reconstruction,

mixing time,

information theory,

###### keywords:

[class=MSC]

###### keywords:

##  1 Introduction

Consider the following broadcasting process. At the root $R$ of a tree, sample
a state of alphabet ${\mathbb{A}=\\{0,1,\cdots,K\\}}$ following distribution
$\bm{\mu}>0$. The tree is $d$-ary (every node has at most $d$ children) and
has $g$ levels (the unique path from the root $R$ to each of the leaves has
$g$ edges). The sampled state at $R$ is then transmitted independently to each
child node of $R$ through a noisy channel, described by an aperiodic,
irreducible Markov matrix $P$. Thus in channel $P=(p_{ij})$, where
$i,j\in\mathbb{A}$, entry $p_{ij}$ is the probability of state $i$ mutating to
state $j$ during transmission.

The transmission of states to the next level continues analogously until a
state is transmitted to every leaf of the tree. The ordered set of states at
the leaves is called a pattern, represented by symbol $\partial$. See Figure 1
for an example of this process with $\mathbb{A}=\\{0,1,2,3\\}$.

Figure 1: Example of broadcasting process on a $2$-level, incomplete $4$-ary
tree. The ancestral state $i\in\mathbb{A}$ at the root $R$ is sent
independently to each node $A_{1},\cdots,A_{4}$. The probability of $i$
mutating to $k$ during this transmission is $p_{ik}$. Then, the state $i_{c}$
at each node $A_{c}$ is sent independently to each of its child leaves, with a
probability $p_{i_{c}k}$ of mutating to $k$ during transmission. The observed
pattern is $\partial=01302002$, while the four subpatterns determined by
clades $A_{1},\cdots,A_{4}$ are $\partial_{1}=01$, $\partial_{2}=30$,
$\partial_{3}=200$ and $\partial_{4}=2$.

We address the following problem: Estimate the ancestral state at the root $R$
from the pattern $\partial$ assuming that $g$ is large, if the tree, the prior
$\bm{\mu}$ and channel $P$ are known. Notably, Maximum Likelihood (ML) has the
highest probability of a correct reconstruction among all reconstruction
methods (see Theorem 17.2, [3]). ML computes the posterior state distribution
$\bm{r_{\partial}}$ at the root given $\partial$. The ML estimate is the state
with the maximum posterior probability, also called the Maximum A Posteriori
(MAP) estimate.

Here we find sufficient conditions making the reconstruction problem
unsolvable, meaning that $\bm{r_{\partial}}=\bm{\mu}$ for all patterns
$\partial$ assuming that $g\to\infty$. More explicitly, in Theorem 8.1 we
consider a $d$-ary tree and the same channel $P$ for all transmissions, with
equilibrium frequency $\bm{\pi}$. We prove that, for some constant $C>0$
depending on channel $P$, if

$Cd<\min\Big{\\{}\frac{1}{3},\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\Big{\\}},$

then the reconstruction problem is unsolvable for every pattern $\partial$. As
an example, in Corollary 8.3 we show that $C=|\theta_{1}|$ when the channel
$P$ is reversible, where $\theta_{1}\in(-1,1)$ is the non-unitary absolutely
largest eigenvalue of channel $P$.

If the reconstruction problem is unsolvable, then the MAP estimate is
identical to the maximum a priori estimate, that is, the ML estimate using
only prior $\bm{\mu}$. Since ML has an optimal probability of a correct
reconstruction, we can say that, under these conditions, any pattern
$\partial$ is uninformative about the ancestral root state.

This paper is structured as follows. In Section 3, we describe the likelihood
computation on a tree, and then in Section 4 we introduce a new measure of the
information carried by a likelihood vector, namely the $L_{2}(\pi)$-norm of
the memory vector. We rewrite the likelihood vector using the memory vector in
Section 5, which is useful for the bounds of Section 6.

Our core result is Theorem 6.4, where we bound the memory-vector norm at a
parent node by the sum of memory-vector norms at the child nodes. This theorem
is very versatile, since it can be applied to any tree structure, even with a
different channel for every child node. The possible definitions of
unsolvability are explained in Section 7. Using the bound of Theorem 6.4, in
Section 8 we give sufficient conditions on matrix $P$ such that the
reconstruction problem is unsolvable. Unsolvability in expectation is studied
in Section 9.

##  2 Comparison with previous results

The solvability of the reconstruction problem has been studied repeatedly in
physics, statistic and phylogenetics (see [7]). Notably, focus has been placed
on solvability in expectation, meaning the following: If pattern $\partial$
has a probability $\Pr(\partial)$ of being observed, then characterize whether
$\mathbb{E}[\|\bm{r_{\partial}}-\bm{\mu}\|]\to 0$ as $g\to\infty$. See Section
7 regarding the possible definitions of unsolvability.

Assuming a binary symmetric channel (the so called Ising model), in [1] it was
proven that $d|\theta_{1}|^{2}<1$ implies that the reconstruction problem is
unsolvable in expectation, where $d$ is the $d$-arity of the tree and
$\theta_{1}\in(-1,1)$ is the non-unitary absolutely largest eigenvalue of
matrix $P$. Two generalizations of the Ising model were studied later, namely
the binary asymmetric channel and the symmetric $\mathbb{A}$-dimensional
channel (Potts model in physics [7]; Jukes-Cantor model in phylogenetics
[11]). In [8] and [9], it is stated that for those two kind of channels, the
reconstruction problem is unsolvable in expectation if ${d|\theta_{1}|<1}$.
Solvable examples in expectation when ${d|\theta_{1}|>1}$ are presented in
[8].

In contrast, our results apply to any noisy channel, as long as it is
irreducible and aperiodic, which are typical assumptions. Notably, we do not
rely on the entropy-based theory of communication described by [10], as [8]
and [9] do. Instead, in Subsection 4.3 we propose a new measure of the
information carried by a likelihood vector, namely the $L_{2}(\pi)$-norm of
the memory vector.

##  3 Likelihoods on a d-ary Tree

The Pruning algorithm to recursively compute the likelihood of the model
parameters given a pattern was introduced in [2]. In this section, we rephrase
the Pruning algorithm for a $d$-ary tree with a different channel for each
child node.

We want to compute the likelihood of each state at the root $R$ given pattern
$\partial$. To that end, we define the likelihood vector at the root as

$\bm{\rho_{\partial}}:=(\text{Pr}(\partial\;|\;R=0),\cdots,\text{Pr}(\partial\;|\;R=K)).$
(1)

Figure 2 shows the root $R$ and its $d$ outgoing channels $P_{1},\cdots,P_{d}$
with their respective child nodes $A_{1},\cdots,A_{d}$. Abusing of the
notation, we define clade $A_{c}$ as the subtree rooted at node $A_{c}$
containing all descendant nodes from $A_{c}$. The leaves of clade $A_{c}$
determine subpattern $\partial_{c}$. Considered independently, each clade
allows to compute a likelihood vector $\bm{\alpha_{c}}$ at the root $A_{c}$
given subpattern $\partial_{c}$. More explicitly, we define

$\aaa:=(\text{Pr}(\partial_{c}\;|\;A_{c}=0),\cdots,\text{Pr}(\partial_{c}\;|\;A_{c}=K)).$
(2)

Figure 2: The state at node $A_{c}$, for $c\in[d]$, was obtained by
transmitting the state at the root $R$ through a channel $P_{c}$. The
likelihood vector $\bm{\rho_{\partial}}$ at $R$ satisfies
$\bm{\rho_{\partial}}=\bigcomp_{c\in[d]}P_{c}\aaa$.

The Pruning algorithm consists in expressing $\bm{\rho_{\partial}}$ in terms
of the likelihood vectors $\bm{\alpha_{1}},\cdots,\bm{\alpha_{d}}$. Using the
law of total probability, the likelihood vector at the root $R$ considering
only clade $A_{c}$ is $P_{c}\aaa$. More explicitly,

$P_{c}\aaa=(\text{Pr}(\partial_{c}\;|\;R=0),\cdots,\text{Pr}(\partial_{c}\;|\;R=K)).$
(3)

Now we use the fact that the state at each node $A_{c}$ was obtained
independently from the state at $R$. This implies that $\rrr$ equals the
entrywise product of all likelihood vectors $P_{c}\aaa$. To visualize this
better, if we focus on state $R=0$, it holds that

$\text{Pr}(\partial\;|\;R=0)=\prod_{c\in[d]}\text{Pr}(\partial_{c}\;|\;R=0).$
(4)

We denote the entrywise product between two vectors $\bm{v}=(v_{i})$ and
$\bm{w}=(w_{i})$ as ${\bm{v}\circ\bm{w}:=(v_{i}w_{i})}$. Given vectors
$\bm{v_{1}},\cdots,\bm{v_{d}}$, their entrywise product is denoted as
${\bigcomp_{c\in[d]}\bm{v_{c}}:=\bm{v_{1}}\circ\cdots\circ\bm{v_{d}}.}$ With
this notation, we can write

$\rrr=\bigcomp_{c\in[d]}P_{c}\aaa.$ (5)

Now we just have to proceed analogously: Every vector $\aaa$ can be expressed
in terms of the child nodes of $A_{c}$, and so on, until we eventually arrive
to the likelihood vectors at the leaves. The likelihood vector at a leaf where
state $i$ was observed is the canonical vector $\bm{e_{i}}$, composed by $0$’s
except for a $1$ at coordinate $i$. Thus the Pruning algorithm is a recursion
based on Eq. 5 where the leaves have known likelihood vectors and the
computation proceeds towards the root of the tree.

Often one needs to compute $\text{Pr}(\partial)$, that is, the probability of
observing pattern $\partial$. This computation requires the assumption of some
prior state distribution $\bm{\mu}>0$ at node $R$. The law of total
probability implies that

$\text{Pr}(\partial)=\bm{\mu}\cdot\bm{\rho_{\partial}},$ (6)

where $"\cdot"$ denotes the Euclidean dot product.

##  4 The norm of the memory vector

###  4.1 The equilibrium frequency

The equilibrium frequency of the noisy channel plays a fundamental role in
this work. The necessary preliminaries about the equilibrium frequency can be
summarized as follows (see [6], Chapter $1$ and Section $12.1$).

######  Proposition 4.1.

For an irreducible and aperiodic Markov matrix $P$, the following holds:

  * a)

Matrix $P$ has a unique equilibrium distribution $\bm{\pi}>0$, defined by
equation ${\bm{\pi}^{T}P=\bm{\pi}^{T}}$.

  * b)

Matrix $P$ has eigenvalue $\theta_{0}=1$ with algebraic multiplicity $1$, and
the other eigenvalues $\\{\theta_{1},\cdots,\theta_{K}\\}\subset\mathbb{C}$
have a module smaller than $1$. We assume
${1>|\theta_{1}|\geq\cdots\geq|\theta_{K}|}.$

  * c)

If $P$ is reversible, all eigenvalues are real. Moreover, matrix $P$ has an
orthogonal basis of right eigenvectors $\bm{v_{k}}$ and left eigenvectors
$\bm{h_{k}}^{T}$ such that $\bm{h_{k}}=\bm{\pi}\circ\bm{v_{k}}$ for
$k\in[0,K]$, where $\bm{v_{0}}=\bm{1}$, $\bm{h_{0}}=\bm{\pi}$ and

$P=\bm{1}\bm{\pi}^{T}+\bm{v_{1}}\bm{h_{1}}^{T}\theta_{1}+\cdots+\bm{v_{K}}\bm{h_{K}}^{T}\theta_{K}.$

###  4.2 General properties of the norm

For some definitions of this subsection, we follow the notation of [6],
Section $12.5$. Given distribution $\bm{\pi}>0$, for any two vectors
$\bm{x}=(x_{i})$ and $\bm{y}=(y_{i})$ where $i\in\mathbb{A}$, we define the
$\pi$-inner product as

$\langle\bm{x},\bm{y}\rangle_{\pi}:=\bm{\pi}\cdot(\bm{x}\circ\bm{y})=\sum_{i}\pi_{i}x_{i}y_{i}.$
(7)

The $\pi$-inner product induces the $L_{2}(\pi)$-norm, defined as

$\|\bm{x}\|_{\pi}:=\sqrt{\langle\bm{x},\bm{x}\rangle_{\pi}}.$ (8)

As in every inner product space, the triangle inequality holds. Explicitly,

$\|\bm{x}+\bm{y}\|_{\pi}\leq\|\bm{x}\|_{\pi}+\|\bm{y}\|_{\pi}.$ (9)

Denote the Euclidean norm of $\bm{x}$ as
$\|\bm{x}\|:=\sqrt{\sum_{i}x^{2}_{i}}$, and the uniform norm as
${\|\bm{x}\|_{\infty}:=\max_{i}|x_{i}|}$. Since $|x_{i}|\leq\|\bm{x}\|$ for
all $i$ and $\sqrt{\min_{i}}\pi_{i}\|\bm{x}\|\leq\|\bm{x}\|_{\pi}$, it holds
that

$\|\bm{x}\|_{\infty}\leq\|\bm{x}\|\leq\frac{\|\bm{x}\|_{\pi}}{\sqrt{\min_{i}\pi_{i}}}.$
(10)

An important reason to use the $L_{2}(\pi)$-norm is that a vector cannot
increase its $L_{2}(\pi)$-norm when we centralize its entries with weights
$\bm{\pi}$, as described in the following proposition.

######  Proposition 4.2 (Centralizing inequality).

Given vector $\bm{x}$, the $L_{2}(\pi)$-norm satisfies

$\|\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi}\|^{2}_{\pi}=\|\bm{x}\|^{2}_{\pi}-\langle\bm{x},\bm{1}\rangle^{2}_{\pi}.$

In particular, it holds that

$\|\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi}\|_{\pi}\leq\|\bm{x}\|_{\pi}.$

###### Proof.

Developing the $\pi$-inner product, we obtain

$\displaystyle\Big{\langle}\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi},\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi}\Big{\rangle}_{\pi}=\langle\bm{x},\bm{x}\rangle_{\pi}-2\langle\bm{x},\bm{1}\rangle^{2}_{\pi}+\langle\bm{x},\bm{1}\rangle^{2}_{\pi}\langle\bm{1},\bm{1}\rangle_{\pi}.$
(11)

Since $\langle\bm{1},\bm{1}\rangle_{\pi}=1$, it follows that

$\|\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi}\|^{2}_{\pi}=\|\bm{x}\|^{2}_{\pi}-\langle\bm{x},\bm{1}\rangle^{2}_{\pi},$

as desired. To obtain the inequality, use the fact that
$\langle\bm{x},\bm{1}\rangle^{2}_{\pi}\geq 0$, giving

$\|\bm{x}-\bm{1}\langle\bm{x},\bm{1}\rangle_{\pi}\|^{2}_{\pi}\leq\|\bm{x}\|^{2}_{\pi}.$

∎

###  4.3 The memory vector

Consider the likelihood vector $\rrr$ at node $R$ determined by pattern
$\partial$. We define the normalized likelihood vector
$\rrt:=\rrr/(\rrr\cdot\bm{\pi})$ and the distribution
$\bm{r_{\pi}}:=\rrt\circ\bm{\pi}$. With analogous definitions, given the
likelihood vector $\bm{\alpha}$ at $A$ and pattern $\pred$,
$\bm{\tilde{\alpha}}:=\bm{\alpha}/(\bm{\alpha}\cdot\bm{\pi})$ and
$\bm{a_{\pi}}:=\bm{\tilde{\alpha}}\circ\bm{\pi}$. Note that, assuming prior
$\bm{\mu}=\bm{\pi}$ (so called stationarity), it holds that
$\text{Pr}(\partial)=\rrr\cdot\bm{\pi}$,
$\text{Pr}(\pred)=\bm{\alpha}\cdot\bm{\pi}$, and thus $\bm{r_{\pi}}$ and
$\bm{a_{\pi}}$ are the posteriors under this assumption.

The $\pi$-inner product of $\rrt$ and $\bm{\tilde{\alpha}}$ is

$\langle\rrt,\bm{\tilde{\alpha}}\rangle_{\pi}:=\bm{\pi}\cdot(\rrt\circ\bm{\tilde{\alpha}})=\bm{r_{\pi}}\cdot\bm{\tilde{\alpha}}=\bm{a_{\pi}}\cdot\rrt.$
(12)

Notably, we have $\langle\rrt,\bm{1}\rangle_{\pi}=\rrt\cdot\bm{\pi}=1$. Using
the Cauchy-Schwartz inequality, if we write
${\rrt=(\tilde{\rho}_{0},\cdots,\tilde{\rho}_{K})}$, we obtain the lower bound

$\|\rrt\|^{2}_{\pi}:=\langle\rrt,\rrt\rangle_{\pi}=\sum_{i}\pi_{i}\tilde{\rho}^{2}_{i}=(\sum_{i}\pi_{i})(\sum_{i}\pi_{i}\tilde{\rho}^{2}_{i})\geq\sum_{i}\sqrt{\pi_{i}}\sqrt{\pi_{i}}\tilde{\rho}_{i}=1.$
(13)

A useful upper bound when dealing with normalized likelihood vectors is

$\|\rrt\|^{2}_{\pi}=\bm{r_{\pi}}^{T}\rrt\leq\max_{k}\tilde{\rho}_{k}\leq\frac{1}{\min_{i}\pi_{i}},$
(14)

where we used the fact that $\rrt\cdot\bm{\pi}=1$, and therefore for all $k$,
$\tilde{\rho}_{k}\leq 1/\pi_{k}\leq 1/\min_{i}\pi_{i}$.

However, we are more interested in the distance from $\rrt$ to $\bm{1}$.
Intuitively, as $\rrt$ approaches $\bm{1}$, all ancestral states become
equally likely, that is, pattern $\partial$ becomes less informative. This
motivates the following definition.

######  Definition 4.3.

We say that vector $\rrt-\bm{1}$ is the memory vector at node $R$ given
$\partial$.

When needed, the memory vector will be denoted as $\bm{m}$, with adequate
indices depending on the context. The memory vector satisfies

$0\leq\|\rrt-\bm{1}\|^{2}_{\pi}=\langle\rrt-\bm{1},\rrt-\bm{1}\rangle_{\pi}=\|\rrt\|^{2}_{\pi}-1\leq\frac{1}{\min_{i}\pi_{i}}-1,$
(15)

that is, the $L_{2}(\pi)$-norm of any memory vector is upper bounded by
$\sqrt{1/\min_{i}\pi_{i}-1}$.

###  4.4 Endomorphism of memory vectors

Consider the process of transmission using channel $P$ with equilibrium
frequency $\bm{\pi}$. If node $A$ received its state from a node, say $PA$,
then given $\partial_{A}$, node $PA$ has likelihood vector $P\bm{\alpha}$.
Importantly, since
${\bm{\pi}^{T}P\bm{\alpha}=\bm{\pi}^{T}\bm{\alpha}=\bm{\pi}\cdot\bm{\alpha}}$,
it follows that the normalized likelihood vector at node $PA$ is
$P\bm{\tilde{\alpha}}$. Thus matrix $P$ is an endomorphism of normalized
likelihood vectors. Consequently, the memory vector at node $PA$ is
$P\bm{\tilde{\alpha}}-\bm{1}$. Moreover, since $P\bm{1}=\bm{1}$, it holds that

$P\bm{\tilde{\alpha}}-\bm{1}=P(\bm{\tilde{\alpha}}-\bm{1}),$

and thus matrix $P$ is also an endomorphism of memory vectors. In Section 8,
we will assume that $\bm{\pi}$ is the equilibrium frequency of all channels to
preserve this endomorphism.

###  4.5 The reversible case

If channel $P$ is reversible, then the eigendecomposition of Prop. 4.1.c
applies, yielding simple ways to describe the $L_{2}(\pi)$-norm and the action
of $P$. Indeed, using decomposition
$I=\bm{1}\bm{\pi}^{T}+\sum_{k\in[K]}\bm{v_{k}}\bm{h_{k}}^{T}$ where
$\bm{h_{k}}=\bm{\pi}\circ\bm{v_{k}}$, we can rewrite the $L_{2}(\pi)$-norm as

$\|\rrt\|^{2}_{\pi}=\bm{r_{\pi}}^{T}\rrt=\bm{r_{\pi}}^{T}I\rrt=1+\sum_{k\in[K]}(\rrt\cdot\bm{h_{k}})^{2}\geq
1.$ (16)

Regarding the action of a reversible Markov matrix $P$ on a normalized
likelihood vector $\bm{\tilde{\alpha}}$, it can be alternatively described as

$P\bm{\tilde{\alpha}}=\bm{1}+\sum_{k\in[K]}\theta_{k}(\bm{\tilde{\alpha}}\cdot\bm{h_{k}})\bm{v_{k}},$
(17)

where we used the eigendecomposition of Prop. 4.1.c,
$P=\bm{1}\bm{\pi}^{T}+\sum_{k\in[K]}\theta_{k}\bm{v_{k}}\bm{h_{k}}^{T}$.
Recall that the eigenvalues $\theta_{k}$ satisfy
$1>|\theta_{1}|\geq\cdots\geq|\theta_{K}|$. Using Equations 15 and 16 with
${\rrt=P\bm{\tilde{\alpha}}}$, the memory vector at node $PA$ satisfies

$\|P\bm{\tilde{\alpha}}-\bm{1}\|^{2}_{\pi}=\sum_{k\in[K]}\theta_{k}^{2}(\bm{\tilde{\alpha}}\cdot\bm{h_{k}})^{2}.$
(18)

Interestingly, this yields the bound

$\|P\bm{\tilde{\alpha}}-\bm{1}\|^{2}_{\pi}\leq\theta^{2}_{1}\sum_{k\in[K]}(\bm{\tilde{\alpha}}\cdot\bm{h_{k}})^{2}=\theta_{1}^{2}\;\|\bm{\tilde{\alpha}}-\bm{1}\|^{2}_{\pi},$
(19)

or taking the square root,

$\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq|\theta_{1}|\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}.$
(20)

Hence the $L_{2}(\pi)$-norm of the memory vector decreases at least by a
factor of $|\theta_{1}|$ under the action of the reversible matrix $P$.

###  4.6 A general bound of the norm growth

The bounds of norm growth as the one of Eq. 20 are useful for our proofs.
Without the assumption that matrix $P$ be reversible, a general bound similar
to Eq. 20 as

$\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq
C\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}$ (21)

for some constant $C>0$ is more difficult to obtain, since matrix $P$ may have
complex eigenvalues or not diagonalize. A weak bound using well known
properties of the singular value decomposition (explained in [4]) can be
obtained as follows.

Let us define $\Pi:=\bm{1}\bm{\pi}^{T}$ and
$\Psi:=\operatorname{diag}(\bm{\pi})$. Since
$P\bm{1}=\Pi\bm{1}=\Pi\bm{\tilde{\alpha}}=\bm{1}$ for any normalized
likelihood vector $\bm{\tilde{\alpha}}$, it holds that

$P\bm{\tilde{\alpha}}-\bm{1}=(P-\Pi)(\bm{\tilde{\alpha}}-\bm{1}).$ (22)

Notably, matrix $P-\Pi$ has eigenvalues $0,\theta_{1},\cdots,\theta_{K}$,
although we only need its singular values. Consider the largest singular value
$\sigma_{1}$ of $P-\Pi$, which satisfies $\sigma_{1}\geq|\theta_{1}|$ and thus
may be larger than $1$ (see [4]). Let $\|\cdot\|$ denote the matrix norm
induced by the Euclidean norm. It holds that

$\displaystyle\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}$
$\displaystyle=\|(P-\Pi)(\bm{\tilde{\alpha}}-\bm{1})\|_{\pi}=$
$\displaystyle=\|\sqrt{\Psi}(P-\Pi)(\bm{\tilde{\alpha}}-\bm{1})\|\leq\|\sqrt{\Psi}\|\;\|P-\Pi\|\;\|\bm{\tilde{\alpha}}-\bm{1}\|,$
(23)

where the inequality follows because induced norms are sub-multiplicative.
Since the Euclidean matrix norm coincides with the spectral norm,
${\|\sqrt{\Psi}\|=\max_{i}\sqrt{\pi_{i}}}$ and ${\|P-\Pi\|=\sigma_{1}}$. This
together with $\|\bm{x}\|\leq\|\bm{x}\|_{\pi}/\min_{i}\sqrt{\pi_{i}}$ gives

$\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq\frac{\max_{i}\sqrt{\pi_{i}}}{\min_{i}\sqrt{\pi_{i}}}\sigma_{1}\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi},$
(24)

and thus the bound of Eq. 21 holds for
$C=\sigma_{1}\max_{i}\sqrt{\pi_{i}}/\min_{i}\sqrt{\pi_{i}}$. This bound is
specially weak when $\min_{i}\sqrt{\pi_{i}}<<\max_{i}\sqrt{\pi_{i}}$.

##  5 Rewriting the likelihood vectors

In this section, we will rewrite the likelihood vectors $\rrr$ and $\aaa$
described in Section 3. We assume that all matrices $P_{c}$ have the same
equilibrium distribution $\bm{\pi}$. Recall that the normalized likelihood
vectors are defined as ${\rrt:=\rrr/(\rrr\cdot\bm{\pi})}$ and
${\aat:=\aaa/(\aaa\cdot\bm{\pi})}$. Assuming prior $\bm{\mu}=\bm{\pi}$, it
holds that ${\text{Pr}(\partial)=\rrr\cdot\bm{\pi}}$ and
${\text{Pr}(\partial_{c})=\aaa\cdot\bm{\pi}}$. Thus we define
${\text{Pr}_{\pi}(\partial)=\rrr\cdot\bm{\pi}}$ and
${\text{Pr}_{\pi}(\partial_{c})=\aaa\cdot\bm{\pi}}$

The normalized likelihood vectors are useful to identify the dependence
between the subpatterns $\partial_{1},\cdots,\partial_{d}$ composing pattern
$\partial$. Indeed, since $\bm{\rho_{\partial}}=\bigcomp_{c\in[d]}P_{c}\aat$
and ${\text{Pr}_{\pi}(\partial)=\rrr\cdot\bm{\pi}}$, it holds that

$\text{Pr}_{\pi}(\partial)=\text{Pr}_{\pi}(\partial_{1},\cdots,\partial_{d})=\Big{(}\prod_{c\in[d]}\text{Pr}_{\pi}(\partial_{c})\Big{)}\Big{(}\bm{\pi}\cdot\bigcomp_{c\in[d]}P_{c}\aat\Big{)},$
(25)

showing that the dependence factor between observations
$\partial_{1},\cdots,\partial_{d}$ is
$\bm{\pi}\cdot\bigcomp_{c\in[d]}P_{c}\aat$. We additionally define the
probability of observing $\partial$ assuming subpattern independence,

${\text{Pr}_{IND}(\partial):=\prod_{c\in[d]}\text{Pr}_{\pi}(\partial_{c})}$
(26)

and the dependence factor $D(\partial)$ of the subpatterns of $\partial$,

${D(\partial):=\bm{\pi}\cdot\bigcomp_{c\in[d]}P_{c}\aat},$ (27)

yielding the relationship

$\text{Pr}_{\pi}(\partial)=D(\partial)\text{Pr}_{IND}(\partial).$ (28)

By introducing $\aat:=\aaa/\text{Pr}_{\pi}(\partial_{c})$ and the memory
vectors $\bm{m_{c}}:=P_{c}\aat-\bm{1}$ in equation
$\bm{\rho_{\partial}}=\bigcomp_{c\in[d]}P_{c}\bm{\alpha^{c}_{\partial}}$, we
obtain

$\displaystyle\frac{\bm{\rho_{\partial}}}{\text{Pr}_{IND}(\partial)}$
$\displaystyle=\bigcomp_{c\in[d]}\;\Big{(}\bm{1}+\bm{m_{c}}\Big{)}=$
$\displaystyle=\bm{1}+\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}.$ (29)

This equation combined with the relationship
$\text{Pr}_{\pi}(\partial)=\bm{\rho_{\partial}}\cdot\bm{\pi}=D(\partial)\text{Pr}_{IND}(\partial)$
gives

$\displaystyle D(\partial)$
$\displaystyle=\frac{\text{Pr}_{\pi}(\partial)}{\text{Pr}_{IND}(\partial)}=\frac{\bm{\rho_{\partial}}}{\text{Pr}_{IND}(\partial)}\cdot\bm{\pi}=$
$\displaystyle=1+\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bm{\pi}\cdot\bigcomp_{c\in
C}\bm{m_{c}},$ (30)

where the terms where $p=1$ vanish, because
$\bm{\pi}^{T}(P_{c}\aat-\bm{1})=\bm{1}-\bm{1}=0$. The expanded products of
Equations 5 and 5 will be useful to bound information flow in Section 6.

##  6 Bounds of information flow

Along our proofs, we often need to bound the entrywise product by a sum of
vectors. To this end, we prove the following.

######  Lemma 6.1.

For any integer $d\geq 2$ and reals $S\in(0,2)$ and $\epsilon>0$, if $S\leq
4\epsilon/(1+2\epsilon)$, then

$(1+\frac{S}{d})^{d}<1+(1+\epsilon)S.$ (31)

###### Proof.

Expanding $(1+\frac{S}{d})^{d}$, Eq. 31 is equivalent to

$\sum_{c\in[2,d]}\binom{d}{c}\frac{S^{c}}{d^{c}}<\epsilon S.$ (32)

Since $0<S<2$, we have the bound

$\sum_{c\in[2,d]}\binom{d}{c}\frac{S^{c}}{d^{c}}<\sum_{c\in[2,d]}\frac{S^{c}}{c!}<\sum_{c\in[2,\infty]}\frac{S^{c}}{2^{c}}=\frac{S^{2}}{2(2-S)}.$
(33)

It is easy to see that, for $S\in(0,2)$, inequality

$\frac{S^{2}}{2(2-S)}\leq\epsilon S$ (34)

holds iff

$S\leq\frac{4\epsilon}{1+2\epsilon},$ (35)

and the result follows.

∎

In Section 5, we introduced the dependence factor $D(\partial)$, defined by
Eq. 28 as

$\text{Pr}_{\pi}(\partial)=\text{Pr}_{\pi}(\partial_{1},\cdots,\partial_{d})=D(\partial)\text{Pr}_{IND}(\partial).$

Intuitively, if memory vectors $\bm{m_{c}}$ of Eq. 5 approach $\bm{0}$, then
all patterns $\partial_{1},\cdots,\partial_{d}$ are uninformative, and
consequently they are also independent, that is, $D(\partial)\approx 1$. This
is the content of the following lemma. Notably, in the statement of Lemma 6.2,
normalized vectors $P_{c}\aat$ can be substituted by any normalized vectors
$\bbt$. We use vectors $P_{c}\aat$ just to make the connection to other
results of this work explicit.

######  Lemma 6.2 (Mixing of the dependence factor).

In the broadcasting process of Figure 2, assume that all matrices $P_{c}$ have
the same equilibrium frequency $\bm{\pi}$. Consider moreover the normalized
likelihood vector $\rrt$ at $R$ and the normalized likelihood vectors
${P_{c}\aat=\bm{1}+\bm{m_{c}}}$ at nodes $P_{c}A_{c}$. Then, under the
assumption that ${\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq
4\epsilon/(1+2\epsilon)}$, the dependence factor satisfies

$|D(\partial)-1|<\epsilon\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq\frac{4\epsilon^{2}}{1+2\epsilon}.$

###### Proof.

Let us bound the dependence factor $D(\partial)$ using the expansion of Eq. 5.
First, we denote by $|\bm{m_{c}}|$ the vector obtained by taking the absolute
value of each entry of $\bm{m_{c}}$, and thus write
$|\bm{m_{c}}|=(|m_{c}^{0}|,\cdots,|m_{c}^{K}|).$ Using the fact that a
weighted sum is smaller than its biggest term, plus the Arithmetic-Geometric
Mean inequality, we obtain

$\displaystyle|D(\partial)-1|$
$\displaystyle=|\bm{\pi}\cdot\sum_{p\in[2,d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}|$
$\displaystyle\leq\max_{i}\sum_{p\in[2,d]}\sum_{C\in\binom{[d]}{p}}\prod_{c\in
C}|m_{c}^{i}|=$
$\displaystyle=\max_{i}\prod_{i\in[c]}(1+|m_{c}^{i}|)-\sum_{c\in[d]}|m_{c}^{i}|-1\leq$
$\displaystyle\leq\max_{i}\;\;(1+\frac{\sum_{c\in[d]}|m_{c}^{i}|}{d})^{d}-\sum_{c\in[d]}|m_{c}^{i}|-1.$
(36)

Using Lemma 6.1, if $\sum_{c\in[d]}|m_{c}^{i}|<4\epsilon/(1+2\epsilon)$ for
all $i$, then the expression of Eq. 36 can be upperly, strictly bounded by
$\epsilon\max_{i}\sum_{c\in[d]}|m_{c}^{i}|.$ Moreover, it is clear that

$\sum_{c\in[d]}|m_{c}^{i}|\leq\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}.$

Therefore, assuming that the last sum is smaller than
$4\epsilon/(1+2\epsilon)$, the dependence factor $D(\partial)$ satisfies

$\displaystyle|D(\partial)-1|$
$\displaystyle<\epsilon\max_{i}\sum_{c\in[d]}|m_{c}^{i}|\leq$
$\displaystyle\leq\epsilon\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty},$ (37)

proving the first inequality of the statement. The second inequality follows
by reusing the assumption $\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq
4\epsilon/(1+2\epsilon)$.

∎

It is well known that, for $x\approx 0$, one can use the approximation
${(1+x)^{n}\approx 1+nx}$. In this sense, for numbers close to $1$,
multiplication can be approximated by addition. In a similar fashion, if
memory vectors $\bm{m_{c}}=P_{c}\aat-\bm{1}$ approach $\bm{0}$, then
$P_{c}\aat\approx\bm{1}$ and the entrywise product
$\bigcomp_{c\in[d]}P_{c}\aat$ can be approximated by
$\bm{1}+\sum_{c\in[d]}\bm{m_{c}}$. A more subtle argument yields a linear
bound of a memory vector given pattern $\partial$ using subpatterns
$\partial_{c}$, as explained in Theorem 6.3. As in Lemma 6.2, we use vectors
$P_{c}\aat$ just to make the connection to other results clear, and we could
write any normalized vectors $\bbt$ instead.

######  Theorem 6.3 (Hadamard-product upper bounds of the memory vector).

In the broadcasting process of Figure 2, assume that all matrices $P_{c}$ have
the same equilibrium frequency $\bm{\pi}$. Consider moreover the normalized
likelihood vector $\rrt$ at $R$ and the normalized likelihood vectors
$P_{c}\aat=\bm{1}+\bm{m_{c}}$ at nodes $P_{c}A_{c}$. Then, under the
assumption that, for some $\epsilon>0$,
${\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq 4\epsilon/(1+2\epsilon)}$, the
following holds:

  * a)

We have the bound

$D(\partial)\|\rrt-\bm{1}\|_{\pi}<(1+\epsilon)\sum_{c\in[d]}\|\bm{m_{c}}\|_{\pi}.$
(38)

  * b)

If moreover $\epsilon<(1+\sqrt{5})/4$, then

$\|\rrt-\bm{1}\|_{\pi}<\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}\sum_{c\in[d]}\|\bm{m_{c}}\|_{\pi}.$

###### Proof.

First of all, since in Eq. 28 we stated that
$\text{Pr}_{\pi}(\partial)=D(\partial)\text{Pr}_{IND}(\partial)$, it holds
that

$\displaystyle D(\partial)\|\rrt-\bm{1}\|_{\pi}$
$\displaystyle=\|\frac{\rrr}{\text{Pr}_{\pi}(\partial)}D(\partial)-\bm{1}D(\partial)\|_{\pi}=$
$\displaystyle=\|\frac{\rrr}{\text{Pr}_{IND}(\partial)}-\bm{1}D(\partial)\|_{\pi}$
(39)

Now we can use Equations 5 and 5, where we expanded
$\rrr/\text{Pr}_{IND}(\partial)$ and $D(\partial)$, giving

$\displaystyle D(\partial)\|\rrt-\bm{1}\|_{\pi}$
$\displaystyle=\|\bm{1}+\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}-\bm{1}\Big{(}1+\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bm{\pi}\cdot\bigcomp_{c\in
C}\bm{m_{c}}\Big{)}\|_{\pi}=$
$\displaystyle=\|\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}-\bm{1}\Big{(}\bm{\pi}\cdot\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}\Big{)}\|_{\pi}$
$\displaystyle=\|\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}-\bm{1}\langle\bm{1},\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}\rangle_{\pi}\|_{\pi}.$ (40)

Using the centralizing inequality of Prop. 4.2, we obtain

$\displaystyle D(\partial)\|\rrt-\bm{1}\|_{\pi}$
$\displaystyle\leq\|\sum_{p\in[d]}\sum_{C\in\binom{[d]}{p}}\bigcomp_{c\in
C}\bm{m_{c}}\|_{\pi}=$ (41)
$\displaystyle=\|\bigcomp_{c\in[d]}(\bm{1}+\bm{m_{c}})-\bm{1}\|_{\pi}=$ (42)
$\displaystyle=\|\;|\bigcomp_{c\in[d]}(\bm{1}+\bm{m_{c}})-\bm{1}|\;\|_{\pi},$
(43)

where $|\cdot|$ denotes the entrywise absolute value. We have the entrywise
inequality

$|\bigcomp_{c\in[d]}(\bm{1}+\bm{m_{c}})-\bm{1}|\leq\bigcomp_{c\in[d]}(\bm{1}+|\bm{m_{c}}|)-\bm{1},$
(44)

and the Arithmetic-Geometric Mean Inequality applied to
$\bigcomp_{c\in[d]}(\bm{1}+|\bm{m_{c}}|)$ implies that, in an entrywise
manner,

$0\leq\bigcomp_{c\in[d]}(\bm{1}+|\bm{m_{c}}|)-\bm{1}\leq\Big{(}\bm{1}+\frac{\sum_{c\in[d]}\bm{|m^{c}_{\partial}}|}{d}\Big{)}^{d}-\bm{1},$

where the exponentiation occurs entrywise. Consequently

$\displaystyle\|\bigcomp_{c\in[d]}(\bm{1}+\bm{m_{c}})-\bm{1}\|_{\pi}$
$\displaystyle\leq\|\Big{(}\bm{1}+\frac{\sum_{c\in[d]}\bm{|m^{c}_{\partial}}|}{d}\Big{)}^{d}-\bm{1}\|_{\pi}.$
(45)

We write $|\bm{m_{c}}|=(|m_{c}^{0}|,\cdots,|m_{c}^{K}|).$ Lemma 6.1 with
$S=\sum_{c\in[d]}|m_{c}^{i}|$ for $i\in\mathbb{A}$ further implies that, if we
have ${\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq 4\epsilon/(1+2\epsilon)}$,
then the following entrywise inequality holds

$\Big{(}\bm{1}+\frac{\sum_{c\in[d]}\bm{|m^{c}_{\partial}}|}{d}\Big{)}^{d}-\bm{1}<(1+\epsilon)\sum_{c\in[d]}\bm{|m^{c}_{\partial}}|.$
(46)

Therefore, assuming that $\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq
4\epsilon/(1+2\epsilon)$, and combining Equations 43, 45 and 46, it holds that

$\displaystyle D(\partial)\|\rrt-\bm{1}\|_{\pi}$
$\displaystyle<(1+\epsilon)\|\sum_{c\in[d]}\bm{|m^{c}_{\partial}}|\|_{\pi}\leq$
$\displaystyle\leq(1+\epsilon)\sum_{c\in[d]}\|\;|\bm{m_{c}}|\;\|_{\pi}=(1+\epsilon)\sum_{c\in[d]}\|\bm{m_{c}}\|_{\pi},$
(47)

where we applied the triangle inequality. This proves item $a)$.

To prove item $b)$, we use Prop. 6.2, concretely the fact that, if
${\sum_{c\in[d]}\|\bm{m_{c}}\|_{\infty}\leq 4\epsilon/(1+2\epsilon)}$ and
$1-\frac{4\epsilon^{2}}{1+2\epsilon}>0$, then

$D(\partial)>1-\frac{4\epsilon^{2}}{1+2\epsilon}>0.$ (48)

It is easy to see that $1-\frac{4\epsilon^{2}}{1+2\epsilon}>0$ holds when
$\epsilon>(1+\sqrt{5})/4$. The inequality of Eq. 48, applied to Eq. 38, yields
the result.

∎

Theorem 6.3 does not consider the child nodes $A_{c}$, but only the parent
nodes $P_{c}A_{c}$. Moreover, we did not mention how to make the memory
vectors at $P_{c}A_{c}$ small enough to satisfy the assumption of Theorem 6.3.
These particularities are considered in Theorem 6.4, which is our core result
bounding the information flow on trees from children to parent node.
Intuitively, one expects that information flows somehow decreasingly from the
leaves towards the root. Theorem 6.4 formalizes this intuition, sub-additively
bounding the memory-vector norm at the root $R$ by the sum of norms at its
child nodes $A_{c}$.

######  Theorem 6.4 (Root-Children upper bounds of the memory vector).

In the broadcasting process of Figure 2, assume that all matrices $P_{c}$ have
the same equilibrium frequency $\bm{\pi}$. Consider moreover the normalized
likelihood vector $\rrt$ at $R$ and the normalized likelihood vectors $\aat$
at child nodes $A_{c}$. Moreover assume that, for some constants $C_{c}>0$ and
for any normalized likelihood vector $\bm{\tilde{\alpha}}$, we have the bound

$\|P_{c}\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq
C_{c}\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}.$

In these conditions, if

$\sum_{c\in[d]}C_{c}\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon}$

for some $\epsilon>0$, then the following holds:

  * a)

We have the bound

$D(\partial)\|\rrt-\bm{1}\|_{\pi}<(1+\epsilon)\sum_{c\in[d]}C_{c}\|\aat-\bm{1}\|_{\pi}.$

  * b)

If moreover $\epsilon<(1+\sqrt{5})/4$, then

$\|\rrt-\bm{1}\|_{\pi}<\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}\sum_{c\in[d]}C_{c}\|\aat-\bm{1}\|_{\pi}.$

###### Proof.

To apply Theorem 6.3, we need the fulfillment of inequality

${\sum_{c\in[d]}\|P_{c}\aat-\bm{1}\|_{\infty}\leq 4\epsilon/(1+2\epsilon)}.$

Since $\|\bm{x}\|_{\infty}\leq\|\bm{x}\|_{\pi}/\min_{i}\sqrt{\pi_{i}}$ as
stated in Eq. 9, it holds that

$\sum_{c\in[d]}\|P_{c}\aat-\bm{1}\|_{\infty}\leq\frac{1}{\min_{i}\sqrt{\pi_{i}}}\sum_{c\in[d]}\|P_{c}\aat-\bm{1}\|_{\pi}.$

We bounded the $L_{2}(\pi)$-norm of any memory vector in Eq. 15, implying

$\displaystyle\sum_{c\in[d]}\|P_{c}\aat-\bm{1}\|_{\pi}$
$\displaystyle\leq\sum_{c\in[d]}C_{c}\|\aat-\bm{1}\|_{\pi}\leq$ (49)
$\displaystyle\leq\sqrt{\frac{1}{\min_{i}\pi_{i}}-1}\sum_{c\in[d]}C_{c}.$ (50)

Consequently, to apply Theorem 6.3 it is enough that

$\frac{1}{\min_{i}\sqrt{\pi_{i}}}\sqrt{\frac{1}{\min_{i}\pi_{i}}-1}\sum_{c\in[d]}C_{c}\leq\frac{4\epsilon}{1+2\epsilon},$

or equivalently

$\sum_{c\in[d]}C_{c}\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon}.$
(51)

Equations 49 and 51, combined with Theorem 6.3, yield the desired results.

∎

##  7 Definitions of unsolvability

###  7.1 Patternwise unsolvability

In a broadcasting process on a $d$-ary tree, we want to describe when the root
state cannot be confidently reconstructed using pattern $\partial$, assuming
that the tree has a large number of levels $g$. In general, the channels of
the broadcasting process can be different, although in Sections 8 and 9 we
focus on the case when all channels are equal to $P$.

If we assume a prior state distribution $\bm{\mu}=(\mu_{0},\cdots,\mu_{K})$
and the likelihood vector at the root $R$ is $\rrr$, then Bayes’ theorem
implies that the posterior state distribution is

$\bm{r_{\partial}}=\frac{\rrr\circ\bm{\mu}}{\text{Pr}(\partial)}=\frac{\rrr\circ\bm{\mu}}{\rrr\cdot\bm{\mu}}.$
(52)

If we write $\bm{r_{\partial}}=(r_{0},\cdots,r_{K})$, then the MAP estimate is
a state $i\in\mathbb{A}$ such that $r_{i}=\max_{i}r_{i}$, and the MAP
reconstruction probability is $\max_{i}r_{i}$.

######  Definition 7.1.

When $\bm{r_{\partial}}\neq\bm{\mu}$, we say that pattern $\partial$ is
informative, because the observation of $\partial$ influences the posterior.
In contrast, we say that pattern $\partial$ is uninformative when
$\bm{r_{\partial}}=\bm{\mu}$.

Since ${\bm{r_{\partial}}=\rrr\circ\bm{\mu}/(\rrr\cdot\bm{\mu}),}$ pattern
$\partial$ in uninformative iff $\rrr$ is uniform, which occurs iff
$\rrt=\bm{1}$. The next definition states the kind of unsolvability that we
will focus on.

######  Definition 7.2.

We say that the reconstruction problem is unsolvable if every pattern
$\partial$ is asymptotically uninformative as $g$ grows, that is, if

$\rrt\to\bm{1}\text{ as }g\to\infty.$

Since $\bm{\pi}>0$, unsolvability is equivalent to the condition that, for all
patterns $\partial$,

$\;\|\rrt-\bm{1}\|_{\pi}\to 0\text{ as }g\to\infty.$

More generally, since all finite-dimensional norms are equivalent (see [5]),
we can use any norm to measure $\rrt-\bm{1}$, although the $L_{2}(\pi)$-norm
is convenient for our proofs.

When the reconstruction problem is unsolvable, then, as $g\to\infty$, we have
${\bm{r_{\partial}}\to\bm{\mu}}$ and consequently
${\max_{i}r_{i}\to\max_{i}\mu_{i}}$, that is, the MAP reconstruction
probability is achieved by just considering the prior. In other words, the
observed pattern $\partial$ is uninformative about the ancestral root state of
the broadcasting process. This is why we use the term ”unsolvable”, in the
sense that we cannot estimate the ancestral root state better than the prior
can do.

###  7.2 Unsolvability in expectation

Notably, the set of all possible patterns $\Delta_{g}$ at the leaves of a
$g$-level tree grows with $g$. Consequently, the expected value

$\mathbb{E}_{\partial}[\;\|\rrt-\bm{1}\|_{\pi}]=\sum_{\partial\in\Delta_{g}}\Pr(\partial)\|\rrt-\bm{1}\|_{\pi}$
(53)

has a growing number of summands as $g\to\infty$. In any case, the equivalence
between finite-dimensional norms (see [5]) implies that all definitions using
norms are equivalent.

######  Definition 7.3.

We say that the reconstruction problem is unsolvable in expectation when, for
some norm $\|\cdot\|_{*}$,

$\mathbb{E}_{\partial}[\;\|\rrt-\bm{1}\|_{*}]\to 0\text{ as }g\to\infty.$

Unsolvability for $2$-dimensional or highly symmetric channels was studied in
[8] using the Total Variation (TV) distance.

######  Definition 7.4 (Unsolvability in [8]).

We say that the reconstruction problem is TV-unsolvable if the likelihood
vector ${\rrr=(\rho^{0}_{\partial},\cdots,\rho^{K}_{\partial})}$ satisfies,
for all ${i\neq j\in\mathbb{A}}$,

$\sum_{\partial\in\Delta_{g}}|\rho^{i}_{\partial}-\rho^{j}_{\partial}|\to
0\text{ as }g\to\infty.$

Now define $\mathbb{E}^{\pi}_{\partial}[\|\rrt-1\|_{*}]$ as the expected value
of $\|\rrt-1\|_{*}$ with prior $\bm{\mu}=\bm{\pi}$. Recall that $\bm{\mu}>0$
by definition and $\bm{\pi}>0$ due to Prop. 4.1.a. In Prop. 7.5, we prove that
Definitions 7.3 and 7.4 are equivalent.

######  Proposition 7.5.

The following statements are equivalent:

  * a)

The reconstruction problem is unsolvable in expectation.

  * b)

The reconstruction problem is unsolvable in expectation assuming prior
$\bm{\mu}=\bm{\pi}$.

  * c)

The reconstruction problem is TV-unsolvable.

###### Proof.

  * •

$a)\iff b)$: Since $\text{Pr}_{\pi}(\partial)=\bm{\pi}\cdot\rrt$ and
$\text{Pr}(\partial)=\bm{\mu}\cdot\rrt$, it holds that

$\text{Pr}(\partial)\min_{i}\pi_{i}\leq\text{Pr}_{\pi}(\partial)\leq\frac{\text{Pr}(\partial)}{\min_{i}\mu_{i}},$
(54)

and consequently

$\mathbb{E}_{\partial}[\|\rrt-1\|_{*}]\min_{i}\pi_{i}\leq\mathbb{E}^{\pi}_{\partial}[\|\rrt-1\|_{*}]\leq\frac{\mathbb{E}_{\partial}[\|\rrt-1\|_{*}]}{\min_{i}\mu_{i}}.$
(55)

These chain of inequalities implies that
$\mathbb{E}_{\partial}[\|\rrt-1\|_{*}]\to 0$ iff
$\mathbb{E}^{\pi}_{\partial}[\|\rrt-1\|_{*}]\to 0$, as desired. Note that we
can chose any prior as long as it has positive entries.

  * •

$b)\iff c)$: If we write
$\rrt=(\tilde{\rho}^{0}_{\partial},\cdots,\tilde{\rho}^{K}_{\partial})$, we
can do

$\displaystyle\sum_{\partial\in\Delta_{g}}|\rho^{i}_{\partial}-\rho^{j}_{\partial}|=\sum_{\partial\in\Delta_{g}}\text{Pr}_{\pi}(\partial)|\tilde{\rho}^{i}_{\partial}-\tilde{\rho}^{j}_{\partial}|=\mathbb{E}^{\pi}_{\partial}[|\tilde{\rho}^{i}_{\partial}-\tilde{\rho}^{j}_{\partial}|]$
(56)

We have the inequality

$|\tilde{\rho}^{i}_{\partial}-\tilde{\rho}^{j}_{\partial}|\leq|\tilde{\rho}^{i}_{\partial}-1|+|\tilde{\rho}^{j}_{\partial}-1|,$
(57)

and consequently unsolvability in expectation (using the $L_{1}$-norm) implies
TV-unsolvability. Conversely, since $\bm{\pi}$ is a distribution and
$\bm{\pi}\cdot\rrt=1,$ it holds that

$\displaystyle|\tilde{\rho}_{\partial}^{i}-1|$
$\displaystyle=|\sum_{j}\tilde{\rho}_{\partial}^{i}\pi_{j}-\sum_{j}\tilde{\rho}_{\partial}^{j}\pi_{j}|=$
$\displaystyle=|\sum_{j\neq
i}\pi_{j}(\tilde{\rho}_{\partial}^{i}-\tilde{\rho}_{\partial}^{j})|\leq\sum_{j\neq
i}\pi_{j}|(\tilde{\rho}_{\partial}^{i}-\tilde{\rho}_{\partial}^{j})|.$ (58)

Thus if
$\mathbb{E}^{\pi}_{\partial}[|\tilde{\rho}^{i}_{\partial}-\tilde{\rho}^{j}_{\partial}|]\to
0$ for all $i\neq j$ then $\mathbb{E}_{\partial}[\|\rrt-1\|_{1}]\to 0$, as
desired.

∎

##  8 Bounds to the unsolvability problem

Theorem 6.4 is very general, because the only tree structure required is a
parent node with $d$ children. By applying Theorem 6.4 recursively, for any
tree we can bound the memory vector at the root by the sum of the memory-
vector norms at the leaves. Applying this strategy, we can find sufficient
conditions for the unsolvability of the reconstruction problem.

######  Theorem 8.1.

Given any irreducible and aperiodic Markov matrix $P$, assume that, for some
$C>0$ and for any normalized likelihood vector $\bm{\tilde{\alpha}}$, we have
the bound

$\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq
C\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}.$

Then, on a $d$-ary tree, the reconstruction problem using channel $P$ is
unsolvable if

$Cd<\min\Big{\\{}\frac{1}{3},\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\Big{\\}}.$

###### Proof.

We want to apply Theorem 6.4 with all constants $C_{c}$ equal to $C$. First
note that, for any upper bound $U$, if the assumption $dC\leq U$ holds, then
also $kC\leq U$ holds for any number of children $k\leq d$. Therefore,
assuming $\epsilon<(1+\sqrt{5})/4$ and

$dC\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon}$
(59)

as required by Theorem 6.4.b, then for any node with $k\leq d$ children we can
apply the bound

$\|\rrt-1\|_{\pi}<\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}C\sum_{c\in[k]}\|\aat-\bm{1}\|_{\pi}.$
(60)

Consider the normalized likelihood vectors at the leaves, from now on $\llt$
where ${c\in\\{1,\cdots,N\\}}$ and $N\leq d^{g}$. The recursive application of
Eq. 60 yields that

$\displaystyle\|\rrt-1\|_{\pi}$
$\displaystyle<(\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}C)^{g}\sum_{c\in[N]}\|\llt-\bm{1}\|_{\pi},$
(61)

while the upper bound of the norm of any memory vector (Eq. 15) gives

$\displaystyle\|\rrt-1\|_{\pi}$
$\displaystyle<(\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}C)^{g}\sum_{c\in[N]}\sqrt{\frac{1}{\min_{i}\pi_{i}}-1}\leq$
$\displaystyle\leq(\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}C)^{g}d^{g}\sqrt{\frac{1}{\min_{i}\pi_{i}}-1}.$
(62)

Recall that the reconstruction problem is unsolvable iff $\|\rrt-1\|_{\pi}$
tends to $0$ as $g$ grows. Thus the reconstruction problem is unsolvable if
Eq. 59 holds and

$\frac{1+\epsilon}{1-\frac{4\epsilon^{2}}{1+2\epsilon}}Cd<1,$ (63)

as implied by the bound of Eq. 62. To make the following bounds hold
simultaneously,

$\displaystyle Cd$
$\displaystyle<\frac{1-\frac{4\epsilon^{2}}{1+2\epsilon}}{1+\epsilon}$
$\displaystyle Cd$
$\displaystyle\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon},$
(64)

the optimal $\epsilon<(1+\sqrt{5})/4$ is the one making the two bounds
coincide, although this intersection depends on $\min_{i}\pi_{i}$. For the
sake of clarity, set $\epsilon=1/2$, yielding the result.

∎

Theorem 8.1 assumes that any memory vector decreases at least by a factor of
$C$ under the action of $P$. We have inferred such bounds in Equations 20 and
24, giving the following corollaries.

######  Corollary 8.2.

Consider any irreducible and aperiodic Markov matrix $P$ with largest singular
value $\sigma_{1}$. Then, on a $d$-ary tree, the reconstruction problem using
channel $P$ is unsolvable if

$\sigma_{1}d<\frac{\min_{i}\sqrt{\pi_{i}}}{\max_{i}\sqrt{\pi_{i}}}\min\Big{\\{}\frac{1}{3},\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\Big{\\}}.$

######  Corollary 8.3.

Consider any irreducible, aperiodic and reversible Markov matrix $P$ with non-
unitary absolutely largest eigenvalue $\theta_{1}$. Then, on a $d$-ary tree,
the reconstruction problem using channel $P$ is unsolvable if

$|\theta_{1}|d<\min\Big{\\{}\frac{1}{3},\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\Big{\\}}.$

In this section we only assumed that the tree is $d$-ary, but Theorem 6.4 is
very general and can be applied in multiple scenarios. We can, for example,
allow a different channel for every child node as long as $\bm{\pi}$ is the
equilibrium distribution. To get a tighter bound, one can also apply Theorem
6.4 using the exact number of children at every node, and not an upper bound
$d$ as we did here.

##  9 A bound of unsolvability in expectation

Clearly, if the reconstruction problem is unsolvable, then it is unsolvable in
expectation. Moreover, there is room to slightly improve our bounds when
dealing with unsolvability in expectation. First we can state the analogous of
Theorem 6.4.

######  Proposition 9.1.

In the broadcasting process of Figure 2, , assume that all matrices $P_{c}$
have the same equilibrium frequency $\bm{\pi}$. We consider for each pattern
$\partial$ the normalized likelihood vector $\rrt$ at $R$ and the normalized
likelihood vectors ${\rm A\&A}$ at child nodes $A_{c}$. Moreover assume that,
for some constants $C_{c}>0$ and for any normalized likelihood vector
$\bm{\tilde{\alpha}}$, we have the bound

$\|P_{c}\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq
C_{c}\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}.$

In these conditions, if

$\sum_{c\in[d]}C_{c}\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon}$

for some $\epsilon>0$, then we have the bound

$\mathbb{E}^{\pi}_{\partial}[\|\rrt-1\|_{\pi}]<(1+\epsilon)\sum_{c\in[d]}C_{c}\mathbb{E}^{\pi}_{\partial_{c}}[\|{\rm
A\&A}-\bm{1}\|_{\pi}].$

###### Proof.

We can apply Theorem 6.4.a, because the assumptions are identical. Multiplying
both sides by $\text{Pr}_{IND}(\partial)$, we get

$\text{Pr}_{\pi}(\partial)\|\rrt-\bm{1}\|_{\pi}<(1+\epsilon)\sum_{c\in[d]}C_{c}\text{Pr}_{IND}(\partial)\|{\rm
A\&A}-\bm{1}\|_{\pi}$ (65)

Recall that pattern $\partial$ is composed by subpatterns
$\partial_{1},\cdots,\partial_{d}$, and thus indexation using $\partial$ is
equivalent to indexation using $\partial_{1},\cdots,\partial_{d}$. Moreover,
vector ${\rm A\&A}$ depends only on $\partial_{c}$, so we can write ${\rm
A\&A}=\aapp$. Summing over all $\partial$, it follows that

$\displaystyle\mathbb{E}^{\pi}_{\partial}[\|\rrt-\bm{1}\|_{\pi}$
$\displaystyle<(1+\epsilon)\sum_{c\in[d]}C_{c}\sum_{\partial_{1},\cdots,\partial_{d}}\text{Pr}_{IND}(\partial)\|\aapp-\bm{1}\|_{\pi}=$
$\displaystyle=(1+\epsilon)\sum_{c\in[d]}C_{c}\sum_{\partial_{c}}\text{Pr}_{\pi}(\partial_{c})\|\aapp-\bm{1}\|_{\pi}\prod_{f\in[d]-\\{c\\}}\sum_{\partial_{f}}\text{Pr}_{\pi}(\partial_{f}),$
(66)

where we substituted
$\text{Pr}_{IND}(\partial)=\prod_{f\in[d]}\text{Pr}_{\pi}(\partial_{f})$ and
rearranged the summands. Since
${\sum_{\partial_{f}}\text{Pr}_{\pi}(\partial_{f})=1}$ for all $f\in[d]$, we
get the desired inequality

$\displaystyle\mathbb{E}^{\pi}_{\partial}[\|\rrt-\bm{1}\|_{\pi}]$
$\displaystyle<(1+\epsilon)\sum_{c\in[d]}C_{c}\sum_{\partial_{c}}\text{Pr}_{\pi}(\partial_{c})\|\aapp-\bm{1}\|_{\pi}$
$\displaystyle=(1+\epsilon)\sum_{c\in[d]}C_{c}\mathbb{E}_{\partial_{c}}[\|\aapp-\bm{1}\|_{\pi}].$
(67)

∎

Using Proposition 9.1, we can improve the unsolvability bounds of Section 8.

######  Proposition 9.2.

Given any irreducible and aperiodic Markov matrix $P$, assume that, for some
$C>0$ and for any normalized likelihood vector $\bm{\tilde{\alpha}}$, we have
the bound

$\|P\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}\leq
C\;\|\bm{\tilde{\alpha}}-\bm{1}\|_{\pi}.$

Then, on a $d$-ary tree, the reconstruction problem using channel $P$ is
unsolvable in expectation if

$Cd<\min\Big{\\{}\frac{1}{3},\frac{8}{5}\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\Big{\\}}.$

###### Proof.

Applying Prop. 9.1, the proof is analogous to that of Theorem 8.1. Eventually
we need to make the following two bounds hold simultaneously,

$\displaystyle Cd$ $\displaystyle<\frac{1}{1+\epsilon}$ $\displaystyle Cd$
$\displaystyle\leq\frac{\min_{i}\pi_{i}}{\sqrt{1-\min_{i}\pi_{i}}}\frac{4\epsilon}{1+2\epsilon}.$
(68)

Picking $\epsilon=2$ yields the result.

∎

[Acknowledgments] The author would like to thank Arndt von Haeseler for his
useful comments that improved this paper.

C.M. was partly supported by the Austrian Science Fund (FWF, grant number
I-1824-B22) to Arndt von Haeseler.

## References

  * [1] [author] Bleher, P. M.P. M., Ruiz, J.J. and Zagrebnov, V. A.V. A. (1995). On the purity of the limiting gibbs state for the Ising model on the Bethe lattice. Journal of Statistical Physics 79 473-482. 10.1007/BF02179399
  * [2] [author] Felsenstein, JosephJ. (1981). Evolutionary trees from DNA sequences: A maximum likelihood approach. Journal of Molecular Evolution 17 368-376. 10.1007/BF01734359
  * [3] [author] Guiasu, SilviuS. (1977). Information Theory with Applications. McGraw-Hill Companies.
  * [4] [author] Horn, Roger A.R. A. and Johnson, Charles R.C. R. (1991). Topics in Matrix Analysis Chapter 3. Cambridge University Press. 10.1017/CBO9780511840371
  * [5] [author] Steven G. Johnson (2020). Notes on the equivalence of norms. https://math.mit.edu/~stevenj/18.335/norm-equivalence.pdf.
  * [6] [author] Levin, David AD. A. and Peres, YuvalY. (2017). Markov chains and mixing times 107\. American Mathematical Soc.
  * [7] [author] Mossel, ElchananE. (2001). Survey: Information Flow on Trees. In Graphs, Morphisms and Statistical Physics.
  * [8] [author] Mossel, ElchananE. (2001). Reconstruction on Trees: Beating the Second Eigenvalue. The Annals of Applied Probability 11 285 – 300. 10.1214/aoap/998926994
  * [9] [author] Mossel, ElchananE. and Peres, YuvalY. (2003). Information flow on trees. The Annals of Applied Probability 13 817 – 844. 10.1214/aoap/1060202828
  * [10] [author] Shannon, C. E.C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal 27 379-423. 10.1002/j.1538-7305.1948.tb01338.x
  * [11] [author] Strimmer, KorbinianK. and von Haeseler, ArndtA. (2009). Genetic distances and nucleotide substitution models. In The Phylogenetic Handbook: a Practical Approach to Phylogenetic Analysis and Hypothesis Testing 2 ed. (PhilippeP. Lemey, MarcoM. Salemi and VandammeV. Anne-Mieke, eds.) 111-141. Cambridge University Press, Cambridge. 10.1017/CBO9780511819049.006