Central limit theorem for the Horton-Strahler bifurcation ratio of general branch order Ken Yamamoto Department of Physics and Earth Sciences, Faculty of Science, University of the Ryukyus, 1 Sembaru, Nishihara, Okinawa 903–0213, Japan Abstract TheHorton-Strahlerorderingmethod,originatinginhydrology,formulatesthehierarchicalstruc- ture of branching patterns using a quantity called the bifurcation ratio. The main result of this paperisthecentrallimittheoremforbifurcationratioofgeneralbranchorder. Thisisageneralized form of the central limit theorem for the lowest bifurcation ratio, which was previously proved. Someuseful relations are also derived in theproofs of the main theorems. 1. INTRODUCTION 7 1 Branchingobjectsarefoundverywidely[1],rangingfromnaturalpatternslikerivernetworks,plants,anddendritic 0 crystals, to conceptual expressions like binary search trees in computer science [2] and phylogenetic trees in taxon- 2 omy [3]. The topological structure of a branching pattern is modeled by a binary tree if a segment bifurcates (does n not trifurcate or more) at every branching point. a Let Ω denote the set of the different binary trees having n leaves. The number of leaves is called the magnitude n J in researchofbranchingpatterns. As knownwell[8], the number ofthe differentbinary trees ofmagnitude n is given 2 by 1 1 2n 1 (2n 2)! ] Ω = − = − , R | n| 2n 1 n n!(n 1)! − (cid:18) (cid:19) − P which iscalled the n 1st Catalan number. In Fig. 1, Ω for n = 2,3, and 4 are schematically shown. Introducing . n h − the uniform probability measure P on Ω (so that each binary tree is assigned equal probability 1/Ω ), we obtain n n n t | | a the probability space (Ωn,Pn) referred to as the random model [6]. The formation of real-world branching patterns m moreorlessinvolvesstochasticeffects,andtherandommodelisakindofmathematicalsimplificationofsuchrandom [ factors. Inhydrology,methodsformeasuringthehierarchicalstructureofarivernetworkhavebeenproposedbyHorton[4], 1 Strahler [5], Shreve [6], Tokunaga [7], and other researchers. Their methods define how to assign an integer number v (called the order) to each stream. Among all, Strahler’s method is currently the most popular because of its simple 3 computationrule. Strahler’smethodisarefinementofHorton’smethod,soitissometimescalledtheHorton-Strahler 1 2 ordering method. The Horton-Strahler method recursively defines the order of each node by the following rules. (i) 3 The leaf nodes are defined to have order one. (ii) A node whose children have different order r and r (r =r ) has 1 2 1 2 6 0 ordermax r ,r . (iii) Anodewhosetwochildrenhavethesameorderr hasorderr+1. We defineabranch oforder 1 2 1. r as a max{imal c}onnected path made by nodes of equal order r. (A branch here is called a stream in the analysis of 0 rivernetworks.) An exampleofStrahler’sorderingis showninFig.2. For abinary treeτ Ωn, we letSr,n(τ) denote ∈ 7 the number ofbranchesoforderr inτ. By the definitionof the order, S (τ)=n and0 S (τ) n/2r−1 (r 2). 1,n r,n 1 Note that S (τ) = 0 if n 2, because a node of order 2 is produced by the merge of≤two leave≤s. For the bi≥nary 2,n : 6 ≥ v tree τ( Ω6) in Fig. 2, S1,6(τ) =6, S2,6(τ)= 2, S3,6(τ) =1, and Sr,6(τ) =0 for r 4. Sr,n is a random variable on ∈ ≥ Xi (ΩFno,rPnan),yafnudncittsiosntofch:as0t,i1c,p2r,o.p..erty iRs,off(mSain(i)n)teirseastreinalt-vhaislusetdudrya.ndomvariable on Ω . According to Ref. [9], the r,n n r { }→ · a Ω Ω Ω 2 3 4 FIG. 1: Ω2,Ω3, and Ω4 contain one, two, and fivebinary trees, respectively. 2 3 branch of order 3 1 3 branch of branch of 2 2 order 2 order 2 2 1 1 1 1 1 FIG.2: Asmallexampleoforderingandbranches. Thenumberoneachnoderepresentstheorderofthenode. Thebranches of order 2 and 3 are shown by the dashed rectangles. This binary tree consists of six branches of order 1, two branches order 2, and onebranch of order 3. recursive relation between the averages of the rth and r 1st variables − n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m E[f(S )]= − − E[f(S )] (1) r,n r−1,m (2n 2)! (n 2m)!m!(m 1)! − m=1 − − X holds, where E[] denotes the average on the random model. The coefficient · n!(n 1)!(n 2)!2n−2m − − (2n 2)!(n 2m)!m!(m 1)! − − − represents the probability P (S =m). In particular, putting r=2 in Eq. (1), we have n 2,n n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m E[f(S )]= − − f(m). (2) 2,n (2n 2)! (n 2m)!m!(m 1)! − m=1 − − X Mathematical properties of S have been investigated thoroughly. For instance, the average and variance are 2,n respectively given by [10] n(n 1) n(n 1)(n 2)(n 3) E[S ]= − , Var[S ]= − − − . (3) 2,n 2(2n 3) 2,n 2(2n 3)2(2n 5) − − − Moreover,from Eq. (2), the moment generating function M (t) of S is given by 2,n 2,n n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m M (t):=E[exp(S t)]= − − emt, 2,n 2,n (2n 2)! (n 2m)!m!(m 1)! − m=1 − − X and this summation can be expressed using the Gauss hypergeometric function F [11]: 2n−2n!(n 1)! 2 n 3 n M (t)= − etF − , − ,2;et . (4) 2,n (2n 2)! 2 2 − (cid:18) (cid:19) TheratioS (τ)/S (τ)iscalledthebifurcation ratio oforderrorsimplytherthbifurcationratio. Hydrologists r+1,n r,n haveempiricallyconfirmedthatthe bifurcationratiosofanactualrivernetworkbecome almostconstantfordifferent orders,andthisrelationisreferredtoasHorton’s law of stream numbers. Bydefinition,thebifurcationratioisalways smaller than or equal to 1/2. When S (τ) = 0, we reasonably define S (τ)/S (τ) = 0. The random variable r,n r+1,n r,n S /S is also called the rthe bifurcation ratio. The lowest bifurcation ratio S /S = S /n is relatively r+1,n r,n 2,n 1,n 2,n easy to deal with, because it is similar to S . The central limit theorem for S /n has been shown by Wang and 2,n 2,n Waymire [12]: Theorem 1 (Central limit theorem for the lowest bifurcation ratio). On the random model, S 1 1 √n 2,n N 0, , n , n − 4 ⇒ 16 →∞ (cid:18) (cid:19) (cid:18) (cid:19) where “ ” denotes convergence in distribution, and N(µ,σ2) is the normal distribution with mean µ and variance σ2. ⇒ 3 Itisasimple andnaturalideathatweextendTheorem1togeneralorderr. ComparedwithS ,however,higher- 2,n order branches S for r 3 and the bifurcation ratio of order r 2 is difficult to handle and less studied. In this r,n ≥ ≥ paper, we generalize Theorem 1 in two ways (Theorems 2 and 3 in 2), and further generalize them (Theorem 4 in § 6). In 3–5, we give proofs of lemmas, which are necessary for the main theorems. In these proofs, Eq. (1) and its § § variant S n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m S r+1,n r,m E f = − − E f . (5) S (2n 2)! (n 2m)!m!(m 1)! S (cid:20) (cid:18) r,n (cid:19)(cid:21) − m=1 − − (cid:20) (cid:18) r−1,m(cid:19)(cid:21) X are very useful. 2. MAIN RESULTS The following two theorems are the main results of the present paper. Theorem 2 (Central limit theorem for the bifurcation ratio of general order). For any order r =1,2,3,..., the rth bifurcation ratio S /S satisfies r+1,n r,n S 1 √n r+1,n N 0,4r−3 , n , (6) S − 4 ⇒ →∞ (cid:18) r,n (cid:19) (cid:0) (cid:1) Theorem 3 (Central limit theorem for the number of branches of general order). For any order r = 1,2,3,..., the number S of r+1st branches satisfies r+1,n S 1 14r 1 √n r+1,n N 0, − , n , (7) n − 4r ⇒ 3 16r →∞ (cid:18) (cid:19) (cid:18) (cid:19) Remark. These two theorems are generalization of Theorem 1 to general order r; they are reduced to Theorem 1 by setting r =1. Theorem2 states the property ofthe bifurcationratio S /S , andTheorem3 states the property r+1,n r,n of the number of branches S . The limit variance 4r−3 in Theorem 2 becomes large as r increases, whereas the r+1,n limit variance in Theorem 3 becomes small as r increases. FromTheorem2,thefollowingproperty,whichcanberegardedasHorton’slawofstreamnumbers,iseasilyderived. Corollary 1 (Horton’slaw ofstreamnumbersfor the randommodel). For any order r =1,2,..., the rth bifurcation ratio S /S converges in probability to the common value 1/4: r+1,n r,n Sr+1,n p 1 , S −→ 4 r,n p where “ ” denotes convergence in probability. −→ Let us introduce the asymptotic equality, since this study mainly focuses on the asymptotic behavior (the limit n ) of S . r,n →∞ Definition 1. The average value E[f(S )] is asymptotically equivalent to g (n) if r,n r E[f(S )] r,n lim =1, n→∞ gr(n) and this is denoted by E[f(S )] g (n). r,n r ∼ For example, from Eq. (3), n(n 1) n E[S ]= − . 2,n 2(2n 3) ∼ 4 − Theorems 2 and 3 are easily proved by using the following Lemmas 1 and 2, respectively. 4 Lemma 1. For r =1,2,... and s=0,1,2,..., S 1 2s (2s 1)!! n −s S 1 2s+1 (2s+1)!! n −s−1 r+1,n r+1,n E − , E "(cid:18) Sr,n − 4(cid:19) #∼ 42s (cid:16)4r−1(cid:17) "(cid:18) Sr,n − 4(cid:19) #∼ 2·42s+1 (cid:16)4r−1(cid:17) Lemma 2. For r =1,2,... and s=0,1,2,..., n 2s (2s 1)!! 4r 1 s E S − − ns, r+1,n− 4r ∼ 42sr 3 (cid:20)(cid:16) n 2s(cid:17)+1(cid:21) (2s+1)!!(cid:18) 4r 1(cid:19) s 1 4r+1 1 4r−1 1 E S − − + − 4(2s+1) ns. r+1,n− 4r ∼ 2 4(2s+1)r 3 5 3 3 (cid:20)(cid:16) (cid:17) (cid:21) · (cid:18) (cid:19) (cid:18) (cid:19) The odd-power result has a more complicated form than the even-power one. Proof of Theorem 2. We let ϕr+1(z) denote the characteristic function of the left-hand side of Eq. (6), where the r,n subscript r and superscript r+1 respectively correspond to S in the denominator and S in the numerator in r,n r+1,n Eq. (6). By definition, ϕr+1(z) is calculated as r,n S 1 ϕr+1(z)=E exp iz√n r+1,n r,n S − 4 (cid:20) (cid:18) (cid:18) r,n (cid:19)(cid:19)(cid:21) ∞ (iz√n)k S 1 k r+1,n =E "k=0 k! (cid:18) Sr,n − 4(cid:19) # X ∞ (iz√n)k S 1 k r+1,n = E k=0 k! "(cid:18) Sr,n − 4(cid:19) # X ∞ (iz√n)2s S 1 2s ∞ (iz√n)2s+1 S 1 2s+1 r+1,n r+1,n = E + E , s=0 (2s)! "(cid:18) Sr,n − 4(cid:19) # s=0 (2s+1)! "(cid:18) Sr,n − 4(cid:19) # X X wherei=√ 1. Atthelastequality,wehavesplitthesumintoevenk (k =2s)andoddk (k =2s+1). ByLemma1, the terms of−the first sum (even k) are O(n0), whereas the terms of the second sum (odd k) are o(n0). Hence, the second sum can be neglected in the limit n , so that →∞ ∞ (iz√n)2s S 1 2s ϕr+1(z) E r+1,n r,n ∼ s=0 (2s)! "(cid:18) Sr,n − 4(cid:19) # X ∞ ( z2n)s(2s 1)!! n−s − − ∼ (2s)! 42s 4−(r−1)s s=0 X ∞ 4r−3z2 s 1 = − 2 s! s=0(cid:18) (cid:19) X 4r−3z2 =exp . − 2 (cid:18) (cid:19) Recall that the characteristic function of N(µ,σ2) is exp(iµz σ2z2/2). Since ϕr+1 converges pointwise to the − r,n characteristic function of N(0,4r−3), convergence in distribution in Theorem 2 is proved. (For the properties of a characteristic function, see Feller [13] for example.) Keep in mind that the neglect of the odd-power terms is a crucial point also in the other central limit theorems in this paper. Proof of Theorem 3. As with the above proof of Theorem 2, the characteristic function ϕr+1(z) of the left-hand side 1,n 5 of Eq. (7) is S 1 ϕr+1(z)=E exp iz√n r+1,n 1,n n − 4r (cid:20) (cid:18) (cid:18) (cid:19)(cid:19)(cid:21) ∞ (iz√n)k S 1 k r+1,n = E k=0 k! "(cid:18) n − 4r(cid:19) # X ∞ (iz√n)2s n 2s ∞ (iz√n)2s+1 n 2s+1 = E S + E S . (2s)!n2s r+1,n− 4r (2s+1)!n2s+1 r+1,n− 4r Xs=0 (cid:20)(cid:16) (cid:17) (cid:21) Xs=0 (cid:20)(cid:16) (cid:17) (cid:21) By Lemma 2, the second sum is neglected and the dominant terms are calculated to ∞ (iz√n)2s n 2s ϕr+1(z) E S 1,n ∼ (2s)!n2s r+1,n− 4r Xs=0 (cid:20)(cid:16) (cid:17) (cid:21) ∞ ( z2n)s(2s 1)!! 4r 1 s − − − ns ∼ (2s)!n2s 42rs 3 s=0 (cid:18) (cid:19) X ∞ z24r 1 s 1 = − − 2 3 16r s! s=0(cid:18) · (cid:19) X z24r 1 =exp − . − 2 3 16r (cid:18) · (cid:19) Therefore, the converges in distribution to N(0,(4r 1)/(3 16r)) is proved. − · We give the proofs of Lemmas 1 and 2 in the following three sections. 3. STARTING POINT OF LEMMAS 1 AND 2 WeshowLemmas1and2byinductiononr. Inthissection,thecaseofr =1inLemmas1and2isproved(Cor.3). Proposition 1. For a two-variable polynomial p(, ) of finite degree, · · n n(n 2) E[S p(S ,n)]= E[p(S ,n)] − E[p(S ,n)]. (8) 2,n 2,n 2,n 2,n−1 2 − 2(2n 3) − Here, E[S p(S ,n)] and E[p(S ,n)] are taken over Ω , whereas E[p(S ,n)] are over Ω . 2,n 2,n 2,n n 2,n−1 n−1 Proof. Because of the linearity of E[], it is sufficient to check the case p(S ,n)=Sk nl. The average is expressed · 2,n 2,n using the moment generating function M (t) in Eq. (4). 2,n dk+1 E S Sk nl =nlE Sk+1 =nl M (t) 2,n 2,n 2,n dtk+1 2,n (cid:12)t=0 (cid:2) (cid:3)=nl2n(cid:2)−2n!(n(cid:3) −1)! dk+1 etF 2(cid:12)(cid:12)(cid:12)−n,3−n,2;et (2n 2)! dtk+1 2 2 − (cid:18) (cid:19)(cid:12)t=0 =nl2n−2n!(n−1)! dk et F 2−n,3−n,2;et +(cid:12)(cid:12)(cid:12) dF 2−n,3−n,2;et . (2n 2)! dtk 2 2 dt 2 2 − (cid:20) (cid:18) (cid:19) (cid:18) (cid:19)(cid:21)(cid:12)t=0 (cid:12) Using the derivative of the Gauss hypergeometric function [14] (cid:12) (cid:12) d α F (α,β,γ;z)= [F (α+1,β,γ;z) F (α,β,γ;z)] dz z − and the symmetry F(α,β,γ;z)=F (β,α,γ;z), we have d 2 n 3 n n 2 2 n 3 n 3 n 4 n F − , − ,2;et = − F − , − ,2;et F − , − ,2;et , (9) dt 2 2 2 2 2 − 2 2 (cid:18) (cid:19) (cid:20) (cid:18) (cid:19) (cid:18) (cid:19)(cid:21) 6 thereby 2n−2n!(n 1)! dk n 2 n 3 n n 2 3 n 4 n E S Sk nl =nl − et F − , − ,2;et − F − , − ,2;et 2,n 2,n (2n 2)! dtk 2 2 2 − 2 2 2 − (cid:20) (cid:18) (cid:19) (cid:18) (cid:19)(cid:21) (cid:2) (cid:3) n 2n(n 1) n 2 =nl E Sk − − E Sk 2 2,n − (2n 2)(2n 3) 2 2,n−1 (cid:18) − − (cid:19) n (cid:2) (cid:3) n(n 2) (cid:2) (cid:3) = E Sk nl − E Sk nl . 2 2,n − 2(2n 3) 2,n−1 − (cid:2) (cid:3) (cid:2) (cid:3) Here we comment on the utility of Prop. 1. We can calculate the moments E Sk recursively using Eq. (8): 2,n (cid:2) (cid:3) n n(n 2) n(n 1) E[S ]=E[S 1]= E[1] − E[1]= − , 2,n 2,n · 2 − 2(2n 3) 2(2n 3) − − n n(n 1) n(n 1)(n2 n 4) E S2 =E[S S ]= E[S ] − E[S ]= − − − , 2,n 2,n 2,n 2 2,n − 2(2n 3) 2,n−1 4(2n 3)(2n 5) − − − (cid:2) (cid:3) n n(n 1) n(n 1)(n4 2n3 15n2+32n+8) E S3 =E S S2 = E S2 − E S2 = − − − , 2,n 2,n 2,n 2 2,n − 2(2n 3) 2,n−1 8(2n 3)(2n 5)(2n 7) − − − − (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) and so on. The first and secondmoments were individually calculated [10] (see Eq.(3)). Note, however,that Prop.1 provides a systematic calculation method of the kth moment of S in a bottom-up way. Furthermore, we easily 2,n obtain E Sk (n/4)k for k =0,1,2,... using Eq. (8). 2,n ∼ Corollar(cid:2)y 2.(cid:3)Subtracting nE[p(S ,n)]/4 from Eq. (8), we have 2,n n n n(n 2) E S p(S ,n) = E[p(S ,n)] − E[p(S ,n)]. 2,n 2,n 2,n 2,n−1 − 4 4 − 2(2n 3) h(cid:16) (cid:17) i − Lemma 3. For k =0,1,2,..., n k k! E S n⌊k/2⌋. 2,n− 4 ∼ 2⌊(k+1)/2⌋ k/2 !4k (cid:20)(cid:16) (cid:17) (cid:21) ⌊ ⌋ That is to say, the asymptotic form of E (S n/4)k depends on whether k is even or odd: 2,n − (cid:2) (cid:3) n 2s (2s 1)!! n 2s+1 (2s+1)!! E S − ns, E S ns, (10) 2,n− 4 ∼ 42s 2,n− 4 ∼ 2 42s+1 (cid:20)(cid:16) (cid:17) (cid:21) (cid:20)(cid:16) (cid:17) (cid:21) · for s=0,1,2,.... Remark. In E[S n/4] (k = 1), the leading O(n1) terms are canceled because of E[S ] n/4. Similarly, in 2,n 2,n generalk,O(nk),O(−nk−1),...termsaresuccessivelycanceled,sothattheresultantleadingorder∼ofE (S n/4)k 2,n − becomes k/2 . This effect makes the estimation of E (S n/4)k difficult. ⌊ ⌋ 2,n− (cid:2) (cid:3) Proof. The proof is by induction on k. The statement(cid:2)is true for k =(cid:3)0,1, and 2, because n 0 E S =1, 2,n − 4 (cid:20)(cid:16) (cid:17) (cid:21) n 1 n(n 1) n n 1 E S = − = , 2,n − 4 2(2n 3) − 4 4(2n 3) ∼ 8 (cid:20)(cid:16) (cid:17) (cid:21) − − n 2 n n2 n(4n2 17n+16) n E S =E S2 E[S ]+ = − . 2,n− 4 2,n − 2 2,n 16 16(2n 3)(2n 5) ∼ 16 (cid:20)(cid:16) (cid:17) (cid:21) (cid:2) (cid:3) − − 7 Assume that it is true up to k 2, and we show it is true for k+1. It follows from Cor. 2 that ≥ n k+1 n n k E S =E S S 2,n 2,n 2,n − 4 − 4 − 4 (cid:20)(cid:16) (cid:17) (cid:21) (cid:20)(cid:16) (cid:17)(cid:16) (cid:17) (cid:21) n n k n(n 2) n k = E S − E S 2,n 2,n−1 4 − 4 − 2(2n 3) − 4 (cid:20)(cid:16) (cid:17) (cid:21) − (cid:20)(cid:16) (cid:17) (cid:21) n n k n(n 2) n 1 1 k = E S − E S − 2,n 2,n−1 4 (cid:20)(cid:16) − 4(cid:17) (cid:21)− 2(2n−3) "(cid:18) − 4 − 4(cid:19) # n n k n(n 2) k k 1 l n 1 k−l = E S − E S − . 2,n 2,n−1 4 (cid:20)(cid:16) − 4(cid:17) (cid:21)− 2(2n−3)Xl=0(cid:18)l(cid:19)(cid:18)−4(cid:19) "(cid:18) − 4 (cid:19) # In the following, we separately investigate odd and even k. Case 1: k is odd (k = 2s+1). The dominant terms are l = 0 and 1 in the summation, and the others can be neglected. Thus, n 2s+1+1 E S 2,n − 4 (cid:20)(cid:16) (cid:17) (cid:21) n n 2s+1 n(n 2) n 1 2s+1 2s+1 n 1 2s E S − E S − E S − 2,n 2,n−1 2,n−1 ∼ 4 (cid:20)(cid:16) − 4(cid:17) (cid:21)− 2(2n−3) "(cid:18) − 4 (cid:19) #− 4 "(cid:18) − 4 (cid:19) #! n(2s+1)!! n (2s+1)!! 2s+1(2s 1)!! (n 1)s − (n 1)s ∼ 4 42s+1 − 4 42s+1 − − 4 42s − (cid:18) (cid:19) (2s+1)!! ns+1. ∼ 42s+2 Case 2: k is even (k =2s). Picking out the terms up to O(ns) carefully, we obtain n 2s+1 E S 2,n − 4 (cid:20)(cid:16) (cid:17) (cid:21) n n 2s n(n 2) n 1 2s 2s n 1 2s−1 = E S − E S − E S − 2,n 2,n−1 2,n−1 4 (cid:20)(cid:16) − 4(cid:17) (cid:21)− 2(2n−3) "(cid:18) − 4 (cid:19) #− 4 "(cid:18) − 4 (cid:19) # 2s−2 2s(2s 1) n 1 + − E S − +o(ns−1) . (11) 2,n−1 16·2 "(cid:18) − 4 (cid:19) # ! We introduce the coefficient a as s n 2s (2s 1)!! E S = − ns+a ns−1+o(ns−1), 2,n− 4 42s s (cid:20)(cid:16) (cid:17) (cid:21) and expand each term on the right-hand side of Eq. (11) up to O(ns) using the induction hypothesis: n n 2s (2s 1)!! a E S = − ns+1+ sns+o(ns), 4 2,n− 4 42s+1 4 (cid:20)(cid:16) (cid:17) (cid:21) n(n 2) n 1 2s (2s 1)!! (2s+1)!! a − E S − = − ns+1 ns+ sns+o(ns), 2(2n−3) "(cid:18) 2,n−1− 4 (cid:19) # 42s+1 − 2·42s+1 4 2s−1 n(n 2) 2s n 1 (2s 1)!! − E S − = − sns+o(ns), 2(2n−3) 4 "(cid:18) 2,n−1− 4 (cid:19) # 42s+1 2s−2 n(n 2) 2s(2s 1) n 1 (2s 1)!! − − E S − = − sns+o(ns). 2(2n−3) 16·2 "(cid:18) 2,n−1− 4 (cid:19) # 42s+1 Therefore, n 2s+1 (2s+1)!! E S = ns+o(ns). 2,n− 4 2 42s+1 (cid:20)(cid:16) (cid:17) (cid:21) · 8 Note that O(ns+1) terms and those including a are all cancelled. s Therefore, the statement is true for any k. Corollary 3. Multiplying Eq. (10) by n−k, we have 2s 2s+1 S 1 (2s 1)!! S 1 (2s+1)!! E 2,n − n−s, E 2,n n−s−1. "(cid:18) n − 4(cid:19) #∼ 42s "(cid:18) n − 4(cid:19) #∼ 2·42s+1 Remark. This result corresponds to the case r =1 in Lemmas 1 and 2. Using this corollary,we can provide another proof of Theorem 1 as follows. The characteristic function ϕ2 (z) for 1,n the lowest bifurcation ratio in Theorem 1 is calculated as S 1 ϕ2 (z)=E exp iz√n 2,n 1,n n − 4 (cid:20) (cid:18) (cid:18) (cid:19)(cid:19)(cid:21) ∞ (iz√n)k S 1 k 2,n =E "k=0 k! (cid:18) n − 4(cid:19) # X ∞ (iz√n)k S 1 k 2,n = E k=0 k! "(cid:18) n − 4(cid:19) # X ∞ (iz√n)2s S 1 2s ∞ (iz√n)2s+1 S 1 2s+1 2,n 2,n = E + E s=0 (2s)! "(cid:18) n − 4(cid:19) # s=0 (2s+1)! "(cid:18) n − 4(cid:19) # X X ∞ z2 s 1 − ∼ 32 s! s=0(cid:18) (cid:19) X z2 =exp , −32 (cid:18) (cid:19) so the convergence of √n(S /n 1/4) to N(0,1/16)is proved. 2,n − 4. PROOF OF LEMMA 1 We first derive the asymptotic form of E S−k , which is needed in the proof of Lemma 1. 2,n Proposition 2. For k =0,1,2,..., we have(cid:2) (cid:3) n −k E S−k . 2,n ∼ 4 (cid:2) (cid:3) (cid:16) (cid:17) Remark. Since S (τ)=0 for any τ Ω , S−k surely takes a finite value and E S−k is not divergent. 2,n 6 ∈ n 2,n 2,n Proof. Let us introduce the operator (d/dt)−1 defined by (cid:2) (cid:3) d −1 t f(t):= f(s)ds, dt (cid:18) (cid:19) Z−∞ where f is integrable on any interval ( ,t). Note that (d/dt)−1 is the inverse of d/dt. Owing to the property −∞ −k d emt =m−kemt, dt (cid:18) (cid:19) 9 the average of S−k is expressed by 2,n n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m E S−k = − − m−k 2,n (2n 2)! (n 2m)!m!(m 1)! − m=1 − − (cid:2) (cid:3) X n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m d −k = − − emt (2n 2)! (n 2m)!m!(m 1)! dt (cid:12) − mX=1 − − (cid:18) (cid:19) (cid:12)t=0 (cid:12) 2n−2n!(n 1)! d −k 2 n 3 n (cid:12) = − etF − , − ,2;et . (cid:12) (2n 2)! dt 2 2 (cid:12) − (cid:18) (cid:19) (cid:18) (cid:19)(cid:12)t=0 (cid:12) (cid:12) Let us derive a relation between E S−k and E S−(k+1) as in Prop. 1. (cid:12) 2,n 2,n (cid:2) (cid:3) h i 2n−2n!(n 1)! d −k d −1 2 n 3 n E S−(k+1) = − etF − , − ,2;et 2,n (2n 2)! dt dt 2 2 (cid:12) h i − (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19)(cid:12)t=0 (cid:12) 2n−2n!(n 1)! d −k t 2 n 3 n (cid:12) = − esF − , − ,2;es ds (cid:12) (2n−2)! (cid:18)dt(cid:19) Z−∞ (cid:18) 2 2 (cid:19) (cid:12)(cid:12)t=0 (cid:12) 2n−2n!(n 1)! d −k 2 n 3 n t (cid:12) t d 2 n 3 n = − esF − , − ,2;es (cid:12) es F − , − ,2;es ds (2n−2)! (cid:18)dt(cid:19) ((cid:20) (cid:18) 2 2 (cid:19)(cid:21)s=−∞−Z−∞ ds (cid:18) 2 2 (cid:19) )(cid:12)(cid:12)t=0 (cid:12) 2n−2n!(n 1)! d −k 2 n 3 n d −1 d 2 n 3 n (cid:12) = − etF − , − ,2;et et F − , − ,2;et (cid:12) (2n−2)! (cid:18)dt(cid:19) ( (cid:18) 2 2 (cid:19)−(cid:18)dt(cid:19) dt (cid:18) 2 2 (cid:19))(cid:12)(cid:12)t=0 (cid:12) 2n−2n!(n 1)! d −(k+1) d 2 n 3 n (cid:12) =E S−k − et F − , − ,2;et . (cid:12) 2,n − (2n 2)! dt dt 2 2 (cid:12) − (cid:18) (cid:19) (cid:18) (cid:19)(cid:12)t=0 (cid:2) (cid:3) (cid:12) (cid:12) By using the derivative of the hypergeometric function in Eq. (9), (cid:12) n 2 n(n 2) E S−(k+1) =E S−k − E S−(k+1) + − E S−(k+1) , 2,n 2,n − 2 2,n 2(2n 3) 2,n−1 h i (cid:2) (cid:3) h i − h i whose asymptotic form is n n(n 2) n E S−(k+1) =E S−k + − E S−(k+1) E S−k + E S−(k+1) , 2 2,n 2,n 2(2n 3) 2,n−1 ∼ 2,n 4 2,n h i (cid:2) (cid:3) − h i (cid:2) (cid:3) h i or 4 E S−(k+1) E S−k . 2,n ∼ n 2,n h i (cid:2) (cid:3) Considering E S0 =1, we obtain 2,n (cid:2) (cid:3) n −k E S−k . 2,n ∼ 4 (cid:2) (cid:3) (cid:16) (cid:17) Proof of Lemma 1. By induction on r. For r =1, the statement is equivalent to Cor. 3. Assume that it is true up to r 1, and we show it is true for r. Using Eq. (5), − S 1 k n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m S 1 k r+1,n r,m E = − − E . "(cid:18) Sr,n − 4(cid:19) # (2n−2)! m=1 (n−2m)!m!(m−1)! "(cid:18)Sr−1,m − 4(cid:19) # X 10 Case 1: k is even (k =2s). S 1 2s n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m S 1 2s r+1,n r,m E = − − E "(cid:18) Sr,n − 4(cid:19) # (2n−2)! m=1 (n−2m)!m!(m−1)! "(cid:18)Sr−1,m − 4(cid:19) # X n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m (2s 1)!! m −s − − − ∼ (2n 2)! (n 2m)!m!(m 1)! 42s 4r−2 − mX=1 − − (cid:16) (cid:17) (2s 1)!! n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m = − − − m−s. 42s4−s(r−2) (2n 2)! (n 2m)!m!(m 1)! − m=1 − − X By using Eq. (5) again and Prop. 2, S 1 2s (2s 1)!! (2s 1)!! n −s (2s 1)!! n −s E r+1,n − E S−s − = − . "(cid:18) Sr,n − 4(cid:19) #∼ 42s4−s(r−2) (cid:2) 2,n(cid:3)∼ 42s4−s(r−2) (cid:16)4(cid:17) 42s (cid:16)4r−1(cid:17) Case 2: k is odd (k =2s+1). Using Eq. (5) and Prop. 2 as above, S 1 2s+1 n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m S 1 2s+1 r+1,n r,m E = − − E "(cid:18) Sr,n − 4(cid:19) # (2n−2)! m=1 (n−2m)!m!(m−1)! "(cid:18)Sr−1,m − 4(cid:19) # X n!(n 1)!(n 2)!⌊n/2⌋ 2n−2m (2s+1)!! m −s−1 − − ∼ (2n 2)! (n 2m)!m!(m 1)! 2 42s+1 4r−2 − mX=1 − − · (cid:16) (cid:17) (2s+1)!! E S−s−1 ∼ 2 42s+14(r−1)(−s−1) 2,n · (2s+1)!! n −s−1 (cid:2) (cid:3) = . 2 42s+1 4r · (cid:16) (cid:17) 5. PROOF OF LEMMA 2 In the proof of Lemma 2, we use the following relations. Lemma 4. For s,l =0,1,2,..., n 2s n l (2s 1)!! n 2s+1 n l (2s+1)!! E Sl S − ns, E Sl S (2l+1)ns. 2,n 2,n− 4 ∼ 4 42s 2,n 2,n− 4 ∼ 4 2 42s+1 (cid:20) (cid:16) (cid:17) (cid:21) (cid:16) (cid:17) (cid:20) (cid:16) (cid:17) (cid:21) (cid:16) (cid:17) · Remark. The complicated form of the odd-power result in Lemma 2 is actually due to the factor “(2l+1)”. Proof. By induction on l. For l=0, the statement is equivalent to Lemma 3. Assume that it is true up to l 0, and we show for l+1. Using Prop. 1, ≥ n k n n k n(n 2) n k E Sl+1 S = E Sl S − E Sl S 2,n 2,n− 4 2 2,n 2,n− 4 − 2(2n 3) 2,n−1 2,n−1− 4 (cid:20) (cid:16) (cid:17) (cid:21) (cid:20) (cid:16) (cid:17) (cid:21) − (cid:20) (cid:16) (cid:17) (cid:21) n n k n(n 2) n 1 1 k = E Sl S − E Sl S − 2 (cid:20) 2,n(cid:16) 2,n− 4(cid:17) (cid:21)− 2(2n−3) " 2,n−1(cid:18) 2,n−1− 4 − 4(cid:19) # n n k n(n 2) k k 1 p n 1 k−p = E Sl S − E Sl S − . 2 (cid:20) 2,n(cid:16) 2,n− 4(cid:17) (cid:21)− 2(2n−3)Xp=0(cid:18)p(cid:19)(cid:18)−4(cid:19) " 2,n−1(cid:18) 2,n−1− 4 (cid:19) # Case 1: k is even (k =2s). In the summation, only p=0 is dominant, so that n 2s n n 2s n(n 2) n 1 2s E Sl+1 S E Sl S − E Sl S − . (cid:20) 2,n (cid:16) 2,n− 4(cid:17) (cid:21)∼ 2 (cid:20) 2,n(cid:16) 2,n− 4(cid:17) (cid:21)− 2(2n−3) " 2,n−1(cid:18) 2,n−1− 4 (cid:19) #