THE WIENER INDEX OF SIMPLY GENERATED RANDOM TREES

SVANTE JANSON

Abstract. Asymptotics are obtained for the mean, variance and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton– Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion.

The methods include both Aldous’ theory of the continuum random tree and analysis of generating functions.

1. Introduction

The Wiener index W (G) of a connected graph G is the sum of all the distances between pairs of vertices of G. This index was introduced by the chemist Wiener [27] in the study of relations between the structure of organic compounds and their properties. It has since been studied extensively by both chemists and mathematicians, especially for trees; see the survey [8] for many results and references.

There has been comparatively little work on the Wiener index of random trees. A pioneering paper by Entringer, Meir, Moon and Székely [10] gives asymptotics for the mean 𝔼 W (T_{n}) as n → ∞, where T_{n} is a random tree of order n with the distribution given by a simply generated family of trees. (For some special simply generated families, exact expressions for 𝔼 W (T_{n}) were derived too.) Recall that the simply generated families include several important families, for example binary trees, ordered trees and unordered labelled trees. Moreover, the simply generated random trees are the same as the conditioned Galton–Watson trees [2]. See further Section 2.

It was shown in [10] that for simply generated families of trees, 𝔼 W (T_{n}) ∼ Kn^{5/2} for a constant K depending on the family, see further Theorem 3.4 below. In other words, the average distance between two vertices in an average tree is of the order n^{1/2}.

More recently, Neininger [22] took a another pioneering step and obtained asymptotics for both the mean and variance as well as for the distribution of the Wiener index of two other types of random trees, viz. random recursive trees and binary search trees. These random trees are more compact than the simply generated trees; they have average distances of the order log n and thus 𝔼 W (T_{n}) is of the order n^{2} log n. Neininger [22] uses the contraction method and the limit distributions are characterized by a fixed point property from which moments can be pumped.

Date: May 30, 2002.

We are not aware of any paper besides [22] where distributional properties of the Wiener index is studied for some families of random trees. The purpose of the present paper is to prove corresponding results on variance, higher moments and asymptotic distribution for the simply generated families considered by [10].

The convergence in distribution is an almost immediate consequence of Aldous’s theory of the continuum random tree [2, 3], see Sections 3 and 4 for details. The asymptotic moments are found in Section 5 by a generating function approach related to the arguments in [10], but expressed using subcritical Galton–Watson trees. Moment convergence follows immediately under some extra conditions, see Remark 3.5; we give a general proof in Section 6 by a related generating function method. (It might be possible to combine the arguments of Sections 5 and 6 and prove both results together, but we think that the result would be more complicated. Moreover, we find it interesting to compare the two related but differently formulated arguments in the two sections.) Finally, some possible extensions are mentioned in Section 7.

2. Simply generated trees

A simply generated family of trees is defined by a sequence φ_{k}, k ≥ 0, of non-negative numbers (with φ_{0} > 0); each ordered tree T is given a weight ∏_{v} φ_{d(v)}, where v ranges over the vertices of T and d(v) is the outdegree (number of children) of v [21]. The corresponding simply generated random tree T_{n} is defined by choosing a tree of order n with probability proportional to its weight (provided that there is some tree of order n with positive weight).

It is well known [2] that the simply generated random trees obtained in this way are (except for some extreme cases usually not considered) the same as the random conditioned Galton–Watson trees, obtained as the family tree of a Galton–Watson process conditioned on a given total size. More precisely, suppose that the generating function φ(z) := ∑_{k} φ_{k}z^{k} converges for some z > 0, and that X is an integer valued random variable with the distribution ℙ(X = k) = φ_{k}z^{k}/φ(z). Then the conditioned Galton–Watson tree given by the offspring distribution X is easily seen to coincide with the simply generated random tree defined by (φ_{k}), regardless of the choice of z. (We make a slight abuse of notation here, since X is a random variable and not a distribution, but it is only the distribution of X that matters.) Conversely, given a conditioned Galton–Watson tree with an offspring distribution X, we can take φ_{k} = ℙ(X = k).

Let R ≤ ∞ be the radius of convergence of φ(z). Usually (for example in [10]), it is assumed that there exists a τ with 0 < τ < R and τφ′(τ) = φ(τ); taking z = τ above, this is equivalent to 𝔼 X = 1, so we are dealing with a critical Galton–Watson process. Moreover, then the variance of X, which appears as a scale factor in the results below, is given by σ^{2} := Var(X) = τ^{2}φ′′(τ)/φ(τ). In this case we also have an exponential moment 𝔼 e^{αX} < ∞ for some α > 0. We are mainly interested in this case, but we will be somewhat more general and only demand a finite second moment. (This means in the simply generated setting that we allow τ = R, provided φ′′(τ) is finite.)

Many combinatorially interesting families are simply generated. Some examples to which our results apply are the following; for further examples see e.g. [2, 7].

(i) Ordered (=plane) trees. ℙ(X = k) = 2^{−k−1}; σ^{2} = 2.

(ii) Unordered labelled trees (Cayley trees). X ∼ Po(1); σ^{2} = 1.

(iii) Binary trees. X ∼ Bi(2, 1/2); σ^{2} = 1/2.

(iv) Strict (full) binary trees. ℙ(X = 0) = ℙ(X = 2) = 1/2; σ^{2} = 1.

(v) Unary-binary trees. ℙ(X = 0) = ℙ(X = 1) = ℙ(X = 2) = 1/3; σ^{2} = 2/3.

(vi) m-ary trees. X ∼ Bi(m, 1/m); σ^{2} = 1 − 1/m.

3. Results

The Wiener index is defined for unrooted trees; the trees studied in this paper are rooted, but the root is ignored. For rooted trees T we also define the internal path length P (T) = P (T, o) := ∑_{v∈T} d(o, v), where o is the root, d is the distance in T and v ranges over the vertices in T. Note that

W (T) := \frac{1}{2} ∑_{v,w∈T} d(v, w) = \frac{1}{2} ∑_{w∈T} P (T, w),  (3.1)

so (2/n)W (T) is the average of P (T) after a random rerooting.

Returning to a fixed root o, let v ∧ w denote the last common ancestor of two vertices v and w, i.e. the branch point where the paths from o to v and w diverge. Then the path from v to w consists of the parts of these paths beyond v ∧ w, and thus

d(v, w) = d(v, v∧w)+d(v∧w, w) = d(v, o)−d(v∧w, o)+d(w, o)−d(v∧w, o).

Consequently, if n = |T |,

W (T) := \frac{1}{2} ∑_{v,w∈T} d(v, w) = n ∑_{v∈T} d(v, o) − ∑_{v,w∈T} d(v ∧ w, o).

We define, for any rooted tree T with root o,

Q(T) := ∑_{v,w∈T} d(v ∧ w, o)

(summing over ordered pairs v, w). Thus, with n = |T |,

W (T) = nP (T) − Q(T).  (3.2)

Hence, in order to study the joint distribution of W and P, we may instead study the joint distribution of P and Q, which will be convenient below.

The internal path length P has been studied by many authors. In particular, Aldous [2, 3] has shown that n^{−3/2}P converges in distribution to twice the Brownian excursion area. Our first theorem is a simple extension of this to include the Wiener index (and Q).

Theorem 3.1. There exists a triple of positive random variables (ξ, η, ζ), with ζ = ξ − η, such that if T_{n} is a conditioned Galton–Watson tree of order n defined by an offspring distribution X with 𝔼 X = 1 and 0 < σ^{2} := Var X < ∞, then, as n → ∞,

(n^{−3/2}P (T_{n}), n^{−5/2}Q(T_{n}), n^{−5/2}W (T_{n})) →^{d} (σ^{−1}ξ, σ^{−1}η, σ^{−1}ζ).

The random variables (ξ, η, ζ) can be constructed from a normalized Brownian excursion e(t), 0 ≤ t ≤ 1, by

ξ = 2 ∫_{0}^{1} e(t) dt,
η = 4 ∫∫_{0<s<t<1} min_{s≤u≤t} e(u) ds dt,

ζ = ξ − η = 2 ∫∫_{0<s<t<1}(e(s) + e(t) − 2 min_{s≤u≤t} e(u)) ds dt.

A proof following Aldous [2] is given in Section 4.

Remark 3.2. Alternatively, we can use another version of Aldous’s limit result, which is intuitively simple but technically more complicated [3, Theorem 23, Remark 1]: There exist measure- and set-representations μ_{n} and S_{n} of rescaled T_{n} such that (μ_{n}, S_{n}) →^{d} (μ, S), where (μ, S) is the Brownian continuum random tree (alias compact continuum random tree [2]), see [3] for definitions. Since σn^{−1/2}P (T_{n}) = n ∫ d(0, x) dμ_{n}(x) and σn^{−1/2}W (T_{n}) = \frac{1}{2}n^{2} ∫∫ d(x, y) dμ_{n}(x) dμ_{n}(y), it follows immediately that Theorem 3.1 holds with ξ = ∫ d(0, x) dμ(x) and ζ = \frac{1}{2} ∫∫ d(x, y) dμ(x) dμ(y).

We may thus interpret ζ as the Wiener index of the continuum random tree, just as ξ is its internal path length.

The moments of the Brownian excursion area ξ/2 were found by Louchard [19] using stochastic calculus [18]. We have not been able to find the moments of η and ζ by similar methods, but encourage the adventurous reader to try to do so. Instead, we will in Section 5 use Theorem 3.1 and calculation for binary trees to obtain the following result. We use ≐ for approximate equality.

Theorem 3.3. The moments of (ξ, η, ζ) can be obtained from ζ = ξ −η and the formula

𝔼 ξ^{k}η^{l} = \frac{k! l! \sqrt{π}}{2^{(5k+7l−4)/2}Γ((3k + 5l − 1)/2)}ω_{kl}^{∗}  (3.3)

where the numbers ω_{kl}^{∗} are defined by ω_{10}^{∗} = ω_{01}^{∗} = 1 and the recursion relation

ω_{k,l}^{∗} = 2(3k + 5l − 4)ω_{k−1,l}^{∗} + 2(3k + 5l − 6)(3k + 5l − 4)ω_{k,l−1}^{∗}

+ ∑ ∑_{0<i+j<k+l} ω_{i,j}^{∗}ω_{k−i,l−j}^{∗}, (3.4)

with ω_{kl}^{∗} = 0 when k < 0 or l < 0.

In particular, the first and second moments are given by

𝔼 ξ = \sqrt{π/2}  𝔼 η = \sqrt{π/8}  𝔼 ζ = \sqrt{π/8}
𝔼 ξ^{2} = \frac{5}{3}  𝔼 η^{2} = \frac{7}{15}  𝔼 ζ^{2} = \frac{2}{5}
𝔼 ξη = \frac{13}{15}  𝔼 ξζ = \frac{4}{5}  𝔼 ηζ = \frac{2}{5}

and as a consequence

Var(ξ) = \frac{10 − 3π}{6} ≐ 0.0959,
Var(η) = \frac{56 − 15π}{120} ≐ 0.0740,
Var(ζ) = \frac{16 − 5π}{40} ≐ 0.0073,
Cov(ξ, ζ) = \frac{16 − 5π}{20} ≐ 0.0146,
Corr(ξ, ζ) = \sqrt{\frac{48 − 15π}{50 − 15π}} ≐ 0.5519.

This leads to moment asymptotics for P, Q and W. (For the mean, we recover the result by [10].)

Theorem 3.4. Let T_{n} be as in Theorem 3.1. Then all mixed moments converge in Theorem 3.1, i.e., for any k, l, m ≥ 0

𝔼(P (T_{n})^{k}Q(T_{n})^{l}W (T_{n})^{m}) ∼ σ^{−(k+l+m)}n^{(3k+5l+5m)/2} 𝔼(ξ^{k}η^{l}ζ^{m}). (3.5)

In particular,

𝔼 W (T_{n}) ∼ \sqrt{\frac{π}{8σ^{2}}} n^{5/2},

𝔼 W (T_{n})^{2} ∼ \frac{2}{5σ^{2}} n^{5}.

Remark 3.5. In view of Theorem 3.1, (3.5) is equivalent to uniform integrability of n^{−(3k+5l+5m)/2}P (T_{n})^{k}Q(T_{n})^{l}W (T_{n})^{m} for n ≥ 1 and any fixed k, l, m. Since Q(T_{n}) ≤ nP (T_{n}) and W (T_{n}) ≤ nP (T_{n}) by (3.2), this follows if n^{−3k/2}P (T_{n})^{k}, n ≥ 1, is uniformly integrable for every fixed k. Consequently, (3.5) holds for all k, l, m ≥ 0 if it holds for all k ≥ 0 and l = m = 0. This is further, by a standard fact, equivalent to

sup_{n} n^{−3k/2} 𝔼 P (T_{n})^{k} < ∞ for every k ≥ 1.  (3.6)

In the case that X has moments of all orders, Takács [24, 25] has proved (3.6) (and moment convergence), which thus implies (3.5). For completeness, we give a proof of (3.6) assuming only 𝔼 X^{2} < ∞ in Section 6.

Remark 3.6. Since P (T_{n}) ≤ nH(T_{n}), where H := max_{v} d(o, v) is the height, it is evidently sufficient for (3.6) and thus for (3.5) that

sup_{n} n^{−k/2} 𝔼 H(T_{n})^{k} < ∞ for every k ≥ 1.  (3.7)

Under the assumption sup_{k} φ_{k} < ∞, this was proved (in the form of moment convergence) by Flajolet and Odlyzko [11]; see also [12, Theorem 2]. More generally, a proof of (3.7) when X has an exponential moment is given by Drmota and Marckert [9]. It seems to be unknown whether (3.7) holds assuming only a second moment of X.

Remark 3.7. The limit distributions found here are quite different from the ones found by Neininger [22] for random recursive trees and binary search trees. For one thing, the limit distributions in [22] are supported on the whole real line, while the ones found here are supported on a half-line.

Remark 3.8. The fact that 𝔼 ζ = 𝔼 η = \frac{1}{2} 𝔼 ξ follows easily by symmetry, as remarked in [10] for the corresponding statement there. Indeed, consider random unordered labelled trees. Since a random rerooting gives a tree with the same distribution, (3.1) yields in this case, for every n,

𝔼 W (T) = \frac{n}{2} 𝔼 P (T),

and the moment convergence in Theorem 3.4 implies 𝔼 ζ = \frac{1}{2} 𝔼 ξ.

Similarly, 𝔼 ζ^{2} = \frac{1}{2} 𝔼 ξζ and, more generally, 𝔼 ζ^{k+1} = \frac{1}{2} 𝔼 ξζ^{k} for any k ≥ 0.

Remark 3.9. It is well known that the moment generating function (Laplace transform) 𝔼 e^{tξ} is finite for every t. (For example, this follows easily from (3.8) below and (3.3).) Since 0 ≤ η ≤ ξ and 0 ≤ ζ ≤ ξ, also 𝔼 e^{tη} and 𝔼 e^{tζ} are finite for every t. It follows that the distributions of these variables are determined by their moments, and that the joint distribution is determined by the mixed moments in Theorem 3.3.

Remark 3.10. We have to define ω_{00}^{∗} = −1/2 in order for (3.3) to hold for k = l = 0 too. Apart from this exceptional case, the numbers ω_{kl}^{∗} are

\begin{matrix}k, l & 0 & 1 & 2 & 3 & 4 \\ 0 & −1/2 & 1 & 49 & 9800 & 4412401 \\ 1 & 1 & 26 & 4308 & 1752652 & 1313146320 \\ 2 & 5 & 776 & 300966 & 217588128 & 252515984662 \\ 3 & 60 & 27052 & 20324608 & 23856758216 & 40646627470976 \\ 4 & 1105 & 1086576 & 1406019822 & 2510422982912 & 6022491449087070 \\ 5 & 27120 & 49568684 & 101869846464 & 263304392184360 & 860045720189315072 \end{matrix}

Table 1. The constants ω_{kl}^{∗}.

positive integers by (3.4) and induction. These numbers are tabulated in Table 1 for small k and l. One can see that they grow fairly rapidly.

The formula for the moments can be written in several ways. For example, combining (3.3) and (3.4), we obtain a recursion formula for the moments directly, without the need for the constants ω_{kl}^{∗}; this recursion formula is somewhat more complicated, however, and we leave it to the reader. We have chosen the version above because the recursion is fairly simple and the numbers are integers. Moreover, the numbers ω_{k0}^{∗} are the same as ω_{k}^{∗} in Flajolet, Poblete and Viola [13], where ξ is studied in another context. (They use the normalization \sqrt{2}ξ, called the Airy distribution in [13].) In particular, [13] gives recursions equivalent to the case l = 0 of (3.4). The Brownian excursion area \frac{1}{2}ξ appears also in several other combinatorial problems, see again [13] and the references cited there. We do not know any similar other results involving η or ζ.

There is a simple connection, discovered by Spencer [23] and Aldous [4], between the moments of ξ and Wright’s constants in the enumeration of connected graphs with n vertices and n + k edges [28]. In fact, ρ_{k} and σ_{k} in

[28] are given by ρ_{k−1} = 𝔼(ξ/2)^{k}/k! and ω_{k0}^{∗} = 2^{2k}σ_{k−1} (the latter can be obtained by comparing the recursion for σ_{k} in [28] to (3.4)). The well-known asymptotics for Wright’s constants, see [5], [6], [26], [14, §8], which can be expressed as, for k → ∞,

σ_{k} ∼ \frac{1}{2π} (\frac{3}{2})^{k+1}k!

thus yields

ω_{k0}^{∗} ∼ \frac{1}{2π} 6^{k}(k − 1)!.  (3.8)

It would be interesting to find similar asymptotics for ω_{kl}^{∗}, l > 0, as k or l or both tend to ∞, or asymptotics of 𝔼 ζ^{k}. Numerical calculations suggest

ω_{0l}^{∗} ∼ C50^{l}(l − 1)!^{2},

with C ≐ 0.01962 ≐ 1/50.9664, but we have no proof of this, nor an identification of C (if it exists).

4. Convergence in distribution

Proof of Theorem 3.1. Consider a random simply generated tree T_{n} and its depth-first walk (or search-depth process [2, 3]) f : {0, 1, …, 2n} → [0, ∞) with f(0) = f(2n) = 0, and extend f to the interval [0, 2n] by linear interpolation. Rescale f to V (t) := σn^{−1/2}f(2nt). This is a random function in C[0, 1], and Aldous [3, Theorem 23 with Remark 2] has shown that, in C[0, 1] with its usual topology,

V (t) →^{d} 2e(t).  (4.1)

Each vertex v ∈ T_{n}, except the root o, has an edge to its parent. This edge is traversed twice by the depth-first walk, say on the intervals I_{1v} = [i_{1v} −1, i_{1v}] and I_{2v} = [i_{2v}, i_{2v} +1] where i_{1v} ≤ i_{2v}; we have f(i_{1v}) = f(i_{2v}) = d(v, o). Moreover, f(x) > d(v, o) on (i_{1v}, i_{2v}); this is the interval where the depth-first walk visits the descendants of v. For v = o we define i_{1o} = 1 and i_{2o} = 2n − 1 and have the same results. The intervals {I_{jv}}_{j=0,1, v∈I_{n}} form a partition of [0, 2n], and ⌈f(x)⌉ = d(v, o) when x ∈ I_{jv} (except at some endpoints).

Consider first P (T_{n}), essentially repeating Aldous [2]. We have

∫_{0}^{2n}⌈f(x)⌉ dx = ∑_{j=0}^{1} ∑_{v∈T_{n}} d(v, o) = 2P (T_{n})

so

P (T_{n}) = \frac{1}{2} ∫_{0}^{2n}⌈f(x)⌉ dx = \frac{1}{2} ∫_{0}^{2n} f(x) dx + O(n)

and thus

σn^{−3/2}P (T_{n}) = \frac{1}{2n} ∫_{0}^{2n} V (\frac{x}{2n}) dx + O(n^{−1/2}) = ∫_{0}^{1} V (t) dt + o(1).

Consequently, (4.1) yields the desired result

σn^{−3/2}P (T_{n}) →^{d} ∫_{0}^{1} 2e(t) dt.  (4.2)

Next, we turn to Q. In the remainder of the proof we, for convenience, define [x, y] := [y, x] when x > y. In other words, [x, y] always denotes the interval [min(x, y), max(x, y)].

If u and v are two vertices in T_{n}, then for any j, k ∈ {1, 2},

d(u ∧ v, o) = min_{x∈[i_{ju},i_{kv}]} f(x).

This is easily verified by separately considering the three cases (i) u ∧ v = u, i.e. v is a descendant of u; (ii) u ∧ v = v, i.e. u is a descendant of v; (iii) neither of these holds.

Hence, for any j, k ∈ {1, 2},

∫∫_{I_{ju}×I_{kv}} min_{x∈[y,z]} f(x) dy dz = d(u ∧ v, o) + O(1)

and summing over all j, k, u, v we obtain

∫_{0}^{2n} ∫_{0}^{2n} min_{x∈[y,z]} f(x) dy dz = 4Q(T_{n}) + O(n^{2})

and so

σn^{−5/2}Q(T_{n}) = (2n)^{−2} ∫_{0}^{2n} ∫_{0}^{2n} min_{x∈[y,z]} V (2nx) dy dz + O(n^{−1/2})

= ∫_{0}^{1} ∫_{0}^{1} min_{u∈[s,t]} V (u) ds dt + O(n^{−1/2})

= 2 ∫∫_{0<s<t<1} min_{u∈[s,t]} V (u) ds dt + o(1).

Hence (4.1) implies

σn^{−5/2}Q(T_{n}) →^{d} 4 ∫∫_{0<s<t<1} min_{u∈[s,t]} e(u) ds dt.

Moreover, this holds jointly with (4.2), and Theorem 3.1 follows, using also (3.2). □

Remark 4.1. In the case 𝔼 e^{αX} < ∞ for some α > 0, a simpler proof of (4.2) has been given by Marckert and Mokkadem [20]. Moreover, [20] also shows convergence in this case of the height process to a Brownian excursion. More precisely, if h(i) := d(v_{i}, o) where v_{1}, …, v_{n} are the vertices of T_{n} in the order they appear in the depth-first walk, then σn^{−1/2}h(nt) →^{d} 2e(t).

We can argue as above using the height process instead of the depth-first walk; this is slightly simpler since each vertex corresponds to one interval instead of two. However, it seems to be unknown whether the height process converges assuming only a second moment on X, so this argument does not (yet?) prove Theorem 3.1 in full generality.

5. Moments

We calculate the moments of ζ by calculating the asymptotics of the moments of W for some simply generated family, applying Theorem 3.4. We may choose any family for which Theorem 3.4 applies; we find it most convenient to study full binary trees, i.e. trees where all internal nodes have degree 2; these are the conditioned Galton–Watson trees obtained with the offspring distribution ℙ(X = 0) = ℙ(X = 2) = 1/2. Note that 𝔼 X = 1 and σ^{2} = Var X = 1, and thus (n^{−3/2}P (T_{n}), n^{−5/2}Q(T_{n})) →^{d} (ξ, η) by Theorem 3.1. (Similar calculations can be done for e.g. binary trees or unordered trees.)

We obtain asymptotics of moments of P (T_{n}) and Q(T_{n}) by studying the corresponding subcritical Galton–Watson tree, defined by the offspring distribution ℙ(X = 2) = p and ℙ(X = 0) = 1 − p with 0 < p < 1/2. We take p = (1 − δ)/2, with 0 < δ < 1, and let ℙ_{δ} and 𝔼_{δ} denote probability and expectation for this Galton–Watson tree T = T_{δ}.

Let b_{n} be the number of full binary trees of order n. Note that the trees all have odd order, and thus b_{n} = 0 when n is even. Consequently, we restrict n to odd numbers in this section. (It is well known that b_{2k+1} is the Catalan number (2k)!/(k! (k + 1)!), see e.g. [15], but we do not need that.)

Let N := |T |. A full binary tree with n = 2k + 1 vertices has k vertices with 2 children and k + 1 with none. Hence

\begin{aligned}ℙ_{δ}(N = 2k + 1) & = b_{2k+1}p^{k}(1 − p)^{k+1} = 2^{−(2k+1)}b_{2k+1}(1 − δ)^{k}(1 + δ)^{k+1} \\ & = 2^{−(2k+1)}b_{2k+1}(1 − δ^{2})^{k}(1 + δ). \end{aligned}

We let in this section Z = Z(T) denote an arbitrary functional of the trees such that |Z(T)| ≤ C|T |^{k} for some C and k (to guarantee that all sums below converge). If z_{n} := 𝔼 Z(T_{n}) we have

𝔼_{δ} Z = ∑_{n} ℙ_{δ}(N = n)z_{n} = ∑_{k} 2^{−(2k+1)}b_{2k+1}z_{2k+1}(1 − δ^{2})^{k}(1 + δ), (5.1)

which is a generating function of {z_{n}} (or rather of {b_{n}z_{n}}).

Lemma 5.1. Let f(δ) = 𝔼_{δ} Z. Then

𝔼_{δ}(NZ) = −(\frac{1}{δ} − δ)f′(δ) + \frac{1}{δ}f(δ).

Proof. Differentiating (5.1) we obtain

\frac{d}{dδ} 𝔼_{δ} Z = ∑_{k} 2^{−(2k+1)}b_{2k+1}z_{2k+1}(−2kδ)(1 − δ^{2})^{k−1}(1 + δ) + \frac{1}{1 + δ} 𝔼_{δ} Z

= −\frac{δ}{1 − δ^{2}} 𝔼_{δ}(Z(N − 1)) + \frac{1}{1 + δ} 𝔼_{δ} Z.

Hence (1 − δ^{2})f′(δ) = −δ 𝔼_{δ}(ZN) + δ 𝔼_{δ} Z + (1 − δ) 𝔼_{δ} Z, and the result follows. □

Since the choice Z := 1 obviously gives 𝔼_{δ} Z = 1, Lemma 5.1 yields

𝔼_{δ} N = δ^{−1}.  (5.2)

Another application of Lemma 5.1 then yields

𝔼_{δ} N^{2} = δ^{−3} + δ^{−2} − δ^{−1}.  (5.3)

Repeating, we see that 𝔼_{δ} N^{k} is a polynomial in δ^{−1} for each k ≥ 1, but we have no need for exact formulas. We turn to asymptotics.

In the remainder of this section, we let O(δ^{−m}) denote an unspecified polynomial in δ^{−1} of degree at most m. Lemma 5.1 has the following consequence.

Lemma 5.2. If 𝔼_{δ} Z = aδ^{−m} + O(δ^{−(m−1)}), where m ≥ 1 and a ∈ ℝ, then 𝔼_{δ}(NZ) = maδ^{−(m+2)} + O(δ^{−(m+1)}). □

The behaviour of the function 𝔼_{δ} Z is translated into asymptotics of 𝔼 Z(T_{n}) as follows.

Lemma 5.3. If 𝔼_{δ} Z = aδ^{−m} + O(δ^{−(m−1)}), where m ≥ 1 and a ≠ 0, then

𝔼 Z(T_{n}) ∼ 2^{(1−m)/2} \frac{Γ(1/2)}{Γ(m/2)}an^{(m+1)/2} as n → ∞.

Proof. It suffices to consider the case 𝔼_{δ} Z = δ^{−m}. In this case we have by (5.1), with z_{n} := 𝔼 Z(T_{n}),

∑_{k} 2^{−(2k+1)}b_{2k+1}z_{2k+1}(1 − δ^{2})^{k+1} = (1 − δ) 𝔼_{δ} Z = δ^{−m} − δ^{−m−1}

and thus, taking δ = \sqrt{1 − x},

\begin{aligned}2^{−(2k+1)}b_{2k+1}z_{2k+1} & = [x^{k+1}]((1 − x)^{−m/2} − (1 − x)^{−(m−1)/2}) \\ & = \frac{Γ(m/2 + k + 1)}{Γ(m/2)(k + 1)!} − \frac{Γ((m − 1)/2 + k + 1)}{Γ((m − 1)/2)(k + 1)!} \\ & ∼ \frac{1}{Γ(m/2)}k^{m/2−1}  as k → ∞. \end{aligned} (5.4)

By (5.2), the choice Z = N is of this type with m = 1; hence (5.4) yields, since then z_{n} = n,

2^{−(2k+1)}b_{2k+1}(2k + 1) ∼ \frac{1}{Γ(1/2)}k^{−1/2}.  (5.5)

(This also follows by well-known asymptotics of the Catalan numbers.) Returning to a general m ≥ 1, we find by (5.4) and (5.5), when 𝔼_{δ} Z = δ^{−m},

\frac{z_{2k+1}}{2k + 1} ∼ \frac{Γ(1/2)}{Γ(m/2)}k^{m/2−1/2}.

The result follows in this case, and thus in general. □

Consider now the functionals P and Q on T = T_{δ}. With probability 1−p, T consists of the root only, and then P (T) = Q(T) = 0. With probability p, T consists of the root o and two subtrees T′ and T′′; these are independent and each has the same distribution as T. In this case, the definitions of P and Q yield (note that x ∧ y = o when x ∈ T′ and y ∈ T′′)

P (T) = P (T′) + N(T′) + P (T′′) + N(T′′),  (5.6)
Q(T) = Q(T′) + N(T′)^{2} + Q(T′′) + N(T′′)^{2}.  (5.7)

Taking expectations we find

𝔼_{δ} P = p 𝔼_{δ}(P (T′) + N(T′) + P (T′′) + N(T′′))

= \frac{1 − δ}{2} (𝔼_{δ} P + 𝔼_{δ} N + 𝔼_{δ} P + 𝔼_{δ} N)

= (1 − δ) 𝔼_{δ} P + (1 − δ) 𝔼_{δ} N

and similarly

𝔼_{δ} Q = (1 − δ) 𝔼_{δ} Q + (1 − δ) 𝔼_{δ} N^{2}.

Hence, using (5.2) and (5.3),

𝔼_{δ} P = \frac{1 − δ}{δ} 𝔼_{δ} N = δ^{−2} − δ^{−1},  (5.8)
𝔼_{δ} Q = \frac{1 − δ}{δ} 𝔼_{δ} N^{2} = δ^{−4} − 2δ^{−2} + δ^{−1}.  (5.9)

More generally, for any k ≥ 0, l ≥ 0 with k + l ≥ 1, by (5.6), (5.7) and the binomial theorem,

\begin{matrix}𝔼_{δ}(P (T)^{k}Q(T)^{l}) = \frac{1 − δ}{2} ∑_{i=0}^{k} ∑_{j=0}^{l} \binom{k}{i}\binom{l}{j} 𝔼_{δ}((P (T′) + N(T′))^{i} \\ · (P (T′′) + N(T′′))^{k−i}(Q(T′) + N(T′)^{2})^{j}(Q(T′′) + N(T′′)^{2})^{l−j}) \\ = \frac{1 − δ}{2} ∑_{i=0}^{k} ∑_{j=0}^{l} \binom{k}{i}\binom{l}{j} 𝔼_{δ}((P + N)^{i}(Q + N^{2})^{j}) 𝔼_{δ}((P + N)^{k−i}(Q + N^{2})^{l−j}) \end{matrix} ; (5.10)

This can be used together with Lemma 5.1 to calculate 𝔼_{δ}(P^{k}Q^{l}) recursively; we are only interested in the following asymptotical formula.

Lemma 5.4. If k ≥ 0 and l ≥ 0 with k + l ≥ 1, then

𝔼_{δ}(P^{k}Q^{l}) = a_{kl}δ^{−(3k+5l−1)} + O(δ^{−(3k+5l−2)})  (5.11)

for some positive numbers a_{kl} satisfying a_{10} = a_{01} = 1 and the recursion relation

a_{k,l} = k(3k + 5l − 4)a_{k−1,l} + l(3k + 5l − 6)(3k + 5l − 4)a_{k,l−1}

+ \frac{1}{2} ∑ ∑_{0<i+j<k+l} \binom{k}{i}\binom{l}{j}a_{i,j}a_{k−i,l−j}. (5.12)

Proof. Let P_{0} denote the set of all polynomials in δ^{−1} without constant term. Note that (5.8) and (5.9) show that (5.11) holds when k + l = 1, with 𝔼_{δ}(P^{k}Q^{l}) ∈ P_{0} and a_{10} = a_{01} = 1. We continue by induction on k + l, and assume that K, L ≥ 0 with K + L ≥ 2 are such that (5.11) holds and furthermore 𝔼_{δ}(P^{k}Q^{l}) ∈ P_{0}, when 1 ≤ k + l < K + L. For such k and l and any m ≥ 0, Lemma 5.2 implies

\begin{aligned}𝔼_{δ}(P^{k}Q^{l}N^{m}) & = a_{kl} ∏_{j=0}^{m−1}(3k + 5l + 2j − 1) · δ^{−(3k+5l+2m−1)} + O(δ^{−(3k+5l+2m−2)}) \\ & = O(δ^{−(3k+5l+2m−1)}), \end{aligned} ; (5.13)

and Lemma 5.1 shows further that 𝔼_{δ}(P^{k}Q^{l}N^{m}) ∈ P_{0}. The same holds for k = l = 0 and m ≥ 1 too (with a_{00} = −1) by (5.2) and Lemmas 5.2 and 5.1.

Now consider (5.10) with k = K and l = L. The two terms with i = j = 0 or i = K, j = L on the right hand side yield together, using the binomial theorem and (5.13),

(1 − δ) 𝔼_{δ}((P + N)^{K}(Q + N^{2})^{L}) = (1 − δ) 𝔼_{δ}(P^{K}Q^{L}) + K 𝔼_{δ}(P^{K−1}Q^{L}N)

+ L 𝔼_{δ}(P^{K}Q^{L−1}N^{2}) + O(δ^{−(3K+5L−3)}).

Note that the fact 𝔼_{δ}(P^{k}Q^{l}N^{m}) ∈ P_{0} is used to guarantee that the error term is a polynomial in δ^{−1}, even though it contains terms with the factor δ or 1 − δ.

Similarly, continuing with the right hand side of (5.10) for k = K and l = L, a term with 1 ≤ i + j ≤ k + l − 1 yields

\frac{(1 − δ)}{2}\binom{K}{i}\binom{L}{j}(𝔼_{δ}(P^{i}Q^{j}) + O(δ^{−(3i+5j−2)}))(𝔼_{δ}(P^{K−i}Q^{L−j})

+ O(δ^{−(3(K−i)+5(L−j)−2)}))

= \frac{1}{2}\binom{K}{i}\binom{L}{j} 𝔼_{δ}(P^{i}Q^{j}) 𝔼_{δ}(P^{K−i}Q^{L−j}) + O(δ^{−(3K+5L−3)}).

Consequently, (5.10) yields, using the induction hypothesis (5.11) and (5.13),

δ 𝔼_{δ}(P^{K}Q^{L}) = K(3K + 5L − 4)a_{K−1,L}δ^{−(3K+5L−2)}

\begin{matrix}+ L(3K + 5L − 6)(3K + 5L − 4)a_{K,L−1}δ^{−(3K+5L−2)} \\ + ∑ ∑_{0<i+j<K+L} \frac{1}{2}\binom{K}{i}\binom{L}{j}a_{i,j}a_{K−i,L−j}δ^{−(3K+5L−2)} + O(δ^{−(3K+5L−3)}). \end{matrix}

This proves both the induction hypothesis and (5.12). □

Lemmas 5.3 and 5.4 now yield the sought moment asymptotics for full binary trees.

Lemma 5.5. If k ≥ 0 and l ≥ 0 with k + l ≥ 1, then

𝔼(P (T_{n})^{k}Q(T_{n})^{l}) ∼ \frac{\sqrt{π}}{2^{(3k+5l−2)/2}Γ((3k + 5l − 1)/2)}a_{kl}n^{(3k+5l)/2}. (5.14)

where the numbers a_{kl} are defined in Lemma 5.4. □

Proof of Theorem 3.3. Note that (5.14) implies that (3.5) holds for the family of full binary trees, cf. Remark 3.5. Recall further that σ^{2} = 1 for this family. Thus Lemma 5.5 yields

𝔼 ξ^{k}η^{l} = \frac{\sqrt{π}}{2^{(3k+5l−2)/2}Γ((3k + 5l − 1)/2)}a_{kl}, k + l ≥ 1.

We define ω_{kl}^{∗} = 2^{k+l−1}a_{kl}/k! l! and obtain (3.3), while the recursion relation (3.4) follows from (5.12).

We have ω_{10}^{∗} = ω_{01}^{∗} = 1 and find from (3.4) ω_{20}^{∗} = 5, ω_{11}^{∗} = 26, ω_{02}^{∗} = 49, which yields the first and second moments by simple calculations. □

6. Moment convergence

Proof of Theorem 3.4. As said in Remark 3.5, it suffices to show (3.6) in order to obtain (3.5). The values of 𝔼 ζ and 𝔼 ζ^{2} obtained in Theorem 3.3 then complete the proof of Theorem 3.4.

Takács [24] has proved (3.6) under the assumption that 𝔼 X^{m} < ∞ for each m. (In fact, he proved n^{−3/2}P (T_{n}) →^{d} σ^{−1}ξ by the method of moments.) We give here a proof by a variation of his method assuming only a second moment.

Remark 6.1. It should be possible to refine the argument below and obtain convergence of moments of n^{−3/2}P (T_{n}) to the moments of σ^{−1}ξ in this way as in [24], but we only need a bound (which simplifies the argument considerably), since convergence then follows using Theorem 3.1. It might even be possible to combine the argument below and the related one in Section 5 and obtain asymptotics for mixed moments of P (T_{n}) and Q(T_{n}) for general simply generated random trees directly.

Let span(X) := GCD{n : ℙ(X = n) > 0}. For simplicity we assume below that span(X) = 1, and leave the minor modifications when span(X) = d > 1 to the reader; the most important is that the estimates in Lemmas 6.2 and 6.3 hold in the sector | arg z| ≤ π/d, and that similar estimates hold in other sectors because F (e^{2πi/d}z, w) = e^{2πi/d}F (z, w).

Let T be the Galton–Watson tree defined by X, and consider the bivariate probability generating function

F (z, w) := 𝔼(z^{|T |}w^{P (T)})  (6.1)

and the univariate probability generating function

G(z) := 𝔼 z^{|T |} = F (z, 1).

Further let ψ(z) := 𝔼 z^{X} be the probability generating function of X. (In the first setup of Section 2, ψ(z) = φ(zτ)/φ(τ).)

Let U = \{z : |z| < 1\} and \overline{U} = \{z : |z| ≤ 1\} be the open and the closed unit disk. As all probability generating functions, F, G and ψ are continuous on \overline{U} × \overline{U} or \overline{U}, respectively, and analytic in the interior U × U or U; further, F (1, 1) = G(1) = ψ(1) = 1.

As is well known, see e.g. [24], and easily seen by conditioning on the number of children of the root,

F (z, w) = zψ(F (zw, w)),  z, w ∈ \overline{U}.  (6.2)

Lemma 6.2. If span(X) = 1, then, for some c_{1}, c_{2} > 0 and every z ∈ U,

|F (z, 1)| = |G(z)| ≤ 1 − c_{1}|1 − z|^{1/2},  (6.3)
|1 − zψ′(F (z, 1))| ≥ c_{2}|1 − z|^{1/2},  (6.4)

and, for every fixed m ≥ 2,

ψ^{(m)}(F (z, 1)) = O(|1 − z|^{−(m−2)/2}).  (6.5)

Proof. We begin with (6.3). This is well-known if the radius of convergence of ψ is greater than 1, and implicit in [24] in the present case; for completeness we give a simple proof.

Since span(X) = 1, it is easily seen that |G(z)| < 1 for every z ∈ \overline{U} \ \{1\}. Hence, for any δ > 0, by compactness, (6.3) holds for z ∈ \overline{U} with |1−z| ≥ δ, provided c_{1} is small enough. Hence it suffices to consider z close to 1.

Since 𝔼 X^{2} < ∞, ψ is twice continuously differentiable in \overline{U}. Further, G(1) = 1, ψ(1) = 1, ψ′(1) = 𝔼 X = 1 and ψ′′(1) = 𝔼 X(X −1) = σ^{2}. Hence, (6.2) and a Taylor expansion yield, as z → 1 with z ∈ \overline{U},

G(z) = zψ(G(z))

= z(1 + ψ′(1)(G(z) − 1) + \frac{1}{2}ψ′′(1)(G(z) − 1)^{2} + o(G(z) − 1)^{2})

= zG(z) + \frac{1}{2}σ^{2}(G(z) − 1)^{2} + o(G(z) − 1)^{2}

and thus (1 − z) ∼ (1 − z)G(z) ∼ \frac{1}{2}σ^{2}(G(z) − 1)^{2} and

1 − G(z) = (\frac{\sqrt{2}}{σ} + o(1))\sqrt{1 − z}.  (6.6)

Since |G(z)| ≤ 1 and arg(1 − z) ∈ (−π/2, π/2), we have here the principal branch of \sqrt{1 − z}, and thus | arg \sqrt{1 − z}| < π/4, and it is easily seen that (6.6) implies (6.3) for z close to 1. Consequently (6.3) holds for all z ∈ \overline{U} with a suitable c_{1} > 0.

Another Taylor expansion yields

\begin{aligned}zψ′(G(z)) & = ψ′(G(z)) + O(1 − z) \\ & = ψ′(1) + ψ′′(1)(G(z) − 1) + O(1 − z) + o(G(z) − 1) \end{aligned}

and thus, by (6.6),

\begin{aligned}1 − zψ′(G(z)) & = σ^{2}(1 − G(z)) + O(1 − z) + o(1 − G(z)) \\ & = (\sqrt{2}σ + o(1))\sqrt{1 − z}, \end{aligned}

which yields (6.4) for z close to 1 (again this is proved in [24] too). The general case follows by another compactness argument, using (6.3) and the fact that |ψ′(w)| < 1 when |w| < 1.

Finally, since ψ′′(z) is bounded and analytic in U, Cauchy’s estimate gives

|ψ^{(m)}(w)| ≤ C_{m}(1 − |w|)^{−(m−2)}, w ∈ U

(with C_{m} = (m − 2)! σ^{2}), which by (6.3) yields (6.5). □

Lemma 6.3. For any fixed integers k, l ≥ 0, the limit ∂_{z}^{k}∂_{w}^{l}F (z, 1) := lim_{U∋w→1} ∂_{z}^{k}∂_{w}^{l}F (z, w) exists for z ∈ U. If span(X) = 1 and k + l ≥ 1, then,

∂_{z}^{k}∂_{w}^{l}F (z, 1) = O(|1 − z|^{−(2k+3l−1)/2}),  z ∈ U.  (6.7)

Proof. The existence of the limit follows because P (T) ≤ |T |^{2}.

To prove (6.7), we use induction. Let K, L ≥ 0 and assume that (6.7) holds when 1 ≤ k + l < K + L, or when k + l = K + L but l < L. For z, w ∈ U we have by (6.2)

∂_{z}^{K}∂_{w}^{L}F (z, w) = ∂_{z}^{K}∂_{w}^{L}(zψ(F (zw, w))).  (6.8)

The right hand side can, by induction, be written as a linear combination of terms

z^{1−k_{0}}ψ^{(m)}(F (zw, w)) ∏_{i=1}^{m} ∂_{z}^{k_{i}}∂_{w}^{l_{i}}(F (zw, w))  (6.9)

where 0 ≤ m ≤ K +L, 0 ≤ k_{0} ≤ 1, k_{i} ≥ 0, l_{i} ≥ 0, k_{i} +l_{i} ≥ 1 for i = 1, …, m, and ∑_{0}^{m} k_{i} = K, ∑_{1}^{m} l_{i} = L. Now let w → 1, keeping z ∈ U fixed. Since, as is verified by induction,

∂_{w}^{l}(F (zw, w)) = ∑_{j=0}^{l} \binom{l}{j}z^{j}(∂_{z}^{j}∂_{w}^{l−j}F )(zw, w),  (6.10)

the induction hypothesis easily implies, for 1 ≤ k+l < K+L, or k+l = K+L and l < L,

∂_{z}^{k}∂_{w}^{l}(F (zw, w))|_{w=1} = O(|1 − z|^{−(2k+3l−1)/2}).  (6.11)

Using also (6.5), we see that a term (6.9) with m ≥ 2 can, for w = 1, be estimated by

O(|1 − z|^{−(m−2+∑_{1}^{m}(2k_{i}+3l_{i}−1))/2}) = O(|1 − z|^{−(2K+3L−2)/2}).

There is no term (6.9) with m = 0 except for K = 1, L = 0, when there is a single term ψ(F (zw, w)) = O(1) = O(|1 − z|^{−(2K+3L−2)/2}). Finally, for m = 1, we have the terms

A_{1}(z, w) := zψ′(F (zw, w))∂_{z}^{K}∂_{w}^{L}(F (zw, w)),  (6.12)

which appears exactly once in (6.8), and (when K ≥ 1)

A_{2}(z, w) := ψ′(F (zw, w))∂_{z}^{K−1}∂_{w}^{L}(F (zw, w)).  (6.13)

Since ψ′ is bounded in \overline{U}, we obtain from (6.11) (and directly for K = 1, L = 0)

A_{2}(z, 1) = O(|1 − z|^{−(2K+3L−2)/2}).

Moreover, expanding (6.12) by (6.10) and Leibniz’ rule, collecting all terms coming from j ≥ 1 in (6.10) into A_{3}(z, w),

A_{1}(z, w) = zψ′(F (zw, w))w^{k}(∂_{z}^{K}∂_{w}^{L}F )(zw, w) + A_{3}(z, w)

where, again by (6.11),

A_{3}(z, 1) = O(|1 − z|^{−(2K+3L−2)/2}).

Consequently, letting w → 1 in (6.8) yields

∂_{z}^{K}∂_{w}^{L}F (z, 1) = zψ′(F (z, 1))∂_{z}^{K}∂_{w}^{L}F (z, 1) + O(|1 − z|^{−(2K+3L−2)/2})

or

(1 − zψ′(F (z, 1)))∂_{z}^{K}∂_{w}^{L}F (z, 1) = O(|1 − z|^{−(2K+3L−2)/2}),

which by (6.4) implies ∂_{z}^{K}∂_{w}^{L}F (z, 1) = O(|1 − z|^{−(2K+3L−1)/2}), thus completing the induction step and proving (6.7). □

We may now complete the proof of (3.6). Let l ≥ 1. By (6.1),

\begin{aligned}∂_{w}^{l}F (z, 1) & = 𝔼(z^{|T |}(P (T))_{l}) = ∑_{n=1}^{∞} ℙ(|T | = n) 𝔼(z^{|T |}(P (T))_{l} | |T | = n) \\ & = ∑_{n=1}^{∞} ℙ(|T | = n) 𝔼(P (T_{n})_{l})z^{n}. \end{aligned}

Cauchy’s formula thus yields, for 0 < r < 1,

ℙ(|T | = n) 𝔼(P (T_{n})_{l}) = \frac{1}{2πi} ∫_{|z|=r} z^{−(n+1)}∂_{w}^{l}F (z, 1) dz.

Taking r = 1 − 1/n (for n ≥ 2), we find by (6.7), for l ≥ 2 and some C_{1}, … depending on l only,

ℙ(|T | = n) 𝔼(P (T_{n})_{l}) ≤ C_{1} ∫_{−π}^{π} |∂_{w}^{l}F (re^{iθ}, 1)| dθ

≤ C_{2} ∫_{−π}^{π} |1 − re^{iθ}|^{−(3l−1)/2} dθ ≤ C_{3} ∫_{−π}^{π}(\frac{1}{n} + |θ|)^{−(3l−1)/2} dθ

≤ 2C_{3} ∫_{1/n}^{∞} x^{−(3l−1)/2} dx ≤ C_{4} n^{(3l−1)/2−1}.

Moreover, it is well-known, see [16, Lemma 2.1.4], that ℙ(|T | = n) ∼ (2πσ^{2})^{−1/2}n^{−3/2}. Hence, for l ≥ 2,

𝔼(P (T_{n})_{l}) = O(n^{3l/2}),

which is equivalent to 𝔼(P (T_{n})^{l}) = O(n^{3l/2}), l ≥ 2. The case l = 1 follows from (𝔼 P (T_{n}))^{2} ≤ 𝔼 P (T_{n})^{2}, and (3.6) is proved. □

7. Further comments

1. A generalization of the Wiener index that has been considered by chemists is

W_{λ}(T) := \frac{1}{2} ∑_{v,w∈T} d(v, w)^{λ},

where λ is a positive constant, see [8] and the references given there. Both versions above (in Remark 3.2 and Section 4) of the proof of Theorem 3.1 generalize, and we obtain

n^{−(2+λ/2)}W_{λ}(T_{n}) →^{d} σ^{−λ}ζ_{λ}

with

ζ_{λ} = \frac{1}{2} ∫∫ d(x, y)^{λ} dμ(x) dμ(y) = 2^{λ} ∫∫_{0<s<t<1}(e(s)+e(t)−2 min_{s≤u≤t} e(u))^{λ} ds dt.

The expectation can be computed as follows. Arguing as in Remark 3.8 with random rerootings of random unordered labelled trees, we see that 𝔼 ζ_{λ} = \frac{1}{2} 𝔼 ξ_{λ}, with ξ_{λ} := ∫ d(0, x)^{λ} dμ(x) = ∫_{0}^{1}(2e(t))^{λ} dt. As shown by Lévy [17], the expected occupation density of e is 4xe^{−2x^{2}} (in other words, if U is uniform on [0, 1] and independent of e, then e(U) has the Rayleigh distribution with this density), and thus

\begin{aligned}𝔼 ζ_{λ} & = \frac{1}{2} 𝔼 ξ_{λ} = 2^{λ−1} 𝔼 ∫_{0}^{1} e(t)^{λ} dt = 2^{λ−1} ∫_{0}^{∞} x^{λ} · 4xe^{−2x^{2}} dx \\ & = 2^{λ/2−1}Γ(λ/2 + 1). \end{aligned}

Hence, at least when (3.7) holds (see Remark 3.6), for any λ > 0,

𝔼 W_{λ}(T_{n}) ∼ σ^{−λ}2^{λ/2−1}Γ(λ/2 + 1)n^{2+λ/2}.

It should be possible to derive higher moments of ζ_{λ}, and thus asymptotics for the moments of W_{λ}(T_{n}), by the method of Section 5, at least when λ is an integer, but we have not pursued this.

2. Define the weight w(e) of an edge e a the tree T to be the product of the numbers of vertices in the two components of T − e. Thus w(e) is the number of all paths in T that pass through e, and summing we find [27]

W (T) = ∑_{e} w(e).  (7.1)

Let us consider the individual terms in this representation of the Wiener index. Note that when W (T) is written as the sum of all path lengths, as in the definition in Section 1, the individual terms are typically of the same order as the average, i.e. n^{1/2}. On the other hand, there are n − 1 edges and thus the average edge weight in a typical tree is of order n^{3/2}, while a typical edge weight only is of order n. In fact, as a reformulation of Aldous [1, Lemma 9], if we take a random conditioned Galton–Watson tree T_{n} and a random edge e ∈ T_{n}, then the subtree which consists of the component of T_{n} − e not containing the root has asymptotically the distribution of the corresponding (unconditioned) Galton–Watson tree T. Consequently, then

w(e)/n →^{d} |T |.

This shows that the main contribution to the sum (7.1) comes from the few extremal edges that split the tree into two large parts. It might be interesting to study the distribution of these large edge weights further, for example by studying ∑_{e} w(e)^{λ} for constants λ ≠ 1.

3. Takács [25] gives a limit theorem for P (T_{n}) for unlabelled rooted trees too. It seems likely that there are versions of the results in this paper for unlabelled (rooted or unrooted) trees; cf. Aldous [2, Section 4], where also other types of random trees are discussed.

References

[1] D. Aldous, Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228–266.

[2] D. Aldous, The continuum random tree II: an overview. Stochastic analysis (Proc., Durham, 1990), 23–70, London Math. Soc. Lecture Note Ser. 167, Cambridge Univ. Press, Cambridge, 1991.

[3] D. Aldous, The continuum random tree III. Ann. Probab. 21, no. 1, 248–289.

[4] D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), no. 2, 812–854.

[5] G.N. Bagaev & E.F. Dmitriev, Enumeration of connected labeled bipartite graphs. (Russian) Dokl. Akad. Nauk BSSR 28 (1984), no. 12, 1061–1063, 1148.

[6] E.A. Bender, E.R. Canfield & B.D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Structures Algorithms 1 (1990), no. 2, 127–169.

[7] L. Devroye, Branching processes and their applications in the analysis of tree structures and tree algorithms. Probabilistic methods for algorithmic discrete mathematics, 249– 314, eds. M. Habib et al., Algorithms Combin. 16, Springer, Berlin, 1998.

[8] A.A. Dobrynin, R. Entringer & I. Gutman, Wiener index of trees: theory and applications. Acta Appl. Math. 66 (2001), no. 3, 211–249.

[9] M. Drmota & J.-F. Marckert, Reinforced weak convergence of stochastic processes.

Preprint, 2001. Available from http://www.geometrie.tuwien.ac.at/drmota/

[10] R.C. Entringer, A. Meir, J.W. Moon & L.A. Székely, The Wiener index of trees from certain families. Australas. J. Combin. 10 (1994), 211–224.

[11] P. Flajolet & A. Odlyzko, The average height of binary trees and other simple trees. J. Comp. Sys. Sci. 25 (1982), 171–213.

[12] P. Flajolet, Z. Gao, A. Odlyzko, & B. Richmond, The distribution of heights of binary trees and other simple trees. Combin. Probab. Comput. 2 (1993), 145-156.

[13] P. Flajolet, P. Poblete & A. Viola, On the analysis of linear probing hashing. Algorithmica 22 (1998), no. 4, 490–515.

[14] S. Janson, D.E. Knuth, T. Łuczak & B. Pittel, The birth of the giant component. Random Structures Algorithms 4 (1993), no. 3, 233–358.

[15] D.E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental algorithms. 3rd ed., Addison–Wesley, Reading, Mass., 1997.

[16] V.F. Kolchin, Random Mappings. Nauka, Moscow, 1984 (Russian). English transl.: Optimization Software, New York, 1986.

[17] P. Lévy, Processus Stochastiques et Mouvement Brownien. Gauthier-Villars, Paris, [18] G. Louchard, Kac’s formula, Lévy’s local time and Brownian excursion. J. Appl.

Probab. 21 (1984), no. 3, 479–499.

[19] G. Louchard, The Brownian excursion area: a numerical analysis. Comput. Math. Appl. 10 (1984), no. 6, 413–417. Erratum: Comput. Math. Appl. Part A 12 (1986), no. 3, 375.

[20] J.-F. Marckert & A. Mokkadem, The depth first processes of Galton–Watson trees converge to the same Brownian excursion. Preprint, 2001. Available from

http://www.math.uvsq.fr/~marckert/

[21] A. Meir & J.W. Moon, On the altitude of nodes in random trees. Canad. J. Math. 30 (1978), 997–1015.

[22] R. Neininger, Wiener index of random trees. Preprint, 2001. Available from

http://www.stochastik.uni-freiburg.de/homepages/neininger/

[23] J. Spencer, Enumerating graphs and Brownian motion. Commun. Pure Appl. Math. 50 (1997), 291–294.

[24] L. Takács, Conditional limit theorems for branching processes. J. Appl. Math. Stochastic Anal. 4 (1991), no. 4, 263–292.

[25] L. Takács, The asymptotic distribution of the total heights of random rooted trees. Acta Sci. Math. (Szeged) 57 (1993), no. 1-4, 613–625.

[26] V.A. Voblyĭ, Wright and Stepanov-Wright coefficients. (Russian) Mat. Zametki 42 (1987), no. 6, 854–862, 911. English transl.: Math. Notes 42 (1987), 969–974.

[27] H. Wiener, Structural determination of paraffin boiling points. J. Amer. Chem. Soc. 69 (1947), 17–20.

[28] E.M. Wright, The number of connected sparsely edged graphs. J. Graph Th. 1 (1977), 317–330.

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/