IDEALS IN A FOREST, ONE-WAY INFINITE BINARY TREES AND THE CONTRACTION METHOD

SVANTE JANSON

Abstract. The analysis of an algorithm by Koda and Ruskey for listing ideals in a forest poset leads to a study of random binary trees and their limits as infinite random binary trees. The corresponding finite and infinite random forests are studied too. The infinite random binary trees and forests studied here have exactly one infinite path; they can be defined using suitable size-biazed Galton–Watson processs. Limit theorems are proved using a version of the contraction method.

1. Introduction

The vertices of a rooted forest may be regarded as a poset in a natural way, with the roots being the minimal elements. Consider the family of all ideals (or down-sets) of this poset. If the forest consists of trees T_{1},…,T_{k}, then the ideals are the sets of the form V_{1} ∪ ⋯ ∪ V_{k}, where each V_{i} is either empty or the vertex set of a rooted subtree of T_{i}.

Koda and Ruskey [11] described two algorithms for listing the ideals of a forest poset in a Gray code manner, i.e. such that consecutive ideals differ by exactly one element. (For background and applications, see [11]. For actual implementations, see Knuth [10].) We are here concerned only with their first algorithm, Algorithm P in [11]. Since the algorithm operates on ordered forests, we assume from now on that all forests and trees are rooted and ordered.

As noted in [11], the running time per ideal of Algorithm P, i.e. the total running time divided by the number of ideals listed, is not bounded. However, it is conjectured in [11, Section 6] that the expected running time per ideal for a randomly selected rooted tree on n vertices is bounded as n → ∞.

In the present paper, we study random ordered rooted trees, and verify the conjecture of [11] in this case. (As pointed out by a referee, the conjecture in [11] is really stated for random rooted trees; the algorithm operates on ordered trees, but the probability distribution depends on whether the ordering is imposed before or after the random selection. Presumably, the result holds for random rooted trees and other families of simply generated trees too.) Moreover, we show that both the expectation and the distribution of the running time per ideal converges as n → ∞ (without further normalization).

Date: November 2, 2001; revised April 25, 2001.

The proofs use a version of the contraction method, which earlier has been used to study many other algorithms, see e.g. [16, 17, 18, 19]. The present application includes some novel features, however, which we find at least as interesting as the results themselves. Thus, although the paper exclusively studies Algorithm P, it should mainly be seen as an example illustrating a method that we hope may be useful for the study of other algorithms as well.

In the proofs we find it convenient to transfer the problem to an equivalent one for random binary trees, see Section 3. Note that we consider random binary trees with the uniform distribution over all binary trees of a given size (sometimes called Catalan trees), in contrast to the binary search trees that appear in connection with other applications of the contraction method (in particular, Quicksort). The distributions are quite different, with the uniform binary trees studied here tending to be much more unbalanced and stringy, which leads to new phenomena.

In the present case (unlike the case of binary search trees), there is a natural limit of the random binary tree as its size tends to infinity; this is a non-trivial infinite random binary tree. Similarly, there is an infinite random forest that is the limit of the random ordered rooted forest. We study these infinite trees and forests in Sections 5 and 6 and show that the cost per ideal can be defined (a.s.) for these infinite objects too, in such a way that its distribution is the limiting distribution of the cost per ideal for finite random forests. This enables us to deduce some properties of the limiting distribution. For example, we show that the distribution is continuous (Theorem 5.10). It is, however, an open problem whether it is absolutely continuous.

The infinite random forests and binary trees studied here have exactly one infinite branch. They can be defined using a size-biased Galton–Watson branching process, see Section 5. We include some further comments on the structure of these infinite objects in Sections 5 and 6.

Acknowledgement. I thank Donald Knuth for suggesting this problem.

2. Preliminaries

We let |F | denote the number of vertices in a forest, or tree, F. If T is a tree, we let T^{∗} be the forest obtained by deleting the root, letting the children of the old root be the new roots. Thus |T^{∗}| = |T | − 1.

Denote the number of ideals of a forest F by N(F). If F consists of the trees T_{1}, …, T_{m}, then

N(F) = ∏_{i=1}^{m} N(T_{i}).  (2.1)

In particular, N(∅) = 1. Moreover, it is easily seen that if T is a tree, then

N(T) = 1 + N(T^{∗}).  (2.2)

Note that (2.1) and (2.2) together determine N recursively. It is easily seen by induction, or directly, considering the ideals consisting of paths from the root and the empty ideal, that

N(F) ≥ |F | + 1.  (2.3)

We let W (F) denote a measure of the running time (work) of Algorithm P on a forest F. Of course, the actual running time depends on details in the implementation, but we make a precise definition as follows, using the descriptions in the proof of Lemma 3.1 in [11]:

If F is empty, we let W (F) = 0.

If F consists of a single tree T, then Algorithm P lists first ∅ and then all ideals of T^{∗}, in the order given by Algorithm P on T^{∗}, with the root of T added to each. The work required by the algorithm on T is therefore the same as for T^{∗}, but with one extra unit for each ideal of T^{∗} (because of the added root) and two extra units for the additional ideal. Hence

W (T) = W (T^{∗}) + N(T^{∗}) + 2 = W (T^{∗}) + N(T) + 1.  (2.4)

If F consists of several trees T_{1}, …, T_{k}, k ≥ 2, let F′ = F \ T_{1} = T_{2} ∪ ⋯ ∪ T_{k}. Then Algorithm P first lists all ideals of T_{1}, ignoring F′, then acts in F′ as if running on F′, then lists all ideals of T_{1} in reverse order with the first nonempty ideal of F′ added to each, then acts in F′ again, then lists the ideals of T_{1} in order with the second nonempty ideal of F′ added to each, and so on. Hence the ideals of T_{1} are run through N(F′) times (in alternating directions) with a work W (T_{1}) each time, while the remaining steps together are equivalent to running the algorithm on F′, which requires W (F′). Hence

W (F) = N(F′)W (T_{1}) + W (F′).  (2.5)

This completes our (recursive) definition of W. (This definition of W by (2.4) and (2.5) was given, in an equivalent form, by Knuth [personal communication].)

Remark 2.1. There is some arbitrariness in the definition; in particular, (2.4) might be modified to W (T) = W (T^{∗}) + aN(T^{∗}) + b for some other positive constants a and b. This would not cause any important differences to the results of this paper (although numerical values will differ); we can assume that a = 1 by dividing W by a, and a value of b different from 2 would cause only routine changes below.

Note that N(F) and W (F) vary wildly among forests of the same size. The extreme cases are, as is easily verified by induction:

(i) n isolated roots; N = 2^{n}, W = 3(2^{n} − 1).

(ii) n vertices in a path; N = n + 1, W = \binom{n+1}{2} + 2n = (n^{2} + 5n)/2.

We therefore study Q(F) := W (F)/N(F), the work per ideal. Note that the path in (ii) shows that Q is unbounded (on trees as well as on forests). (N(F) and N(T) are studied in [8, 20], but we do not use the results there.)

There are C_{n} ordered forests with n vertices, where

C_{n} = \frac{1}{n + 1}\binom{2n}{n} = \frac{(2n)!}{n! (n + 1)!}  (2.6)

is the n:th Catalan number, and thus there are C_{n−1} ordered trees with n vertices [9, 2.3.4.4].

Let F_{n} denote a random ordered rooted forest with n vertices, uniformly selected among the C_{n} possibilities; let similarly T_{n} be a uniformly selected random ordered rooted tree with n vertices. We can now state the main results of the paper, proved in Section 4.

Theorem 2.2. There exists a positive random variable Q with finite mean such that, as n → ∞, Q(F_{n}) →^{d} Q and 𝔼 Q(F_{n}) → 𝔼 Q.

Corollary 2.3. As n → ∞, with Q as in Theorem 2.2, Q(T_{n}) →^{d} Q + 1 and 𝔼 Q(T_{n}) → 𝔼 Q + 1.

Proof. By (2.2) and (2.4),

Q(T_{n}) = \frac{W (T_{n})}{N(T_{n})} = \frac{W (T_{n}^{∗}) + N(T_{n}^{∗}) + 2}{N(T_{n}^{∗}) + 1} = Q(T_{n}^{∗}) + 1 + \frac{1 − Q(T_{n}^{∗})}{N(T_{n}^{∗}) + 1}.

Since T_{n}^{∗} is distributed as F_{n−1}, and N(T_{n}^{∗}) ≥ n by (2.3), the results follow from Theorem 2.2. □

We have no explicit description of the limit distribution L(Q), but it is characterized by a fixed point equation. This fixed point equation is more complicated than in many other similar cases, so we postpone it to Section 5, see Theorems 5.7 and 5.8. In Sections 5 and 6 we further show that Q may be interpreted as an extension of Q to random infinite forests.

3. Binary trees

We find it convenient to consider binary trees instead of forests, using the well-known correspondence in [9, Section 2.3.2], which can be defined recursively as follows: If F = ∅, then B(F) = ∅. If F is a forest consisting of trees T_{1}, …, T_{k}, k ≥ 1, then B(F) is the binary tree with a root, a left subtree B(T_{1}^{∗}) and a right subtree B(T_{2} ∪ ⋯ ∪ T_{k}). Note that |B(F)| = |F |.

We define N, W and Q for binary trees by this correspondence, setting N(B(F)) = N(F) and so on.

It is easily seen that (2.1), (2.2), (2.4), (2.5) translate as follows: If B is a nonempty binary tree with left and right subtrees L and R, then

N(B) = (N(L) + 1)N(R)  (3.1)
W (B) = N(R)(W (L) + N(L) + 2) + W (R).  (3.2)

Together with N(∅) = 1 and W (∅) = 0, (3.1) and (3.2) define N and W directly on binary trees by recursion. Taking the quotient, we further obtain

\begin{aligned}Q(B) & = \frac{W (L) + N(L) + 2}{N(L) + 1} + \frac{W (R)}{N(R)(N(L) + 1)} \\ & = Q(L) + 1 + \frac{1 − Q(L) + Q(R)}{N(L) + 1}. \end{aligned}  (3.3)

Let B_{n} denote a (uniformly selected) random binary tree with n vertices (n ≥ 0). Then Theorem 2.2 is equivalent to the following.

Theorem 3.1. As n → ∞, Q(B_{n}) →^{d} Q and 𝔼 Q(B_{n}) → 𝔼 Q, with Q as in Theorem 2.2.

Let, for n ≥ 1, L_{n} and R_{n} denote the left and right subtrees of B_{n}. Note that

|L_{n}| + |R_{n}| = n − 1.  (3.4)

Let (p_{n,k})_{k=0}^{n−1} be the probability distribution of the size of the left (or, by symmetry, the right) subtree of B_{n}, i.e.

p_{n,k} := ℙ(|L_{n}| = k) = ℙ(|R_{n}| = k).  (3.5)

By (3.4),

p_{n,k} = ℙ(|L_{n}| = k) = ℙ(|R_{n}| = n − 1 − k) = p_{n,n−1−k}.  (3.6)

There are C_{n} binary trees with n vertices, where again C_{n} is the Catalan number (2.6). Hence, the number of binary trees with k vertices in the left subtree and n − 1 − k in the right is C_{k}C_{n−1−k}, and

p_{n,k} = \frac{C_{k}C_{n−1−k}}{C_{n}} .

Stirling’s formula easily yields

C_{n} = \frac{1}{n + 1}\binom{2n}{n} = π^{−1/2}n^{−3/2}2^{2n}(1 + O(n^{−1})).

Hence, uniformly for 0 ≤ k ≤ n/2,

p_{n,k} = C_{k}(n − 1 − k)^{−3/2}n^{3/2}2^{2(n−1−k)−2n}(1 + O(n^{−1}))

= C_{k}4^{−k−1}(1 + O(\frac{k + 1}{n}))

= π_{k}(1 + O(\frac{k + 1}{n})),

where

π_{k} = lim_{n→∞} p_{n,k} = C_{k}4^{−k−1}, k ≥ 0.

By the generating function for Catalan numbers

B(z) := ∑_{k=0}^{∞} C_{k}z^{k} = \frac{1 − \sqrt{1 − 4z}}{2z} ,  (3.7)

see e.g. [9, (2.3.4.4-13)], we have

∑_{k=0}^{∞} π_{k} = ∑_{k=0}^{∞} C_{k}4^{−k−1} = \frac{1}{4}B(\frac{1}{4}) = \frac{1}{2}.  (3.8)

Hence (π_{k})_{0}^{∞} is not a probability distribution. This reflects the symmetry of the left and right sides; roughly speaking, for n large, with probability 1/2 |L_{n}| is small, and with probability 1/2 |R_{n}| is small and then |L_{n}| ≈ n. In particular, a large random binary tree is extremely unbalanced. We state this more precisely.

Lemma 3.2. For each ε > 0 there exists M such that, for every n,

ℙ(|L_{n}| < M) > \frac{1}{2} − ε  (3.9)
ℙ(|L_{n}| ≥ n − M) > \frac{1}{2} − ε  (3.10)
ℙ(M ≤ |L_{n}| < n − M) < 2ε.  (3.11)

Proof. Choose M_{1} such that ∑_{k=M_{1}}^{∞} π_{k} < ε. Then, as n → ∞,

ℙ(|L_{n}| < M_{1}) → ∑_{k=0}^{M_{1}−1} π_{k} > \frac{1}{2} − ε,

so (3.9) holds with M = M_{1} for sufficiently large n, say n ≥ n_{0}. Taking M := max(M_{1}, n_{0}), (3.9) holds for all n. Furthermore, (3.10) holds by (3.6), while (3.11) is an immediate consequence of (3.9) and (3.10). □

We can modify (π_{k}) to make it into a probability distribution in two ways, both of which will be used below. First, we can allow the value +∞, giving it the probability 1/2 because of (3.8). We let ξ^{∗} be a random variable with values in N^{∗} := {0, 1, …, ∞} having this distribution, i.e.

ℙ(ξ^{∗} = k) = \begin{cases}π_{k}, & 0 ≤ k < ∞, \\ \frac{1}{2}, & k = ∞. \end{cases}

Alternatively, we can renormalize (π_{k}) and consider the probability distribution (2π_{k})_{0≤k<∞}. We let ξ be a random variable with this distribution, i.e.

ℙ(ξ = k) = 2π_{k} = 2^{−2k−1}C_{k},  k ≥ 0.  (3.12)

Note that ξ can be defined as ξ^{∗} conditioned on ξ^{∗} < ∞.

With this notation, the following lemmas are immediate consequences of the results above.

Lemma 3.3. Let n → ∞. Then |L_{n}| →^{d} ξ^{∗}, as random variables in N^{∗}. □

Lemma 3.4. Let n → ∞. Then |L_{n}|, conditioned on |L_{n}| < n/2, converges in distribution to ξ. □

Of course, the same results hold for |R_{n}|.

Remark 3.5. These results for the uniform random binary tree studied here should be compared with the corresponding results for random binary search trees, which have a different distribution and for which |L_{n}| is uniformly distributed on {0, …, n−1}. The stronger imbalance in our case is a source of phenomena quite different from the binary search tree case.

Finally we record a simple but important observation. We let B̃_{n} be another (uniform) random binary tree, independent of {B_{k}}_{k=0}^{∞}.

Lemma 3.6. Let 0 ≤ k < n. The conditional joint distribution of L_{n} and R_{n} given |L_{n}| = k equals the distribution of (B_{k}, B̃_{n−1−k}). □

In other words, conditioned on the sizes of the subtrees L_{n} and R_{n}, they are two independent random binary trees.

4. Proof of the limit theorems

We begin with a preliminary estimate, which verifies the conjecture that the expected running time is bounded.

Lemma 4.1. sup_{n≥0} 𝔼 Q(B_{n}) < ∞.

Proof. Define, for n ≥ 0,

a_{n} := 𝔼 Q(B_{n}) + 1,
b_{n} := 𝔼 \frac{1}{N(B_{n}) + 1} ≤ \frac{1}{2}.

From (3.3), conditioning on |L_{n}| and using Lemma 3.6,

\begin{aligned}a_{n} & ≤ 𝔼(Q(L_{n}) + 1 + (1 + Q(R_{n}))\frac{1}{N(L_{n}) + 1}) + 1 \\ & = ∑_{l=0}^{n−1} p_{n,l}a_{l} + ∑_{r=0}^{n−1} p_{n,r}a_{r}b_{n−1−r} + 1 \\ & = ∑_{l=0}^{n−1} p_{n,l}a_{l}(1 + b_{n−1−l}) + 1 \\ & ≤ \frac{3}{2} ∑_{l=0}^{n−1} p_{n,l}a_{l} + 1. \end{aligned}  (4.1)

Let a_{n}^{∗} := max_{0≤k≤n} a_{k}. By (4.1), for any M ≥ 0,

\begin{aligned}a_{n} & ≤ \frac{3}{2}a_{M}^{∗} ℙ(|L_{n}| ≤ M) + \frac{3}{2}a_{n−1}^{∗} ℙ(|L_{n}| > M) + 1 \\ & ≤ 1 + \frac{3}{2}a_{M}^{∗} + \frac{3}{2}a_{n−1}^{∗}(1 − ℙ(|L_{n}| ≤ M)). \end{aligned}

We choose M as in Lemma 3.2 with ε = 0.1. Then ℙ(|L_{n}| ≤ M) > 0.4 and thus, for all n ≥ 1,

a_{n} ≤ 1 + \frac{3}{2}a_{M}^{∗} + \frac{3}{2} · 0.6a_{n−1}^{∗} = 0.9a_{n−1}^{∗} + 1 + \frac{3}{2}a_{M}^{∗}.

An easy induction yields

a_{n} ≤ 10(1 + \frac{3}{2}a_{M}^{∗}), n ≥ 0.

The lemma follows because 𝔼 Q(B_{n}) ≤ a_{n}. □

We prove Theorem 3.1, and thus Theorem 2.2 and Corollary 2.3, using the Mallows metric d_{1} for probability distributions with finite expectations. (This metric is also known under many other names, such as the Dudley, Fortet-Mourier, Kantorovich or Wasserstein distance.) It has several equivalent definitions, see e.g. [15]; for us the following is convenient.

If f is a real (or complex) function on ℝ, let

∥f∥_{Lip} := sup_{x≠y} \frac{|f(x) − f(y)|}{|x − y|}.

If μ and ν are probability measures on ℝ with finite expectations, then

d_{1}(μ, ν) := sup{|∫ f dμ − ∫ f dν| : ∥f∥_{Lip} ≤ 1}.  (4.2)

In other words, we take the supremum in (4.2) over all functions f satisfying the Lipschitz condition |f(x) − f(y)| ≤ |x − y|. (It does not matter whether we consider real or complex functions.)

If X and Y are random variables with finite expectations, we will for simplicity write d_{1}(X, Y) for the d_{1} distance between their distributions. Thus

d_{1}(X, Y) := sup{|𝔼 f(X) − 𝔼 f(Y)| : ∥f∥_{Lip} ≤ 1}.  (4.3)

It is easily seen that d_{1}(X_{n}, X) → 0 implies X_{n} →^{d} X and 𝔼 X_{n} → 𝔼 X. (Take f(x) = |t|^{−1}e^{itx}, t ≠ 0, and f(x) = x.) We will show that d_{1}(Q(B_{n}), Q) → 0 for some random variable Q; this thus proves Theorem 3.1. (Indeed, Theorem 3.1 is equivalent to d_{1}(Q(B_{n}), Q) → 0, using the fact that d_{1}(X_{n}, X) → 0 is equivalent to X_{1} →^{d} X and 𝔼 |X_{n}| → 𝔼 |X| for any random variables with finite expectations.)

Remark 4.2. That 𝔼 Q(B_{n}) converges could also be shown directly using a simplified version of the proof below, taking f(x) = x.

Note first that replacing f by f − f(0) does not change 𝔼 f(X) − 𝔼 f(Y). Hence we may in (4.3) further impose f(0) = 0. Since then |f(x)| = |f(x) − f(0)| ≤ |x|, we have the bound

d_{1}(X, Y) ≤ 𝔼 |X| + 𝔼 |Y |.  (4.4)

We now consider Q(B_{n}). For notational convenience we write X_{n} = Q(B_{n}), Y_{n} = (N(B_{n}) + 1)^{−1} and X̃_{n} = Q(B̃_{n}). Thus X̃_{n} has the same distribution as X_{n} but is independent of all X_{k} and Y_{k}. Note that, by (2.3),

Y_{n} ≤ \frac{1}{n + 2}.

We further define

δ_{N} := sup{d_{1}(X_{n}, X_{m}) : n, m ≥ N}.  (4.5)

Let c_{1} := sup_{n} 𝔼 X_{n}, which is finite by Lemma 4.1. By (4.4), δ_{N} ≤ 2c_{1} < ∞.

Fix a function f with ∥f∥_{Lip} ≤ 1 and f(0) = 0. By (3.3) and Lemma 3.6, conditioning on |L_{n}|, for n ≥ 1,

\begin{aligned}𝔼 f(X_{n}) & = 𝔼 f(Q(B_{n})) = 𝔼 f(Q(L_{n}) + 1 + \frac{1 − Q(L_{n}) + Q(R_{n})}{N(L_{n}) + 1}) \\ & = ∑_{k} p_{n,k} 𝔼 f(Q(B_{k}) + 1 + \frac{1 − Q(B_{k}) + Q(B̃_{n−1−k})}{N(B_{k}) + 1}) \\ & = ∑_{k} p_{n,k} 𝔼 f(X_{k} + 1 + Y_{k}(1 − X_{k} + X̃_{n−1−k})) \\ & = ∑_{k} p_{n,k} 𝔼 f(U_{n,k}) \end{aligned} (4.6)

where

U_{n,k} := X_{k} + 1 + Y_{k}(1 − X_{k} + X̃_{n−1−k}).  (4.7)

We have, for 0 ≤ k ≤ n,

| 𝔼 f(U_{n,k})| ≤ 𝔼 |U_{n,k}| ≤ 𝔼(X_{k} + 2 + X̃_{n−1−k}) ≤ c_{2} := 2c_{1} + 2  (4.8)

and

\begin{aligned}| 𝔼 f(U_{n,k}) & − 𝔼 f(X_{k} + 1)| ≤ 𝔼 |f(U_{n,k}) − f(X_{k} + 1)| \\ & ≤ 𝔼 |U_{n,k} − X_{k} − 1| = 𝔼 |Y_{k}(1 − X_{k} + X̃_{n−1−k})| \\ & ≤ 𝔼 \frac{1}{k + 2}|1 − X_{k} + X̃_{n−1−k}| ≤ \frac{c_{2}}{k + 2}. \end{aligned}  (4.9)

Let ε > 0 and let M be as in Lemma 3.2. By (4.8),

|∑_{k=0}^{M} p_{n,k} 𝔼 f(U_{n,k}) − ∑_{k=0}^{M} π_{k} 𝔼 f(U_{n,k})| ≤ ∑_{k=0}^{M} |p_{n,k} − π_{k}|c_{2}  (4.10)

and

\begin{aligned}| ∑_{k=M+1}^{n−M−2} p_{n,k} 𝔼 f(U_{n,k})| & ≤ c_{2} ∑_{k=M+1}^{n−M−2} p_{n,k} = c_{2} ℙ(M < |L_{n}| < n − 1 − M) \\ & < 2c_{2}ε. \end{aligned} ; (4.11)

Furthermore,

∑_{k=n−1−M}^{n−1}p_{n,k} 𝔼 f(U_{n,k}) = ∑_{j=0}^{M} p_{n,n−j−1} 𝔼 f(U_{n,n−1−j}) = ∑_{j=0}^{M} p_{n,j} 𝔼 f(U_{n,n−1−j})

and thus by (4.8) and (4.9)

\begin{matrix}| ∑_{k=n−1−M}^{n−1} p_{n,k} 𝔼 f(U_{n,k}) − ∑_{j=0}^{M} π_{j} 𝔼 f(X_{n−1−j} + 1)| \\ ≤ ∑_{j=0}^{M} |p_{n,j} − π_{j}| | 𝔼 f(U_{n,n−1−j})| + ∑_{j=0}^{M} π_{j}| 𝔼 f(U_{n,n−1−j}) − 𝔼 f(X_{n−1−j} + 1)| \\ ≤ c_{2} ∑_{j=0}^{M} |p_{n,j} − π_{j}| + \frac{c_{2}}{n − M} ∑_{j=0}^{M} π_{j}. \end{matrix} ; (4.12)

We define R_{n} by

𝔼 f(X_{n}) = ∑_{k=0}^{M} π_{k} 𝔼 f(U_{n,k}) + ∑_{k=0}^{M} π_{k} 𝔼 f(X_{n−1−k} + 1) + R_{n}  (4.13)

and obtain by (4.6) and (4.10)–(4.12), for n ≥ 2M,

|R_{n}| ≤ 2c_{2} ∑_{k=0}^{M} |p_{n,k} − π_{k}| + 2c_{2}ε + \frac{c_{2}}{n − M} .  (4.14)

Let N_{0} be so large that N_{0} > 2M, N_{0} > M +1/ε and |p_{n,k} −π_{k}| < ε/(M +1) when n ≥ N_{0} for k ≤ M. Then (4.14) yields

|R_{n}| ≤ 5c_{2}ε, n ≥ N_{0}. (4.15)

Now suppose N ≥ N_{0} and m, n ≥ N. Using (4.13) and (4.15) we have

\begin{matrix}| 𝔼 f(X_{n}) − 𝔼 f(X_{m})| \\ ≤ ∑_{k=0}^{M} π_{k}| 𝔼 f(U_{n,k}) − 𝔼 f(U_{m,k})| \\ + ∑_{k=0}^{M} π_{k}| 𝔼 f(X_{n−1−k} + 1) − 𝔼 f(X_{m−1−k} + 1)| + 10c_{2}ε. \end{matrix} (4.16)

Since f_{1}(x) := f(x + 1) is a function with ∥f_{1}∥_{Lip} = ∥f∥_{Lip} ≤ 1,

| 𝔼 f(X_{n−1−k} + 1) − 𝔼 f(X_{m−1−k} + 1)| ≤ d_{1}(X_{n−1−k}, X_{m−1−k}). (4.17)

Similarly, for any given X_{k} and Y_{k}, the function

g(x) := f(X_{k} + 1 + Y_{k}(1 − X_{k} + x))

has Lipschitz norm ∥g∥_{Lip} ≤ Y_{k}, and thus by (4.7)

\begin{aligned}| 𝔼(f(U_{n,k}) & − f(U_{m,k}) | X_{k}, Y_{k})| = | 𝔼 g(X̃_{n−1−k}) − 𝔼 g(X̃_{m−1−k})| \\ & ≤ ∥g∥_{Lip}d_{1}(X̃_{n−1−k}, X̃_{m−1−k}) ≤ Y_{k}d_{1}(X_{n−1−k}, X_{m−1−k}). \end{aligned}

Using the crude bound Y_{k} ≤ 1/2 and taking the expectation we have

\begin{aligned}| 𝔼 f(U_{n,k}) − 𝔼 f(U_{m,k})| & ≤ 𝔼 | 𝔼(f(U_{n,k}) − f(U_{m,k}) | X_{k}, Y_{k})| \\ & ≤ \frac{1}{2}d_{1}(X_{n−1−k}, X_{m−1−k}). \end{aligned}  (4.18)

Consequently, by (4.16), (4.18) and (4.5), for m, n ≥ N ≥ N_{0},

| 𝔼 f(X_{n}) − 𝔼 f(X_{m})| ≤ ∑_{k=0}^{M} π_{k} \frac{1}{2}δ_{N−1−k} + ∑_{k=0}^{M} π_{k}δ_{N−1−k} + 10c_{2}ε

≤ \frac{3}{2}δ_{N−1−M} ∑_{k=0}^{M} π_{k} + 10c_{2}ε

≤ \frac{3}{4}δ_{N−1−M} + 10c_{2}ε.

Taking the supremum over all f with ∥f∥_{Lip} ≤ 1 and f(0) = 0 we find, for n, m ≥ N ≥ N_{0},

d_{1}(X_{n}, X_{m}) ≤ \frac{3}{4}δ_{N−1−M} + 10c_{2}ε

and thus

δ_{N} ≤ \frac{3}{4}δ_{N−1−M} + 10c_{2}ε, N ≥ N_{0}.

Letting N → ∞ we obtain

lim sup_{N→∞} δ_{N} ≤ \frac{3}{4} lim sup_{N→∞} δ_{N} + 10c_{2}ε

and thus, since lim sup_{N→∞} δ_{N} ≤ 2c_{1} < ∞,

lim sup_{N→∞} δ_{N} ≤ 40c_{2}ε.

Finally, letting ε → 0, we obtain δ_{N} → 0 as N → ∞.

By the definition (4.5), this shows that (X_{n})_{n}, or rather the corresponding sequence of distributions, is a Cauchy sequence in the d_{1} metric. It is easily seen that the space of all probability measures on ℝ with finite expectation is complete with the metric d_{1} [15]. Hence there exists a limit distribution, and thus a random variable Q such that d_{1}(X_{n}, Q) → 0, which completes the proof. □

Remark 4.3. The proof above shows that the distributions of (X_{n})_{n} form a Cauchy sequence, and thus converge to some limit. The limit will in the next section be characterized by fixed point equations. An anonymous referee has pointed out that, alternatively, it is possible to first define the limit distribution by the fixed point equation in Theorem 5.7 and then use arguments similar to the proof above to show that d_{1}(X_{n}, Q) → 0. This is the usual procedure in applications of the contraction method; it has some advantages in the current setting too but also some disadvantages, and we do not find the differences decisive. Anyone interested in extending the present results should consider both versions of the method.

5. More on binary trees

We begin with some more or less well-known (folk-lore?) observations on random binary trees.

Define a random binary tree B_{∗} with random size by the following construction: Flip a fair coin. If it comes up tails, let B_{∗} be empty, otherwise begin with a root. In the latter case, flip the coin again twice and add a left child of the root if the first flip results in heads and a right child if the second flip results in heads. Continue in this way, flipping the coin twice for every new vertex, as long as new vertices are added. (Equivalently, do site percolation on the complete infinite binary tree by flipping a fair coin for each vertex and removing the vertices that get tails, and let B_{∗} be the component of the root, if any.)

We can regard B_{∗} as the family tree of a Galton–Watson branching process with offspring distribution Bi(2, 1/2) (and children labelled as left or right), starting with Bi(1, 1/2) individuals. We thus call B_{∗} the Galton–Watson binary tree. Since this Galton–Watson process is critical, it a.s. dies out, and thus B_{∗} is finite.

The probability that B_{∗} equals a given binary tree with n vertices is 2^{−2n−1}, since the vertices have to be chosen by n specified coin flips coming up heads, while n + 1 other coin flips have to yield tails. Hence

ℙ(|B_{∗}| = n) = C_{n}2^{−2n−1} = 2π_{n}.  (5.1)

In other words, |B_{∗}| has the same distribution as ξ defined in (3.12). Moreover, the conditional distribution of B_{∗} given |B_{∗}| = n is uniform, and thus equals the distribution of B_{n}. This yields yet another possibility of defining B_{∗}: select its size by (5.1) and then select uniformly a binary tree with this size. Equivalently, if ξ is independent of (B_{n})_{n=0}^{∞}, we can take B_{∗} = B_{ξ}.

Lemmas 3.4 and 3.6 imply the following:

Lemma 5.1. Let n → ∞. Then L_{n}, conditioned on |L_{n}| < n/2, converges in distribution to B_{∗}. □

Consequently, a large random binary tree has one branch at the root distributed (asymptotically) as B_{∗}, while the other is large. We may continue recursively with the large branch, which suggests the following construction.

Define a (noncomplete) infinite random binary tree B_{∞} as follows. Begin with the root and create an infinite path from it by randomly adding, an infinite number of times, either a left or a right child to the last added vertex. Finally, add independent copies of B_{∗} at the free sites of the vertices in the path, i.e. as left or right subtrees depending on which side is not already occupied by the remainder of the infinite path. Note that B_{∞} has exactly one infinite path from the root; we call this path the trunk.

It is easily seen that B_{∞} can be defined by the following modification of the branching process above creating B_{∗}. Consider a Galton–Watson process with two types of individuals, mortals and immortals. Let a mortal have Bi(2, 1/2) children, all mortal, and let an immortal have exactly one immortal child and Bi(1, 1/2) mortal children. Moreover, label each child as left or right, at random but ensuring that two siblings get different labels. The resulting family tree is B_{∞}.

It is now easy to see that Lemma 5.1 implies the following description of the asymptotic shape of large random binary trees. Let, for any tree B, B^{(M)} be the first M levels of B, i.e. the tree with all branches pruned at height M.

Lemma 5.2. As n → ∞, B_{n} →^{d} B_{∞} in the sense of finite-dimensional distributions, i.e., B_{n}^{(M)} →^{d} B_{∞}^{(M)} for every finite M. □

Remark 5.3. If we regard the space B of all finite or infinite binary trees as a subset of the power set of the vertex set of the complete infinite binary tree, with the natural product space topology on the power set, B is a metrizable compact space. A metric can be defined e.g. by d(B, B′) = 1/(k + 1) if B and B′ differ in the k-th level but not below it. The conclusion of Lemma 5.2 is equivalent to B_{n} →^{d} B_{∞} in this compact metric space B.

Remark 5.4. The construction of B_{∞} is a special case of the following general construction of the size-biased Galton–Watson process (regarded as a family tree); see e.g. [1] and [13]. Starting from a Galton–Watson process with an offspring distribution μ having finite, positive mean, the size-biased process can be obtained by considering a branching process with two types: mortals with an offspring distribution μ and all children mortals, and immortals with the size-biased offspring distribution μ̂ and exactly one immortal child (in a random position among its siblings). The process starts with a single immortal. In the critical case studied here (and in the subcritical case), the size-biased process is the same as the Q-process studied in [3, Section I.14]. It is shown there that this process arises as the limit (in the sense of finite-dimensional distributions) as t → ∞ of the original process conditioned on extinction occuring after time t (see also [5]). Informally (for critical and subcritical processes), it is the process conditioned on living forever. Similarly, it is easily shown that for a critical Galton–Watson process with finite offspring variance, the size-biased process is the limit as n → ∞ of the process conditioned on the total progeny being n [7, 1]. In the case of random binary trees, this conditioning yields B_{n}, and we recover Lemma 5.2.

Having proved that both the trees B_{n} and the functional Q(B_{n}) defined on them converge in distribution, it is natural to try to interpret the limit in Theorem 3.1 as Q(B_{∞}) for an extension of Q to infinite trees. Unfortunately, we cannot define this extension by continuity on the space B in Remark 5.3. Indeed, it is easily seen that for any infinite binary tree b, there is a sequence b_{n} of finite binary trees such that b_{n} → b in B but Q(b_{n}) → ∞; for example, construct b_{n} by pruning b at height n and adding a sufficiently large complete binary tree at one of the cuts. (We leave the verification to the reader.) Hence, Q has no continuous extension to B.

However, we can extend Q in the following, somewhat weaker, way. We let N(B) = ∞ for any infinite tree B. We further let L_{∞} and R_{∞} denote the left and right subtree of the root of B_{∞}. Note that exactly one of L_{∞} and R_{∞} is finite.

Theorem 5.5. There exists an extension of Q to infinite binary trees such that 𝔼 |Q(B_{∞}^{(M)})−Q(B_{∞})| → 0 as M → ∞. This extension satisfies a.s. the equation

Q(B_{∞}) = Q(L_{∞}) + 1 + \frac{1}{N(L_{∞}) + 1}(1 − Q(L_{∞}) + Q(R_{∞})).  (5.2)

Moreover, the limit random variable Q in Theorems 2.2 and 3.1 can be taken

as Q(B_{∞}), i.e. Q(B_{n}) →^{d} Q(B_{∞}) as n → ∞.

We do not know whether Q(B_{∞}^{(M)}) → Q(B_{∞}) a.s. as M → ∞.

We begin with a lemma on truncations of finite trees.

Lemma 5.6. Let, for M ≥ 1,

δ^{(M)} := sup_{n} 𝔼 |Q(B_{n}^{(M)}) − Q(B_{n})|.

Then δ^{(M)} → 0 as M → ∞.

Proof. Note first that δ^{(M)} < ∞ by Lemma 4.1 because Q(B_{n}^{(M)}) attains only a finite number of values for each M.

For any n and M ≥ 1, the left and right subtrees of B_{n}^{(M+1)} are L_{n}^{(M)} and R_{n}^{(M)}, and thus (3.3) yields

Q(B_{n}^{(M+1)}) − Q(B_{n}) = \frac{N(L_{n}^{(M)})}{N(L_{n}^{(M)}) + 1}(Q(L_{n}^{(M)}) − Q(L_{n}))

+ \frac{1}{N(L_{n}^{(M)}) + 1}(Q(R_{n}^{(M)}) − Q(R_{n}))

+ (\frac{1}{N(L_{n}^{(M)}) + 1} − \frac{1}{N(L_{n}) + 1})(1 − Q(L_{n}) + Q(R_{n})).

Since either L_{n}^{(M)} = L_{n} or |L_{n}| > |L_{n}^{(M)}| > M, this implies

\begin{aligned}|Q(B_{n}^{(M+1)}) − Q(B_{n})| & ≤ |Q(L_{n}^{(M)}) − Q(L_{n})| + \frac{1}{2}|Q(R_{n}^{(M)}) − Q(R_{n})| \\ & + \frac{1}{M} |1 − Q(L_{n}) + Q(R_{n})|. \end{aligned} (5.3)

For any k ≥ 0, by Lemma 3.6,

𝔼(|Q(L_{n}^{(M)}) − Q(L_{n})| | |L_{n}| = k) = 𝔼 |Q(B_{k}^{(M)}) − Q(B_{k})| ≤ δ^{(M)}.

Moreover, if |L_{n}| = k ≤ M, then L_{n}^{(M)} = L_{n}. Hence,

𝔼 |Q(L_{n}^{(M)}) − Q(L_{n})| ≤ δ^{(M)} ℙ(|L_{n}| > M).

The same estimate holds for 𝔼 |Q(R_{n}^{(M)}) − Q(R_{n})|. We thus obtain from (5.3), again letting c_{1} := sup_{n} 𝔼 Q(B_{n}) < ∞, see Lemma 4.1,

𝔼 |Q(B_{n}^{(M+1)}) − Q(B_{n})| ≤ \frac{3}{2}δ^{(M)} ℙ(|L_{n}| > M) + \frac{1 + 2c_{1}}{M} .  (5.4)

Let M_{0} be as in Lemma 3.2 with ε = 0.1. Then, for every M ≥ M_{0}, we have ℙ(|L_{n}| > M) ≤ ℙ(|L_{n}| > M_{0}) < 0.6, and thus by (5.4)

𝔼 |Q(B_{n}^{(M+1)}) − Q(B_{n})| ≤ 0.9δ^{(M)} + \frac{c_{2}}{M} .

for every n and thus

δ^{(M+1)} ≤ 0.9δ^{(M)} + \frac{c_{2}}{M} ,  M ≥ M_{0}.  (5.5)

It follows by induction that δ^{(M)} ≤ δ^{(M_{0})} + 10c_{2}, M ≥ M_{0}, and thus δ := lim sup_{M→∞} δ^{(M)} < ∞. Furthermore, (5.5) implies δ ≤ 0.9δ, and consequently δ = 0. □

Proof of Theorem 5.5. For any M, N ≥ 1, it follows from Lemma 5.2 that

Q(B_{n}^{(M)}) − Q(B_{n}^{(N)}) →^{d} Q(B_{∞}^{(M)}) − Q(B_{∞}^{(N)}) as n → ∞, and thus by Fatou’s

lemma

𝔼 |Q(B_{∞}^{(M)}) − Q(B_{∞}^{(N)})| ≤ lim inf_{n→∞} 𝔼 |Q(B_{n}^{(M)}) − Q(B_{n}^{(N)})| ≤ δ^{(M)} + δ^{(N)}.

It follows from Lemma 5.6 that B_{∞}^{(M)}, M ≥ 1, is a Cauchy sequence in L^{1}, and thus this sequence converges to a limit, which can be written Q(B_{∞}).

This proves the first assertion and the third follows from this and Lemmas 5.2 and 5.6 by a standard 3ε argument, see e.g. [4, Theorem 4.2].

For (5.2), we observe again that by (3.3)

Q(B_{∞}^{(M+1)}) = Q(L_{∞}^{(M)}) + 1 + \frac{1 − Q(L_{∞}^{(M)}) + Q(R_{∞}^{(M)})}{N(L_{∞}^{(M)}) + 1}.  (5.6)

As M → ∞, the left hand side converges to Q(B_{∞}) in L^{1} and thus in probability by the first part of the theorem. Similarly, conditioned on |L_{∞}| = ∞, Q(L_{∞}^{(M)}) → Q(L_{∞}) in L^{1} and thus in probability, since the conditional distribution of L_{∞} given that it is infinite equals the distribution of B_{∞}. On the other hand, conditioned on |L_{∞}| < ∞, obviously Q(L_{∞}^{(M)}) → Q(L_{∞}) a.s.. Combining the two cases, Q(L_{∞}^{(M)}) →^{p} Q(L_{∞}). Similarly Q(R_{∞}^{(M)}) →^{p} Q(R_{∞}), while N(L_{∞}^{(M)}) →^{p} N(L_{∞}) ≤ ∞ is evident. Letting M → ∞ in (5.6) thus yields (5.2). □

We can develop (5.2) further. First, L_{∞} is infinite with probability 1/2. In this case, N(L_{∞}) = ∞ and (5.2) reduces to

Q(B_{∞}) = Q(L_{∞}) + 1.  (5.7)

Moreover, the conditional distribution of L_{∞} given |L_{∞}| = ∞ equals the unconditional distribution of B_{∞}.

The other possibility is L_{∞} finite; in this case R_{∞} is infinite and its (conditional) distribution equals the unconditional distribution of B_{∞}, while L_{∞} has the same distribution as B_{∗}. We rewrite (5.2) as

Q(B_{∞}) = β(L_{∞}) + α(L_{∞})Q(R_{∞})  (5.8)

where, for a finite binary tree B,

α(B) := \frac{1}{N(B) + 1}
β(B) := \frac{N(B)Q(B) + N(B) + 2}{N(B) + 1} = \frac{W (B) + N(B) + 2}{N(B) + 1}.

We can combine (5.7) and (5.8) into the following fixed point equation.

Theorem 5.7. The limit random variable Q = Q(B_{∞}) in Theorems 2.2 and 3.1 satifies the fixed point equation Q =^{d} AQ + B, where (A, B) is independent of Q and has the distribution given by

(A, B) =^{d} \begin{cases}(1, 1), & η = 0, \\ (α(B_{∗}), β(B_{∗})), & η = 1, \end{cases}

where η ∼ Bi(1, 1/2) and B_{∗} are independent. □

We can obtain a slightly simpler fixed point equation if we follow the leftmost branch of B_{∞} until we find a vertex v with a finite left subtree, i.e. until the infinite path makes its first right turn. (In the branching process construction above, we continue until the left child is mortal.) Let ζ ≥ 0 be the height of v, and denote its left and right subtrees by L and R. Then, ζ, L and R are independent; ζ has a geometric distribution Ge(1/2); L is finite and L =^{d} B_{∗}; and R is infinite and R =^{d} B_{∞}. Applying (5.7) ζ times followed by (5.8), we find

Q(B_{∞}) = β(L) + α(L)Q(R) + ζ.

This yields the following alternative fixed point equation.

Theorem 5.8. The limit random variable Q in Theorems 2.2 and 3.1 satifies the fixed point equation Q =^{d} A′Q + B′, where (A′, B′) is independent of Q and has the distribution given by

(A′, B′) =^{d} (α(B_{∗}), β(B_{∗}) + ζ),

where ζ ∼ Ge(1/2) and B_{∗} are independent. □

Corollary 5.9. The limit of 𝔼 Q(F_{n}) and 𝔼 Q(B_{n}) is given by

\begin{aligned}𝔼 Q & = 𝔼 Q(B_{∞}) = \frac{𝔼 B′}{1 − 𝔼 A′} = \frac{𝔼 β(B_{∗}) + 1}{1 − 𝔼 α(B_{∗})} \\ & = \frac{(2 − 𝔼 α(B_{∗})) 𝔼 Q(B_{∗}) + 1}{1 − 𝔼 α(B_{∗})} = 𝔼 Q(B_{∗}) + \frac{𝔼 Q(B_{∗}) + 1}{1 − 𝔼 α(B_{∗})}. \end{aligned}

Proof. Taking expectations in Theorem 5.8 we find 𝔼 Q = 𝔼 A′ 𝔼 Q + 𝔼 B′, which yields the second inequality, and the third follows by the definitions of A′ and B′, since 𝔼 ζ = 1. (Theorem 5.7 leads to the same result.)

Next, we argue as above for the finite random tree B_{∗} too. In this case, the tree is empty and Q(B_{∗}) = 0 with probability 1/2, and otherwise Q(B_{∗}) = β(L_{∗}) + α(L_{∗})Q(R_{∗}), where L_{∗} and R_{∗} are independent with the same distribution as B_{∗}. This can be written, in analogy with Theorem 5.7, Q(B_{∗}) =^{d} A_{0}Q(B_{∗}) + B_{0}, where (A_{0}, B_{0}) is independent of Q(B_{∗}) and has the distribution given by

(A_{0}, B_{0}) =^{d} \begin{cases}(0, 0), & η = 0, \\ (α(B_{∗}), β(B_{∗})), & η = 1, \end{cases}

where η ∼ Bi(1, 1/2) as above is independent of B_{∗}. Taking expectations we find

𝔼 Q(B_{∗}) = \frac{𝔼 B_{0}}{1 − 𝔼 A_{0}} = \frac{𝔼 β(B_{∗})}{2 − 𝔼 α(B_{∗})}

or 𝔼 β(B_{∗}) = (2 − 𝔼 α(B_{∗})) 𝔼 Q(B_{∗}), and the result follows. □

Note that the variables A, B, A′ and B′ are discrete and take only rational values; for example, A′ takes the values {1/k}_{k=2}^{∞}, while B and B′ are unbounded. (We do not know whether the range B and B′ is the set of all nonnegative rational numbers.) Since B_{∗} and the auxiliary variables η and ζ only take countably many values, with explicitly given probabilities, the distributions of these variables, and in particular their expectations, can in principle be determined numerically with arbitrary accuracy. In practice, the slow convergence of ℙ(|B_{∗}| > n) to zero together with the exponential growth of the number of trees of a given size may make it difficult to attain high precision.

We have found, using Maple, the estimates 𝔼 α(B_{∗}) = 𝔼(1+N(B_{∗}))^{−1}) ≐ 0.318, 𝔼 β(B_{∗}) ≐ 2.9, and 𝔼 Q(B_{∗}) ≐ 1.7, which yields 𝔼 Q ≐ 5.7; we have no sharp rigorous error bounds, however, so these values should not be taken as absolute truths.

The fixed point equations imply further some qualitative properties of Q.

Theorem 5.10. The limit random variable Q has a continuous distribution with support [3, ∞).

Remark 5.11. Although A and B (and A′ and B′) are discrete, Q is continuous. Indeed, this is very general, and the proof below uses only A′ ≠ 0 a.s.. However, we have not been able to resolve whether Q is absolutely continuous, although it seems very plausible. Note that singular distributions may occur in this type of fixed point equations. For example, A = 1/3 and B ∼ Bi(1, 1/2) yields the Cantor measure (up to a scale factor).

Proof. Let p(x) := ℙ(Q = x) and suppose that p(x) > 0 for some x. Let p_{0} := sup_{x} p(x) > 0. It is easily seen that this supremum is attained, since ∑_{x} p(x) ≤ 1, so we can choose x with p(x) = p_{0}. By Theorem 5.8,

p_{0} = ℙ(A′Q + B′ = x) = 𝔼(ℙ(Q = (x − B′)/A′)) = 𝔼 p((x − B′)/A′).

Since p(y) ≤ p_{0}, this is possible only if p((x − B′)/A′) = p_{0} for all values of A′ and B′, but this implies that p(y) = p_{0} for infinitely many values of y, which contradicts ∑_{y} p(y) ≤ 1. Hence p(x) = 0 for every x, i.e., the distribution of Q is continuous.

Next, it is easily shown by (3.1) and (3.2) and induction that for any finite binary tree B,

W (B) ≥ 2N(B) − 2.

Consequently,

B′ ≥ β(B_{∗}) ≥ \frac{3N(B_{∗})}{N(B_{∗}) + 1}.

Hence, for any ε > 0, again using Theorem 5.8,

\begin{aligned}ℙ(Q < 3 − ε) & = ℙ(A′Q + B′ < 3 − ε) ≤ ℙ(\frac{Q + 3N(B_{∗})}{N(B_{∗}) + 1} < 3 − ε) \\ & = ℙ(Q < 3 − (N(B_{∗}) + 1)ε) ≤ ℙ(Q < 3 − 2ε). \end{aligned}

Evidently, this implies ℙ(Q < 3 − ε) = 0 for every ε > 0, and thus Q ≥ 3 a.s..

Conversely, let E be the support of the distribution of Q; by definition, E is closed. It follows from the fixed point equation that if x ∈ E and ℙ((A′, B′) = (a, b)) > 0, then ax + b ∈ E. In particular, taking B_{∗} = ∅ which yields α(B_{∗}) = 1/2 and β(B_{∗}) = 3/2, we find

x ∈ E ⟹ (x + 3)/2 + n ∈ E for every integer n ≥ 0.  (5.9)

Starting with any x ∈ E, taking n = 0 and iterating (5.9), we find in the limit 3 ∈ E. Taking x = 3 in (5.9), we find 3 + n ∈ E for every n ≥ 0. Finally, again taking n = 0 in (5.9), we find by induction on k, that E contains every dyadic rational 3 + m2^{−k} with m, k ≥ 0. Since E is closed, E ⊇ [3, ∞). □

Remark 5.12. Although B_{∗} is finite, its size has infinite expectation. Indeed, for every critical branching process, the expected size of each generation is the same, in this case 1/2; this follows also from the fact that each of the 2^{k} possible vertices at height k appears with probability 2^{−k−1}.

In B_{∞}, there is at height k one immortal and on the average 1/2 mortal in each of the k finite branches descending from the k immortals closer to the root. Hence the expected number of vertices at height k is k/2 + 1 and, by symmetry, each of the 2^{k} possible vertices appears with probability (k +2)2^{−k−1}. This illustrates that the infinite tree B_{∞} is sparse and stringy.

As a further illustration, consider the intersection of two independent copies of B_{∞}; the expected size is ∑_{k=0}^{∞} 2^{k}(k + 2)^{2}2^{−2k−2} = 11/2. (This can also be seen by considering the two independent two-type branching processes generating the trees as a single branching process with 4 types representing the common vertices and the pairs of types there. We leave the details as an exercise.) Hence, two independent random large binary trees have on the average close to 5.5 vertices in common.

For the finite trees B_{n}, and more generally for any conditioned Galton– Watson trees with finite offspring variance, it is known that the bulk of the vertices have heights of the order \sqrt{n}; see e.g. [1], [2] and [14] for much more detailed results.

6. Back to the forest

The results on binary trees in Section 5 can be translated to results on forests by the correspondence discussed in Section 3, which extends to infinite forests and binary trees. Note that the number of trees in a forest equals the number of vertices in the rightmost branch of the corresponding binary tree. Again, we begin with some simple, more or less well-known observations.

We let F_{∗} be the (finite) random forest corresponding to the random binary tree B_{∗}. The construction of B_{∗} in Section 5 shows that the number of vertices in the rightmost branch has the geometric distribution Ge(1/2). Consequently, the number of trees in F_{∗} is Ge(1/2). Similarly, the number of children of any vertex is Ge(1/2), and all these numbers are independent. Consequently, F_{∗} is a Galton–Watson forest obtained from a Galton–Watson process with Ge(1/2) initial individuals (roots) and offspring distribution Ge(1/2). Note that this, too, is a critical Galton–Watson process.

Equivalently, if T_{∗} is the Galton–Watson tree with offspring distribution Ge(1/2), then T_{∗} equals F_{∗} with all components joined to a common added root; conversely, F_{∗} = T_{∗}^{∗}.

It follows immediately that |F_{∗}| = |B_{∗}| =^{d} ξ and |T_{∗}| = |F_{∗}| + 1 =^{d} ξ + 1, that F_{∗} conditioned on |F_{∗}| = n has the distribution of F_{n}, and that T_{∗} conditioned on |T_{∗}| = n has the distribution of T_{n}.

Similarly, let F_{∞} be the random infinite forest corresponding to B_{∞}, and let T_{∞} be the random infinite tree obtained by adding a root to F_{∞}; thus F_{∞} = T_{∞}^{∗}. We can decompose the rightmost branch of B_{∞} into the part belonging to the infinite path, which has 1 + Ge(1/2) vertices, and the part after it, which is independent of the first part and has the same distribution as the rightmost branch in B_{∗}, i.e. it has Ge(1/2) vertices. Hence, if ζ̂ is the total number of vertices in the rightmost branch of B_{∞}, then ζ̂ = 1 + ζ + ζ′, where ζ and ζ′ are independent and Ge(1/2). (In the equivalent branching process construction, the rightmost branch has 1+ζ immortal and ζ′ mortal vertices.) It follows that ζ̂, which also is the number of components in F_{∞} and the degree of the root in T_{∞}, has a shifted negative binomial distribution,

ℙ(ζ̂ = k) = k2^{−k−1},  k = 1, 2, …;  (6.1)

this is the size-biased distribution Ĝe(1/2).

Using the branching process construction of B_{∞}, exposing first the rightmost branch, then the rightmost branches in the left subtrees sprouting from it, and so on, it is now easily seen that T_{∞} is the tree produced by the size-biased Galton–Watson process defined in Remark 5.4 with the offspring distribution Ge(1/2) for the mortals, and thus Ĝe(1/2) for the immortals. F_{∞} is obtained by chopping off the root of T_{∞}, or by starting with Ĝe(1/2) individuals (roots), one of them immortal.

Note that F_{∞} and T_{∞} are locally finite and have exactly one infinite path (the immortals). The equation ζ̂ = ζ + 1 + ζ′ above shows that F_{∞} and T_{∞} also can be constructed by starting with an infinite path (the trunk) and adding to each vertex in it a Ge(1/2) number of branches to each side, each branch being an independent copy of T_{∗}; for F_{∞} we further add a Ge(1/2) number of copies of T_{∗} on each side of the infinite component as separate components. (All random choices should be independent.)

It is easily seen that Lemma 5.2 implies the corresponding statements for forests and trees. (This is another instance of the general result given in Remark 5.4.) Note, however, that the truncation F_{∞}^{(M)} does not correspond to the truncation B_{∞}^{(M)}; it corresponds to B_{∞}^{[M]}, where we let B^{[M]} denote the binary tree B with each branch truncated after M steps to the left. (Note that B_{∞}^{[M]} a.s. is a finite tree.) We give a formal statement.

Lemma 6.1. As n → ∞, F_{n} →^{d} F_{∞} and T_{n} →^{d} T_{∞} in the sense of finite-di-mensional distributions, in the sense F_{n}^{(M)} →^{d} F_{∞}^{(M)} and T_{n}^{(M)} →^{d} T_{∞}^{(M)} for every finite M.

Proof. Fix M ≥ 0. Lemma 5.2 implies that for each fixed finite binary tree

b, ℙ(B_{n}^{[M]} = b) → ℙ(B_{∞}^{[M]} = b), and thus B_{n}^{[M]} →^{d} B_{∞}^{[M]}. □

Using the correspondence between forests and binary trees, we now define Q for infinite forests too; thus Q(F_{∞}) = Q(B_{∞}), and the limit Q in Theorem 2.2 can be taken as Q(F_{∞}). The following theorem shows that Q can be defined (a.s.) directly on infinite forests without our use of binary forests as a convenient technical tool.

Theorem 6.2. There exists an extension of Q to infinite forests such that we have 𝔼 |Q(F_{∞}^{(M)}) − Q(F_{∞})| → 0 as M → ∞. We have Q(F_{n}) →^{d} Q(F_{∞}) as n → ∞. Furthermore, Q(F_{∞}) = Q(B_{∞}) when B_{∞} corresponds to F_{∞}.

Proof. It remains only to prove that 𝔼 |Q(F_{∞}^{(M)}) − Q(F_{∞})| → 0, or equivalently, transfering to binary trees again, that 𝔼 |Q(B_{∞}^{[M]}) − Q(B_{∞})| → 0.

Let, for M ≥ 1,

δ^{[M]} := sup_{n} 𝔼 |Q(B_{n}^{[M]}) − Q(B_{n})|.

The proof of Lemma 5.6 shows with minor modifications that δ^{[M]} → 0; note that B_{n}^{[M+1]} has the subtrees L_{n}^{[M]} and R_{n}^{[M+1]}, but this causes no significant problem. Moreover, we now need a preliminary step to ensure that δ^{[M]} < ∞; this is easily done using induction, since (3.3) implies Q(B) < Q(L) + 2 + \frac{1}{2}Q(R), and we omit the details.

For every M we have as n → ∞, see the proof of Lemma 6.1, B_{n}^{[M]} →^{d} B_{∞}^{[M]}. Moreover, since B^{(M)} is a truncation of B^{[M]}, we have joint convergence of (B_{n}^{[M]}, B_{n}^{(M)}) to (B_{∞}^{[M]}, B_{∞}^{(M)}), and consequently

Q(B_{n}^{[M]}) − Q(B_{n}^{(M)}) →^{d} Q(B_{∞}^{[M]}) − Q(B_{∞}^{(M)}).

Since 𝔼 |Q(B_{n}^{[M]})−Q(B_{n}^{(M)})| ≤ δ^{[M]} +δ^{(M)} for each n, Fatou’s lemma yields

𝔼 |Q(B_{∞}^{[M]}) − Q(B_{∞}^{(M)})| ≤ δ^{[M]} + δ^{(M)},

which tends to 0 as M → ∞ by Lemma 5.6 and the claim above. Finally, the triangle inequality and Theorem 5.5 yields

𝔼 |Q(F_{∞}^{(M)}) − Q(F_{∞})| = 𝔼 |Q(B_{∞}^{[M]}) − Q(B_{∞})| → 0,  M → ∞. □

Remark 6.3. We saw above that the number of components of the infinite random forest F_{∞} has the shifted negative binomial distribution in (6.1); hence, by Lemma 6.1, the number of components of the random forest F_{n} has asymptotically this distribution. It is easy to find the exact distribution for finite n as follows. The generating function for ordered trees is zB(z), with B(z) given in (3.7), and thus the generating function for ordered forests with k components is z^{k}B(z)^{k}. It follows as an easy exercise, using e.g. [6, (5.70)], that, with n\underline{k} denoting the falling factorial,

ℙ(F_{n} has k components) = \frac{\frac{k}{2n−k} \binom{2n−k}{n}}{C_{n}} = k \frac{(n + 1)\underline{k+1}}{(2n)\underline{k+1}} .

This evidently converges to k2^{−k−1} as n → ∞, as asserted above.

Remark 6.4. There is a well-known correspondence between (random) trees and (random) walks on the non-negative integers by means of the depth first walk, see e.g. [1]. In this context, several nice results are known for the random trees studied here.

The random tree T_{n} corresponds to a simple random walk of length 2n conditioned on returning to 0 at the end but not before (sometimes called Dyck paths). The random tree T_{∗} corresponds to a simple random walk stopped at its first return to 0 [12]. For the infinite tree T_{∞}, the depth first walk only captures the structure on one side of the infinite trunk; the other side is described by a depth first walk running in the opposite direction. The two depth first walks are independent, and each is a biased random walk which is a discrete version of the three-dimensional Bessel process, see Le Gall [12].

References

[1] D. Aldous (1991), The continuum random tree II: an overview. In Proc. Durham Symp. Stoch. Analysis 1990, Cambridge Univ. Press, 23–70.

[2] D. Aldous (1993), The continuum random tree III. Ann. Probab. 21, no. 1, 248–289.

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

[4] P. Billingsley (1968), Convergence of Probability Measures. Wiley, New York.

[5] T.E. Harris (1951), Some mathematical models for branching processes. In Second Berkeley Symposium on Mathematical Statistics and Probability, Univ. California Press, Berkeley, 305–328.

[6] R.L. Graham, D.E. Knuth & O. Patashnik (1994), Concrete Mathematics. 2nd ed., Addison–Wesley, Reading, Mass.

[7] D.P. Kennedy (1975), The Galton–Watson process conditioned on the total progeny. J. Appl. Probab. 12, 800–806.

[8] M. Klazar (1997), Twelve countings with rooted plane trees. European J. Combin. 18, no. 2, 195–210. Addendum: European J. Combin. 18, no. 6, 739–740.

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

[10] D.E. Knuth, KODA-RUSKEY. CWEB program. Available from

http://Sunburn.Stanford.EDU/~knuth/programs/koda-ruskey.w

[11] Y. Koda & F. Ruskey (1993), A Gray code for the ideals of a forest poset. J. Algorithms 15, no. 2, 324–340.

[12] J.-F. Le Gall (1986), Une approche élémentaire des théorèmes de décomposition de Williams. In Séminaire de Probabilités, XX, 1984/85, Lecture Notes in Math., 1204, Springer, Berlin, 447–464.

[13] R. Lyons, R. Pemantle & Y. Peres (1995), Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab. 23, no. 3, 1125–1138.

[14] J.-F. Marckert & A. Mokkadem (2001), The depth first processes of Galton–Watson trees converge to the same Brownian excursion. To appear in Ann. Probab.

[15] S.T. Rachev (1991), Probability metrics and the stability of stochastic models. Wiley, Chichester, U.K.

[16] S.T. Rachev & L. Rüschendorf (1995), Probability metrics and recursive algorithms, Adv. Appl. Probab. 27, 770–799.

[17] U. Rösler(1991), A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25, no. 1, 85–100.

[18] U. Rösler(1992), A fixed point theorem for distributions. Stochastic Process. Appl. 42, no. 2, 195–214.

[19] U. Rösler & L. Rüschendorf (2001), The contraction method for recursive algorithms. Algorithmica 29, 3-33.

[20] F. Ruskey (1981), Listing and counting subtrees of a tree. SIAM J. Comput. 10, no. 1, 141–150.

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/