Proof. We prove the claim by induction on $\ell$ , where we take

\begin{align*} K \,:\!=\,\max\left\{c_1,\sqrt{\frac{c_2}{2}},\ldots,\sqrt[9]{\frac{c_9}{9!}},512\right\}.\end{align*}

Note that by this choice, the claim holds for $1\leqslant \ell\leqslant 9$ . In addition, it trivially holds for $\ell=0$ . In addition, note that $g_{\ell}(\rho)$ is increasing in $\ell$ and $g_1(\rho)\equiv 0.570194101601\ldots$ . Thus, by (A.1), we have to show that

\begin{align*}c_{\ell,1}+c_{\ell,2}+c_{\ell,3}\leqslant g_{1}(\rho)K^{\ell}\ell!\end{align*}

for $\ell\geqslant 10$ . We assume that this claim holds for $\ell'<\ell$ and prove it for $\ell$ . For this, we estimate $c_{\ell,i}$ with $i=1,2,3$ separately.

First, for $c_{\ell,1}$ , we have

(A.2) \begin{align}c_{\ell,1} & \leqslant \frac{1}{2}\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\frac{\ell!}{\ell_3!}\frac{1}{2^{\ell_1+\ell_2}}K^{\ell_1+\ell_2}\leqslant \frac{\ell!}{2}\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\frac{K^{\ell-\ell_3}}{2^{\ell-\ell_3}}\nonumber\\&=\frac{\ell!}{2}\left(\frac{K}{2}\right)^{\ell}\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\left(\frac{2}{K}\right)^{\ell_3}\leqslant \frac{\ell!}{2}\left(\frac{K}{2}\right)^\ell\sum_{\ell_3=0}^{\ell}\left(\frac{1}{256}\right)^{\ell_3}\sum_{\substack{\ell_1+\ell_2=\ell-\ell_3\\\ell_1,\ell_2<\ell}}1\nonumber\\&\leqslant K^{\ell}\ell!\left(\frac{1}{2}\right)^{\ell+1}\sum_{\ell_3=0}^{\ell}\left(\frac{1}{256}\right)^{\ell_3}(\ell-\ell_3+1)\nonumber\\&=K^{\ell}\ell!\left(\frac{1}{2}\right)^{\ell+1}\left(\frac{256}{255}\ell+\frac{256^{-\ell}}{65025}+\frac{65024}{65025}\right)\nonumber\\ & \leqslant 0.005390234525\ldots K^{\ell}\ell!,\end{align}

where in the estimate of the second line, we used that $K\geqslant 512$ , and the last inequality holds for $\ell\geqslant 10$ .

Next, we consider $c_{\ell,2}$ . Here we first note that since $\ell_1+\cdots+\ell_{k+2}=\ell$ , we have $k+1$ degrees of freedom, i.e. $\ell_{k+1}$ is fixed if $\ell_{1},\ldots,\ell_{k}$ and $\ell_{k+2}$ are decided. We replace $c_{\ell_{k+1}}$ on the right-hand side of $c_{\ell,2}$ by $K^{\ell_{k+1}}\ell_{k+1}!$ except when $\ell_{k+1}=0$ and $\ell_{k+1}=1$ , where we replace it by $\rho$ and $c_1$ , respectively. This gives

(A.3) \begin{equation}c_{\ell,2}\leqslant \frac{9}{16}\sum_{k\geqslant 1}\sideset{}{'}\sum\binom{\ell}{\ell_1,\ldots,\ell_{k+2}}\prod_{s=1}^{k}\frac{1}{2^{(s+1)\ell_s}}\mu_{k,0}^{\ell_{k+2}}\left(\prod_{s=1}^{k} c_{\ell_s}\right)K^{\ell_{k+1}}\ell_{k+1}!,\end{equation}

where $\ell_{k+1}=\ell-\ell_1-\cdots-\ell_{k}-\ell_{k+2}$ , the second sum is over all $0<\ell_1+\cdots+\ell_{k}+ \ell_{k+2}\leqslant \ell$ with $\ell_j<\ell,1\leqslant j\leqslant k$ , and we have used that $\xi_{k,\ell_{k+1}}\leqslant 9/16$ with

\begin{align*}\xi_{k,\ell_{k+1}}=\begin{cases}\rho&\text{if}\ \ell_{k+1}=0,\\\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)\frac{c_1}{K}&\text{if}\ \ell_{k+1}=1,\\\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}&\text{if}\ \ell_{k+1}\geqslant 2.\end{cases}\end{align*}

Next, by using $\mu_{k,0}\leqslant 2$ and plugging the induction hypothesis for $c_{\ell_s}$ into (A.3) except when $s\neq k+1$ , where we again use $\rho$ and $c_1$ if $\ell_s=0$ and $\ell_s=1$ , we have

(A.4) \begin{align}c_{\ell,2}&\leqslant \frac{9}{16}K^{\ell}\ell!\sum_{k\geqslant 1}\prod_{s=1}^{k}\left(\rho+\frac{c_1}{K2^{s+1}}+\sum_{\ell_s\geqslant 2}\frac{1}{2^{(s+1)\ell_s}}\right)\sum_{\ell_{k+2}=0}^{\infty}\frac{2^{\ell_{k+2}}}{K^{\ell_{k+2}}\ell_{k+2}!}\nonumber\\&\leqslant \frac{9e^{1/256}}{16}K^{\ell}\ell!\sum_{k\geqslant 1}\prod_{s=1}^{k}\left(\rho+\frac{c_1}{K2^{s+1}}+\frac{1}{2^{s+1}(2^{s+1}-1)}\right)\nonumber\\&=0.223033369804\ldots K^{\ell}\ell!,\end{align}

where we used that $K\geqslant 512$ in the second last step and MAPLE to evaluate the numerical constant.

Similarly, by using $\mu_{k,m}\leqslant 3$ , we obtain

(A.5) \begin{align}c_{\ell,3}&\leqslant \frac{\rho e^{3/512}}{2}K^{\ell}\ell!\sum_{k\geqslant 1}\prod_{s=1}^{k}\left(\rho+\frac{c_1}{K2^{s+1}}+\frac{1}{2^{s+1}(2^{s+1}-1)}\right)\nonumber\\&\qquad\qquad\qquad\qquad\times\sum_{m\geqslant 1}\prod_{t=1}^{m}\left(\rho+\frac{c_1}{K2^{t+1}}+\frac{1}{2^{t+1}(2^{t+1}-1)}\right)\nonumber\\&=0.017199020110\ldots K^{\ell}\ell!.\end{align}

Combining (A.2), (A.4), and (A.5), we get

\begin{align*}c_{\ell,1}+c_{\ell,2}+c_{\ell,3}\leqslant 0.245622624440\ldots K^{\ell}\ell!\leqslant g_1(\rho)K^{\ell}\ell!,\end{align*}

which proves the desired result.

Proof. We again use induction on $\ell$ where the claim holds for $\ell=0$ . Moreover, we choose K large enough such that the conclusion of Lemma 1 holds and in addition that:

• • $K\geqslant \max\left\{d_1,\sqrt{d_2/2},\ldots,\sqrt{d_9/9!},4608c'/c_1,4608d'/d_1\right\}$ ;

• • $\rho\geqslant \max\left\{3c_1/(4K),3^2c_2/(2! 4^2K^2),\ldots,3^{9}c_9/(9!4^9K^9)\right\}$ ;

where $c'\,:\!=\, \max\{c_1,\ldots,c_9\}$ and $d'\,:\!=\, \max\{d_1,\ldots,d_9\}$ .

By item (i), the claim holds for all $1\leqslant \ell\leqslant 9$ . Thus, we can assume that $\ell\geqslant 10$ and that the claim holds for all $\ell'<\ell$ . We are going to bound $d_{\ell,i}$ for $i=1,2,3$ .

First, for $d_{\ell,1}$ , we have

\begin{align*}f'_{\ell,1}(z)&=\frac{1}{2}\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\binom{\ell}{\ell_1,\ell_2,\ell_3}\frac{1}{2^{\ell_1+\ell_2}}\left((A^{[\ell_1]})'(z)A^{[\ell_2]}(z)+A^{[\ell_1]}(z)(A^{[\ell_2]})'(z)\right)\end{align*}

and thus

\begin{align*}d_{\ell,1} & = \frac{1}{2}\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\binom{\ell}{\ell_1,\ell_2, \ell_3}\frac{1}{2^{\ell_1+\ell_2}}\left(d_{\ell_1}c_{\ell_2}+c_{\ell_1}d_{\ell_2}\right)\\&=\sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\binom{\ell}{\ell_1,\ell_2, \ell_3}\frac{1}{2^{\ell_1+\ell_2}}c_{\ell_1}d_{\ell_2}.\end{align*}

Using the induction hypothesis and the estimate from Lemma 1, we obtain

(A.6) \begin{equation}d_{\ell,1}\leqslant \sum_{\substack{\ell_1+\ell_2+\ell_3=\ell\\ \ell_1,\ell_2<\ell}}\frac{\ell!}{\ell_3!}\frac{1}{2^{\ell_1+\ell_2}}K^{\ell_1+\ell_2}\leqslant 0.010780469050\ldots K^{\ell}\ell!,\end{equation}

which is twice the bound from (A.2).

Next, for $d_{\ell,2}$ , we have

\begin{align*}f'_{\ell,2}(z)=\sum_{k\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+2}=\ell\\ \ell_j<\ell,1\leqslant j\leqslant k+1}}&\binom{\ell}{\ell_1, \ldots,\ell_{k+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}\mu_{k,0}^{\ell_{k+2}}\\&\times\left(\sum_{i=1}^{k+1}(A^{[\ell_i]})'(z)\prod_{\substack{1\leqslant j\leqslant k+1\\j\neq i}}A^{[\ell_j]}(z)\right)\end{align*}

and thus

\begin{align*}d_{\ell,2}&=\sum_{k\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+2}=\ell\\ \ell_j<\ell,1\leqslant j\leqslant k+1}}\binom{\ell}{\ell_1,\ldots,\ell_{k+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}\mu_{k,0}^{\ell_{k+2}}\\&\qquad\qquad\qquad\times\left(\sum_{i=1}^{k+1}d_{\ell_i}\prod_{\substack{j=1\\j\neq i}}^{k+1}c_{\ell_j}\right)\\&=\sum_{k\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+2}=\ell\\ \ell_j<\ell,1\leqslant j\leqslant k+1}}\binom{\ell}{\ell_1,\ldots,\ell_{k+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}\mu_{k,0}^{\ell_{k+2}}\\&\qquad\qquad\qquad\times\left(\sum_{i=1}^{k}d_{\ell_i}\prod_{\substack{j=1\\j\neq i}}^{k+1}c_{\ell_j}\right)\\&\quad+\sum_{k\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+2}=\ell\\ \ell_j<\ell,1\leqslant j\leqslant k+1}}\binom{\ell}{\ell_1,\ldots,\ell_{k+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}\mu_{k,0}^{\ell_{k+2}}\\&\qquad\qquad\qquad\times d_{\ell_{k+1}}\prod_{j=1}^{k}c_{\ell_j}.\end{align*}

We use now both the estimate for $c_{\ell}$ from Lemma 1 and the induction hypothesis for $d_{\ell}$ except for $0\leqslant \ell\leqslant 9$ . Moreover, we use $\mu_{k,0}\leqslant 2$ (as in the proof of Lemma 1) and

\begin{align*}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}c_{\ell_{k+1}}\leqslant \left(\frac{3}{4}\right)^{\ell_{k+1}}c_{\ell_{k+1}}\leqslant \rho K^{\ell_{k+1}}\ell_{k+1}!,\end{align*}

which follows by item (ii) above and

\begin{align*}\left(\frac{1}{2}+\frac{1}{2^{k+1}}\right)^{\ell_{k+1}}d_{\ell_{k+1}}\leqslant K^{\ell_{k+1}}\ell_{k+1}!,\end{align*}

which holds trivially. The rest is handled by similar ideas as in the proof of Lemma 1. Thus, we obtain

\begin{align*}d_{\ell,2}&\leqslant \rho e^{2/K} K^{\ell}\ell!\sum_{k\geqslant 1}\prod_{s=1}^k\left(\rho+\left(\sum_{i=1}^9\frac{c_i}{2^{i(s+1)}i!K^i}\right)+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}\right)\\&\qquad\qquad\qquad\times\left(\sum_{s=1}^k\frac{1+\left(\sum_{i=1}^9\frac{d_i}{2^{i(s+1)}i!K^i}\right)+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}}{\rho+\left(\sum_{i=1}^9\frac{c_i}{2^{i(s+1)}i!K^i}\right)+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}}\right)\\&\hspace{1.25 em}+ e^{2/K} K^{\ell}\ell!\sum_{k\geqslant 1}\prod_{s=1}^k\left(\rho+\left(\sum_{i=1}^9\frac{c_i}{2^{i(s+1)}i!K^i}\right)+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}\right).\end{align*}

Note that, by our choice of K,

\begin{align*}\sum_{i=1}^{9}\frac{c_i}{2^{i(s+1)}i!K^i}\leqslant \frac{9c'}{2^{s+1}K}\leqslant \frac{1}{512\cdot 2^{s+1}}\end{align*}

and likewise with the $c_i$ ’s replaced by $d_i$ ’s. Plugging this into the above expression and numerically evaluating it (again with MAPLE), we obtain

(A.7) \begin{equation}d_{\ell,2}\leqslant 0.643482769458\ldots K^{\ell}\ell!.\end{equation}

We finally consider $d_{\ell,3}$ , which is treated in a similar fashion. First,

\begin{align*}f'_{\ell,3}(z)&=\frac{1}{2}\sum_{k\geqslant 1}\sum_{m\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+m+2}=\ell \\ \ell_j< \ell,1\leqslant j\leqslant k+m+1}}\binom{\ell}{\ell_1, \ldots,\ell_{k+m+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\prod_{t=1}^m\frac{1}{2^{(t+1)\ell_{k+t}}}\\&\qquad\times\left(\frac{1}{2^{k+1}}+\frac{1}{2^{m+1}}\right)^{\ell_{k+m+1}}\mu_{k,m}^{\ell_{k+m+2}}\left(\sum_{i=1}^{k+m+1}(A^{[\ell_i]})'(z)\prod_{\substack{j=1\\j\neq i}}^{k+m+1}A^{[\ell_j]}(z)\right)\end{align*}

and thus

\begin{align*}d_{\ell,3}&= \frac{1}{2}\sum_{k\geqslant 1}\sum_{m\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+m+2}=\ell \\ \ell_j<\ell,1\leqslant j\leqslant k+m+1}}\binom{\ell}{\ell_1, \ldots,\ell_{k+m+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\prod_{t=1}^m\frac{1}{2^{(t+1)\ell_{k+t}}}\\&\qquad\quad\times\left(\frac{1}{2^{k+1}}+\frac{1}{2^{m+1}}\right)^{\ell_{k+m+1}}\mu_{k,m}^{\ell_{k+m+2}}\left(\sum_{i=1}^{k+m}d_{\ell_i}\prod_{\substack{j=1\\j\neq i}}^{k+m+1}c_{\ell_j}\right)\\& \hspace{1 em} +\frac{1}{2}\sum_{k\geqslant 1}\sum_{m\geqslant 1}\sum_{\substack{\ell_1+\cdots+\ell_{k+m+2}=\ell \\ \ell_j<\ell,1\leqslant j\leqslant k+m+1}}\binom{\ell}{\ell_1, \ldots, \ell_{k+m+2}}\prod_{s=1}^k\frac{1}{2^{(s+1)\ell_s}}\prod_{t=1}^m\frac{1}{2^{(t+1)\ell_{k+t}}}\\&\qquad\quad\times\left(\frac{1}{2^{k+1}}+\frac{1}{2^{m+1}}\right)^{\ell_{k+m+1}}\mu_{k,m}^{\ell_{k+m+2}}d_{\ell_{k+m+1}}\prod_{i=1}^{k+m}c_{\ell_i}(z).\end{align*}

Using $\mu_{k,m}\leqslant 3$ (see the proof of Lemma 1) and arguments as above, we obtain

(A.8) \begin{align}&d_{\ell,3}\leqslant \rho e^{3/K} K^\ell \ell!\sum_{k\geqslant 1}\prod_{s=1}^k\left(\rho+\frac{c_1}{512\cdot2^{(s+1)}K}+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}\right)\nonumber\\&\times \hspace{-0.1cm}\left(\sum_{s=1}^k\frac{1+\frac{d_1}{512\cdot2^{(s+1)}}+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}}{\rho+\frac{c_1}{512\cdot2^{(s+1)}}+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}}\right)\sum_{k\geqslant 1}\prod_{s=1}^k\left(\rho+\frac{c_1}{512\cdot2^{(s+1)}}+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}\right)\nonumber\\&\ +\frac{e^{3/K}K^\ell \ell!}{2}\left(\sum_{k\geqslant 1}\prod_{s=1}^k\left(\rho+\frac{c_1}{512\cdot2^{(s+1)}}+\frac{1}{2^{9(s+1)}(2^{s+1}-1)}\right)\right)^2\nonumber\\&\ =0.141422204463\ldots K^{\ell}\ell!.\end{align}

Combining (A.6), (A.7), and (A.8), we obtain

\begin{align*}d_{\ell,1}+d_{\ell,2}+d_{\ell,3}\leqslant 0.795685442972\ldots K^{\ell}\ell!.\end{align*}

Finally, for $\ell\geqslant 10$ ,

\begin{align*}d_{\ell}&\leqslant \frac{d_{\ell,1}+d_{\ell,2}+d_{\ell,3}}{g_{10}(\rho)}-\frac{g_{10}'(\rho)}{g_{10}(\rho)}c_{\ell}\\&\leqslant 0.869090272578\ldots K^{\ell}\ell!\end{align*}

since $-g_{\ell}'(\rho)/g_{\ell}(\rho)$ decreases to 0 and $g_{10}(\rho)= 0.986940779096\ldots$ and $-g_{10}'(\rho)/g_{10}(\rho)=0.062876303286\ldots$ . This proves the claim.

Proof. First, let us show that $\bar{x}\in \mathcal{K}$ for any $x\in \mathcal{E}$ . Fix $x \in \mathcal{E}$ , $v \in \bar{x}$ , and $u \preccurlyeq v$ . We must show that $u \in \bar{x}$ , i.e. that x contains a ray that goes through u. Let $r\in x$ be such that $v \in r$ . Because G is rooted and $u \preccurlyeq v$ , there exists a path that goes from the root of G to u, and then from u to v. Let r ^′ be the ray that starts with this path and then continues along r. Since $r'$ $r$ , we have $r' \in x$ , concluding the proof that $\bar{x} \in \mathcal{K}$ .

Let us now show that $x\mapsto \bar{x}$ is injective. Consider $x, y \in \mathcal{E}$ such that $\bar{x}=\bar{y}$ , and fix two rays $r = (v_i)_{i\geqslant 0}\in x$ and $r' = (v'_i)_{i\geqslant 0}\in y$ . To show that $x = y$ , we must show that $r$ $r'$ , and for this it suffices to show a ray that intersects r and r ^′ infinitely many times. The key is to show that for all $i\geqslant 0$ , there exists $j \geqslant 0$ such that $v_i \preccurlyeq v'_j$ —indeed, by symmetry we then get that there exists $k \geqslant 0$ such that $v'_j \preccurlyeq v_k$ , etc., and by a straightforward concatenation procedure we can build a ray that goes to and fro between vertices of r and vertices of r ^′. By assumption, $\bar{x} = \bar{y}$ and thus $v_i \in \bar{y}$ . As a result, there exists a ray $r''$ $r'$ such that $v_i \in r''$ , and since r ^″ intersects r ^′ infinitely many times, there exists $u \in r''$ , $u \succcurlyeq v_i$ such that $u \in r'$ , concluding the proof of the injectivity of $x\mapsto \bar{x}$ .

Finally, consider any ray $r = (v_n)_{n\geqslant 0}$ , letting x denote the corresponding end. Let us show that $\bar{v}_n \to \bar{x}$ as $n \to \infty$ , i.e. let us fix some $k\geqslant 0$ and show that $[\bar{x}]_k = [\bar{v}_i]_k$ for all i large enough. Let $v\in [\bar{x}]_k$ , and pick $r_v\in x$ such that $v\in r_v$ . Because $r_v$ $r$ , there exists $i_v\in \mathbb{N}$ such that $v\preccurlyeq v_{i_v}$ . Since $[G]_k$ is finite, we can define

\begin{align*} N_k = \max \{i_v \,:\, v\in [\bar{x}]_k\}.\end{align*}

Thus, $[\bar{x}]_k \subset \bar{v}_i$ for all $i\geqslant N_k$ . Moreover, because $\bar{x}\in \mathcal{K}$ we also have $\bar{v}_i\subset \bar{x}$ for all $i\geqslant 0$ . As a result, $[\bar{x}]_k = [\bar{v}_i]_k$ for all $i\geqslant N_k$ , concluding the proof.

Proof. Let $(A_i)_{i\geqslant 1}$ denote the family of distinct atoms of $\mu$ . Let $A=\bigcup_i A_i$ , and note that by assumption $\mu({A}^{\mathsf{C}}) > 0$ . Define

\begin{align*} \sigma_A = \{A_i \,:\, i \geqslant 1\}\cup \{{A}^{\mathsf{C}}\} .\end{align*}

By Proposition 5, we have

\begin{align*} H(\mu) = H_{\mu}(\sigma_A) + \mu({A}^{\mathsf{C}})\, H(\mu_{{A}^{\mathsf{C}}}) .\end{align*}

Thus, to finish the proof it suffices to show that $H(\mu_{{A}^{\mathsf{C}}}) = +\infty$ .

By Lyapunov’s theorem on non-atomic measures (see, e.g., [Reference Artstein2]), for all n it is possible to find a measurable partition $\pi_n = \{B_1, \dots, B_n\}$ of ${A}^{\mathsf{C}}$ such that $\mu(B_i)=\mu({A}^{\mathsf{C}})/n$ for all $i\in \{1, \dots, n\}$ . It follows that

\begin{align*} H(\mu_{{A}^{\mathsf{C}}}) \geqslant H_{\mu_{{A}^{\mathsf{C}}}}(\pi_n) = \log_2(n) .\end{align*}

Since n can be arbitrarily large, this concludes the proof.

Proof. The fact that $\pi$ is measurable can be deduced from Remark 5. This remark is also the key to the rest of the proof. Indeed, since $\pi_n[x] \to \pi[x]$ for all $x\in \Omega$ ,

(C1) \begin{equation} \mu(\pi_n[x]) \xrightarrow[n\to\infty]{} \mu(\pi[x]) \quad \mbox{for all } x\in \Omega.\end{equation}

For any measurable partition $\sigma$ , define the following measurable function:

\begin{align*} f^\sigma\colon\, x\in \Omega\, \longmapsto \begin{cases} -\log_2\big(\mu(\sigma[x])\big) &\text{if } \mu(\sigma[x])>0, \\ \infty & \text{otherwise}. \end{cases}\end{align*}

By (B1), $f^{\pi_n}\to f^{\pi}$ pointwise. Noting that, in view of Proposition 6, $H_{\mu}(\sigma)=\int f^\sigma \,d\mu$ , we deduce from Fatou’s lemma that

\begin{align*} \liminf_{n\to\infty} H_{\mu}(\pi_n) \geqslant H_{\mu}(\pi).\end{align*}

This concludes the proof, since, by Proposition 4, $H_{\mu}(\pi_n) \leqslant H_{\mu}(\pi)$ for all n.

Proof. We will show that $B_2$ can be expressed as a pointwise limit of continuous functions from $\mathbb{G}$ to $\mathbb{R}$ .

Let G be a fixed phylogenetic network, and let $X=(X_n)_{n\geqslant 0}$ be the directed random walk on G, started from the root. Note that X is the only source of randomness, and that, for any $n \geqslant 0$ , the distribution of $X_n$ depends only on $[G]_n$ . Therefore, the functions

\begin{align*} B_2^{k,n}\colon G \longmapsto -\!\!\!\sum_{A\subset [G]_k}\!\! p_A^n \log_2(p_A^n), \quad \text{where } p_A^n = \mathbb{P}{([\bar{X}_n]_k = A)},\end{align*}

are continuous for the local topology (recall that $\bar{X}_n$ denotes the set of ancestors of $X_n$ in G, and that we use the short notation $[\bar{X}_n]_k = \bar{X}_n \cap [G]_k$ ). Furthermore, we gave in Definition 10 a compactification $\mathcal{K}$ of G in which $X_n$ converges almost surely to $X_{\infty}$ and in which, by definition, the functions $x \mapsto [\bar{x}]_k$ are continuous, for all k. Therefore, for any $k\geqslant 1$ and $A \subset [G]_k$ , by dominated convergence,

\begin{align*} p_A^n = \mathbb{P}{([\bar{X}_n]_k = A)} \xrightarrow[n\to\infty]{} \mathbb{P}{([\bar{X}_{\infty}]_k = A)} \,=\!:\, p_A\, .\end{align*}

This implies that

\begin{align*} B_2^{k,n}(G) \xrightarrow[n\to\infty]{} B_2^k(G) \,:\!=\, -\!\!\!\sum_{A\subset [G]_k}\!\! p_A \log_2(p_A) = H_{\mu}(\pi_k),\end{align*}

where $\mu$ is the distribution of $X_{\infty}$ on $\mathcal{K}$ , and $\pi_k$ is the partition defined by

\begin{align*} x\sim_{\pi_k} y \iff [\bar{x}]_k = [\bar{y}]_k .\end{align*}

Because the map $x\mapsto \bar{x}$ is injective (see Proposition 3), as $k\to\infty$ the partition $\pi_k$ tends to the partition into singletons. Therefore, by Lemma 3 and definition of $B_2$ ,

\begin{align*} B_{2}^k(G) = H_{\mu}(\pi_{k}) \xrightarrow[k\to\infty]{} H(\mu) = B_2(G),\end{align*}

concluding the proof.

Proof. Let $\mathcal{L}$ be the leaf set of G, and let $\mathcal{L}_k = \{\ell \in \mathcal{L} \,:\, h(\ell) \leqslant k\}$ be the set of leaves at height at most k. As always, write X for the directed random walk on G, and $X_{\infty}$ for its limit on the boundary of G. Finally, let $p_{\ell} = \mathbb{P}{(X_{\infty}=\ell)}$ .

Since $\mathbb{P}{(X_{\infty} \in \mathcal{L})} = 1$ , we have $B_2(G) = -\!\sum_{\ell \in \mathcal{L}} p_{\ell} \log_2 p_{\ell}$ , and since $\mathcal{L} = \operatorname{lim\!\uparrow\,}_k \mathcal{L}_k$ , it follows that

\begin{align*} -\sum_{\ell \in \mathcal{L}_k} \! p_{\ell}\log_2 p_{\ell} \xrightarrow[k\to\infty]{} B_2(G).\end{align*}

Now fix some b such that $0< b <B_2(G)$ , and let k be such that the sum in the expression above be greater than b. Fix $n_0$ such that $[G_n]_k=[G]_k$ for all $n\geqslant n_0$ . Then, for all $n\geqslant n_0$ ,

\begin{align*} B_2(G_n) \geqslant -\sum_{\ell \in \mathcal{L}_k} p_{\ell}\log_2 p_{\ell} > b.\end{align*}

This shows that $\liminf_n B_2(G_n) \geqslant b$ . Our letting $b\to B_2(G)$ concludes the proof.

Proof. Let us write $q_n = \mathbb{P}{(h(X_{\infty}) > k_n)}$ . Since $\log \left|{G_n}\right|$ cannot tend to 0 (except in the trivial case where G is a finite DAG with a single leaf), we must have $q_n\to 0$ . This means that $\mathbb{P}{(X_{\infty} \in \mathcal{L})} = 1$ , where $\mathcal{L}$ denotes the leaf set of G. As a result, by Proposition 9 it suffices to show

\begin{align*} \limsup_{n\to\infty} B_2(G_n) \leqslant B_2(G) = -\sum_{\ell\in \mathcal{L}}p_{\ell} \log_2 p_{\ell} ,\end{align*}

where $p_{\ell} = \mathbb{P}{(X_{\infty} = \ell)}$ . Let us write $\mathcal{L}_{k_n}^{n}$ (respectively $\mathcal{L}_{>k_n}^n$ ) for the set of leaves in $G_n$ at height at most $k_n$ (respectively at least $k_n+1$ ). For any leaf $\ell\in G_n$ , write $\smash{p_{\ell}^{(n)}}$ for the probability that the directed random walk on $G_n$ ends in $\ell$ . Notice that, since $[G_n]_{k_n}=[G]_{k_n}$ ,

\begin{align*} -\!\sum_{\ell \in \mathcal{L}_{k_n}^{n}}\!\! p^{(n)}_{\ell} \log_2 p^{(n)}_{\ell} = -\!\sum_{\ell \in \mathcal{L}_{k_n}}\!\! p_{\ell} \log_2 p_{\ell} ,\end{align*}

and that, since $(p^{(n)}_{\ell}\! / q_n \,:\, \ell \in \mathcal{L}_{>k_n}^{n})$ is a probability distribution, Jensen’s inequality gives

\begin{align*} -\frac{1}{q_n}\sum_{{\ell \in \mathcal{L}_{ > k_n}^{n}}}\; p^{(n)}_{\ell} \log_2p^{(n)}_{\ell} \leqslant \log_2\Bigg(\sum_{{\ell \in \mathcal{L}_{>k_n}^{n}}}\;\; \frac{p^{(n)}_{\ell}}{q_n}\cdot\frac{1}{p^{(n)}_{\ell}} \Bigg) \leqslant \log_2\bigg(\frac{\left|{G_n}\right|}{q_n}\bigg).\end{align*}

It follows that

\begin{align*} B_2(G_n) \leqslant -\!\sum_{\ell \in \mathcal{L}_{k_n}}\!\! p_{\ell} \log_2 p_{\ell} + q_n\log_2\bigg(\frac{\left|{G_n}\right|}{q_n}\bigg),\end{align*}

where the first term on the right-hand side tends to $B_2(G)$ , while the second one tends to 0 because $q_n\to 0$ and $q_n \log_2 |G_n|\to 0$ by hypothesis.

Proof. For any stub $S \sqsubset G$ , let $\pi_S$ be the partition of $\partial G$ defined by the following equivalence relation:

\begin{align*} x \sim_{S} y \iff x = y \text{ or } \bar{x} \cap \bar{y} \text{ contains a leaf of } S.\end{align*}

To see that this is indeed an equivalence relation, recall that the leaves of S are either leaves or cut-vertices in G, and note that for all $x \in \partial G$ , the set $\bar{x}$ contains at most one leaf of S. The transitivity of $\sim_S$ then follows readily.

Note that the partitions $\pi_{S_n}$ are refining along the stub sequence $(S_n)$ , and that they converge simply (see Definition 13) to $\pi_G$ , the partition into singletons. Indeed, pick $x\neq y$ and assume that $x\sim_{S_n}y$ for all n. For each n, let $v_n$ be the unique leaf of $S_n$ in $\bar{x} \cap \bar{y}$ . Then

• • If $\{v_n \,:\, n \geqslant 1\}$ is finite then there exists $\ell$ such that $v_n = \ell$ for all n large enough. By the local convergence of $S_n$ to G, this vertex $\ell$ is a leaf of G, and therefore $x = y = \ell$ , yielding a contradiction.

• • If $\{v_n \,:\, n \geqslant 1\}$ is infinite then $v_1, v_2, \ldots$ are cut-vertices of G and they lie on a ray $r \subset \bar{x} \cap \bar{y}$ . This entails $x = y$ : indeed, let $r_x \in x$ and $r_y \in y$ . For all n, since $v_n \in \bar{x}$ and $v_n$ is a cut-vertex of G, $v_n \in r_x$ . As a result, $r_x$ intersects r infinitely many times. Similarly, $r_y$ intersects r infinitely many times. Thus, we have $r_x$ $r_y$ , and therefore $x = y$ , again yielding a contradiction.

Finally, note that $B_2(S_n) = H_{\mu}(\pi_{S_n})$ , where $\mu$ is the distribution of $X_{\infty}$ , and that, by definition, $B_2(G) = H_{\mu}(\pi_G)$ . Thus, the proposition follows from Lemma 3.

Proof. (i) By Minami’s correspondence [Reference Minami23, Theorem 2], we have

\begin{align*} \mathbb{P}{(|{T}|=n)} = \mathbb{P}{(v(T')=n)},\end{align*}

where v(T ^′) denotes the number of vertices of T ^′, and T ^′ is a $\mathrm{GW}(\xi')$ tree whose offspring distribution is given by

\begin{align*} \xi' = \sum_{i=1}^{Z}Y_i ,\end{align*}

with $\mathbb{P}{(Z=n)} = \mathbb{P}{(\xi>0)}^n\, \mathbb{P}{(\xi=0)}$ for all $n\geqslant 0$ , and where the variables $Y_i$ are i.i.d., independent of Z, and distributed as $(\xi-1 \mid \xi>0)$ . It is easy to see that T ^′ is critical and that $\xi'$ has a finite third moment.

Next, we use the well-known fact (see, e.g., [Reference Dwass10]) that

\begin{align*} n\, \mathbb{P}{(v(T')=n)} =\mathbb{P}{(S_n=n-1)}, \quad \text{with } S_n = \sum_{i=1}^{n} \xi'_i,\end{align*}

where the $\xi'_i$ are i.i.d. copies of $\xi'$ . Since $\xi'$ has a finite third moment, the asymptotic expansion given in (i) follows readily from a Berry–Esseen-type estimate for the local central limit theorem [Reference Petrov24, Chapter VII, Theorem 6].

(ii) Let us fix a sequence $k_n = o(\sqrt{n})$ . By construction of Kesten’s tree, we have

(E2) \begin{equation} \big|{T_*^{k_n}}\big|-1 \overset{d}{=} \sum_{i=1}^{k_n} X_i,\end{equation}

where the $X_i$ are independent and distributed as $\sum_{i=1}^{Y}\left|T_i\right|$ , where Y is distributed as $\hat{\xi}-1$ and the $T_i$ are i.i.d. $\mathrm{GW}(\xi)$ trees.

Similarly to the proof of (i), using a standard local central limit theorem—this time requiring only a finite second moment for $\xi$ —we get $\mathbb{P}{(|{T}|\geqslant n)} \sim C_1n^{-1/2}$ for some constant $C_1>0$ (for a complete proof in a more general case, see, e.g., [Reference Kortchemski21, Theorem 3.1]). Because $\hat{\xi}-1$ has a finite expectation, we also have $\mathbb{P}{(X_1\geqslant n)} \sim C_2n^{-1/2}$ for the variables $X_i$ in (B2), for some constant $C_2>0$ . Therefore, $X_1$ is in the domain of attraction of a $(1/2)$ -stable distribution and we can apply Heyde’s large deviation theorem [Reference Heyde14]: for any non-decreasing sequence $(x_m)$ such that $\sum_{i=1}^m X_i/x_m \to 0$ in probability, we have

\begin{align*} \mathbb{P}{\Bigg(\sum_{i=1}^m X_i \geqslant x_n\Bigg)} = \Theta\big(m\,\mathbb{P}{(X_1 \geqslant x_n)}\big) = \Theta\Big(\frac{m }{\sqrt{x_n}}\Big).\end{align*}

Since $k_n=o(\sqrt{n})$ and since $X_1$ is in the domain of a $(1/2)$ -stable distribution, we have $\sum_{i=1}^{k_n} X_i/n \to 0$ in probability, and so the equation above translates to

\begin{align*} \mathbb{P}{(|T_*^{k_n}| \geqslant n)} = \mathbb{P}{\Bigg(\sum_{i=1}^{k_n} X_i \geqslant n\Bigg)} = \Theta\Big(\frac{k_n}{\sqrt{n}}\Big),\end{align*}

concluding the proof.

Proof. For $k\geqslant 0$ , let $G_*^k$ denote the almost surely finite network obtained from $G^*$ by removing all (strict) descendants of $v_k$ —with the notation of Appendix E, this is a blowup of $T_*^k$ with respect to $\nu$ . Let us now fix $k\geqslant 0$ and define D to be the out-degree of $u_k$ , i.e. the number of leaves of $\Gamma_{u_k}$ . For each $i = 1, \ldots, D$ , let then $q_i$ denote the probability, conditional on $\Gamma_{u_k}$ , for a random walk started from $v_k$ to pass through the ith leaf of $\Gamma_{u_k}$ . Because $\Gamma_{u_k}$ is leaf-exchangeable, we have

\begin{align*} \mathbb{E}{[q_1 | G_*^k, D]} = \frac{1}{D},\end{align*}

and because $u_{k+1}$ is chosen uniformly among the children of $u_k$ ,

\begin{align*} \mathbb{E}{\bigg[\frac{p_{k+1}}{p_k} \Big| G_*^k, D\bigg]} = \mathbb{E}{[q_1 | G_*^k, D]} = \frac{1}{D}.\end{align*}

Integrating this with respect to D, we get

\begin{align*} \frac{1}{p_k}\,\mathbb{E}{[p_{k+1} | G_*^k]} = \sum_{n\geqslant 1} n\,\mathbb{P}{(\xi=n)}\cdot \frac{1}{n} = \mathbb{P}{(\xi \geqslant 1)} = 1-\eta_0.\end{align*}

Because the out-degrees of the vertices are i.i.d. on the spine of $T_*$ , it follows that $(1-\eta_0)^{-k}p_k$ is a positive martingale. As a result, it converges almost surely to a non-negative random variable. This concludes the proof.

Proof. The proof of the convergence in distribution consists in building a coupling of $(G_n)_{n\geqslant 1}$ and $G_*$ such that any subsequence of $(B_2(G_n))_{n\geqslant 0}$ has a subsequence that converges to $B_2(G_*)$ almost surely. To prove the convergence of moments, we show that, for all $m \geqslant 1$ , the sequence $(\mathbb{E}{[B_2(G_n)^m]})_{n \geqslant 1}$ is bounded.

Let us describe our coupling: First, pick any sequence of integers $(k_n)_{n\geqslant 1}$ such that

\begin{align*} \log\log n \ll k_n \ll n^{1/2 - \varepsilon},\end{align*}

for some $\varepsilon > 0$ . Then, build $(G_*, T_*)$ as in Subsection 3.3: let $\mathcal{U}$ denote the Ulam–Harris tree, and let $\Gamma = (\Gamma_{\!v}^{k} \,:\, v \in \mathcal{U}, k \geqslant 1)$ be a family of independent phylogenetic networks such that $\Gamma_{\!v}^{k} \sim \nu_{k}$ . Finally, sample $T_*$ independently of $\Gamma$ , and let $G_*$ be the blowup obtained from $(T_*, \Gamma)$ .

Next, conditional on $T_*$ , build a sequence $(G_n, T_n)_{n\geqslant 1}$ as follows: for each $n \geqslant 1$ , sample a conditioned $\mathrm{GW}(\xi)$ tree $T_n$ with n leaves, independently of $\Gamma$ and in such a way that

\begin{align*} \mathbb{P}{\big(T_n^{k_n} \neq T_*^{k_n}\big)} = d_{\mathrm{TV}}\big(T_n^{k_n}, T_*^{k_n}\big),\end{align*}

where the truncated trees $T_n^{k}$ and $T_*^k$ are defined as in Appendix E. Finally, let $G_n$ be the blowup obtained from $T_n$ and $\Gamma$ .

Let us now show that any subsequence of $(B_2(G_n))_{n \geqslant 1}$ has a subsequence that converges to $B_2(G_*)$ almost surely—and, therefore, in distribution. By a standard result (see, e.g., [Reference Billingsley7, Theorem 2.6]), this will prove that $B_2(G_n) \to B_2(G_*)$ in distribution. First, note that since $k_n = o(\sqrt{n})$ , by Proposition 12 we have

\begin{align*} d_{\mathrm{TV}}\big(T_n^{k_n}, T_*^{k_n}\big) = O\Big(\frac{k_n}{\sqrt{n}}\Big) \xrightarrow[n\to\infty]{} 0 .\end{align*}

As a result, along any increasing sequence of integers there exists a subsequence, whose range we denote by A, such that

\begin{align*} \sum_{n\in A} \mathbb{P}{\big(T_n^{k_n} \neq T_*^{k_n}\big)} < \infty .\end{align*}

Thus, by the Borel–Cantelli lemma, there exists a random $n_0$ such that, for all $n\in A\cap [n_0,\infty[$ , we have $T_n^{k_n}=T_*^{k_n}$ —and, therefore, $G_n^{k_n}=G_*^{k_n}$ .

As previously, for each k let $v_k$ denote the distinguished leaf of $G_n^{k}$ and let $p_k = p_{v_k}$ denote the probability that the directed random walk reaches it. Since on the event $\{G_n^{k_n}=G_*^{k_n}\}$ , the network $G_n$ can be obtained from $G_*^k$ by grafting a network with at most n leaves on $v_k$ , by Proposition 1 we have

\begin{align*} B_2\big(G_*^{k_n}\big) \leqslant B_2(G_n) \leqslant B_2\big(G_*^{k_n}\big) + p_{k_n} \log_2 n.\end{align*}

Because $k_n \gg \log\log n$ , by Lemma 5 the term $p_{k_n} \log_2 n$ vanishes almost surely. Finally, by Proposition 11, $B_2(G_*^{k_n}) \to B_2(G_*)$ almost surely. As a result, $B_2(G_n) \to B_2(G_*)$ along the subsequence indexed by A, concluding the proof of point (i).

It remains to show the convergence of all moments of $B_2(G_n)$ . Because we have already proved the convergence in distribution, it is sufficient to show that for all $m\geqslant 1$ , $\mathbb{E}{[B_2(G_n)^m]}$ is bounded: indeed, this implies that $(B_2(G_n)^m)_{n\geqslant 1}$ is uniformly integrable—which, together with the convergence in distribution, implies the convergence of moments (see, e.g., [Reference Kallenberg17, Lemma 5.11]).

Note that

\begin{align*} B_2(G_n)^m \leqslant \unicode{x1D7D9}_{\{G_n^{k_n}\neq G_*^{k_n}\}}(\!\log_2n)^m + \unicode{x1D7D9}_{\{G_n^{k_n}= G_*^{k_n}\}} \big(B_2(G_*^{k_n}) + p_{k_n}\log_2 n\big)^m .\end{align*}

Using $(a+b)^m \leqslant 2^{m-1}(a^m + b^m)$ for $a, b \geqslant 0$ , bounding $\unicode{x1D7D9}_{\{G_n^{k_n} = G_*^{k_n}\}}$ by 1, and taking expectations, we get

\begin{align*} \mathbb{E}{[B_2(G_n)^m]} \leqslant d_{\mathrm{TV}}\big(T_n^{k_n}, T_*^{k_n}\big) (\!\log_2 n)^m + 2^{m-1} \big(\mathbb{E}{\big[B_2\big(G_*^{k_n}\big)^m\big]} + \mathbb{E}{[p_{k_n}^m]} (\!\log_2 n)^m\big).\end{align*}

Recalling that $\log \log n \ll k_n \ll n^{1/2-\epsilon}$ and that $d_{\mathrm{TV}}(T_n^{k_n}, T_*^{k_n}) = O(k_n / \sqrt{n})$ , we see that the first term on the right-hand side vanishes as $n\to\infty$ . So does $\mathbb{E}{[p_{k_n}^m]} (\!\log_2 n)^m$ , since $p_{k_n}^m \leqslant p_{k_n}$ and, by Lemma 5, $\mathbb{E}{[p_{k_n}]} = (1-\eta_0)^{k_n}$ with $(1-\eta_0)<1$ . Finally, $B_2(G_*^{k_n})\leqslant B_2(G_*)$ . Therefore, to conclude the proof it suffices to show that $\mathbb{E}{[B_2(G_*)^m]}$ is finite.

Let us fix some notation: let $u_k$ denote the kth vertex along the spine of $T_*$ , and let $\Gamma_{\!u_k}$ be the corresponding network in the blowup construction of $G_*$ . Let $\hat{\xi}_k$ be the number of leaves of $\Gamma_{\!u_k}$ , and for $i = 1, \ldots, \hat{\xi}_k$ let $q_{k, i}$ be the probability that the directed random walk started from the root of $G_*$ goes through the ith leaf of $\Gamma_{\!u_k}$ . Note that, because of the leaf-exchangeability of $\Gamma_{\!u_k}$ , we can assume that for all $k\geqslant 0$ the spine goes through the first leaf of $\Gamma_{\!u_k}$ , so that $q_{k, 1} = p_{k+1}$ . Finally, let us write $G_{k,i}$ for the finite phylogenetic network consisting of the ith leaf of $\Gamma_{\!u_k}$ and all of its descendants. With this notation, by the grafting property,

\begin{align*} B_2(G_*) = \sum_{k\geqslant 0} \Bigg( p_k\, B_2(\Gamma_{\!u_k}) + \sum_{i=2}^{\hat{\xi}_k} q_{k,i}\, B_2(G_{k,i}) \Bigg).\end{align*}

Therefore,

(F1) \begin{equation} \mathbb{E}{[B_2(G_*)^m]} \leqslant 2^{m-1} \left(\! \mathbb{E}{\Bigg[\!\Bigg(\sum_{k\geqslant 0}p_k\,B_2(\Gamma_{\!u_k})\!\Bigg)^m\Bigg]} + \mathbb{E}{\Bigg[\!\Bigg(\sum_{k\geqslant 0}\sum_{i=2}^{\hat{\xi}_k} q_{k,i} B_2(G_{k,i})\Bigg)^m\Bigg]} \right).\end{equation}

To bound the first term on the right-hand side, note that since $p_k^m \leqslant p_{k}$ and since $p_{k}$ is independent of $\Gamma_{\!u_k}$ ,