Increasing paths on N-ary trees Xinxin Chen LPMA, Universit´e Paris VI Summary. Consider a rooted N-ary tree. To every vertex of this tree, we attach an i.i.d. continuous random variable. A vertex is called accessible if along its ancestral line, the attached random variables are increasing. We keep accessible vertices and kill all the others. For any positive constant α, we de- scribe the asymptotic behaviors of the population at the αN-th generation as N goes to infinity. We also study the criticality of the survival probability at the (eN 3 logN)-th generation in this paper. − 2 Keywords. Increasing path; House of Cards. 1 Introduction 1.1 The model We consider an N-ary tree T(N), which is rooted at ∅, so that each vertex in T(N) has exactly N children. To every vertex σ T(N), we assign a continuous random variable, denoted by x . All σ ∈ these variables x , σ T(N) are i.i.d. Let σ denote the generation of σ, and σ (for 0 i σ ) σ i ∈ | | ≤ ≤ | | denote its ancestor at generation i. The ancestral line of σ is denoted by [[∅, σ]] := σ := ∅,σ , ,σ := σ , 0 1 σ { ··· | | } which is also the unique shortest path relating σ to the root ∅. A vertex σ is called accessible if along its ancestral line, the assigned random variables are increasing, i.e., (1.1) σ accessible ⇔ x∅ < xσ1 < ··· < xσ. 1 This model is called accessibility percolation by Nowak and Krug [6]. We also call [[∅, σ]] an accessible path if σ is accessible. Themodelcomesfromevolutionarybiology, inwhichbothmutationandselectioninvolve. As themainsourceofevolutionarynovelty, mutationsactonthegeneticconstitutionofanorganism. In our setting, each vertex represents one gene type, or genotype. A certain genotype may reproduce several new genotypes through mutations. The mechanism of successive mutations hence gives the structure of trees if we also assume that each mutation gives rise to a new genotype. Selection involves so that organisms better adapted to their respective surroundings are favored to survive. We suppose that each genotype (vertex) has an associated fitness value, which is represented by the assigned random variable. In the strong-selection/weak mutation regime, we assume that only mutations which give rise to a larger fitness value survive. In this way, the survival mutational pathways are noted by the accessible vertices. In this paper, we use ‘House of Cards’ model (see [5]), in which all fitness values are i.i.d. As is explained in [3], it serves as a null model. A variation of our model by replacing N-ary trees with N-dimensional hypercube has been considered in [2] and [4]. More models are introduced in [1] and [3] to explain evolution via mutation and selection. 1.2 Main results For any k 1, let := σ T(N) : σ = k,σ is accessible . We define N,k ≥ A { ∈ | | } (1.2) Z := 1 = # , k 1. N,k (σ∈AN,k) AN,k ∀ ≥ σ=k |X| Since we are only concerned with the order of the random variables, under the assumption of continuity of their law, changing the precise distribution will not influence the results. With- out loss of generality, we assume throughout the paper that the assigned random variables are distributed uniformly in [0,1], i.e., σ T(N), x has the uniform distribution in [0,1], which is σ ∀ ∈ denoted by U[0,1]. For any x [0,1], we introduce the following probability measure: ∈ (1.3) Px( ) := P( x∅ = x). · ·| AnaturequestionisaboutthesurvivalprobabilityP (Z 1). NotethatforanyN, k 1, x N,k ≥ ≥ Z = 1 = 1 . We observe that N,k |σ|=k (σ∈AN,k) |σ|=k (x∅<xσ1<···<xσ) P P Nk (1.4) E ZN,k = NkP(x∅ < xσ1 < ··· < xσ) = (k +1)!, h i 2 since x∅,xσ1,xσ2··· ,xσ are i.i.d. and distributed uniformly in [0,1]. Immediately, (1 x)k (1.5) E Z = NkP (x < x < < x 1) = Nk − , x [0,1]. x N,k x σ1 ··· σ ≤ k! ∀ ∈ h i Stirling’s approximation says that k! (1.6) 2 < < 3, k 1. √k(k/e)k ∀ ≥ It follows that 1 eN(1 x) k 1 eN(1 x) k (1.7) − E Z − . x N,k 3√k k ≤ ≤ 2√k k (cid:16) (cid:17) h i (cid:16) (cid:17) It is thus reasonable to take k = αN with α > 0. ⌊ ⌋ For convenience, we write αN to represent the integer αN throughout this paper. We are ⌊ ⌋ interested in the asymptotic behaviors of Z as N . N,αN → ∞ Nowak and Krug [6] showed that liminf P [Z 1] > 0 for 0 < α < 1 and that N 0 N,αN →∞ ≥ lim P [Z 1] = 0 for α e. This transition of phases implies the existence of a critical N 0 N,αN →∞ ≥ ≥ value of α. Roberts and Zhao [7] proved that the critical value is α = e, by considering some c typical increasing paths. In fact, we have 1 if α < e; (1.8) lim P Z 1 = N 0 N,αN ≥ 0 if α e. →∞ (cid:26) ≥ (cid:16) (cid:17) This result tells us that, for N large, roughly speaking, the population of accessible vertices survives until the eN-th generation and then dies out. Let us describe the asymptotic behaviors of the population more precisely by the following theorems. Theorem 1.1. Let θ(α) := α(1 logα) for α > 0. − (i) When α (0,e), the following convergence holds P almost surely, 0 ∈ − Z N,αN (1.9) lim = θ(α) > 0. N N →∞ (ii) When α = e, we have (1.10) P0 ZN,αN 1 = N−3/2+oN(1) as N , ≥ → ∞ (cid:16) (cid:17) where o (1) is a sequence of real numbers which goes to zero as N . N N 1 { } ≥ → ∞ 3 (iii) When α > e, we have logP Z 1 0 N,αN ≥ (1.11) lim = θ(α) < 0. N (cid:16) N (cid:17) →∞ Remark 1.2. For α < e, the accessible population Z is exponentially large. Its second order N,αN is not given here, but we present some arguments in Appendix B. When α = e, the explicit order of the survival probability is still unknown. It is clear that the system becomes extinct before the generation eN. In the next theorem, we see that the real critical generation is eN 3 logN. − 2 Theorem 1.3. Let k = eN βlogN. Then we have − 1 if β > 3/2; (1.12) lim P Z 1 = N 0 N,k ≥ 0 if β < 3/2. →∞ (cid:26) (cid:16) (cid:17) At the critical generation k = eN 3 logN, the survival probability is not clear at this − 2 moment. We state the following proposition, which only gives a lower bound. Proposition 1.4. For any ε > 0 and n sufficiently large, we have (1.13) P Z 1 N ε. 0 N,eN−32logN ≥ ≥ − (cid:16) (cid:17) It is possible to replace the N-ary tree by the Galton-Watson tree whose offspring is Poisson with parameter N, in which case all these results still hold. The rest of the paper is organized as follows. In Section 2, we state some basic results of the accessible population and the increasing paths. In Section 3 we prove Theorem 1.1. Finally, in Section 4, we show the criticality at eN 3 logN, by proving Theorem 1.3 and 1.4. − 2 Throughout the paper, we use the letter c with subscript to denote a finite and positive constant. 2 Basic ideas of the increasing paths 2.1 The generating function of Z N,k AsZ isaninteger-valuedr.w.,weconsideritsgenerationfunctionE sZN,k inthissubsection. N,k x Generally, for any 0 a < b 1, we define Z (a,b) as follows: (cid:16) (cid:17) N,k ≤ ≤ (2.1) Z (a,b) := 1 , k 1. N,k (a<xσ1<···<xσk≤b) ∀ ≥ σ=k |X| 4 For convenience, we write Z (b) for Z (0,b) and set Z (b) 1. One sees that Z (b a) N,k N,k N,0 N,k ≡ − (N) and Z (a,b) have the same law. Let f (s,b) be the generating function of Z (b), i.e., N,k k N,k (2.2) f(N)(s,b) := E sZN,k(b) , s [0,1]. k ∀ ∈ h i For k = 1, Z (b) is a binomial variable with parameter (N,b). So f(N)(s,b) = [1 b+sb]N. N,1 1 − For any k 1, one observes that ≥ (2.3) Z (b) = 1 1 1 . N,k+1 (xσ<b) (ω1=σ) (xσ<xω2<···<xω≤b) σ=1 ω=k+1 |X| | X| For all vertices σ of the first generation, the variables 1 1 1 are (xσ<b) |ω|=k+1 (ω1=σ) (xσ<xω2<···<xω≤b) i.i.d., and given x = y < b , 1 1 is distributed as Z (y,b). It { σ } |ω|=k+1 (ω1=σ) (xσ<xω2<···<Pxω≤b) N,k follows that for any k 1 and any b [0,1], P ≥ ∈ b N f(N)(s,b) = 1 b+ dyE sZN,k(y,b) k+1 − Z0 h (cid:16) (cid:17)i b N (2.4) = 1 b+ f(N)(s,b y)dy − k − Z0 h i b N (N) = 1 b+ f (s,y)dy . − k Z0 h i For brevity, we denote the generating function of Z under P by f(N)(s) instead of f(N)(s,1). N,k 0 k k Immediately, 1 N (N) (N) (2.5) f (s) = f (s,y)dy , k 1. k+1 k ∀ ≥ Z0 h i This gives that 1 N (2.6) P Z 1 = 1 f(N)(0) = 1 f(N)(0,y)dy , k 2. 0 N,k ≥ − k − k 1 ∀ ≥ Z0 − (cid:16) (cid:17) h i To study the law of Z , it suffices to study (2.4). However, it is quite difficult to investigate N,k (N) analytically the sequence f , k 1, from the recursive relation (2.4). We thus turn to study k ≥ the accessible vertices via their paths. 2.2 Typical accessible paths To study an increasing path, we let U ;j 1 be a sequence of i.i.d. U[0,1] random variables. j { ≥ } Observe that for any 1 j k, ≤ ≤ j (2.7) E U U U U = . j 1 2 k ≤ ≤ ··· ≤ k +1 (cid:16) (cid:12) (cid:17) (cid:12) (cid:12) 5 This leads us to comparing an increasing path U U U with the line j ;1 j { 1 ≤ 2 ≤ ··· ≤ k} {k+1 ≤ ≤ k . For example, in Lemma 2 of [7], the authors showed that } j 1 P U U U ;U , 1 j k = . 1 2 k j ≤ ≤ ··· ≤ ≥ k +1 ∀ ≤ ≤ (k +1)! (cid:16) (cid:17) In what follows, we generalize their ideas and state the two lemmas, which estimate the probabilities of some typical accessible paths. Lemma 2.1. (1) For any 1 k J 1, ≤ ≤ − j J k (2.8) φ(k,J) := P U U ;U , 1 j k = − . 1 k j ≤ ··· ≤ ≥ J ∀ ≤ ≤ k!J (cid:18) (cid:19) (2) For any ε [0,1) and 1 k J, ∈ ≤ ≤ j 1 ψ(k,J,ε) :=P U U ;U ε+(1 ε) − , 1 j k 1 k j ≤ ··· ≤ ≥ − J ∀ ≤ ≤ (2.9) (cid:18) (cid:19) (1+1/J)k(J +1 k) = − (1 ε)k. k!(J +1) − Proof. According to the assumption, we compute φ(k,J) directly. 1 uk u2 φ(k,J) = du du 1 k ··· ··· Zk/J Z(k 1)/J Z1/J − 1 uk uj+1 uj−1 1 uj−2 j j = du du j k ··· (j 1)! − J (j 2)! ··· Zk/J Z(k−1)/J Zj/J (cid:16) − − (cid:17) J k = − , k!J giving (2.8). We now compute ψ by using φ. Rewrite ψ(k,J,ε) as follows: 1 u2 ψ(k,J,ε) = du du . 1 k ··· ··· Zε+(1−ε)k−J1 Zε Take u = ε+(1 ε)v for all 1 j k. By a change of variables, j j − ≤ ≤ 1 v2 (2.10) ψ(k,J,ε) = (1 ε)kdv dv = (1 ε)kψ(k,J,0). 1 k ··· − ··· − Z(k 1)/J Z0 − In particular, when ε = 1 , we have J+1 1 1 ψ(k,J, ) = ψ(k,J,0)(1 )k. J +1 − J +1 6 On the other hand, when ε = 1 , ε+(1 ε)j 1 = j for any 1 j k. Hence, − J+1 − J J+1 ≤ ≤ 1 J +1 k ψ(k,J, ) = φ(k,J +1) = − . J +1 k!(J +1) It follows that ψ(k,J,0) = ψ(k,J, J+11)(1− J+11)−k = (1+1/kJ!()Jk+(J1+)1−k). By (2.10), we then obtain that (1+1/J)k(J +1 k) (2.11) ψ(k,J,ε) = (1 ε)kψ(k,J,0) = − (1 ε)k, − k!(J +1) − as desired. Following the assumption of Lemma 2.1, we define for any 0 L < K, ≤ (j L) + (2.12) A (K) := U < < U ;U − ; 1 j K . L 1 K j ··· ≥ K +1 ∀ ≤ ≤ (cid:26) (cid:27) Obviously, P[A (K)] = φ(K,K +1) = 1 by (2.8). 0 (K+1)! Lemma 2.2. There exists a positive constant c > 0 such that for any 1 L < K, 0 ≤ ec0√L eK (2.13) P A (K) . L ≤ K3/2 (K +1)K h i Proof. Clearly, P[A (K)] = ψ(K,K,0) = (1+1/K)K by (2.9). By (1.6), 1 (K+1)! e2√L eK (2.14) P A (K) , for L = 1. L ≤ K3/2(K +1)K h i The fact A (K) A (K) A (K) leads to 1 2 L ⊂ ⊂ ··· ⊂ L 1 − (2.15) P[A (K)] = P[A (K) A (K)]+P[A (K)], 2 L < K. L i+1 i 1 \ ≤ i=1 X Let us estimate P[A (K) A (K)]. Observe that i+1 i \ K (2.16) P[A (K) A (K)] = P[C (K)], i+1 i i,k \ k=i+1 X where U < < U ;U j i , i+1 j k 1; (2.17) C (K) := 1 ··· K j ≥ K−+1 ∀ ≤ ≤ − . i,k U < k i ;U j i 1, k +1 j K (cid:26) k K−+1 j ≥ K−+−1 ∀ ≤ ≤ (cid:27) 7 It follows from the independence of U ’s that P[C (K)] = p q where j i,k i,k i,k k i j i p := P U < < U < − ;U − , i+1 j k 1 ; i,k 1 k j ··· K +1 ≥ K +1 ∀ ≤ ≤ − (cid:18) (cid:19) k i j i 1 q := P − U < < U ;U − − , k +1 j K . i,k k+1 K j K +1 ≤ ··· ≥ K +1 ∀ ≤ ≤ (cid:18) (cid:19) Then (2.16) becomes that K (2.18) P[A (K) A (K)] = p q . i+1 i i,k i,k \ k=i+1 X We first compute q : i,k j +k i 1 q = P U < < U ;U − − , 1 j K k i,k 1 K k j ··· − ≥ K +1 ∀ ≤ ≤ − (cid:18) (cid:19) k i = ψ(K k,K k +i+1, − ). − − K +1 By (2.9), we obtain that K +2+i k K k i+2 (2.19) q = − − . i,k K +1 (K k)!(K k +i+2) (cid:16) (cid:17) − − It remains to estimate p . One sees that i,k k i k j i p = − P U < < U ;U − , i+1 j k 1 i,k 1 k j K +1 ··· ≥ k i ∀ ≤ ≤ − (cid:16) (cid:17) (cid:18) − (cid:19) k i k 1 (2.20) − P(D ), i,k 1 ≤ K +1 k i − (cid:16) (cid:17) − where j i (2.21) D := U < < U ,U − , i+1 j k , k i 1. i,k 1 k j ··· ≥ k i+1 ∀ ≤ ≤ ≥ ≥ n − o Let us admit for the moment the following lemma, whose proof will be given later. Lemma 2.3. For k i 1, there exists a constant c > 0 such that 1 ≥ ≥ ek iec1√i 1+2 − − (2.22) u := P D . i,k i,k ≤ (k +1 i)kk3/2 (cid:16) (cid:17) − Lemma 2.3 implies that k i k 1 p − u i,k i,k 1 ≤ K +1 k i − (cid:16) (cid:17) − e ke i 1ec1√i 1+2 −− − (2.23) . ≤ K +1 (k 1)3/2 (cid:16) (cid:17) − 8 Let us go back to (2.18). In view of (2.19) and (2.23), we see that K (2.24) P[A (K) A (K)] = p q i+1 i i,k i,k \ k=i+1 X K K +2+i k K k i+2 e ke i 1ec1√i 1+2 − − −− − . ≤ K +1 (K k)!(K k +i+2) K +1 (k 1)3/2 kX=i+1(cid:16) (cid:17) − − (cid:16) (cid:17) − Applying Stirling’s formula (1.6) to (K k)! yields that − (i+2)ec1√i−1+2eK K−1 e P[A (K) A (K)] i+1 \ i ≤ (K +1)K 2k3/2(K +i+1 k)3/2 k=i − X √iec1√i 1+2 eK − c . ≤ 2 (K +1)3/2 (K +1)K We then deduce from (2.15) that for L 2, ≥ L−1 L3/2ec1√L−1+2 eK (2.25) P[A (K)] = P[A (K) A (K)]+P[A (K)] c , L i+1 \ i 1 ≤ 3 K3/2 (K +1)K i=1 X which is sufficient to conclude Lemma 2.2. We now present the proof of Lemma 2.3. Proof of Lemma 2.3. Recall that D = U < < U ,U j i , i + 1 j k . Since i,k 1 ··· k j ≥ k −i+1 ∀ ≤ ≤ − D U < < U , we have for any kn i, o i,k 1 k ⊂ { ··· } ≥ 1 (2.26) u = P D P U < < U = . i,k i,k 1 k ≤ ··· k! (cid:16) (cid:17) (cid:16) (cid:17) By Stirling’s formula (1.6), we get that ek ek i 1 kk ek+1 i k − u = 1 − , i,k ≤ 2kk√k (k +1 i)kk3/2 − k 2 ≤ (k +1 i)kk3/2 2 − (cid:16) (cid:17) − as 1 z e z for any z 0. Take c := max 40,sup 1+logi < . Then when k 2i, we − ≤ − ≥ 1 { i≥2 √i−1 } ∞ ≤ deduce that ek i ek iec1√i 1+2 (2.27) u − elogi+1 − − . i,k ≤ (k +1 i)kk3/2 ≤ (k +1 i)kk3/2 − − It remain to prove the inequality (2.22) when k/2 i 1. Let γ(i) := ec1√i 1+2. According − ≥ ≥ to Lemma 2.1, we have (1+ 1)k ek+1 ek 1γ(1) (2.28) u = ψ(k,k,0) = k − , k 1, 1,k (k +1)! ≤ 2kk+3/2 ≤ (k +1 1)kk3/2 ∀ ≥ − 9 giving (2.22) in case i = 1. We prove (2.22) by induction on i. Assume (2.22) for some i 1 (and all k i). We need ≥ ≥ to bound P(D ) for k 2(i+1). i+1,k ≥ Since D D D , we have: 1,k 2,k k 1,k ⊂ ⊂ ··· − (2.29) u u = P D D i+1,k i,k i+1,k i,k − \ k i (cid:16) (cid:17) − 1 j 1 j = P U < < U ,U , 1 ℓ < j; − U < ; 1 k i+ℓ i+j ··· ≥ k i+1 ∀ ≤ k i ≤ k i+1 j=1 (cid:18) − − − X j j +ℓ 1 < − U , 1 ℓ k j i . i+j+ℓ k i+1 k i ≤ ∀ ≤ ≤ − − − − (cid:19) By the independence of the Ui’s, we have ui+1,k −ui,k = kj=−1i ri,j,ksi,j,k where P ℓ j 1 j r : = P U < < U ,U , 1 ℓ < j; − U < i,j,k 1 i+j i+ℓ i+j ··· ≥ k i+1 ∀ ≤ k i ≤ k i+1 (cid:18) − − − (cid:19) j +ℓ 1 s : = P U < < U ; − U , 1 ℓ k j i . i,j,k i+j+1 k i+j+ℓ ··· k i ≤ ∀ ≤ ≤ − − (cid:18) − (cid:19) Once again by (2.9), k i j j k i j +1 −− 1 (2.30) s = ψ(k i j,k i j, ) = − − . i,j,k − − − − k i k i (k i j +1)! − (cid:18) − (cid:19) − − On the other hand, j ℓ j j 1 r P U U ,U , 1 ℓ < j − i,j,k 1 i+j 1 i+ℓ ≤ ≤ ··· ≤ − ≤ k i+1 ≥ k i+1 ∀ ≤ × k i+1 − k i (cid:18) − − (cid:19) (cid:20) − − (cid:21) i+j 1 j − ℓ k i j +1 = P U U ,U , 1 ℓ j 1 − − 1 i+j 1 i+ℓ k i+1 ≤ ··· ≤ − ≥ j ∀ ≤ ≤ − (k i)(k i+1) (cid:18) − (cid:19) (cid:18) (cid:19) − − i+j 1 j − k i j +1 = − − u . i,i+j 1 k i+1 (k i)(k i+1) − (cid:18) − (cid:19) − − This implies that k i − (2.31) u u = r s i+1,k i,k i,j,k i,j,k − j=1 X k i k i j i+j 1 − k i j +1 −− 1 j − k i j +1 − − − − u . i,i+j 1 ≤ k i (k i j +1)! k i+1 (k i)(k i+1) − j=1 (cid:18) − (cid:19) − − (cid:18) − (cid:19) − − X 10