A functional limit law for the profile of plane-oriented recursive trees.

We give a functional limit law for the normalized profile of random plane-oriented recursive trees. The proof uses martingale convergence theorems in discrete and continuous-time. This complements results of Hwang (2007).

Keywords: plane-oriented recursive trees, random trees, profile of trees, preferential attachment, branching random walk, martingales, analysis of algorithms 

1 Introduction

We start with a combinatorical definition of plane-oriented recursive trees (PORTs). A PORT is a planar labelled tree with the property that labels along any path down from the root are increasing. Let [N.sub.n] be the number of these trees of size n with labels {1, ..., n}, see Figure 1(a) for an example. Considering the construction node by node, starting with the root labelled by 1, the i-th node has 2i - 3 possible positions, so we have

[N.sub.n] = (2n - 3)!! = n![2.sup.1-n][C.sub.n],

where [C.sub.n] denotes the Catalan numbers and n!! = n x (n - 2) ... 3 x 1 for n odd. A random PORT is obtained by choosing one of these [N.sub.n] trees uniformly among all. Recently Janson (Jan08) gave an easy coding of PORTs by stirling permutations and obtained results for the distribution of the number of certain types of nodes, in particular leaves.

The above construction suggests a more probabilistic approach, where the PORT is generated by an evolution starting with a single node. In each step we choose the position of the a node uniformly at random. Then, the parent node is chosen with probability proportional to its degree, more precisely the (i + 1)-th node is attached by an edge to an existing node having d children with probability (d + 1)/(2i - 1). This tells us that a random PORT is nothing but a random graph in the so-called preferential attachment model. These graphs have been widely studied recently due to the famous paper by Barabasi and Albert (BA99) on network models.

The probablistic construction of PORTs was first given by Szymanski (Szy87). If the parent of a new node is chosen uniformly among all then the resulting tree is known as the random recursive tree (RT). Therefore PORTs are also called nonuniform recursive trees, also the term heap-ordered trees is used (CN94a), (CN94b), (CN94c). The preferential attachment rule provides power-law distributions for the number of nodes of the same degree, see (Dur07). Other quantities like typical distances between two nodes or the diameter of the graph are currently under investigation, cf. (vdHHZ07), (vH07).

Properties. We are interested in the profile of random PORRs, i.e. the number of nodes at a given distance to the root. The profile has been investigated for many types of random trees like the binary (or m-ary) search tree (BST) or the recursive tree (RT), see (CDJH01), (CKMR05), (FHN06), (DJN08). It is necessary to distinguish between two types of nodes. Nodes, which are filled with labels are said to be internal, whereas possible free nodes where the next label can be placed are called external, see Figure 1(b) for an unlabelled PORT with internal and external nodes. We mainly deal with external nodes and denote the number of external nodes in a random PORT of size n on level k by [X.sub.k](n), the number of internal by [Y.sub.k](n). The processes [([X.sub.k](n)).sub.k [greater than or equal to] 0] and [([Y.sub.k](n)).sub.k [greater than or equal to] 0] are called external and internal profile of the random PORT respectively.

[FIGURE 1 OMITTED]

Obviously we have the following relation

[Y.sub.k-1](n) + [Y.sub.k](n) = [X.sub.k](n), k [greater than or equal to] 1.

Recursively, this leads to

[Y.sub.k](n) = [k.summation over (i=1)][(-1).sup.k-i][X.sub.i](n) + [(-1).sup.k].

Mahmoud (Mah92) found an expression for the expectation of the external profile

E[X.sub.k](n) = [2.sup.n-k] s(n, k)/(2n - 3)!!, (1)

where s(n, k) are the signless stirling numbers of the first kind, i.e. the number of permutations of size n which split in k cycles. Hwang gave asympotics for the expectation of the internal profile in (Hwa07). Similarly, for any constant C > 0, uniformly for 1 [less than or equal to] k [less than or equal to] C log n, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

with [z.sub.0] = 2k/log n. This result is essential for our purpose.

Let [H.sub.n] be the height of the tree, [H.sub.n] = max{k [greater than or equal to] 1 : [Y.sub.k](n) [greater than or equal to] 1}. By (Pit94) (see also (BG97)) it is known that

[H.sub.n]/log n [??] c, n [right arrow] [infinity],

where c is the unique positive solution of 2x - 2x log(2x) = -1, c [approximately equal to] 1.796. Note, that this result fits well with (2). In particular if k [greater than or equal to] (c + [epsilon]) log n for any [epsilon] > 0 then E[X.sub.k](n) = o(1). We also see that most external nodes lie at levels 1/2 log n + O([square root of log n]), each level having roughly 2n/[square root of [pi] log n] external nodes. From (Hwa07) it also follows that the degree of the root is about [square root of [pi]n].

Analysis of the profile. For the asymptotic behaviour of the profile of plane-oriented recursive trees, as in the cases of m-ary search trees or recursive trees, it has turned out that an appropriate scaling is the normalized profile

[X.sub.k](n)/E[X.sub.k](n), for k ~ [alpha] log n.

In our case [alpha] should be taken from [0, c]. For [alpha] = 1/2 a different scaling is needed to avoid a degenerate limit as in this case we have VarE[X.sub.k](n) = o[((E[X.sub.k](n)).sup.2]). Hwang showed in (Hwa07) that for k = 1/2 log n + [s.sub.n,k] with [absolute value of [s.sub.n,k]] [right arrow] [infinity] and [s.sub.n,k] = o(log n) convergence in distribution holds whereas for [s.sub.n,k] = O(1) there is no convergence to a fixed limit due to periodicities.

The following methods have been applied to derive limit results for the normalized profile of various random trees.

* martingales: Considering the so-called profil-polynomial, whose coefficients is the profile sequence, leads to a certain family of martingales. Convergence results for these martingales lead to convergence results for the normalized profile by an inversion formula. This method has first been applied in the BST case, see (CDJH01). Katona (Kat05) used similar arguments in the case of trees in the preferential attachment model, in particular PORTs and obtained asymptotic results for the width. Recently this method has been improved by an embedding in a continuous-time model (CKMR05). It gives the strongest results, e.g. functional a.s. limit equation in the full domain of interest. However it relies on martingales which only exist in a certain class of random trees.

* method of moments: By establishing recursive formulas for the moment series it is possible to show convergence of moments of any order (FHN06), (Hwa07). Typically the limit does not have moments of any order in the whole domain of interest and the approach leads to convergence of the marginal distributions. However, it is the only method so far capable to deal with the central range (here [alpha] = 1/2).

* contraction method: By conditioning on the size of certain subtrees it is possible to derive recursive formulas for internal and external profile. After rescaling it is possible to show that the limit distribution fulfills a certain fixed-point equation. This methods works quite well in the cases of BST and RT, however in the plane-oriented recursive tree it has not been applied successfully yet. At the end of the section we will discuss this in greater detail. Note that the contraction method has also been applied to the profil-polynomial in (DJN08).

Results. In (Hwa07), Hwang showed that for [alpha] [member of] [0, 1/2], there exists a random variable Y ([alpha]), such that for k/log n [right arrow] [alpha], we have

[Y.sub.k](n)/E[Y.sub.k](n) [??] Y([alpha]), n [right arrow] [infinity]

and with convergence of all moments. As mentioned before, for [alpha] > 1/2 the method of moments fails since the limit, if it exists, does not have moments of any order. This is very similar to BST or RT cases. Our main result is the following functional limit theorem.

Theorem 1 For every compact subset C [subset or equal to] (0, c) there exists a random, non-negative analytic function [M.sub.[infinity]] (z), z [member of] C with E[M.sub.[infinity]] (z) = 1 such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Unlike the cases of BST or RT there is no fixed-point equation known for the limit. The following theorem gives some information.

Theorem 2 Let 1 < p [less than or equal to] 2 and z [member of] [R.sup.+]. Then E[[absolute value of [M.sub.[infinity](z)].sup.p] < [infinity] if and only if

-1 + p(z + 1) - [z.sup.p] > 0.

In particular E[[absolute value of [M.sub.[infinity](z)].sup.p] < [infinity] for all p > 0 if z [less than or equal to] 1.

Recursive description. We condition on the size I(n) of the first subtree of the root, i.e. the subtree whose root is the second inserted node. This subtree and the remaining tree are again random PORTs, independent of each other. We have

[Y.sub.k](n) [??] [Y.sub.k-1]([I.sub.n]) + [Y.sup.*.sub.k](n - [I.sub.n]), (3)

where [([Y.sup.*.sub.k](n)).sub.k,n] are independent copies of [([Y.sub.k](n)).sub.k,n], both independent of I(n). As mentioned before, the contraction method has been applied to similar recursions for profiles of random trees successfully. Thereby, information is obtained by a fixed-point equation for the limit (after rescaling). However, in our case it is easy to see that

I(n) [??] I, n [right arrow] [infinity]

for some random variable I. So the size I(n) of the first subtree tends to obtain very small values which leads from (3) to a degenerated fixed-point equation. Such cases are typically beyond the scope of the contraction method, an exception being found in (NR04) where asymptotic normality of certain rescaled quantities of logarithmic size is investigated. Another way of decomposing the tree is to consider the leftmost subtree. Its size is of the same order as the size of the initial tree but unfortunately the remaining tree cannot be treated as a random PORT, basically because the root has too many children.

The paper is organized as follows: In Section 2 a slightly modified version of random PORTs is defined as a Markov chain and an embedding in continuous-time is given. Then our main ingredient, the random profile-polynomial, whose coefficients is the external profile sequence will be considered in both models. We follow the approach of (CKMR05). Based on this polynomial we will find a family of martingales and obtain convergence results for these by well-known properties in the branching random walk. Thereby we always take care for the relation between the discrete and continuous-time models. In Section 3 we will prove Theorem 1 by extracting the profile from the profile-polynomial via a Fourier inversion formula. Also Theorem 2 will be proven here.

2 Continuous-time model and martingales

In the paper we heavily rely on the homogeneous growth rule of the process and therefore modify the model slightly such that the evolution of the process is the same in each step.

We construct a version of the PORT-model as a Markov chain on the space of unlabelled planar trees. At time n = 0 start with one external node on level 0. In each step one external node becomes internal and three new external nodes are inserted according to the following rule: Pick one external node, say v uniformly at random among all and make it internal. Then add one external node as a child of v one level beneath, two external nodes as brothers of v at the same level and connect these with the parent of v one level above (if v is at the root level, brothers come without edges). Let [T.sub.n] be the Markov chain for this process. [partial derivative][T.sub.n] are the external nodes, [T.sub.n]\[partial derivative][T.sub.n] are internal. Obviously

[absolute value of [partial derivative][T.sub.n]] = 2n + 1, [absolute value of [T.sub.n]\[partial derivative][T.sub.n]] = n.

Again, we denote the number of external nodes on level k by [X'.sub.k],(n). This graph is obtained from the original random PORT by deleting the root with all its edges and shifting levels by one. Since we have [X.sub.k+1](n+1) = [X'.sub.k](n), it suffices to prove Theorem 1 for the modified model. This simplifies calculations and arguments in the following. Observe that (2) implies that for any constant C > 0, uniformly for 1 [less than or equal to] k [less than or equal to] C log n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

with [z.sub.0] = 2k/log n.

We also consider a continuous-time version of this process. At time t = 0 start with one living individual at position 0 on the real axis. Each individual lives for an Exp(1)-distributed lifetime, independent of any other individuals. After its death it gives birth to two children at the same position and one child one step right. Due to the lack of memory, each individual is equally likely to die next. This process is denoted by [([T.sub.t]).sub.t [greater than or equal to] 0]. The set of living individuals at time t is [partial derivative][T.sub.t].

Embedding. The counting process [N.sub.t] gives the number of living individuals at time t

[N.sub.t] = [absolute value of [partial derivative][T.sub.t]].

Let 0 = [[tau].sub.0] < [[tau].sub.1] < ... be the jump times of the continuous process

[[tau].sub.n] = inf{t : [N.sub.t] = 2n + 1}.

Obviously the jump intervals ([[tau].sub.n] - [[tau].sub.n-1]) are independent and satisfy [[tau].sub.n] - [[tau].sub.n-1] [??] Exp(2n - 1). In the following we consider positions of individuals as levels, dead individuals as internal nodes and living individuals as external nodes. Furthermore we draw an edge between an individual (or node) and its ancestor one level above (nodes on the root level are not connected). Then, since the jump times are independent of the shape of the tree, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [F.sub.t] and F(n) be the natural filtrations of [T.sub.t] and [T.sub.n], i.e. [F.sub.t] = [sigma]([T.sub.s] : s [less than or equal to] t), F(n) = [sigma]([T.sub.i] : i [less than or equal to] n).

[FIGURE 2 OMITTED]

Martingales--discrete case. In the analysis of the profile our main tool will be the so-called profile-polynomial. For z [member of] C let

[W.sub.n](z) = [summation over (k [greater than or equal to] 0)][X'.sub.k](n)[z.sup.k].

Its degree is the external height of the tree. Let [D.sub.n] be the depth of the n-th inserted node. By construction, we have [X'.sub.k](n + 1) = [X'.sub.k](n) + 1{[D.sub.n+1] [member of] {k - 1, k}}. This leads to the crucial observation, that

E[[W.sub.n+1](z)|[F.sub.n]] = 2n + 2 + z/2n + 1 [W.sub.n](z).

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then for z [member of] C\2[Z.sup.-]

[([M.sub.n](z) = [W.sub.n](z)/[C.sub.n](z)).sub.n [greater than or equal to] 0] (5)

is an F(n)-martingale with expectation 1. This type of martingale was first observed in the BST case by Jabbour-Hattab, see (JHOI).

Lemma 1 We have for n [greater than or equal to] 1 and z [member of] C\2[Z.sup.-]

[C.sub.n](z) = 2[square root of [pi]]/z[GAMMA](Z/2) [GAMMA](n + 1 + z/2)/[GAMMA](n + 1/2) = 2[square root of [pi]]/z[GAMMA](z/2) [n.sup.(z+1)/2] (1 + O (1/n))

uniformly on every compact subset of C\2[Z.sup.-].

Proof: The proof is based upon Stirling's formula. For all z [member of] C\[Z.sup.-] we have

[GAMMA](z) = [square root of 2[pi]][z.sup.z-1/2][e.sup.-z](1 + [THETA](1/z)),

for [absolute value of z] [right arrow] [infinity]. For convenience we set [alpha] = z/2. Thus, for n large enough,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By continuity we can choose the constant in the O-term uniformly on compact sets.

Remark: It is possible to compute the second order of the profile polynomial explicitly as in (CDJH01). Basically, [M.sub.n](z) is bounded in [L.sup.2] if [absolute value of z - 1] < [square root of 2]. In this domain the martingale converges in [L.sup.2] and following (CDJH01) the a.s. convergence is uniform on compact subsets.

Martingales--continuous case. The measure valued process

[[??].sub.t] = [summation over (u[member of][partial derivative][T.sub.t])] [[delta].sub.[absolute value of u]]

can be seen as a continuous-time branching random walk. Particles do not move and the offspring distribution Z equals 2[[delta].sub.0] + [[delta].sub.1] . The lifetime parameter [beta] is 1. It is well-known, see (Big92), that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with b([lambda]) = E [integral] [e.sup.-[lambda]x] dZ(x) is a [F.sub.t]-martingale with mean 1 for all [lambda] [member of] C. In our case this gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Substituting z = [e.sup.-[lambda]] we use the martingale

M(t, z) = [summation over (u[member of][partial derivative][T.sub.t])] [z.sup.[absolute value of u]] [e.sup.-t(z+1)] = [summation over (k [greater than or equal to] 0)] [[??].sub.t] ({k})[z.sup.k][e.sup.-t(z+1)].

Observe the analogy with (5), in particular [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Choosing z = 1 we see that [N.sub.t][e.sup.-2t] is an [F.sub.t]-martingale with mean 1. Since it is non-negative it converges a.s. Let [xi] := [lim.sub.t] [N.sub.t][e.sup.-2t]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a.s. we also have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

in particular

[[tau].sub.n]/log n [right arrow] 1/2 a.s.

We do not need more precise information about the asymptotics of [[tau].sub.n].

Martingale connection. Obviously there is an easy connection between the two martingales. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By construction the processes [C.sub.n](z) and [M.sub.n](z) are independent and satisfy

M([[tau].sub.n], z) = [C.sub.n](z)[M.sub.n](z). (7)

Furthermore it is easy to show that [C.sub.n](z) is a [bar.F](n)-martingale with mean 1, with [bar.F](n) = [sigma]([ [tau].sub.1], ..., [[tau].sub.n]) and by Lemma 1 and (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Convergence of martingales. We turn to the fundamental question in which domain of the complex plane the martingales converge a.s. and in [L.sup.1]. The [L.sup.1]-convergence is important to ensure that the limit is non-degenerate.

Theorem 3 For 1 < p [less than or equal to] 2, let [V.sub.p] = {z : [sup.sub.t]E[[absolute value of M(t, z)].sup.p] < [infinity]}. Then [V.sub.p] = {z : f(z, p) > 0} with

f(z, p) := -1 + p(R(z) + 1) - [[absolute value of z].sup.p].

If V = [[union].sub.1]<p [less than or equal to] 2] [V.sub.p] then M(t, z) and [M.sub.n](z) converge uniformly on compact sets of V, a.s. and in [L.sup.1]. We denote the limits by M([infinity], z) and [M.sub.[infinity]] (z).

Proof: The continuous-time result is Theorem 6 in (Big92). For the reduction to the discrete case we proceed as in (CKMR05). By (7) we have

[C.sub.N](z)([M.sub.n](z) - [M.sub.N] (z)) = E[M([[tau].sub.n], z) - M ([[tau].sub.N], z)[absolute value of [??](N)]

for n [greater than or equal to] N. Let K [subset of equal to] V compact and note that [C.sub.N] (z) [greater than or equal to] 0 for z [member of] K. Taking the absolute value and supremum gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By E[C.sub.N](z) = 1 and independence of [C.sub.N](z) and [M.sub.n](z), taking expectation yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now let [L.sub.N] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then it follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The continuous-time result gives [L.sub.N] [right arrow] 0 a.s. By the triangle inequality we can bound [L.sub.N] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the proof of proposition 3 in (BR) we have E[L.sub.0] < [infinity]. The dominated convergence theorem gives the uniform [L.sup.1] convergence of the discrete martingale. The uniform almost sure convergence follows, since [([sup.sub.z[member of]K] [absolute value of [M.sub.n](z) - [M.sub.N] (z)]).sub.n [greater than or equal to] N] is a non-negative submartingale.

Remark. By computing [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we see that (0, 2c) is included in the domain of convergence and that there is no [L.sup.p] boundedness for z [greater than or equal to] 2c. It is possible to show [L.sup.p] boundedness of the martingale in the discrete case for real z [member of] [V.sub.p] directly by induction using

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [D.sub.n] is the depth of the n-th inserted node. This can be strengthened to an open connected subset contained in [V.sub.p]. If there exists a continuous version of the limit then uniform convergence can be obtained by standard arguments, see (CDJH01) and (JLCN73). For the domain of [L.sup.2] convergence this can be done by the holomorphy of the covariance function of the profil-polynomial as in (CDJH01). It is not clear how to extend this to the case 1 < p < 2.

Due to (7) and (8) we also have the limit martingale connection

[M([infinity], z) = 2[square root of [pi]]/z[GAMMA](z/2) [[xi].sup.(z+1)/2] [M.sub.[infinity]](z), a.s. (9)

By the [L.sup.1] convergence of the martingale M(t, z) we know that M([infinity], z) [member of] [L.sup.p] if and only if M(t, z) is bounded in [L.sup.p]. Due to the limit martingale connection (9) and the fact that [xi] [member of] [L.sup.2] and is independent of [M.sub.[infinity]](z) the same holds in the discrete case. This proves the following corollary.

Corollary 1 For 1 < p [less than or equal to] 2, E[[absolute value of M([infinity], z)].sup.p] < [infinity] if and only if z [member of] [V.sub.p], where [V.sub.p] is defined in Theorem 3. The same holds for [M.sub.[infinity]](z).

The following Theorem treats convergence of the martingales in the remaining case.

Theorem 4 For z [greater than or equal to] 2c we have [lim.sub.t] M(t, z) = [lim.sub.n] [M.sub.n](Z) = 0 a.s.

Proof: The result in the continuous-time model is again in (Big92). Use the above limit martingale connection to deduce the same result in the discrete case.

3 Proof of the main results

It is possible to show a weaker form of Theorem 1 only in the [L.sup.2] domain of convergence without embedding as in (CDJH01). For an extension to the general case [L.sup.p]-bounds for the profil-polynomial are needed not only in a neighbourhood of the real axis but in a larger domain of the complex plane. At the moment it is not clear how to get these bounds directly. Therefore we proceed as in (CKMR05). First we have to get back the profile from the polynomial by a Fourier inversion formula. By (2) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for 0 [less than or equal to] x < 2[pi]. This gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next we need to substitute the martingale term in the integrand by its limit. This can be done with the following Lemma which is a continuous-time version of Lemma 5 in (Big92). As indicated in (CKMR05) it can be proven by replacing Lemma 6 there with the property that for

[beta](t, z) = (M(t, z) - 1)[e.sup.t(z+1)],

it holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where f(z, p) is defined in Theorem 3. This follows from section 2.4 in (Ber03).

Lemma 2 For any compact subset C of (0, 2c) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Combining these two results yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the o-term being uniform in z [member of] C. Cauchy's integral formula gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Take z = 2k/log n. A reformulation gives

[[??].sub.t]({k}) = [z.sup.-k][e.sup.t(z+1)] (M([infinity], z)II(tz)({k}) + o(1)),

where II([lambda]) is the Poisson-distribution with parameter [lambda]. Using a local limit theorem for the Poisson-distribution, see (Pet75)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with

[A.sub.t](k, z) = [e.sup.t(z+1)]/[z.sup.k][square root of 2[pi]tz],

and the o-term being uniform in z [member of] C. Remember [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] so we use the stopping times [T.sub.n] to return to the discrete profile. Due to (6) we have log n - 2[[tau].sub.n] [right arrow] log [xi] and therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By continuity of M([infinity], z) it follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The result follows by the asymptotics of the expectation of [X.sub.k](n) in (4), the limit martingale connection (9) and (6). This proofs Theorem 1.

Theorem 2 follows from corollary 1.

Acknowledgements: I thank my advisor Ralph Neininger for his support.

References

[BA99] A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, October 1999.

[Ber03] Jean Bertoin. The asymptotic behavior of fragmentation processes. J. Eur. Math. Soc. (JEMS), 5(4):395-416,2003.

[BG97] J.D. Biggins and D.R. Grey. A note on the growth of random trees. Stat. Probab. Lett., 32(4):339-342, 1997.

[Big92] J.D. Biggins. Uniform convergence of martingales in the branching random walk. Ann. Probab., 20(1):137-151, 1992.

[BR] J. Bertoin and A. Rouault. Addititive martingales and probability tilting for homogeneous fragmentations, http://www.proba.jussieu.fr/mathdoc/textes/PMA-808.pdf.

[CDJH01] Brigitte Chauvin, Michael Drmota, and Jean Jabbour-Hattab. The profile of binary search trees. Ann. Appl. Probab., 11(4):1042-1062, 2001.

[CKMR05] B. Chauvin, T. Klein, J.-F. Marckert, and A. Rouault. Martingales and profile of binary search trees. Electron. J Probab., 10(12):420-435, 2005.

[CN94a] Wen-Chin Chen and Wen-Chun Ni. Heap-orderd trees, 2-partitions and continued fractions. Eur. J Comb., 15(6):513-517, 1994.

[CN94b] Wen-Chin Chen and Wen-Chun Ni. Internal path length of the binary representation of heap-ordered trees. Inf. Process. Lett., 51(3):129-132, 1994.

[CN94c] Wen-Chin Chen and Wen-Chun Ni. On the average altitude of heap-ordered trees. Int. J Found. Comput. Sci., 5(1):99-109, 1994.

[DJN08] Michael Drmota, Svante Janson, and Ralph Neininger. A functional limit theorem for the profile of search trees. Ann. Appl. Probab., 18(1):288-333, 2008.

[Dur07] Rick Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics 20. Cambridge: Cambridge University Press. x, 212 p. , 2007.

[FHN06] Michael Fuchs, Hsien-Kuei Hwang, and Ralph Neininger. Profiles of random trees: Limit theorems for random recursive trees and binary search trees. Algorithmica, 46(3):367-407, 2006.

[Hwa07] Hsien-Kuei Hwang. Profiles of random trees: Plane-oriented recursive trees. Random Struct. Algorithms, 30(3):380-413, 2007.

[Jan08] Svante Janson. Plane recursive trees, stirling permutations and an urn model, http://www.citebase.org/abstract?id=oai:arXiv.org:0803.1129. 2008.

[JH01] Jean Jabbour-Hattab. Martingales and large deviations for binary search trees. Random Struct. Algorithms, 19(2):112-127, 2001.

[JLCN73] Anatole Joffe, Lucien Le Cam, and Jacques Neveu. Sur la loi des grands nombres pour des variables aleatoires de Bernoulli attachees a un arbre dyadique. C. R. Acad. Sci. Paris. Ser. A, 277:963-964, 1973.

[Kat05] Zsolt Katona. Width of a scale-free tree. J. Appl. Probab., 42(3):839-850, 2005.

[Mah92] Hosam M. Mahmoud. Distances in random plane-oriented recursive trees. J Comput. Appl. Math., 41(1-2):237-245, 1992.

[NR04] Ralph Neininger and Ludger Ruschendorf. On the contraction method with degenerate limit equation. Ann. Probab., 32(3b):2838-2856, 2004.

[Pet75] V.V. Petrov. Sums of independent random variables. Translated from the Russian by A. A. Brown. Berlin: Akademie-Verlag. X, 348 S. M 92.00, 1975.

[Pit94] Boris Pittel. Note on the heights of random recursive trees and random m-ary search trees. Random Struct. Algorithms, 5(2):337-347, 1994.

[Szy87] Jerzy Szymanski. On a nonuniform random recursive tree. Random graphs '85, Lect. 2nd Int. Semin., Poznan/Pol. 1985, Ann. Discrete Math. 33, 297-306 (1987)., 1987.

[vdHHZ07] Remco W. van der Hofstad, Gerard Hooghiemstra, and Dmitri Znamenski. Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab., 12:703-766, 2007.

[vH07] Remco van der Hofstad and Gerard Hooghiemstra. Diameters in preferential attachment models, 2007.

Henning Sulzbach (1)

(1) Institute for Mathematics J. W. Goethe-University Frankfurt a. M. 60054 Frankfurt a. M. Germany