Accessibility percolation on N-ary trees

1.   Introduction

For $N \in \mathbb{N}$, let $\mathbb{T}^{(N)}$ be a rooted $N$-ary tree, in which each vertex has exactly $N$ children. The root of $\mathbb{T}^{(N)}$ is denoted by $o$. Each vertex $\sigma \in \mathbb{T}^{(N)}$ is assigned a continuous random variable $X_{\sigma}$, called its fitness. The fintness values $\{X_{\sigma}, \sigma \in \mathbb{T}^{(N)}\}$ are independent and identically distributed (i.i.d.) random variables. Let $|\sigma|$ denote the graph distance from the root $o$ to $\sigma$. For any $\sigma \in \mathbb{T}^{(N)}$ with $|\sigma|=k \in \mathbb{N}$, there is a unique path $P$ from $o$ to $\sigma$:

We say that $\sigma$ is accessible and the path $P$ is increasing if the assigned random variables are increasing along the path $P$, i.e.,

This model is called accessibility percolation by Nowak and Krug^[1].

The accessibility percolation model is inspired by evolutionary biology. Each vertex represents one genotype that has an associated fitness value. A particular genotype gives rise to $N$ new genotypes through mutations, which either replace the original wild genotype or disappear. In the “strong selection, weak mutation” (SSWM) regime, only mutations which reproduce a fitter genotype can replace the wild genotype and survive. Thus, a survival mutation path is one with increasing fitness values. In this paper, we use the House of Cards (HoC) model (see, for instance, Refs. [2, 3]), in which all fitness values are independent and identically continuously distributed.

The accessibility percolation on $N$-ary tree $\mathbb{T}^{(N)}$ has been studied by many scholars, and most of them concentrated on limit properties of the number of accessible vertices with level $k\in \mathbb{N}$, which can be written as

where we sum over all vertices $\sigma$ with $|\sigma|=k$ in the $N$-ary tree.

Since we only care about whether the fitness values along a path are in increasing order, as long as the random variables are continuous, changing the precise distribution will not influence the results. Without loss of generality, we assume throughout this work that all the random variables $\{X_{\sigma}: \sigma\in \mathbb{T}^{(N)}\}$ are independent and uniformly distributed on [0, 1]. For any $x \in [0,1]$, we introduce the probability measure under the condition that the fitness value of the root $X_o=x$ is given, i.e.,

and denote by $\mathbb{E}_x$ the expectation with respect to $\mathbb{P}_x$.

Nowak and Krug^[1], Roberts and Zhao^[4], Chen^[5], and Duque et al.^[6] studied the probability $\mathbb{P}_0(Z_{N,k}\ge 1)$. Roberts and Zhao^[4] proved that

This implies that there is a phase transition at $\alpha={\rm e}$. Chen^[5] extended it and obtained that

He also obtained the asymptotic behaviors of $Z_{N,\alpha N}$ as $N \to \infty$. Assume that $0<\alpha <1$ and $x>0$. Then, under $\mathbb{P}_{1-\alpha+x/N}$,

where $m_{N,\alpha}=(\alpha N)^{\alpha N}/(\alpha N)!$ and $Z$ is an exponential variable with mean 1.

The numbers of increasing paths on other graphs have also been widely studied. Coletti et al.^[7] considered infinite spherically symmetric trees, Hegarty and Martinsson^[8], Berestycki et al.^{[9, 10]}, and Li^[11] studied the $N$-dimensional binary hypercube $\{0,1\}^N$. We refer to Krug^[12] and reference therein for more related models and results. Hu et al.^[13] studied the number of accessible vertices on random rooted labelled trees.

The remainder of this paper is organized as follows. In Section 2, main results are stated. The proofs of Theorems 2.1–2.3 are provided in Section 3. Finally, we present the proof of Theorem 2.4 in Section 4.

2.   Main results

We first consider the number of accessible vertices in the first $k$ levels, i.e.,

where we sum over all nodes $\sigma$ with $|\sigma|\leqslant k$ in the $N$-ary tree. Assume that $x>0,\; \beta>0$ and $0 < \alpha\leqslant 1$ are real numbers and let $Z$ be an exponential variable with mean 1.

Theorem 2.1. Under $\mathbb{P}_{1-\alpha+x/N}$, we have that as $N\rightarrow \infty$,

(a) if $\beta<\alpha$, then

(b) if $\beta=\alpha$, then

(c) if $\beta>\alpha$, then

We can also study the total number of accessible vertices in the $N$-ary tree $\mathbb{T}^{(N)}$, which can be written as

where we sum over all nodes $\sigma$ in the $N$-ary tree. For any $x\in [0,1]$, by noting that $\mathbb{E}_x (C_N) ={\rm e}^{-N(1-x)} < \infty$ (see Lemma 3.2), we have $C_N < \infty\; {\rm a.s.} \; \mathbb{P}_x$. Furthermore, we obtain the joint limiting distribution of $(C_{N}, C_{N,\,\alpha N+t \sqrt{\alpha N}})$ as $N \to \infty$.

Theorem 2.2. For any $0 < \alpha\leqslant 1, \; x > 0$ and $t\in \mathbb{R}$, we have that under $\mathbb{P}_{1-\alpha+x/N}$,

where $\varPhi(\cdot)$ is the cumulative distribution function of the standard normal distribution.

From Theorems 2.1 and 2.2, $C_N$ and $C_{N,\, \beta N}$ (with $\beta>\alpha$) have the same limit distribution. It is natural to imagine that the number of accessible vertices at distances greater than $\beta N$ from the root $o$ is relatively small. In fact, the following Theorem 2.3 shows that under $\mathbb{P}_{1-\alpha+x/N}$, most of the accessible vertices concentrate on the levels from $\alpha N-b_N \sqrt{N}$ to $\alpha N+b_N \sqrt{N}$ for any sequence $\{b_N\}$ with $b_N\rightarrow \infty$.

Theorem 2.3. Let $\{b_N, N \geqslant 1\}$ be a sequence of real numbers with $b_N\rightarrow \infty$ as $N\rightarrow \infty$. Then under $\mathbb{P}_{1-\alpha+x/N}$,

Theorems 2.1–2.3 describe the distribution of the number of accessible vertices from the root $o$. Another interesting quantity is the maximum level of accessible vertices (i.e., the longest increasing path from $o$) which is defined as

Noting that $\{M_n\geqslant k\}=\{Z_{N,k}\geqslant 1\}$, it follows from Eq. (2) that (under $\mathbb{P}_0$)

In the related existing results on $N$-ary trees, it is generally assumed that $N \rightarrow \infty$. For fixed $N$, it is clear that $M_N\leqslant C_N < \infty$ a.s.. In this case, we can consider the longest increasing path down the $N$-ary tree. We say that the path $P=\sigma_0\sigma_1\cdots \sigma_k$ with length $l(P)=k$ is a path down the tree if $P$ starts at any vertex and descends into children until it stops at some node, i.e., $|\sigma_0|=|\sigma_1|-1=\cdots=|\sigma_k|-k$, and $P$ is increasing if $X_{\sigma_0}<X_{\sigma_1}<\cdots<X_{\sigma_k}$. Let $\mathbb{T}^{(N)}_n$ be the subgraph of $\mathbb{T}^{(N)}$ induced by the set of vertices with levels not exceeding $n$. Define

Theorem 2.4. Let $N\geqslant 2$ be a fixed positive integer. Then

In the following Sections 3 and 4, we prove our main results stated above.

3.   Proofs of Theorems 2.1–2.3

Before the proofs, we need the following preliminary lemmas.

Lemma 3.1. Let $\sigma, \sigma_1,\sigma_2$ be vertices on an $N$-ary tree. If $|\sigma|=k$, then, for any $0\leqslant x\leqslant 1$,

Furthermore, let $\sigma_1\wedge \sigma_2$ denote the latest common ancestor of $\sigma_1$ and $\sigma_2$. If $|\sigma_1|=m+i, |\sigma_2|=m+j$ and $|\sigma_1 \wedge \sigma_2|=m$ for some $m\geqslant 0$ and $i,j\geqslant 0$, then, for any $0\leqslant x\leqslant 1$,

Proof. We assume that $X_1, X_2, \cdots$ are i.i.d. random variables and distributed uniformly on $[0,1]$. By symmetry, we have

This, together with $\mathbb{P}(x\leqslant X_1 ,\cdots, X_k\leqslant 1)=(1-x)^k$, yields that

Thus Eq. (6) holds. The proof of Eq. (7) is similar and we omit the details here.

We next prove Eq. (8). If $|\sigma_1|=m+i,\; |\sigma_2|=m+j$ and $|\sigma_1 \wedge \sigma_2|=m$ for some $m\geqslant 0$ and $i,j\ge 0$, then

where we have used the fact that

and $B(\cdot, \cdot)$ is the beta function. This proves Eq. (8), and also completes the proof of Lemma 3.1.

Lemma 3.2. For any $x\in [0,1]$ and $N, k\in \mathbb{N}$, we have

Furthermore, we have $\mathbb{E}_x (C_N)={\rm e}^{N(1-x)}$ and $\rm{Var}_x(C_{N})\leqslant {\rm e}^{2N(1-x)}$.

Proof. Since $C_{N,k}=\sum_{|\sigma|\leqslant k} \mathbb{I}(\sigma \rm{ is accessible})$ and $\#\{\sigma: |\sigma|= k\}= N^k$, it follows from Eq. (6) that

Similarly,

It is clear that, for any $m,i,j\in \mathbb{N}$,

This, together with Eq. (8), implies that

By noting that, for any $n,j\in \mathbb{N}$,

it follows from (10) that

where we have used

Therefore $\rm{Var}_x(C_{N,k})\leqslant (\mathbb{E}_x C_{N,k+1})^2$.

Since $C_{N,\,k}, k=1,2,\cdots,$ are nondecreasing with respect to $k$ and $\lim_{k\rightarrow \infty} C_{N,k}=C_N$, we obtain that $\rm{Var}_x(C_{N})\leqslant (\mathbb{E}_x C_{N})^2\leqslant {\rm e}^{2N(1-x)}$ by the monotone convergence theorem. The proof of Lemma 3.2 is completed.

Remark 3.1. For $C_N$, we can obtain the explicit expression of $\rm{Var}_x (C_N)$. By using arguments similar to those in (10) and (11), we have

Thus

Lemma 3.3. For any fixed $0 < \alpha\leqslant 1, \; \beta > 0,\, x>0$ and $k\in \mathbb{Z}$, we have that

Proof. For any $N\in \mathbb{N}$, we let $X_{N1}, X_{N2},\cdots, X_{NN}$ denote a sequence of i.i.d. Poisson random variables with mean $\alpha-x/N$, then $X_{N1}+\cdots+X_{NN}$ is also Poisson-distributed (with mean $\alpha N-x$), i.e.,

Thus, by Lemma 3.2,

By using the following basic results:

we have that, for any $t\in \mathbb{R}$,

Thus

and then

This, together with (12), proves Lemma 3.3.

For any $k\geqslant 1$, we let ${\cal{F}}_k$ denote the available information of the first $k$ generation on the $N$-ary tree, i.e., ${\cal{F}}_k=\sigma \{X_{\sigma}: |\sigma|\leqslant k\}$.

Lemma 3.4. For any $0 < \alpha\leqslant 1, \; \beta > 0,\; x>0$ and $\varepsilon>0$, we have

Proof. Let $\sigma$ be a vertex on the $N$-ary tree. On the subtree rooted at $\sigma$, we let $C_{N,\, k}(\sigma)$ be the number of accessible vertices in the first $k$ generations. Then, for any $k<\beta N$,

By noting that $\{(C_{N,\, \beta N-k}(\sigma), X_{\sigma}), |\sigma|=k\}$ are i.i.d. random vectors and have the same distribution as $(C_{N,\, \beta N-k}, X_{o})$, we have

and

By applying Lemma 3.2, we have that, for any $0\leqslant y\leqslant 1$,

Thus,

By using Chebyshev’s inequality, we have

The proof of Lemma 3.4 is completed.

Lemma 3.5. For any $0 < \alpha\leqslant 1, \; \beta > 0, \; x>0$ and $\lambda>0$, we have

Proof. By noting that $C_{N,k}$ is nondecreasing with respect to $k$ and applying Lemma 3.3, we have that, for any fixed $k\in \mathbb{Z}^+$,

Thus, to prove Lemma 3.5, it suffices to show that

where

Write $\theta_k(\lambda, x, N):=\mathbb{E}_{x} \Big(\exp\{-\lambda {\rm e}^{-\alpha N}\varTheta_k\}\Big).$ Since $\varTheta_0= \mathbb{E}_{X_0} (C_{N,\, \beta N})$, we have

Let $v_1, \dots, v_N$ be all the children of the root $o$, and define $\varTheta_k(v_i)$ in the subtree rooted at $v_i$ as in (15), i.e., $\varTheta_{k}(v_i):=\mathbb{E}(C_{N,\,\beta N+k}(v_i) |{\cal{F}}_{k+1})$, where $C_{N,\,\beta N+k}(v_i)$ is the number of accessible vertices in the first $\beta N+k$ generations of the subtree rooted at $v_i$. Then $\{(\varTheta_k(v_i), X_{v_i}), i=1,\cdots,N\}$ are i.i.d. random vectors and have the same distribution as $(\varTheta_k, X_{o})$. By noting that

we have

For any $x,\lambda>0$, define

and

We will show that for any $k\geqslant 0$, $x>0$ and $\lambda >0,$

It follows from Eq. (16) and Lemma 3.3 that Eq. (18) holds true for $k=0$. Now suppose that (18) holds for $k\geqslant 0$. By a change of variable in Eq. (17), we have

Since $1-{\rm e}^{-z}\leqslant z$ holds for all $z\in \mathbb{R}$, by applying Lemma 3.2, we have

Thus, by the dominated convergence theorem, we obtain

and then $\lim_{N\rightarrow \infty}\theta_{k+1}(\lambda,1-\alpha+x/N,N) =Q_{k+1}(\lambda ,x)$ from Eq. (19). By induction, we conclude Eq. (18) for all $k\geqslant 0$.

If $\beta<\alpha$, it is clear that $Q_k(\lambda, x)\equiv 1$ for all $\lambda>0$ and $x>0$. If $\beta\geqslant \alpha$, then, following the same arguments in the proof of Theorem 1 in Ref. [9] or Proposition B.2 in Ref. [5], we have

Combining this with Eq.(18), we can prove Eq.(14). Thus the proof of Lemma 3.5 is completed.

After these preliminaries, we are now ready to prove Theorems 2.1 and 2.2.

Proof of Theorem 2.1. Here we only prove the case $\beta>\alpha$ since the others are similar. By noting that, for any $\varepsilon>0$,

By noting that the generating function of ${\rm e}^{-x}Z$ is $\mathbb{E}(\exp\{-\lambda {\rm e}^{-x} Z\})=(1+\lambda {\rm e}^{-x})^{-1}$, it follows from Lemma 3.5 that

Thus, by using (20) and Lemma 3.4, we obtain

By the arbitrary of $\varepsilon>0$, we have

Similarly, we can obtain

and then

Thus

The proof of Theorem 2.1 is completed.

Proof of Theorem 2.2. For any $a,b\in\mathbb{R}$, a similar argument as in the proof of Theorem 2.1 shows that under $\mathbb{P}_{1-\alpha+x/N}$,

This implies (5) by the Cramér-Wold device.

Proof of Theorem 2.3. Note that for any $t\in \mathbb{R}$, $C_{N, \,\alpha N-b_N \sqrt{N}}\leqslant C_{N,\,\alpha N+t \sqrt{\alpha N}}$ holds for sufficiently large $N$. By using Theorem 2.2, we have that under $\mathbb{P}_{1-\alpha+x/N}$,

Similarly, for any $t\in \mathbb{R}$, $C_N\geqslant C_{N, \alpha N+b_N \sqrt{N}}\geqslant C_{N,\alpha N+t \sqrt{\alpha N}}$ holds for sufficiently large $N$. It follows from Theorem 2.2 that under $\mathbb{P}_{1-\alpha+x/N}$,

Then, under $\mathbb{P}_{1-\alpha+x/N}$,

Therefore, by applying (21), (22), Theorem 2.2 and Slutsky’s theorem, we obtain that under $\mathbb{P}_{1-\alpha+x/N}$,

The proof of Theorem 2.3 is completed.

4.   Proof of Theorem 2.4

In this proof, $N\geqslant 2$ is a fixed positive integer.

Let $\mathcal{P}_{n,\,k}$ be the set of paths down $\mathbb{T}^{(N)}_n$ with length $k$. Define $T_{n,\,k}$ to be the number of increasing paths in $\mathcal{P}_{n,\,k}$:

By Lemma 3.1, it is clear that

Next, we estimate $\rm{Var}(T_{n,\,k})$.

We say that two paths $P$ and $P'$ are vertex-disjoint if $V(P)\cap V(P')=\emptyset$, where $V(P)$ and $V(P')$ are the vertex sets of $P$ and $P'$, respectively. For any $P=x_0x_1\cdots x_k$, $\tilde{P}=\tilde{x}_0\tilde{x}_1\cdots\tilde{x}_k\in \mathcal{P}_{n,k}$ with $|x_0|\leqslant |\tilde{x}_0|$, if $P'$ and $P$ are not vertex-disjoint, then there exist integers $l,\, m$ such that $0\leqslant l \leqslant m \leqslant k$ and $x_i=\tilde{x}_{i-m+l}$ iff $m-l\leqslant i\leqslant m$. By Lemma 3.1, we have

Note that $\mathbb{I}\, (P \; \rm{is increasing})$ and $\mathbb{I}\, (\tilde{P} \; \rm{is increasing})$ are independent if $P$ and $\tilde{P}$ are vertex-disjoint. Thus,

where in the last equality we have used the equality

Since $(k+l+1)! \geqslant k!k^{l+1}$, we have

Hence,

For any sequence $k_n\rightarrow \infty$ with $k_n=o(n)$, it follows from (23) and Stirling’s formula that

For any $\varepsilon>0$, we take $k_n=(1+\varepsilon)n \log N/\log n$ and $\tilde{k}_n=(1-\varepsilon)n \log N/\log n$. Then, by applying Eq. (24), we have

and furthermore, by Chebyshev’s inequality,

Then, we obtain Theorem 2.4.

Acknowledgements

We thank the anonymous referees for the useful suggestions that greatly improved the presentation of this work. This work was supported by the National Natural Science Foundation of China (11671373).

Conflict of interest

The authors declare that they have no conflict of interest.