ASYMPTOTIC DEGREE DISTRIBUTION IN RANDOM RECURSIVE TREES

SVANTE JANSON

Abstract. The distributions of vertex degrees in random recursive trees and random plane recursive trees are shown to be asymptotically normal. Formulas are given for the asymptotic variances and covariances of the number of vertices with given outdegrees. We also give functional limit theorems for the evolution as vertices are added.

The proofs use some old and new results about generalized Pólya urn models. We consider generalized Pólya urns with infinitely many types, but reduce them to the finite type case.

1. Introduction

A random recursive tree with n vertices is a random rooted tree obtained by starting with a single root and then adding n − 1 vertices one by one, each time joining the new vertex to a randomly chosen old vertex; the random choices are uniform and independent of each other. If the vertices are labelled 1, 2, …, we thus obtain a tree where the labels increase along each branch as we travel from the root; the random recursive tree can also be defined as a (uniform) randomly chosen such labelled tree. (The distribution of a random recursive tree differs from the distribution of a uniform random labelled tree.) See also the survey [23].

Mahmoud and Smythe [16] studied the distribution of outdegrees in a random recursive trees and obtained a joint asymptotic normal distribution of the number of nodes of outdegrees 0, 1 and 2. They also indicated how the results in principle extend to higher degrees. We do this extension to arbitrary degrees, using some new results on generalized Pólya urn processes [11].

A variant of the random recursive tree is the random plane recursive tree studied by Mahmoud, Smythe and Szymański [17]. This is a random rooted plane (or ordered) tree, again obtained by starting with a single root and then adding n − 1 vertices one by one. This time, however, the descendants of each vertex are ordered (from left to right, say), and a new vertex may be inserted at any place. At a vertex with outdegree d, there are thus d + 1 possible places to add a new vertex, and in total a plane tree with n vertices has 2n−1 such places. We choose one of these places at random (uniformly) for vertex n + 1. It is often useful to regard the possible places for a new vertex as external vertices; a tree with n (internal) vertices thus has 2n − 1 external vertices, and the random plane recursive tree evolves by converting a randomly chosen external vertex v to an internal vertex and adding three new external vertices: one daughter below v and one sister on each side of v.

Date: February 21, 2003; revised April 13, 2004.

This is a preprint of an article accepted for publication in Random Structure & Algoritms \begin{matrix}c \\ ◯ \end{matrix} 2004 John Wiley & Sons, Inc.

Mahmoud, Smythe and Szymański [17] obtained, among other results, a joint asymptotic normal distribution of the number of nodes of outdegrees 0, 1 and 2 in a random plane recursive tree. We extend this result too to arbitrary degrees.

We can state the results as follows. First, let X_{ni} be the number of vertices of outdegree i ≥ 0 in a random recursive tree with n vertices.

Theorem 1.1. As n → ∞, n^{−1}X_{ni} → 2^{−i−1} a.s., and

n^{−1/2}(X_{ni} − 2^{−i−1}n) →^{d} V_{i},

jointly for all i ≥ 0, where the V_{i} are jointly Gaussian variables with means 𝔼 V_{i} = 0 and covariances σ_{ij} = Cov(V_{i}, V_{j}) given by the generating function

\begin{aligned}∑_{i,j=0}^{∞} σ_{ij}z^{i}w^{j} & = (1 − z)(1 − w)(\frac{1}{2 − zw} − \frac{1}{(2 − z)(2 − w)})\frac{1}{3 − z − w} \\ & = \frac{2(1 − z)^{2}(1 − w)^{2}}{(2 − z)(2 − w)(2 − zw)(3 − z − w)}. \end{aligned} (1.1)

The weaker result X_{ni}/n →^{p} 2^{−i−1} follows from Meir and Moon [18], who studied asymptotics of the means and variances. Earlier, Na and Rapoport [19] had shown that 𝔼 X_{ni}/n → 2^{−i−1}.

The values of σ_{jk} may be found by expanding the generating function. For example, extending a result in [16], the covariance matrix of the first four components (V_{0}, V_{1}, V_{2}, V_{3}) is (using calculations done by Maple)

( \begin{matrix}\frac{1}{12} & −\frac{7}{72} & −\frac{5}{432} & \frac{17}{2592} \\ −\frac{7}{72} & \frac{71}{432} & −\frac{37}{864} & −\frac{269}{15552} \\ −\frac{5}{432} & −\frac{37}{864} & \frac{473}{5184} & −\frac{1831}{93312} \\ \frac{17}{2592} & −\frac{269}{15552} & −\frac{1831}{93312} & \frac{26939}{559872} \end{matrix} )

It is also straightforward to write down a general formula with finite sums only. However, this formula is a bit complicated, so we omit it and leave its formulation to the interested reader.

Remark 1.2. The joint convergence of infinitely many random variables in Theorem 1.1 is, by definition, the same as joint convergence of any finite subset. This is also the same as convergence of the infinite vector (n^{−1/2}(X_{ni} − 2^{−i−1}n))_{i=0}^{∞} in ℝ^{∞} (see [7, p. 19]). We conjecture that this can be strengthened to convergence in ℓ^{1}, or a suitably weighted version of ℓ^{1}, which would imply the convergence of more continuous functionals.

We similarly let Y_{ni} be the number of vertices of outdegree i ≥ 0 in a random plane recursive tree with n vertices.

Theorem 1.3. As n → ∞, n^{−1}Y_{ni} → 4/(i + 1)(i + 2)(i + 3) a.s., and

n^{−1/2}(Y_{ni} − \frac{4}{(i + 1)(i + 2)(i + 3)}n) →^{d} W_{i},

jointly for all i ≥ 0, where the W_{i} are jointly Gaussian variables with means 𝔼 W_{i} = 0 and covariances σ̃_{ij} = Cov(W_{i}, W_{j}) given by

σ̃_{ij} = 2 ∑_{k=0}^{i} ∑_{l=0}^{j} \frac{(−1)^{k+l}}{k + l + 4}\binom{i}{k}\binom{j}{l}(\frac{2(k + l + 4)!}{(k + 3)!(l + 3)!} − 1 − \frac{(k + 1)(l + 1)}{(k + 3)(l + 3)}).

For example, extending a result in [17], the covariance matrix of the first four components (W_{0}, W_{1}, W_{2}, W_{3}) is (again by Maple)

( \begin{matrix}\frac{1}{9} & −\frac{4}{45} & −\frac{1}{45} & −\frac{2}{315} \\ −\frac{4}{45} & \frac{23}{180} & −\frac{11}{630} & −\frac{11}{1260} \\ −\frac{1}{45} & −\frac{11}{630} & \frac{179}{3150} & −\frac{1}{175} \\ −\frac{2}{315} & −\frac{11}{1260} & −\frac{1}{175} & \frac{187}{6300} \end{matrix} )

We can extend the theorems to functional limit theorems, describing the evoultion as new vertices are added.

Theorem 1.4. For the random recursive tree

n^{−1/2}(X_{⌊xn⌋,i} − 2^{−i−1}xn) →^{d} V_{i}(x)  (1.2)

in D[0, ∞), jointly for all i ≥ 0, where the V_{i}(x) are continuous Gaussian processes with V_{i}(0) = 0, 𝔼 V_{i}(x) = 0 and covariance functions

𝔼 V_{j}(x)V_{k}(y) = \frac{x^{2}}{y} ∑_{i=0}^{k} \frac{ln^{i}(y/x)}{i!}σ_{k−i,j},  0 < x ≤ y.  (1.3)

Theorem 1.5. For the random planar recursive tree

n^{−1/2}(Y_{⌊xn⌋,i} − \frac{4}{(i+1)(i+2)(i+3)}xn) →^{d} W_{i}(x)

in D[0, ∞), jointly for all i ≥ 0, where the W_{i}(x) are continuous Gaussian processes with W_{i}(0) = 0, 𝔼 W_{i}(x) = 0 and covariance functions, for 0 < x ≤ y,

𝔼 W_{i}(x)W_{j}(y) = 2 ∑_{k=0}^{i} ∑_{l=0}^{j} \frac{(−1)^{k+l}}{k + l + 4}\binom{i}{k}\binom{j}{l}

· (\frac{2(k + l + 4)!}{(k + 3)!(l + 3)!} − 1 − \frac{(k + 1)(l + 1)}{(k + 3)(l + 3)})x^{(l+3)/2}y^{−(l+1)/2}.

For example, for 0 < x ≤ y,

Cov(V_{2}(x), V_{2}(y)) = \frac{x^{2}}{y} (\frac{473}{5184} − \frac{37}{864} ln \frac{y}{x} − \frac{5}{864} ln^{2} \frac{y}{x}),
Cov(W_{2}(x), W_{2}(y)) = −\frac{1}{45}x^{3/2}y^{−1/2} + \frac{1}{105}x^{2}y^{−1} + \frac{73}{1050}x^{5/2}y^{−3/2}.

We prove the theorems above by the method of [16] and [17], viz. by reformulating them as results for certain urn processes. We discuss such urn processes in Section 2 and quote some results that we will use. Section 4 contains the details of the application of the general theorems to random recursive trees and Section 5 contains the arguments for the random plane recursive trees. In both cases, we consider urns with infinitely many types, but reduce them to the finite type case. It may be observed that the arguments for the two cases differ in some parts because of different eigenvalue structures. In Section 6, we briefly discuss analogous results for random recursive d-ary trees.

We finally note that problems of this type have been studied by other methods too. For example, Najock and Heyde [20] proved the asymptotic normality of X_{n0} (the number of leaves in a random recursive tree). Bergeron, Flajolet and Salvy [6] used generating functions and obtained general results for a class of random trees including the ones studied here; in particular, they show asymptotic normality of X_{n0} and Y_{n0}, and their methods apply also to higher degrees.

2. Generalized Pólya urns

Consider an urn containing a finite number of balls of different types (colours); say that the possible types are 1, …, q. Then the content of the urn at time n is described by the vector (X_{n1}, …, X_{nq}), where X_{ni} ≥ 0 is the number of balls of type i in the urn.

The urn starts with a given vector X_{0} (or perhaps X_{1}), random or not. We are further given, for each type i, an activity a_{i} ≥ 0 and a q-dimensional vector ξ_{i} = (ξ_{i1}, …, ξ_{iq}) with integer coordinates. In general ξ_{i} may be random, but in this paper and many other applications, we only consider deterministic ξ_{i}.

The urn evolves according to a Markov process. At each time n ≥ 1, one of the balls in the urn is drawn at random such that the probability of drawing a particular ball of type i is proportional to the activity a_{i}, i.e. the probability of drawing a ball of type i is a_{i}X_{n−1,i}/ ∑_{j} a_{j}X_{n−1,j}. (In particular, if every a_{i} = 1, a ball is drawn uniformly at random.) The drawn ball is returned to the urn together with, if it is of type i, ξ_{ij} balls of type j, for each j = 1, …, q.

The integers ξ_{ij} may be negative, which means removal of balls from the urn. In order to guarantee that we are not required to remove balls that do not exist, we assume that

ξ_{ij} ≥ 0,  i ≠ j,  (2.1)

(thus balls of other types than the drawn are never removed) and

ξ_{ii} ≥ −1  (2.2)

or, more generally, that for each i there is an integer d_{i} ≥ 1 such that d_{i}|X_{0i} and d_{i}|ξ_{ji} for every j and

ξ_{ii} ≥ 0 or ξ_{ii} = −d_{i}.  (2.3)

(Hence d_{i}|X_{ni} for all n ≥ 0.) Such urns are called tenable by Bagchi and Pal [3].

We further assume that the urn is irreducible, in the sense that for any two distinct types i and j, if we start with only balls of type i, there is a later time when there is a positive probability of having a ball of type j in the urn. In particular, each a_{i} > 0.

For simplicity, cf. Remark 3.4 below, we also assume that there exists m > 0 such that, for every i,

∑_{j} a_{j}ξ_{ij} = m.  (2.4)

(When every a_{i} = 1, this says that exactly m balls are added each time.) It follows that a · X_{n} = nm + a · X_{0} > 0; in particular the urn never becomes empty.

Urn models of this type have been studied by many authors, see the references in [11].

3. Preliminaries

We let A denote the q × q matrix

A := (a_{j}ξ_{ji})_{i,j=1}^{q}.  (3.1)

Thus the j:th column of A is a_{j}ξ_{j}. (E.g. [16, 17] use the transpose matrix.)

By (2.1), A + αI is a non-negative matrix if α is large enough, so by the standard Perron–Frobenius theory, A has a largest real eigenvalue λ_{1} such that every other eigenvalue λ satisfies Re λ < λ_{1} (see e.g. [21, Chapter 1 and Theorem 2.6] or [13, Appendix 2]). We order the eigenvalues with decreasing real parts: λ_{1} > Re λ_{2} ≥ Re λ_{3} ≥ . . ..

We let a denote the (column) vector (a_{1}, …, a_{q}) of activities, and let u_{1} and v_{1} denote left and right eigenvectors of A corresponding to the largest eigenvalue λ_{1}, i.e. vectors satisfying

u′_{1}A = λ_{1}u′_{1}, Av_{1} = λ_{1}v_{1}.

By the Perron–Frobenius theory [13], [21], (applied to A+αI for suitable α), u_{1} and v_{1} are unique up to scalar factors; they may be chosen with positive components and they are the only positive eigenvectors.

By (2.4) and (3.1),

(a′A)_{j} = ∑_{i} a_{i}a_{j}ξ_{ji} = a_{j}a · ξ_{j} = ma_{j}.

So a is a positive left eigenvector and thus a multiple of u_{1}, and λ_{1} = m. We normalize u_{1} and v_{1} such that u_{1} = a and

u_{1} · v_{1} = a · v_{1} = 1.  (3.2)

We define P_{λ_{1}} as the matrix

P_{λ_{1}} = v_{1}u′_{1},  (3.3)

which has rank 1 and is a projection onto the one-dimensional eigenspace \{v : Av = λ_{1}v\}. We will in this paper only consider the case Re λ_{2} < \frac{1}{2}λ_{1}. We then further define P_{I} := I − P_{λ_{1}}, the complementary projection, and the following q × q matrices, regarding ξ_{i} as a column matrix,

B := ∑_{i=1}^{q} v_{1i}a_{i}ξ_{i}ξ′_{i},  (3.4)

Σ_{I} := ∫_{0}^{∞} P_{I}e^{sA}Be^{sA′}P′_{I}e^{−λ_{1}s} ds.  (3.5)

The general result that we use is the following, which summarizes and simplifies some of the results in [11]. The a.s. convergence and the asymptotic normality (without explicit covariance matrix) are due to [1], see also [2, Section V.9]. (At least when (2.2) holds, which easily implies the general case, see [11, Remark 4.2].) See also similar results in [22], [4], [5].

Theorem 3.1. Assume that the urn is irreducible and tenable, and that (2.4) holds with m > 0. Then n^{−1}X_{n} →^{a.s.} λ_{1}v_{1} as n → ∞. If further Re λ_{2} < \frac{1}{2}λ_{1}, then also the following hold.

(i) n^{−1/2}(X_{n} − nλ_{1}v_{1}) →^{d} N(0, mΣ_{I}).

(ii) More generally, in D[0, ∞),

n^{−1/2}(X_{⌊xn⌋} − xnλ_{1}v_{1}) →^{d} V (x),

where V (x) is a continuous Gaussian vector-valued process with V (0) = 0, mean 𝔼 V (x) = 0, and

𝔼 V (x)V (y)′ = \begin{cases}mxΣ_{I}(y/x)^{m^{−1}A′}, & 0 < x ≤ y, \\ my(x/y)^{m^{−1}A}Σ_{I}, & 0 < y ≤ x. \end{cases}  (3.6)

Proof. If (2.2) holds, then all assumptions (A1)–(A6) in [11] are satisfied: (A1) and (A2) hold by assumption, (A3) follows from λ_{1} = m, and (A4)– (A6) hold because the urn is irreducible. The general tenable case is easily reduced to this case, see [11, Remark 4.2].

Hence we can apply the results of [11]. Theorem 3.21 there (or [1]) yields n^{−1}X_{n} →^{a.s.} λ_{1}v_{1} and Theorem 3.22 (or [1]) yields asymptotic normality, with the asymptotic covariance matrix equal to mΣ_{I} by Lemma 5.4 in [11]. Similarly, the functional convergence follows from Theorem 3.31(i) in [11], and (3.6) for x ≤ y follows by Remark 5.7 in [11]; the case y ≤ x follows by taking the transpose and relabelling. □

Remark 3.2. Several formulas for easy evaluation of Σ_{I} and the covariances in (3.6) are given in [11, Section 5]. We will use some of them below.

Remark 3.3. The results extend to random ξ_{ij} with only minor changes. Assume that (2.1) and (2.2) or (2.3) (with d_{i} non-random) hold with probability 1, and that ξ_{ij}^{2} < ∞ for all i and j. Assume further that (2.4) holds on the average, i.e. a · 𝔼 ξ_{i} = m for some m > 0. Define A and B by taking the expectations of the right-hand sides of (3.1) and (3.4). Then Theorem 3.1 still holds, see [11].

Remark 3.4. The assumption (2.4) is not necessary, and can be replaced by the assumptions that λ_{1} > 0 and that extinction is impossible; however, the variance mΣ_{I} and the covariance formula (3.6) in Theorem 3.1 have to be replaced by more complicated expressions, see [11, Theorems 3.22 and 3.31].

Remark 3.5. When Re λ_{2} = \frac{1}{2}λ_{1}, there are similar results but the right normalization factor is (n log^{d} n)^{−1/2} for some d ≥ 1. The case Re λ_{2} > \frac{1}{2}λ_{1} is quite different and asymptotic normality does not hold (at least in general). See e.g. [1], [2], [11].

4. Random recursive trees

We apply Theorem 3.1 to random recursive trees as follows.

Proof of Theorem 1.1. Following Mahmoud and Smythe [16], we observe that the distribution of outdegrees is the same as the distribution of types in a generalized Pólya urn with infinitely many types {0, 1, 2, … }, all activities a_{i} = 1, and the rule that if a ball with type i is drawn, it is removed and replaced by a ball of type i + 1 and a ball of type 0. (We start at time 1 with a single ball of type 0.) In our notation, ξ_{i} = −δ_{i} + δ_{i+1} + δ_{0}, where δ_{i} is the unit vector defined by (δ_{i})_{j} = δ_{ij}.

Theorem 3.1 assumes that the number of types is finite, but luckily we can in this application truncate and lump all high degrees together. Thus, let M ≥ 1 be an integer and use the types {0, 1, …, M} only (thus q = M + 1), where now type M represents all outdegrees ≥ M. The replacement vectors ξ_{i} are as in the infinite model when i < M, while now ξ_{M} = δ_{0}. For example, for M = 3 (the case treated in [16]) we have

A = (\begin{matrix}0 & 1 & 1 & 1 \\ 1 & −1 & 0 & 0 \\ 0 & 1 & −1 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}) .  (4.1)

Exactly one ball is added each time, so (2.4) holds with m = 1, and thus λ_{1} = 1 and u_{1} = a = (1, 1, …, 1). It is easily verified that v_{1} = (1/2, 1/4, …, 2^{−M}, 2^{−M}), i.e. v_{1i} = 2^{−i−1} for 0 ≤ i < M and v_{1M} = 2^{−M}. In particular, Theorem 3.1 shows that X_{ni}/n →^{a.s.} 2^{−i−1} for every i ≥ 0 (by taking M > i).

To find the other eigenvalues of A, we regard ℂ^{q} = ℂ^{M+1} as a subspace of ℓ^{1} = ℓ^{1}(ℕ) and let π_{M} : ℓ^{1} → ℂ^{q} be the projection (x_{0}, x_{1}, …) ↦ (x_{0}, …, x_{M−1}, ∑_{M}^{∞} x_{i}). (ℂ is the set of complex numbers.) Let S be the shift operator on ℓ^{1}, S(x_{0}, x_{1}, …) = (0, x_{0}, x_{1}, …). Then Av = −v + (u_{1} · v)δ_{0} + π_{M}Sv, v ∈ ℂ^{q}.

Let E′ := {v ∈ ℂ^{q} : u_{1} · v = 0}. Then A maps E′ into itself (because u_{1} is a left eigenvector) and, on E′, A = −I + π_{M}S. Thus, for v ∈ E′, (A + I)v = π_{M}Sv and, by induction, since π_{M}Sπ_{M} = π_{M}S,

(A + I)^{k}v = π_{M}S^{k}v,  for v ∈ E′ and k ≥ 0.  (4.2)

In particular, (A + I)^{M}v = π_{M}S^{M}v = 0 for v ∈ E′, so A + I is nilpotent on E′ and the restriction of A to E′ has the single eigenvalue −1. Since E′ + ℂv_{1} = ℂ^{q}, it follows that the eigenvalues of A are 1 and −1, the latter with algebraic multiplicity M. We see further that (A + I)^{M−1} ≠ 0 on E′, so A is not diagonalizable when M ≥ 2. (The geometric multiplicity of the eigenvalue −1 is 1.)

Since thus λ_{2} = −1, Theorem 3.1 applies, and the vector (n^{−1/2}(X_{ni} − 2^{−i−1}n))_{i=0}^{M−1} converges in distribution to a Gaussian vector. Since M is arbitrary, this means joint convergence of for all i, see Remark 1.2.

It remains to find the (co)variances σ_{jk} := Cov(V_{j}, V_{k}). Thus, take any M > j, k. By [11, Lemma 5.1],

σ_{jk} = ∫_{0}^{∞} ∑_{i} v_{1i}(g_{i}(s))_{j}(g_{i}(s))_{k}e^{−λ_{1}s}λ_{1} ds,  (4.3)

where g_{i}(s) = Ae^{sA}(I − P_{λ_{1}})δ_{i}. Since (I − P_{λ_{1}})δ_{i} ∈ E′ and P_{λ_{1}}δ_{i} = v_{1}(u_{1} · δ_{i}) = v_{1}, it follows from (4.2) that

\begin{aligned}g_{i}(s) & = Ae^{sA}(δ_{i} − v_{1}) = e^{−s}(A + I − I)e^{s(A+I)}(δ_{i} − v_{1}) \\ & = e^{−s}π_{M}((S − I)e^{sS}(δ_{i} − v_{1})). \end{aligned}

Consequently, (4.3) yields

σ_{jk} = ∑_{i} v_{1i} ∫_{0}^{∞}((S − I)e^{sS}(δ_{i} − v_{1}))_{j}((S − I)e^{sS}(δ_{i} − v_{1}))_{k}e^{−3s} ds. (4.4)

We may obtain an expression with finite sums only by expanding the terms in this integral. However, we prefer to compute the bivariate generating function of σ_{jk} instead.

In (4.4), v_{1} really depends on our choice of M, and thus implicitly on j and k, but it is easily seen that we can replace v_{1} by ṽ_{1} := (2^{−i−1})_{i=0}^{∞} (the limit of v_{1} as M → ∞), since the integrand does not depend on i for i > max(j, k). Let F be the map of ℓ^{1} into the set of analytic functions in the unit disc given by F(v)(z) = ∑_{i=0}^{∞} v_{i}z^{i}. Note that F(Sv)(z) = zF(v)(z). Let ṽ(z) := F(ṽ_{1})(z) = ∑_{i} 2^{−i−1}z^{i} = 1/(2 − z). Then (4.4) yields, for |z|, |w| ≤ 1, say, when absolute summability easily is checked,

∑_{j,k=0}^{∞} σ_{jk}z^{j}w^{k} =

∑_{i=0}^{∞} 2^{−i−1} ∫_{0}^{∞} F((S − I)e^{sS}(δ_{i} − ṽ_{1}))(z)F((S − I)e^{sS}(δ_{i} − ṽ_{1}))(w)e^{−3s} ds

= ∑_{i=0}^{∞} 2^{−i−1} ∫_{0}^{∞}(z − 1)e^{sz}(z^{i} − ṽ(z))(w − 1)e^{sw}(w^{i} − ṽ(w))e^{−3s} ds

= (z − 1)(w − 1)(\frac{1}{2 − zw} − ṽ(z)ṽ(w)) ∫_{0}^{∞} e^{−(3−z−w)s}ds,

which yields (1.1). □

Proof of Theorem 1.4. The functional convergence (1.2) follows immediately from Theorem 3.1(ii).

We find the covariance functions as follows. Given j and k we again take M > j, k and combine all high degrees as above. Assume 0 < x ≤ y. By (3.6), 𝔼 V (y)V (x)′ = x(y/x)^{A}Σ_{I}. Since u′_{1}X_{n} is deterministic, u′_{1}V (x) = 0 and thus u′_{1}Σ_{I} = 𝔼(u′_{1}V (1)V (1)′) = 0. Hence we can use (4.2) and obtain, for 0 < x ≤ y,

𝔼 V_{k}(y)V_{j}(x) = x((\frac{y}{x})^{A}Σ_{I})_{kj} = \frac{x^{2}}{y} ((\frac{y}{x})^{A+I}Σ_{I})_{kj} = \frac{x^{2}}{y} ((\frac{y}{x})^{π_{M} S}Σ_{I})_{kj}

= \frac{x^{2}}{y} ∑_{i=0}^{k} \frac{ln^{i}(y/x)}{i!}((π_{M}S)^{i}Σ_{I})_{kj} = \frac{x^{2}}{y} ∑_{i=0}^{k} \frac{ln^{i}(y/x)}{i!}σ_{k−i,j}. □

5. Random plane recursive trees

Proof of Theorem 1.3. The outdegrees in the random plane recursive trees studied by Mahmoud, Smythe and Szymański [17] can be modelled using a generalized Pólya urn with infinitely many types as in Section 4; the ξ_{i} are the same, but now the activity a_{i} = i + 1.

It is advantageous to modify the urn so that the activities become the same. We thus replace each ball of type i by i + 1 balls of the same type; equivalently, we let the balls represent external vertices as in [17]. This gives a new generalized Pólya urn with infinitely many types, all activities 1, and the transitions given by

ξ_{ij} = −(i + 1)δ_{ij} + (i + 2)δ_{i+1,j} + δ_{0j}.

The number of balls of type i in this urn is thus (i + 1)Y_{ni}.

We truncate as in Section 4 and use the M + 1 types 0, …, M only, with ξ_{Mj} changed to δ_{0j} + δ_{Mj}. (Note that such truncation does not work in the original urn model representing internal nodes, since the activities vary.)

For example, for M = 3 (the case treated in [17]) we have

A = (ξ_{ji})_{i,j=0}^{M} = (\begin{matrix}0 & 1 & 1 & 1 \\ 2 & −2 & 0 & 0 \\ 0 & 3 & −3 & 0 \\ 0 & 0 & 4 & 1 \end{matrix}) .  (5.1)

Two balls are added each time, so (2.4) holds with m = 2, and thus λ_{1} = 2.

It is not difficult to compute the characteristic polynomial of A (by induction) and thus find the other eigenvalues. We will, however, instead find both the eigenvalues and eigenvectors directly.

For the left eigenvectors, u^{(λ)} say, we have the equations

u_{0}^{(λ)} − (i + 1)u_{i}^{(λ)} + (i + 2)u_{i+1}^{(λ)} = λu_{i}^{(λ)},  0 ≤ i < M,  (5.2a)
u_{0}^{(λ)} + u_{M}^{(λ)}  = λu_{M}^{(λ)}.  (5.2b)

Let Δu_{i}^{(λ)} := u_{i+1}^{(λ)} − u_{i}^{(λ)}, 0 ≤ i < M, and Δu_{M}^{(λ)} := 0. Then (5.2) can be written

(i + 2)Δu_{i}^{(λ)} = (λ − 1)u_{i}^{(λ)} − u_{0}^{(λ)}, 0 ≤ i ≤ M.

Hence, for i < M,

(i + 3)Δu_{i+1}^{(λ)} − (i + 2)Δu_{i}^{(λ)} = (λ − 1)(u_{i+1}^{(λ)} − u_{i}^{(λ)}) = (λ − 1)Δu_{i}^{(λ)}

or

(i + 3)Δu_{i+1}^{(λ)} = (i + 1 + λ)Δu_{i}^{(λ)}, 0 ≤ i < M,

with the solution (where c = 2Δu_{0}^{(λ)} ∈ ℂ)

Δu_{i}^{(λ)} = \frac{∏_{j=1}^{i}(j + λ)}{(i + 2)!}c,  0 ≤ i ≤ M.  (5.3)

If all Δu_{i}^{(λ)} = 0, u_{i}^{(λ)} is a multiple of a = (1, …, 1); we already know that these are the left eigenvectors with eigenvalue λ_{1} = 2. For λ ≠ 2, we thus have c ≠ 0; since Δu_{M}^{(λ)} = 0, (5.3) implies that j + λ = 0, i.e. λ = −j, for some j ∈ {1, …, M}. With λ = −k, (5.3) can be written

Δu_{i}^{(−k)} = \frac{(1 − k) ⋯ (i − k)}{(i + 2)!}c = (−1)^{i}\binom{k + 1}{i + 2}\frac{c}{k(k + 1)} = (−1)^{i}\binom{k + 1}{i + 2}c_{1},

say. This is solved by

u_{i}^{(−k)} = (−1)^{i−1}\binom{k}{i + 1}c_{1} + c_{2}.  (5.4)

In particular, u_{0}^{(−k)} = −kc_{1} + c_{2} and u_{M}^{(−k)} = c_{2}. Hence (5.2b) yields −kc_{1} + 2c_{2} = −kc_{2} and thus c_{2} = k(k + 2)^{−1}c_{1}. Conversely, for any such c_{1} and c_{2}, (5.4) solves (5.2) with λ = −k.

Hence A has the eigenvalues 2, −1, −2, …, −M. In particular, λ_{2} = −1 < \frac{1}{2}λ_{1}, so Theorem 3.1 applies. We also see that A has q = M + 1 distinct eigenvalues and thus is diagonalizable.

For the right eigenvectors, we have the equations

∑_{j=1}^{M} v_{j}^{(λ)}  = λv_{0}^{(λ)}  (5.5a)
(i + 1)v_{i−1}^{(λ)} − (i + 1)v_{i}^{(λ)} = λv_{i}^{(λ)},  1 ≤ i < M,  (5.5b)
(M + 1)v_{M−1}^{(λ)} + v_{M}^{(λ)} = λv_{M}^{(λ)}.  (5.5c)

For λ = λ_{1} = 2, v^{(λ)} = v_{1} and (5.5b) yields (i+1)v_{1,i−1} = (i+3)v_{1,i} and thus v_{1i} = c/(i+2)(i+3), 0 ≤ i < M. With our normalization a·v_{1} = ∑_{0}^{M} v_{1i} = 1, (5.5a) yields 1 = 3v_{10}; thus c = 2 and, using also (5.5c),

\{ \begin{matrix}v_{1i} = \frac{2}{(i + 2)(i + 3)},  0 ≤ i < M, \\ v_{1M} = \frac{2}{M + 2}. \end{matrix}  (5.6)

Theorem 3.1 thus shows that (i + 1)Y_{ni}/n →^{a.s.} 4/(i + 2)(i + 3) as n → ∞. Moreover, it is easily verified that for each k = 1, …, M,

v_{i}^{(−k)} = \binom{i + 1}{k},  0 ≤ i < M,
v_{M}^{(−k)} = −\binom{M + 1}{k + 1}

solves (5.5) with λ = −k.

Recall that u · v = 0 whenever u is a left and v a right eigenvector with different eigenvalues. Moreover, if u^{(−k)} is given by (5.4),

u^{(−k)}·v^{(−k)} = (u^{(−k)}−c_{2}a)·v^{(−k)} = ∑_{i=0}^{k−1}(−1)^{i−1}\binom{k}{i + 1}c_{1}\binom{i + 1}{k} = (−1)^{k}c_{1},

since the only non-zero term is for i = k − 1. Consequently, if we choose c_{1} = (−1)^{k} in (5.4), i.e.

u_{i}^{(−k)} = (−1)^{k+i+1}\binom{k}{i + 1} + (−1)^{k} \frac{k}{k + 2},  (5.7)

and write u_{j} = u^{(1−j)}, v_{j} = v^{(1−j)}, 2 ≤ j ≤ M + 1, then u_{i} · v_{j} = δ_{ij} and {u_{i}}_{1}^{M+1} and {v_{i}}_{1}^{M+1} are dual bases of eigenvectors.

It is now easy to evaluate the integral in (3.5) and obtain, see [11, Lemma 5.3(ii)], with D the diagonal matrix with D_{ii} = v_{1i},

Σ_{I} = ∑_{i,j=2}^{M+1} \frac{λ_{i}λ_{j}u′_{i}Du_{j}}{λ_{1} − λ_{i} − λ_{j}} v_{i}v′_{j} = ∑_{k,l=1}^{M} \frac{kl(u^{(−k)}′Du^{(−l)})}{2 + k + l}v^{(−k)}v^{(−l)}′. (5.8)

Theorem 3.1 thus shows that

n^{−1/2}((i + 1)Y_{ni} − \frac{4}{(i + 2)(i + 3)}n) →^{d} Ŵ_{i},

jointly for all i = 0, …, M −1, where Ŵ_{i} are jointly Gaussian variables with means 0 and covariances

\begin{aligned}Cov(Ŵ_{i}, Ŵ_{j}) & = (mΣ_{I})_{ij} = 2 ∑_{k,l=1}^{M} \frac{kl(u^{(−k)}′Du^{(−l)})}{k + l + 2}v_{i}^{(−k)}v_{j}^{(−l)} \\ & = 2 ∑_{k=1}^{i+1} ∑_{l=1}^{j+1} \frac{kl}{k + l + 2}\binom{i + 1}{k}\binom{j + 1}{l}u^{(−k)}′Du^{(−l)} \\ & = 2 ∑_{k=1}^{i+1} ∑_{l=1}^{j+1} \frac{(i + 1)(j + 1)}{k + l + 2}\binom{i}{k − 1}\binom{j}{l − 1}u^{(−k)}′Du^{(−l)}. \end{aligned} (5.9)

The result follows, with W_{i} = Ŵ_{i}/(i + 1), by the following lemma (and k ↦ k + 1, l ↦ l + 1). □

Lemma 5.1. For 1 ≤ k, l ≤ M,

u^{(−k)}′Du^{(−l)} = (−1)^{k+l}(2\frac{(k + l + 2)!}{(k + 2)! (l + 2)!} − 1 − \frac{kl}{(k + 2)(l + 2)}).

Proof. Let, see (5.7),

\begin{matrix}w_{kl} := & ((−1)^{k}u^{(−k)} − \frac{k}{k + 2}u_{1})′D((−1)^{l}u^{(−l)} − \frac{l}{l + 2}u_{1}) \\ = & ∑_{i=0}^{M} v_{1i}\binom{k}{i + 1}\binom{l}{i + 1} = ∑_{i=0}^{∞} \frac{2}{(i + 2)(i + 3)}\binom{k}{i + 1}\binom{l}{i + 1}, \end{matrix}

because \binom{k}{i+1} = 0 when i ≥ M ≥ k. Hence, w_{kl} does not depend on M, and we may regard w_{kl} as defined for all k, l ≥ 1. Moreover, since u^{(−k)}′Du_{1} = u^{(−k)}′v_{1} = 0 and similarly u′_{1}Du^{(−l)} = 0, while u′_{1}Du_{1} = u′_{1}v_{1} = 1,

w_{kl} = (−1)^{k+l}u^{(−k)}′Du^{(−l)} + \frac{kl}{(k + 2)(l + 2)},  k, l ≤ M.  (5.10)

Let

f(x) := ∑_{i=0}^{∞} \frac{x^{i}}{(i + 2)(i + 3)} = ∑_{i=0}^{∞} x^{i}(\frac{1}{(i + 2)} − \frac{1}{(i + 3)})
= x^{−2}(− ln(1 − x) − x) − x^{−3}(− ln(1 − x) − x − \frac{1}{2}x^{2})
= x^{−3}((1 − x) ln(1 − x) + x − \frac{1}{2}x^{2}).

Then, for |z|, |w| < 1/2, or as formal power series,

∑_{k,l=1}^{∞}w_{kl}z^{k}w^{l} = ∑_{i=0}^{∞} \frac{2}{(i + 2)(i + 3)} ∑_{k=1}^{∞} \binom{k}{i + 1}z^{k} ∑_{l=1}^{∞} \binom{l}{i + 1}z^{l}

= ∑_{i=0}^{∞} \frac{2}{(i + 2)(i + 3)} \frac{z^{i+1}}{(1 − z)^{i+2}} \frac{w^{i+1}}{(1 − w)^{i+2}}

= \frac{2zw}{(1 − z)^{2}(1 − w)^{2}} f(\frac{zw}{(1 − z)(1 − w)})

= \frac{2(1 − z)(1 − w)}{z^{2}w^{2}}((1 − \frac{zw}{(1 − z)(1 − w)}) ln(1 − \frac{zw}{(1 − z)(1 − w)})

+ \frac{zw}{(1 − z)(1 − w)} − \frac{z^{2}w^{2}}{2(1 − z)^{2}(1 − w)^{2}} )

= \frac{2}{z^{2}w^{2}} ((1 − z − w)(ln(1 − z − w) − ln(1 − z) − ln(1 − w)) + zw)

− \frac{1}{(1 − z)(1 − w)}.

Hence

w_{kl} = 2[z^{k+2}w^{l+2}]((1 − z − w) ln(1 − z − w)) − 1

= 2[z^{k+2}w^{l+2}](∑_{i=2}^{∞} \frac{(z + w)^{i}}{i(i − 1)} − z − w) − 1

= 2\frac{1}{(k + l + 4)(k + l + 3)}\binom{k + l + 4}{k + 2} − 1

and the result follows by (5.10). □

Proof of Theorem 1.5. This follows from Theorem 3.1(ii), using the urn for external vertices with truncation (and dividing by i + 1) as in the proof of Theorem 1.3. The covariance matrix (3.6), for 0 < x ≤ y, is by (5.8), since v^{(−l)}′A′ = −lv^{(−l)}′,

mxΣ_{I}(y/x)^{m^{−1}A′} = 2x ∑_{k,l=1}^{M} \frac{kl(u^{(−k)}′Du^{(−l)})}{k + l + 2}v^{(−k)}v^{(−l)}′(\frac{y}{x})^{−l/2}. (5.11)

The result follows by a calculation as in (5.9) and Lemma 5.1. □

6. Random recursive d-ary trees

Another related random tree is the random recursive binary tree defined by growing a subtree of a complete infinite binary tree; we start with the root and add new nodes, each new nodes being randomly put in one of the vacant positions as a child of an existing node. Equivalently, we start with one internal node having two external nodes as children, and in each step a randomly chosen external node is converted to an internal node, with two new external nodes as children. This is the same as a random binary search tree. Let Z_{ni} be the number of (internal) vertices with outdegree i when the tree has n vertices.

The distribution of out-degrees in this random tree was studied by Devroye [10], both by an urn model and by another method. In the urn method approach, we observe that the distribution of out-degrees is given by a generalized Pólya urn with 3 types 0, 1, 2; ξ_{i} is again as in Section 4 but now the activity is a_{i} = 2 − i.

Alternatively, we may consider external nodes; then there are 2 types 0 and 1, a_{i} = 1 and ξ_{0} = δ_{1}, ξ_{1} = 2δ_{0} − δ_{1}.

The matrix A has eigenvalues 1 and −2 in the external version, and 1, 0, −2 in the internal version. Hence λ_{2} < \frac{1}{2}λ_{1}, and Theorem 3.1 yields a.s. convergence and asymptotic normality, as shown by [10]. For example, using e.g. [11, Lemma 5.3] to compute the variance, n^{−1/2}(Z_{n0} − n/3) →^{d} N(0, 2/45) [10].

This is easily generalized to a random recursive d-ary tree, for any fixed d ≥ 2. This tree is defined in the same way as a subtree of a complete infinite d-ary tree. In the internal urn model, we have d + 1 types 0, …, d, the same ξ_{i} as in Section 4 and activities a_{i} = d − i. In the external urn model, we have only d types 0, …, d − 1, ξ_{i} = dδ_{0} − (d − i)δ_{i} + (d − i − 1)δ_{i+1} and a_{i} = 1.

Arguments as in Section 5 show that the eigenvalues are λ_{1} = d − 1 and −2, −3, …, −d in the external version (and also 0 in the internal version). Again, Theorem 3.1 applies (now to either version) and yields a.s. convergence and asymptotic normality. As in Section 5, the eigenvectors are easily computed explicitly, which gives explicit formulas. In particular, for the external version, v_{1i} = \binom{2d−i−2}{d−1}/\binom{2d−1}{d}, i = 0, …, d − 1, which leads to

\frac{Z_{ni}}{n} →^{a.s.} \binom{2d − i − 2}{d − 2} / \binom{2d − 1}{d − 1} = \frac{(d − 1)(d)_{i}}{(2d − 1)_{i}} , 0 ≤ i ≤ d.

The limiting distribution is the same as the distribution of the number of white balls drawn (without replacement) before the first black from an urn with d white and d−1 black balls; this is known as a negative hypergeometric distribution (shifted by 1) [12, §2.5]. The limiting distribution of the types of external vertices is similarly given by another negative hypergeometric distribution, this time taking d − 1 white and d black balls.

For the leaves we have, generalizing the result by [10] given above for d = 2,

n^{−1/2}(Z_{n0} − \frac{d − 1}{2d − 1}n) →^{d} N(0, \frac{d(d − 1)^{2}}{(3d − 1)(2d − 1)^{2}} ).

We leave the verification and formulas for variances and covariances for types other than 0 as an exercise.

Note that for d ≥ 3, this random recursive d-ary tree is not the same as a random d-ary search tree. The latter can also be treated by an urn model [15], but Re λ_{2} < \frac{1}{2}λ_{1} only for d ≤ 26; for larger d asymptotic normality does not hold [9]; see also [14] and [8].

References

[1] K.B. Athreya & S. Karlin, Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 (1968), 1801– 1817.

[2] K.B. Athreya & P.E. Ney, Branching Processes. Springer-Verlag, Berlin, 1972.

[3] A. Bagchi & A.K. Pal, Asymptotic normality in the generalized Pólya–Eggenberger urn model, with an application to computer data structures. SIAM J. Algebraic Discrete Methods 6 (1985), no. 3, 394–405.

[4] Z.D. Bai & F. Hu, Asymptotic theorems for urn models with nonhomogeneous generating matrices. Stochastic Process. Appl. 80 (1999), no. 1, 87–101.

[5] Z.D. Bai, F. Hu & L.-X. Zhang, Gaussian approximation theorems for urn models and their applications. Ann. Appl. Probab. 12 (2002), no. 4, 1149–1173.

[6] F. Bergeron, P. Flajolet & B. Salvy, Varieties of increasing trees. In CAAP ’92 (Rennes, 1992), Lecture Notes in Comput. Sci. 581, Springer, Berlin, 1992, 24–48.

[7] P. Billingsley, Convergence of Probability Measures. Wiley, New York, 1968.

[8] B. Chauvin & N. Pouyanne, m-ary search trees when m ≥ 27: a strong asymptotics for the space requirements. Random Structures Algorithms 24 (2004), no. 2, 133–154.

[9] H.-H. Chern & H.-K. Hwang, Phase changes in random m-ary search trees and generalized quicksort. Random Structures Algorithms 19 (2001), no. 3-4, 316–358.

[10] L. Devroye, Limit laws for local counters in random binary search trees. Random Structures Algorithms 2 (1991), no. 3, 303–315.

[11] S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004), no. 2, 177–245.

[12] N.L. Johnson & S. Kotz, Urn models and their application. Wiley, New York, 1977.

[13] S. Karlin, A First Course in Stochastic Processes. Academic Press, New York, 1969.

[14] W. Lew & H.M. Mahmoud, The joint distribution of elastic buckets in multiway search trees. SIAM J. Comput. 23 (1994), no. 5, 1050–1074.

[15] H.M. Mahmoud, The size of random bucket trees via urn models. Acta Inform. 38 (2002), no. 11-12, 813–838.

[16] H.M. Mahmoud & R.T. Smythe, Asymptotic joint normality of outdegrees of nodes in random recursive trees. Random Structures Algorithms 3 (1992), no. 3, 255–266.

[17] H.M. Mahmoud, R.T. Smythe & J. Szymański, On the structure of random planeoriented recursive trees and their branches. Random Structures Algorithms 4 (1993), no. 2, 151–176.

[18] A. Meir & J.W. Moon, Recursive trees with no nodes of out-degree one. Congr. Numer. 66 (1988), 49–62.

[19] N.S. Na & A. Rapoport, Distribution of nodes of a tree by degree. Math. Biosci. 6 (1970), 313–329.

[20] D. Najock & C.C. Heyde, On the number of terminal vertices in certain random trees with an application to stemma construction in philology. J. Appl. Probab. 19 (1982), no. 3, 675–680.

[21] E. Seneta, Nonnegative matrices and Markov chains. 2nd ed. Springer-Verlag, New York, 1981.

[22] R.T. Smythe, Central limit theorems for urn models. Stochastic Process. Appl. 65 (1996), no. 1, 115–137.

[23] R.T. Smythe and H. Mahmoud, A survey of recursive trees. Theory Probab. Math. Statist. 51 (1995), 1–27.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se
URL: http://www.math.uu.se/~svante/