MOMENT CONVERGENCE IN CONDITIONAL LIMIT THEOREMS

SVANTE JANSON

Abstract. Consider a sum ∑_{1}^{N} Y_{i} of random variables conditioned on a given value of the sum ∑_{1}^{N} X_{i} of some other variables, where X_{i} and Y_{i} are dependent but the pairs (X_{i}, Y_{i}) form an i.i.d. sequence.

We consider here the case when each X_{i} is discrete. We prove, for a triangular array ((X_{ni}, Y_{ni})) of such pairs satisfying certain conditions, both convergence of the distribution of the conditioned sum (after suitable normalization) to a normal distribution, and convergence of its moments.

The results are motivated by an application to hashing with linear probing; we give also some other applications to occupancy problems, random forests, and branching processes.

1. Introduction

Many random variables arising in different areas of probability theory, combinatorics and statistics turn out to have the same distribution as a sum of independent random variables conditioned on a specific value of another such sum. More precisely, we are concerned with variables with the distribution of ∑_{1}^{N} Y_{i} conditioned on ∑_{1}^{N} X_{i}, where the pairs (X_{i}, Y_{i}) form a sequence of i.i.d. random vectors; in general, the variables X_{i} can be discrete or continuous, or even vector-valued. Some examples are given in Section 3 below, and many others in, for example, [5, 6, 7, 11, 12].

General limit theorems yielding the asymptotic behaviour of the conditioned sum under suitable assumptions are given by, among others, Steck [21], Holst [5, 7] and Kudlaev [13]. (See also results on asymptotic expansions in [2, 14, 4, 8] and on rates of convergence in [15].)

The purpose of this paper is to give a set of sufficient conditions for convergence of not only the distribution of the conditioned sum but also its moments. We consider only the case when the variables X_{i} are discrete; we expect that extensions to the continuous case are possible but not trivial. For simplicity we further only consider the case when the limit distribution is normal. (Asymptotics of the mean and variance in a case overlapping with ours has earlier been studied by Swensen [22] in a somewhat different formulation. The mean, in the equivalent form 𝔼(Y_{1} | ∑_{1}^{N} X_{i}), has been studied by Portnoy [19] and Zabell [25, 26].)

Date: May 8, 2000; revised May 2, 2001.

1991 Mathematics Subject Classification. 60F05.

Key words and phrases. Conditional distribution, limit theorem, moment convergence, occupancy, hashing, random forest, branching process.

The theorem is stated, in several versions, in Section 2 and proved in Section 4. The results in this paper were motivated by an application to hashing with linear probing. This application is described in Section 3 (Example 3.2) together with some other applications.

2. Main results

We state our main result in the following form. The large number of conditions in the theorem is perhaps not so elegant, but we have chosen to state a version that is easy to apply; all conditions are easily verified in the applications of interest to us. Some alternative versions of the conditions are discussed in the remarks after the statement.

We use the notation σ_{X}^{2} := Var X for a random variable X.

Theorem 2.1. (a) Suppose that, for each n, (X_{n}, Y_{n}) is a pair of random variables such that X_{n} is integer valued, and that N_{n} and m_{n} are integers. Suppose further that for some γ and c (independent of n), with 0 < γ ≤ 2 and c > 0, the following hold, where all limits are taken as n → ∞:

(i) 𝔼 X_{n} = m_{n}/N_{n}. (ii) 0 < σ_{X_{n}}^{2} < ∞. (iii) 𝔼 |X_{n} − 𝔼 X_{n}|^{3} = o(N_{n}^{1/2}σ_{X_{n}}^{3}). (iv) σ_{X_{n}}^{2} = O(N_{n}^{2/γ−1}).

(v) φ_{X_{n}}(s) := 𝔼 e^{isX_{n}} satisfies 1−|φ_{X_{n}}(s)| ≥ c min(|s|^{γ}, s^{2}σ_{X_{n}}^{2}) for |s| ≤ π. (vi) 0 < σ_{Y_{n}}^{2} < ∞. (vii) 𝔼 |Y_{n} − 𝔼 Y_{n}|^{3} = o(N_{n}^{1/2}σ_{Y_{n}}^{3}). (viii) The correlation ρ_{n} := Cov(X_{n}, Y_{n})/σ_{X_{n}}σ_{Y_{n}} satisfies lim sup |ρ_{n}| < 1.

Let (X_{ni}, Y_{ni}), i = 1, 2, …, be i.i.d. copies of (X_{n}, Y_{n}), and let S_{nN} := ∑_{1}^{N} X_{ni}, T_{nN} := ∑_{1}^{N} Y_{ni} and τ_{n}^{2} := σ_{Y_{n}}^{2}(1 − ρ_{n}^{2}) = σ_{Y_{n}}^{2} − Cov(X_{n}, Y_{n})^{2}/σ_{X_{n}}^{2}. Then, as n → ∞, the conditional distribution of (T_{nN_{n}} − N_{n} 𝔼 Y_{n})/N_{n}^{1/2}τ_{n} given S_{nN_{n}} = m_{n} converges to a standard normal distribution. In other words, if U_{n} is a random variable whose distribution equals the conditional distribution of T_{nN_{n}} given S_{nN_{n}} = m_{n}, then

\frac{U_{n} − N_{n} 𝔼 Y_{n}}{N_{n}^{1/2}τ_{n}} →^{d} N(0, 1).  (2.1)

Moreover, 𝔼 U_{n} = N_{n} 𝔼 Y_{n} + o(N_{n}^{1/2}τ_{n}) and Var U_{n} ∼ N_{n}τ_{n}^{2}, and thus also

\frac{U_{n} − 𝔼 U_{n}}{(Var U_{n})^{1/2}} →^{d} N(0, 1).  (2.2)

(b) Assume furthermore that for each even integer r ≥ 4 (ix) 𝔼(X_{n} − 𝔼 X_{n})^{r} = O(N_{n}^{r/2−1}σ_{X_{n}}^{r}),

(x) 𝔼(Y_{n} − 𝔼 Y_{n})^{r} = O(N_{n}^{r/2−1}σ_{Y_{n}}^{r}). Then the limits (2.1) and (2.2) hold with convergence of all moments too.

Remark 2.1. Note that using the Lebesgue space norm ∥X∥_{r} = (𝔼 |X|^{r})^{1/r}, the assumptions (iii), (vii), (ix) and (x) can be written (iii′) ∥X_{n} − 𝔼 X_{n}∥_{3} = o(N_{n}^{1/6}σ_{X_{n}}), (vii′) ∥Y_{n} − 𝔼 Y_{n}∥_{3} = o(N_{n}^{1/6}σ_{Y_{n}}), (ix′) ∥X_{n} − 𝔼 X_{n}∥_{r} = O(N_{n}^{1/2−1/r}σ_{X_{n}}), (x′) ∥Y_{n} − 𝔼 Y_{n}∥_{r} = O(N_{n}^{1/2−1/r}σ_{Y_{n}}). Since Minkowski’s and Hölder’s inequalities yield ∥X_{n} − 𝔼 X_{n}∥_{3} ≤ ∥X_{n}∥_{3} +

| 𝔼 X_{n}| ≤ 2∥X_{n}∥_{3}, it is for (iii) sufficient that ∥X_{n}∥_{3} = o(N_{n}^{1/6}σ_{X_{n}}), or 𝔼 |X_{n}|^{3} = o(N_{n}^{1/2}σ_{X_{n}}^{3}). More generally, it is sufficient that 𝔼 |X_{n} − a_{n}|^{3} = o(N_{n}^{1/2}σ_{X_{n}}^{3}) for some sequence of constants a_{n}. The same applies, mutatis mutandis, to (vii), (ix) and (x).

In other words, the theorem holds also if 𝔼 X_{n} and 𝔼 Y_{n} in (iii), (vii), (ix) and (x) are omitted or replaced by any other numbers.

Remark 2.2. It is immediate that (viii) is equivalent to lim inf τ_{n}^{2}/σ_{Y_{n}}^{2} > 0, and thus also to

(viii′) τ_{n}^{2} = Θ(σ_{Y_{n}}^{2}). (This notation means that lim sup τ_{n}^{2}/σ_{Y_{n}}^{2} and lim sup σ_{Y_{n}}^{2}/τ_{n}^{2} both are finite.) In cases where this fails, one might apply the theorem to a suitable modification Y_{n} + a_{n}X_{n} + b_{n} instead, for example to the projection Y′_{n} in (4.1); note that this changes U_{n} by the constant a_{n}m_{n} + b_{n}N_{n} only.

Remark 2.3. τ_{n}^{2} equals min{Var(Y_{n} − aX_{n}) : a ∈ ℝ} (the residual variance in linear regression). Hence τ_{n}^{2} is unchanged if Y_{n} is replaced by Y_{n} + a_{n}X_{n} + b_{n} for any real constants a_{n} and b_{n}.

Remark 2.4. We consider here, for simplicity, only the central case when (i) holds; equivalently, m_{n} = 𝔼 S_{nN_{n}} and thus we condition on S_{nN_{n}} = 𝔼 S_{nN_{n}}. In applications we usually take X_{n} from an exponential family and adjust the parameter so that (i) holds. Nevertheless, it is interesting to consider other cases too, and we give a generalization in Theorem 2.3 below.

Remark 2.5. The conditions (iv) and (v) are connected through the choice of γ. They are used in the proof only to provide suitable dominations and may be combined and weakened, for example to

|φ_{X_{n}}(s)| ≤ 1 − \frac{2}{N_{n}} ln(N_{n}σ_{X_{n}}^{2}s^{2}) + \frac{c}{N_{n}} ,  |s| ≤ π,  (2.3)

but the version given above seems more convenient in our applications. Condition (v) (or (2.3)) is the most technical and least intuitive of our conditions, and it would be interesting to find other conditions not explicitly involving the characteristic function that could replace it. (See Corollary 2.1 for a simple case.) Unfortunately, the condition cannot be eliminated completely, as is shown by Example 3.7.

Remark 2.6. The powers of N_{n} in (iii), (vii), (ix) and (x) may look strange at first, but the conditions turn out to be sharp in many cases; moreover, the o in (iii) and (vii) cannot be replaced by O. See Examples 3.1, 3.2, 3.5 and 3.6. (There may be room for improvements of (ix), however.)

Remark 2.7. It follows from the proof below that if the extra conditions in (b) are satisfied for a specific even r ≥ 4 only, then all moments of order less than r converge; moreover, a minor modification of the proof shows that if the O in (ix) and (x) is strengthened to o, then also the r:th moment converges. (It is shown in Example 3.5 that (ix) and (x) are not sufficient for convergence of the r:th moment.) The same holds for odd r ≥ 3 if we use absolute moments in (ix) and (x).

The result simplifies considerably in the special case when (X_{n}, Y_{n}) does not depend on n, so we consider a single sequence instead of a triangular array. This is included in the following, more general, corollary.

Corollary 2.1. Suppose that (X_{n}, Y_{n}) →^{d} (X, Y) as n → ∞, and that, for every fixed r > 0, lim sup_{n→∞} 𝔼 |X_{n}|^{r} < ∞ and lim sup_{n→∞} 𝔼 |Y_{n}|^{r} < ∞. Suppose further that the distribution of X has span 1, and that Y is not a.s. equal to a linear function c + dX.

If m_{n} and N_{n} are integers such that 𝔼 X_{n} = m_{n}/N_{n} and N_{n} → ∞, then all conclusions of Theorem 2.1 hold, with τ_{n}^{2} → Var Y − Cov(X, Y)^{2}/ Var X > 0.

Remark 2.8. The assumptions of Corollary 2.1 imply that m_{n}/N_{n} → 𝔼 X. Conversely, in the important case of an exponential family of distributions, when the set of possible values of 𝔼 X is an interval I, under weak additional assumptions, the corollary applies when lim m_{n}/N_{n} exists and lies in the interior of I.

The results above easily extend to joint convergence for several random variables conditioned on the same sum. Note that the conditions on X_{n} in the next theorem, (i)–(v) and (ix), are exactly the same as in Theorem 2.1, while we have chosen a slightly different formulation of the conditions for Y_{n}, involving somewhat arbitrary normalization constants b_{nj}. This version is sometimes more convenient even in the case of a single variable Y_{n}; for example, in the situation in Corollary 2.1, we may take b_{n1} = 1.

Theorem 2.2. (a) Suppose that, for each n, (X_{n}, Y_{n}) is a pair of random variables such that X_{n} is integer valued and Y_{n} = (Y_{n}^{(1)}, …, Y_{n}^{(l)}) is a random vector (l does not depend on n). Suppose further that N_{n} and m_{n} are integers and b_{nj}, j = 1, …, l, are positive real numbers, and that for some γ and c (independent of n), with 0 < γ ≤ 2 and c > 0, the following hold, where all limits are taken as n → ∞:

(i) 𝔼 X_{n} = m_{n}/N_{n}. (ii) 0 < σ_{X_{n}}^{2} < ∞. (iii) 𝔼 |X_{n} − 𝔼 X_{n}|^{3} = o(N_{n}^{1/2}σ_{X_{n}}^{3}). (iv) σ_{X_{n}}^{2} = O(N_{n}^{2/γ−1}).

(v) φ_{X_{n}}(s) := 𝔼 e^{isX_{n}} satisfies 1−|φ_{X_{n}}(s)| ≥ c min(|s|^{γ}, s^{2}σ_{X_{n}}^{2}) for |s| ≤ π. (vi) Var Y_{n}^{(j)} = O(b_{nj}^{2}). (vii) 𝔼 |Y_{n}^{(j)} − 𝔼 Y_{n}^{(j)}|^{3} = o(N_{n}^{1/2}b_{nj}^{3}).

(viii) For some numbers σ_{jk}, 1 ≤ j, k ≤ l,

b_{nj}^{−1}b_{nl}^{−1}(Cov(Y_{n}^{(j)}, Y_{n}^{(l)}) − \frac{Cov(Y_{n}^{(j)}, X_{n}) Cov(Y_{n}^{(l)}, X_{n})}{Var X_{n}}) → σ_{jk}.  (2.4)

Let (X_{ni}, Y_{ni}), i = 1, 2, …, be i.i.d. copies of (X_{n}, Y_{n}), and let S_{nN} := ∑_{1}^{N} X_{ni} and T_{nN} := ∑_{1}^{N} Y_{ni}. If U_{n} = (U_{n}^{(1)}, …, U_{n}^{(l)}) is a random vector whose distribution equals the conditional distribution of T_{nN_{n}} given S_{nN_{n}} = m_{n}, then, as n → ∞,

(N_{n}^{−1/2}b_{nj}^{−1}(U_{n}^{(j)} − N_{n} 𝔼 Y_{n}^{(j)}))_{j=1}^{l} →^{d} N(0, Σ)  (2.5)

and

(N_{n}^{−1/2}b_{nj}^{−1}(U_{n}^{(j)} − 𝔼 U_{n}^{(j)}))_{j=1}^{l} →^{d} N(0, Σ),  (2.6)

where the covariance matrix Σ := (σ_{jk}). Moreover, the mean and covariance matrix of the left hand sides converge to 0 and Σ, respectively.

(b) Assume furthermore that for each even integer r ≥ 4 (ix) 𝔼(X_{n} − 𝔼 X_{n})^{r} = O(N_{n}^{r/2−1}σ_{X_{n}}^{r}),

(x) 𝔼(Y_{n}^{(j)} − 𝔼 Y_{n}^{(j)})^{r} = O(N_{n}^{r/2−1}b_{nj}^{r}). Then the limits (2.5) and (2.6) hold with convergence of all (mixed) moments.

We can condense the conditions as follows (in a rather general special case).

Corollary 2.2. Suppose that, for each n, (X_{n}, Y_{n}) is as in Theorem 2.2 and that each pair (X_{n}, Y_{n}^{(j)}), j = 1, …, l, satisfies the assumptions of Theorem 2.1 (or Corollary 2.1). Suppose further that b_{nj} are positive numbers such that (2.4) holds. Then the conclusions of Theorem 2.2 hold.

As said in Remark 2.4, it is also interesting to consider the case m_{n} ≠ 𝔼 S_{nN_{n}}. In the central region m_{n} = 𝔼 S_{nN_{n}} + O((Var S_{nN_{n}})^{1/2}) the results above hold with only minor modifications; for simplicity we state only an extension of Theorem 2.1, leaving the special case in Corollary 2.1 and the vector-valued case to the reader. (We will not consider the case when m_{n} is in the more distant tails of the distribution of S_{nN_{n}}. See [25] for the expectation in such a situation.)

Theorem 2.3. Let the conditions in Theorem 2.1 be satisfied except that (i) is replaced by

(i′) m_{n} = N_{n} 𝔼 X_{n} + O(N_{n}^{1/2}σ_{X_{n}}). Then (2.2) still holds, with moment convergence as before if (ix) and (x) hold, but

𝔼 U_{n} = N_{n} 𝔼 Y_{n} + ρ_{n} \frac{σ_{Y_{n}}}{σ_{X_{n}}} (m_{n} − N_{n} 𝔼 X_{n}) + o(N_{n}^{1/2}τ_{n})  (2.7)

and thus (2.1) has to be correspondingly modified.

In particular, this implies results of the type of Swensen [22], under somewhat different conditions.

Remark 2.9. It follows from Theorem 2.3 that the conclusions of Theorem 2.1 are valid without modifications if (i) is weakened to

(i′′) m_{n} = N_{n} 𝔼 X_{n} + o(N_{n}^{1/2}σ_{X_{n}}).

The same holds for Corollary 2.1, Theorem 2.2 and Corollary 2.2.

3. Applications

Example 3.1 (Occupancy). In the classical occupancy problem, m balls are distributed at random into N urns. The resulting numbers of balls Z_{1}, …, Z_{N} have a multinomial distribution, and it is well-known that this equals the distribution of (X_{1}, …, X_{N}) conditioned on ∑_{1}^{N} X_{i} = m, where X_{1}, …, X_{N} are i.i.d. with X_{i} ∈ Po(λ), for an arbitrary λ > 0 [12, 6].

The classical occupancy problem studies the number W of empty urns; this is thus ∑_{1}^{N} 1[X_{i} = 0] conditioned on ∑_{1}^{N} X_{i} = m. Now suppose that m = m_{n} → ∞ and N = N_{n} → ∞. Then, W = W_{n} can thus be taken as U_{n} in Theorem 2.1 with X_{n} ∈ Po(λ_{n}) and Y_{n} := 1[X_{n} = 0] for any λ_{n}; we choose λ_{n} = m_{n}/N_{n} so that (i) holds.

If m_{n}, N_{n} → ∞ such that m_{n}/N_{n} → a ∈ (0, ∞), then Corollary 2.1 immediately yields asymptotic normality of W_{n}, with moment convergence.

In the case m_{n}/N_{n} → ∞, simple calculations, using known moment asymptotics and the explicit formula |φ_{X_{n}}(s)| = exp(−λ_{n}(1 − cos s)), show that Theorem 2.1 applies with any γ < 2, provided N_{n}e^{−m_{n}/N_{n}} → ∞. This condition is necessary for (vii), but it is also necessary for asymptotic normality because W_{n} is asymptotically Poisson distributed and not asymptotically normal if N_{n}e^{−m_{n}/N_{n}} → μ < ∞ [12]. Hence Theorem 2.1 is sharp in this case.

In the case m_{n}/N_{n} → 0, finally, Theorem 2.1 cannot be applied as stated, because Y_{n} = 1[X_{n} = 0] yields ρ_{n} → −1. Instead we choose, cf. Remark 2.2, Y_{n} := 1[X_{n} = 0] + X_{n} − 1 = (X_{n} − 1)_{+}, and it is easily verified that Theorem 2.1 applies (with γ = 2) provided m_{n}^{2}/N_{n} → ∞. Again, this condition is necessary both for (vii) and for asymptotic normality, because W_{n} −(N_{n} −m_{n}) is asymptotically Poisson distributed if m_{n}^{2}/N_{n} → μ < ∞ [12].

Theorem 2.1 thus proves asymptotic normality of W_{n} in all cases where it holds, together with moment convergence.

Actually, asymptotic normality in the case m_{n}/N_{n} → a ∈ (0, ∞) was first proved by Weiss [23] using the method of moments, i.e. by first showing moment convergence. His estimates of the moments uses a complicated combinatorial analysis, however, and the proof here seems simpler. (For other proofs of asymptotic normality, not treating moments, see [20, 12, 5]; the last reference uses the same method as this paper.)

Asymptotic normality in the other cases was shown by Rényi [20, 12]; we do not know any earlier proof of moment convergence in these cases. (It is easy to show that 𝔼 W_{n}^{r} ∼ (N_{n}e^{−m_{n}/N_{n}})^{r} for every r > 0, but we are discussing the moments after normalization, or equivalently the central moments, which are much smaller and thus much more difficult to estimate properly.)

By instead defining Y_{n} := 1[X_{n} = k], we similarly obtain asymptotic normality, with moment convergence, for the number of urns with exactly k balls, if m_{n}, N_{n} → ∞ in a suitable range. Moreover, Theorem 2.2 yields joint convergence for several k. We can also let k depend on n.

We can similarly treat sums ∑_{1}^{N} f(Z_{i}) for other functions f, for example the χ^{2}-statistic (N/m) ∑_{1}^{N}(Z_{i} − m/N)^{2}.

Further similar applications, where we now can add moment convergence, can be found in Holst [6].

Example 3.2 (Hashing). Hashing with linear probing (see Knuth [10, Section 6.4] for the computer science background) can be regarded as throwing n balls sequentially into m urns at random; the urns are arranged in a circle and a ball that lands in an occupied urn is (before the next ball is thrown) moved to the next empty urn, always moving in a fixed direction. The length of the move, if any, is called the displacement of the ball, and we are interested in the sum of all displacements. We assume n < m.

After throwing all balls, there are m − n empty urns. These divide the occupied urns into blocks of consecutive urns; for convenience we consider the empty urn following such a block as belonging to the block, and we regard an empty urn following another empty urn as a block with zero occupied urns. Thus there are N := m − n blocks, and it can be shown, see [9] for details, that the lengths of the blocks (counting the empty urn) and the sums of displacements inside each block are distributed as (X_{1}, Y_{1}), …, (X_{N}, Y_{N}) conditioned on ∑_{i=1}^{N} X_{i} = m, where (X_{i}, Y_{i}) are i.i.d. copies of a pair (X, Y) of random variables, X has the Borel distribution

ℙ(X = ℓ) = \frac{1}{T (λ)} \frac{ℓ^{ℓ−1}}{ℓ!} λ^{ℓ},  ℓ = 1, 2, …,  (3.1)

where T (λ) := ∑_{ℓ} ℓ^{ℓ−1}λ^{ℓ}/ℓ! is the well-known tree function and λ is an arbitrary number with 0 < λ ≤ e^{−1}, and the conditional distribution of Y given X = ℓ is the same as the distribution of the total displacement in the case m = ℓ, n = ℓ − 1. Consequently, the distribution of the total displacement equals the conditional distribution of ∑_{j=1}^{N} Y_{j} given ∑_{j=1}^{N} X_{j} = m, and we are in the situation studied in this paper. It is easily shown that 𝔼 X = 1/(1 − T (λ)).

Assume now that n → ∞ with m = m_{n} → ∞ and N_{n} = m_{n} − n > 0. We define λ_{n} = \frac{n}{m_{n}} exp(−n/m_{n}) which satisfies T (λ_{n}) = n/m_{n} and thus 𝔼 X_{n} = 1/(1 − n/m_{n}) = m_{n}/N_{n}, where X_{n} is as in (3.1) with λ = λ_{n}. If n/m_{n} → α ∈ (0, 1), so m_{n}/N_{n} → 1/(1 − α) and λ_{n} → λ ∈ (0, e^{−1}), Corollary 2.1 immediately shows that that the total displacement is asymptotically normal, as previously shown by Flajolet, Poblete and Viola [3]; we further obtain moment convergence. Moreover, straightforward estimates, see [9] for details, show that Theorem 2.1 applies also when n/m_{n} → 0 or n/m_{n} → 1 (with γ = 2 and γ = 1/2, respectively), provided n ≫ \sqrt{m}_{n} and m_{n} − n ≫ \sqrt{m_{n}}. (When one of these conditions fails, the distribution is not asymptotically normal, see [9]; hence Theorem 2.1 is sharp in this application too.)

Example 3.3 (Random forests). Consider a uniformly distributed random labelled rooted forest with m vertices and N < m roots. (We may assume that the vertices are 1, …, m and, by symmetry, that the roots are 1, …, N.) Let n := m − N be the number of non-roots.

The sizes of the N trees in the forest are distributed as X_{1}, …, X_{N} conditioned on ∑_{i=1}^{N} X_{i} = m, where X_{i} are i.i.d. with the Borel distribution (3.1) for some λ [16, 11, 17]. Thus, the distribution of the tree sizes is the same as the distribution of the block lengths in Example 3.2, cf. [10, Exercise 6.4-31] and [1].

Let N = N_{n} and m = m_{n} = n+N_{n} and consider the number W_{nk} of trees of size k. Pavlov [16, 17] has shown, using similar methods, asymptotic normality of W_{nk} for every fixed k ≥ 1, provided n, N_{n} → ∞ and N_{n}(n/N_{n})^{max(k,2)} → ∞. (He also gave local limit theorems, which are not treated here.) Unfortunately, we do not recover the full result by our theorems, but under the additional assumption m_{n} ≪ N_{n}^{2}, we can show asymptotic normality. The case N_{n}/m_{n} → a ∈ (0, 1) follows by Corollary 2.1, choosing X_{n} as in Example 3.2 and Y_{n} = 1[X_{n} = k]. Similarly, the case N_{n} ≪ m_{n} ≪ N_{n}^{2} follows by Theorem 2.1 (with γ = 1/2), using the calculations in [9] for X_{n} together with simple estimates for Y_{n}. Finally, when N_{n}/m_{n} → 1 (and N_{n}(n/N_{n})^{max(k,2)} → ∞), we can apply Theorem 2.1 (with γ = 2), but this time we take Y_{n} = 1[X_{n} = k] for k ≥ 3 only; for k = 1 and k = 2 we use the modifications 1[X_{n} = 1] + X_{n} − 2 and 1[X_{n} = 2] − X_{n} + 1, respectively, cf. Remark 2.2. We omit the details.

We thus obtain moment convergence too, and Theorem 2.2 yields joint asymptotic normality of W_{n1}, W_{n2}, …, W_{nl}, for any l.

Other additive characteristics of the random forest can be studied similarly. For example, we obtain immediately (by Corollary 2.1) asymptotic normality of the total path length when N/m → a ∈ (0, 1). This can be extended (by Theorem 2.1) to other ranges of N, m → ∞, but we have not worked out the precise conditions.

Example 3.4 (Branching processes). Consider a Galton–Watson process, for simplicity beginning with one individual, where the number of children of an individual is given by a random variable X having finite moments. Assume further that 𝔼 X = 1, i.e. that the process is critical, and that the span of X is 1.

Number the individuals as they appear, and let X_{i} be the number of children of the i:th individual; we can continue with fictitious individuals after extinction, so that X_{i} is defined for all i ≥ 1, forming an i.i.d. sequence.

The total progeny is n ≥ 1 if and only if

S_{k} := ∑_{1}^{k} X_{i} ≥ k for 0 ≤ k < n but S_{n} = n − 1.  (3.2)

This is a different type of conditioning than the one studied in this paper, but we observe that if x_{1}, …, x_{n} are any non-negative integers such that ∑_{1}^{n}(x_{i} − 1) = −1, then there is exactly one cyclical shift x′_{i} := x_{i+l (mod n)} such that ∑_{1}^{k}(x′_{i} − 1) ≥ 0 for 1 ≤ k < n [24, 18] (l is the smallest number for which ∑_{1}^{l} x_{i} = −1). Consequently, if we ignore (or randomize) the order of X_{1}, …, X_{n}, they have the same distribution conditioned on (3.2) as conditioned on S_{n} = n−1, and we are back in the situation studied in this paper; we can thus use our results to study variables of the type ∑_{1}^{n} f(X_{i}) conditioned on having exactly n individuals in the process. (In this example we have a single sequence rather than a triangular array: X_{ni} = X_{i} and we drop the index n from X and Y.)

Note that we take N_{n} = n and m_{n} = n − 1, so 𝔼 S_{nN_{n}} = N_{n} differs from m_{n} (although only by 1), and we have to use Theorem 2.3 instead of Theorem 2.1. On the other hand, Remark 2.9 shows that the conclusions remains the same.

For example, taking Y := 1[X = k] for some k = 0, 1, …, we obtain by Corollary 2.1 and Remark 2.9 that given that the total progeny of the process (up to extinction) is n, the number of individuals with k children is asymptotically normal. More precisely, if this number is denoted by W_{nk} and p_{k} := ℙ(X = k), then n^{−1/2}(W_{nk} − np_{k}) →^{d} N(0, σ_{k}^{2}) as n → ∞, with moment convergence, where σ_{k}^{2} := p_{k}(1−p_{k})−(k −1)^{2}p_{k}^{2}/ Var X. Joint convergence for several k follows too, by Corollary 2.2 with b_{nj} := 1; the asymptotic covariances are σ_{jk} := −p_{j}p_{k} − (j − 1)(k − 1)p_{j}p_{k}/ Var X, j ≠ k.

Finally, we give three artificial counter-examples that illuminate the conditions in the theorems.

Example 3.5. Let α, β ≥ 0 be two fixed real numbers. Take X_{n} and Y_{n} independent, so that U_{n} = T_{nN_{n}} = ∑_{1}^{N_{n}} Y_{ni}. Further, let N_{n} = m_{n} = n, X_{n} ∈ Po(1) and let Y_{n} take the values −1, 1 and n^{α+1/2} with probabilities 1/2, 1/2 − p_{n} and p_{n} := n^{−1−β}, respectively.

All conditions in Theorem 2.1 except (vii) and (x) are readily verified.

If α = β = 0, then τ_{n}^{2} = σ_{Y_{n}}^{2} → 2, and 𝔼 |Y_{n} − 𝔼 Y_{n}|^{3} ∼ 𝔼 |Y_{n}|^{3} ∼ n^{1/2}. Since the number of terms in ∑_{1}^{N_{n}} Y_{ni} that equal n^{1/2} is Bi(n, 1/n), it is easily seen that U_{n}/\sqrt{N}_{n} →^{d} W + Z where W ∈ Po(1) and Z ∈ N(0, 1) are independent. This shows that the factor N_{n}^{1/2} in (vii) is sharp, and moreover that o cannot be relaxed to O.

Assume now that β > 0. It is then easily seen that U_{n}/\sqrt{N}_{n} →^{d} N(0, 1). If further β > 2α, then N_{n} 𝔼 Y_{n} = o(N_{n}^{1/2}) and τ_{n}^{2} → 1 so (2.1) holds. In this case, Var U_{n} ∼ N_{n}, so (2.2) holds too. However, with probability ≈ n^{−β}, U_{n}/\sqrt{N}_{n} has a value ≈ n^{α}, and it is easily verified that convergence of the r:th moments in (2.1) or (2.2) holds if and only if β > rα. Moreover, (vii) holds if and only if β > 3α. Similarly, (x) holds if and only if β ≥ rα, and the O can be strengthened to o if and only if β > rα.

This shows that the results in Remark 2.7 are sharp.

Example 3.6. Let a_{n} ≥ 2 be an integer and let (for n > 4) ℙ(X_{n} = 0) = 1/2, ℙ(X_{n} = ±1) = 1/4−1/n, ℙ(X_{n} = ±a_{n}) = 1/n. Further, let Z_{n} be independent of X_{n} with ℙ(Z_{n} = ±1) = 1/2 and define Y_{n} := X_{n}1[|X_{n}| ≤ 1] + Z_{n}. We take N_{n} = n and m_{n} = 0.

It is easily verified that Theorem 2.1 applies when a_{n} = o(\sqrt{n}).

Now take a_{n} := ⌊\sqrt{n}⌋. Then all conditions in Theorem 2.1 except (iii) still hold, but 𝔼 |X_{n} − 𝔼 X_{n}|^{3} = 𝔼 |X_{n}|^{3} ∼ 2n^{1/2} = Θ(n^{1/2}σ_{X_{n}}^{3}). Note that, if S_{nN_{n}} = m_{n}, then

T_{nN_{n}} = ∑_{1}^{N_{n}} Z_{ni} − ∑_{1}^{N_{n}} X_{ni}1[|X| = a_{n}] = ∑_{1}^{N_{n}} Z_{ni} − a_{n}(L_{n+} − L_{n−}), (3.3)

where L_{n+} and L_{n−} are the numbers of terms X_{ni} equal to a_{n} and −a_{n}, respectively. Without conditioning, these numbers converge in distribution to independent Poisson variables, and it is easily seen that even when conditioning on S_{nN_{n}} = 0, L_{n+} − L_{n−} converges in distribution to some non-degenerate random variable L̃, supported on the integers. Since {Z_{ni}} is independent of \{X_{ni}\}, it follows from (3.3) that U_{n}/\sqrt{N}_{n} →^{d} W − L̃, where W ∈ N(0, 1) is independent of L̃. Consequently, the limit is not normal, which shows that assumption (iii) cannot be weakened to O.

Example 3.7. Let ℙ(X_{n} = 0) = ℙ(X_{n} = 2) = \frac{1}{2} − p_{n} and ℙ(X_{n} = 1) = 2p_{n}, where p_{n} := e^{−n}, say. Let further W and Z be random variables independent of \{X_{n}\} with ℙ(Z = 1) = ℙ(Z = −1) = \frac{1}{2} while W has any distribution with finite moments, and define Y_{n} := Z if X_{n} = 0 or X_{n} = 2, and Y_{n} := \sqrt{2n + 1}W if X_{n} = 1. Finally, let N = m_{n} = 2n + 1.

Clearly, (X_{n}, Y_{n}) →^{d} (X, Y) as n → ∞, with convergence of all moments, where \frac{1}{2}X ∈ Be(\frac{1}{2}), Y = Z, and X and Y are independent, and the conditions of Theorem 2.1 except (v) are satisfied. Indeed, this is an instance of Corollary 2.1 except that the span of the distribution of X is 2. We will see that, nevertheless, the conclusions of Theorem 2.1 do not hold; thus showing that the conditions (v) and ‘span=1’, respectively, cannot be eliminated. Note that N_{n} 𝔼 Y_{n} → 0, ρ_{n} → 0 and τ_{n}^{2} → 1.

Let L_{n} be the number of X_{n1}, …, X_{nN_{n}} that equal 1. Then S_{nN_{n}} ≡ L_{n} (mod 2), so if S_{nN_{n}} = m_{n} then L_{n} is odd. Moreover, since p_{n} → 0 rapidly, ℙ(L_{n} ≥ 3 | S_{nN_{n}} = m_{n}) ≪ ℙ(L_{n} = 1 | S_{nN_{n}} = m_{n}) and thus ℙ(L_{n} = 1 | S_{nN_{n}} = m_{n}) → 1.

If L_{n} = 1 and j is the index with X_{nj} = 1, then Y_{ni} = Z_{i} for i ≠ j and thus T_{nN_{n}} = \sqrt{N}_{n}W_{j} + ∑_{i≠j} Z_{i} (with the obvious meanings of W_{j} and Z_{i}). Since {W_{i}} and {Z_{i}} are independent of {X_{ni}}, it follows that the conditional distribution of T_{nN_{n}} given S_{nN_{n}} = m_{n}, L_{n} = 1 and X_{j} = 1 equals the distribution of \sqrt{N}_{n}W_{j} + ∑_{i≠j} Z_{i}. Furthermore, by symmetry, the latter distribution does not depend on j. Hence, letting d_{TV} denote the total variation distance of the distributions,

d_{TV}(U_{n}, \sqrt{N}_{n}W_{1} + ∑_{i=2}^{N_{n}} Z_{i}) ≤ ℙ(L_{n} ≥ 3 | S_{nN_{n}} = m_{n}) → 0,

and it follows, applying the central limit theorem to {Z_{i}}_{2}^{N_{n}}, that

U_{n}/\sqrt{N}_{n} →^{d} W + V,  (3.4)

where V ∈ N(0, 1) is independent of W. Moreover, simple estimates show that all moments converge in (3.4).

For example, taking W := 1 we find U_{n}/\sqrt{N}_{n} →^{d} N(1, 1) and 𝔼 U_{n} = \sqrt{N}_{n}+ o(N_{n}^{1/2}) ≠ N_{n} 𝔼 Y_{n} + o(N_{n}^{1/2}τ_{n}); hence (2.1) does not hold.

For another simple example, take W := Z. Then 𝔼 Y_{n} = 𝔼 X_{n}Y_{n} = 0, so X_{n} and Y_{n} are uncorrelated. We have 𝔼 U_{n} = 0 but Var U_{n} ∼ N_{n} Var(W + V) = 2N_{n}, and neither (2.1) nor (2.2) holds.

4. Proofs

Lemma 4.1. If X is an integer valued random variable, then

Var X ≤ 4 𝔼 |X − 𝔼 X|^{3}.

Proof. Let k := ⌊𝔼 X + 1/2⌋ be the integer closest to 𝔼 X. Then

𝔼(|X − 𝔼 X|1[X = k]) = | 𝔼((X − 𝔼 X)1[X = k])|

= | 𝔼((X − 𝔼 X)1[X ≠ k])| ≤ 𝔼(|X − 𝔼 X|1[X ≠ k]).

Moreover, |X − 𝔼 X| ≤ 1/2 if X = k and |X − 𝔼 X| ≥ 1/2 if X ≠ k, and thus

𝔼(|X − 𝔼 X|^{2}1[X = k]) ≤ \frac{1}{2} 𝔼(|X − 𝔼 X|1[X = k])

≤ \frac{1}{2} 𝔼(|X − 𝔼 X|1[X ≠ k]) ≤ 𝔼(|X − 𝔼 X|^{2}1[X ≠ k]).

Consequently,

𝔼 |X − 𝔼 X|^{2} ≤ 2 𝔼(|X − 𝔼 X|^{2}1[X ≠ k]) ≤ 4 𝔼 |X − 𝔼 X|^{3}.  □

Proof of Theorem 2.1. We first replace Y_{n} by the projection

Y′_{n} := Y_{n} − 𝔼 Y_{n} − \frac{Cov(X_{n}, Y_{n})}{σ_{X_{n}}^{2}}(X_{n} − 𝔼 X_{n}).  (4.1)

Then 𝔼 Y′_{n} = 0 and Cov(X_{n}, Y′_{n}) = 𝔼 X_{n}Y′_{n} = 0, and, using (viii′),

σ_{Y′_{n}}^{2} := Var Y′_{n} = Var Y_{n} − Cov(X_{n}, Y_{n})^{2}/σ_{X_{n}}^{2} = τ_{n}^{2} = Θ(σ_{Y_{n}}^{2}).  (4.2)

It follows by this (or Remark 2.3) that τ_{n}^{2} remains the same. Moreover, by Minkowski’s inequality, (iii′), (vii′) and (4.2)

∥Y′_{n}∥_{3} ≤ ∥Y_{n} − 𝔼 Y_{n}∥_{3} + \frac{|ρ_{n}|σ_{X_{n}}σ_{Y_{n}}}{σ_{X_{n}}^{2}} ∥X_{n} − 𝔼 X_{n}∥_{3} = o(N_{n}^{1/6}σ_{Y_{n}}) = o(N_{n}^{1/6}σ_{Y′_{n}})

so (vii′), and thus (vii), holds for Y′_{n} too. Similarly, for part (b), if (ix′) and (x′) hold, then (x′) and (x) hold for Y′_{n} too. Consequently, all conditions hold for (X_{n}, Y′_{n}) too.

Finally,

T′_{nN_{n}} := ∑_{1}^{N_{n}} Y′_{ni} = T_{nN_{n}} − N_{n} 𝔼 Y_{n} − Cov(X_{n}, Y_{n})σ_{X_{n}}^{−2}(S_{nN_{n}} − N_{n} 𝔼 X_{n}), (4.3)

so conditioned on S_{nN_{n}} = m_{n} = N_{n} 𝔼 X_{n} we have T′_{nN_{n}} = T_{nN_{n}} − N_{n} 𝔼 Y_{n}. Hence, the conclusions for (X_{n}, Y_{n}) and (X_{n}, Y′_{n}) are equivalent.

Consequently it suffices to prove the theorem for (X_{n}, Y′_{n}); in other words, we may henceforth assume that 𝔼 Y_{n} = 𝔼 X_{n}Y_{n} = 0. Note that then τ_{n}^{2} = σ_{Y_{n}}^{2}.

We introduce some convenient notation. Let

φ_{n}(s, t) := 𝔼 e^{is(X_{n}−𝔼X_{n})+itY_{n}} = e^{−ism_{n}/N_{n}} 𝔼 e^{isX_{n}+itY_{n}},

i.e., e^{−ism_{n}/N_{n}} times the bivariate characteristic function of (X_{n}, Y_{n}). Thus

φ_{n}^{N_{n}}(s, t) = 𝔼 e^{is(S_{nNn}−m_{n})+itT_{nNn}}.

Let further

\begin{aligned}ψ_{n}(t) & := ∫_{−π}^{π} φ_{n}^{N_{n}}(s, t) ds = 𝔼 ∫_{−π}^{π} e^{is(S_{nNn}−m_{n})+itT_{nNn}}ds \\ & = 𝔼(2π1[S_{nN_{n}} = m_{n}]e^{itT_{nNn}}) = 2π ℙ(S_{nN_{n}} = m_{n}) 𝔼(e^{itT_{nNn}} | S_{nN_{n}} = m_{n}) \\ & = 2π ℙ(S_{nN_{n}} = m_{n}) 𝔼 e^{itU_{n}}, \end{aligned} ; (4.4)

where we used the fact that ∫_{−π}^{π} e^{isk}ds = 0 for every non-zero integer k. (This standard Fourier inversion argument is the main reason for the assumption that X_{n} is discrete.) Consequently,

𝔼 e^{itU_{n}} = 𝔼(e^{itT_{nNn}} | S_{nN_{n}} = m_{n}) = ψ_{n}(t)/ψ_{n}(0).  (4.5)

Introduce the scaling constants β_{nX} = N_{n}^{−1/2}σ_{X_{n}}^{−1} and β_{nY} = N_{n}^{−1/2}σ_{Y_{n}}^{−1}, and define

Ψ_{n}(t) := ∫_{−π/β_{nX}}^{π/β_{nX}} φ_{n}^{N_{n}}(β_{nX}s, β_{nY} t) ds = β_{nX}^{−1}ψ_{n}(β_{nY} t).  (4.6)

We claim that, for every fixed real t,

\begin{aligned}Ψ_{n}(t) & = ∫_{−∞}^{∞} 1[|s| ≤ π/β_{nX}]φ_{n}^{N_{n}}(β_{nX}s, β_{nY} t) ds \\ & → ∫_{−∞}^{∞} e^{−s^{2}/2−t^{2}/2} ds = \sqrt{2π}e^{−t^{2}/2}. \end{aligned}  (4.7)

This then yields, by (4.5) and (4.6), 𝔼 e^{itβ_{nY} U_{n}} = Ψ_{n}(t)/Ψ_{n}(0) → e^{−t^{2}/2} for each t, and thus by the continuity theorem β_{nY} U_{n} →^{d} N(0, 1), which is (2.1). (Remember that we now assume 𝔼 Y_{n} = 0 and τ_{n}^{2} = σ_{Y_{n}}^{2}.)

We prove (4.7) by dominated convergence. First, Lemma 4.1 and (iii) yield σ_{X_{n}}^{2} = o(N_{n}^{1/2}σ_{X_{n}}^{3}), so β_{nX}^{−1} = N_{n}^{1/2}σ_{X_{n}} → ∞ and 1[|s| ≤ π/β_{nX}] → 1 for every fixed s.

Next, let s and t be fixed and set Z_{n} := β_{nX}s(X_{n} − 𝔼 X_{n}) + β_{nY} tY_{n}. As is well-known, the Taylor estimate |e^{iZ_{n}} − 1 − iZ_{n} + \frac{1}{2}Z_{n}^{2}| ≤ |Z_{n}|^{3} yields by integration

φ_{n}(β_{nX}s, β_{nY} t) = 𝔼 e^{iZ_{n}} = 1 + i 𝔼 Z_{n} − \frac{1}{2} 𝔼 Z_{n}^{2} + O(𝔼 |Z_{n}|^{3}).  (4.8)

Now, using our assumption 𝔼 Y_{n} = 𝔼 X_{n}Y_{n} = 0, 𝔼 Z_{n} = 0 and

𝔼 Z_{n}^{2} = β_{nX}^{2}s^{2}σ_{X_{n}}^{2} + β_{nY}^{2} t^{2}σ_{Y_{n}}^{2} = \frac{s^{2} + t^{2}}{N_{n}} ,

while, by Minkowski’s inequality with (iii′) and (vii′) again,

∥Z_{n}∥_{3} ≤ N_{n}^{−1/2}σ_{X_{n}}^{−1}|s|∥X_{n} − 𝔼 X_{n}∥_{3} + N_{n}^{−1/2}σ_{Y_{n}}^{−1}|t|∥Y_{n}∥_{3} = o(N_{n}^{−1/3}).

Thus 𝔼 |Z_{n}|^{3} = ∥Z_{n}∥_{3}^{3} = o(N_{n}^{−1}).

Consequently, (4.8) yields

φ_{n}(β_{nX}s, β_{nY} t) = 1 − \frac{s^{2} + t^{2}}{2N_{n}} + o(\frac{1}{N_{n}} )  (4.9)

and thus, since (iii) and Hölder’s (or Lyapunov’s) inequality imply N_{n} → ∞,

1[|s| ≤ π/β_{nX}]φ_{n}^{N_{n}}(β_{nX}s, β_{nY} t) → e^{−(s^{2}+t^{2})/2}.  (4.10)

This shows pointwise convergence of the integrand in (4.7); it remains to show that the left hand side of (4.10) is dominated by an integrable function g(s), which may depend on t (which is fixed during the argument) but not on n.

First consider t = 0, when we have |φ_{n}(s, 0)| = |φ_{X_{n}}(s)|. We write δ_{n}(s) := 1 − |φ_{X_{n}}(s)|; thus assumption (v) yields

δ_{n}(β_{nX}s) ≥ c min(|β_{nX}s|^{γ}, s^{2}β_{nX}^{2}σ_{X_{n}}^{2}), |β_{nX}s| ≤ π.

Now, by (iv), β_{nX}^{−2} = N_{n}σ_{X_{n}}^{2} = O(N_{n}^{2/γ}), so β_{nX} ≥ c_{1}N_{n}^{−1/γ} and |β_{nX}s|^{γ} ≥ c_{2}N_{n}^{−1}|s|^{γ}, with c_{1}, c_{2} > 0. Moreover,

s^{2}β_{nX}^{2}σ_{X_{n}}^{2} + N_{n}^{−1} = \frac{1}{N_{n}} (s^{2} + 1) ≥ \frac{1}{N_{n}} |s|^{γ}.

Consequently, assuming as we may c_{2} ≤ 1,

min(|β_{nX}s|^{γ}, s^{2}β_{nX}^{2}σ_{X_{n}}^{2}) ≥ c_{2} \frac{1}{N_{n}} |s|^{γ} − \frac{1}{N_{n}}

and thus, with c_{3} = c_{2} min(c, 1) > 0,

δ_{n}(β_{nX}s) = 1 − |φ_{X_{n}}(β_{nX}s)| ≥ c_{3} \frac{1}{N_{n}} |s|^{γ} − \frac{1}{N_{n}} ,  |β_{nX}s| ≤ π. (4.11)

Next, for a general t,

φ_{n}(s, t) = φ_{n}(s, 0) + it 𝔼(e^{is(X_{n}−𝔼X_{n})}Y_{n}) + 𝔼(e^{is(X_{n}−𝔼X_{n})}(e^{itY_{n}} − 1 − itY_{n}))

and thus

|φ_{n}(s, t)| ≤ |φ_{n}(s, 0)| + |t|| 𝔼(e^{isX_{n}}Y_{n})| + 𝔼|e^{itY_{n}} − 1 − itY_{n}|.  (4.12)

We estimate the terms separately. First, |φ_{n}(s, 0)| = |φ_{X_{n}}(s)| = 1 − δ_{n}(s). Secondly, let θ = arg φ_{X_{n}}(s). Then, since 𝔼 Y_{n} = 0, by the Cauchy–Schwarz inequality,

\begin{aligned}| 𝔼(e^{isX_{n}}Y_{n})|^{2} & = | 𝔼((e^{isX_{n}} − e^{iθ})Y_{n})|^{2} \\ & ≤ 𝔼 Y_{n}^{2} 𝔼|e^{isX_{n}} − e^{iθ}|^{2} = σ_{Y_{n}}^{2}(2 − 2 Re 𝔼 e^{isX_{n}−iθ}) \\ & = σ_{Y_{n}}^{2}(2 − 2|φ_{X_{n}}(s)|) = 2σ_{Y_{n}}^{2}δ_{n}(s) \end{aligned}  (4.13)

and thus, by the arithmetic-geometric inequality,

|t|| 𝔼(e^{isX_{n}}Y_{n})| ≤ \sqrt{2}|t|σ_{Y_{n}}δ_{n}(s)^{1/2} ≤ t^{2}σ_{Y_{n}}^{2} + \frac{1}{2}δ_{n}(s).

Thirdly, |e^{itY_{n}} − 1 − itY_{n}| ≤ \frac{1}{2}t^{2}Y_{n}^{2}.

Consequently, (4.12) yields

|φ_{n}(s, t)| ≤ 1 − δ_{n}(s) + \frac{1}{2}δ_{n}(s) + 2t^{2}σ_{Y_{n}}^{2} = 1 − \frac{1}{2}δ_{n}(s) + 2t^{2}σ_{Y_{n}}^{2}.

Using (4.11) we obtain, with c_{4} = c_{3}/2 > 0,

\begin{aligned}|φ_{n}(β_{nX}s, β_{nY} t)| & ≤ 1 − \frac{1}{2}δ_{n}(β_{nX}s) + 2t^{2}β_{nY}^{2} σ_{Y_{n}}^{2} ≤ 1 + \frac{1}{N_{n}} (−c_{4}|s|^{γ} + 1 + 2t^{2}) \\ & ≤ exp(\frac{1}{N_{n}} (−c_{4}|s|^{γ} + 1 + 2t^{2})), |β_{nX}s| ≤ π, \end{aligned}

and thus

|φ_{n}^{N_{n}}(β_{nX}s, β_{nY} t)| ≤ exp(1 + 2t^{2} − c_{4}|s|^{γ}), |s| ≤ π/β_{nX}.

This yields the desired domination and completes the proof of (4.7), and thus of (2.1).

Turning to mean and variance, we obtain by differentiating (4.5) and (4.4) twice at t = 0 (differentiation under the integral sign is easily justified using 𝔼 T_{nN_{n}}^{2} < ∞, which follows from (vi))

\begin{matrix}− 𝔼 U_{n}^{2} = ψ′′_{n}(0)/ψ_{n}(0) \\ = ψ_{n}(0)^{−1} ∫_{−π}^{π} [N_{n}∂_{t}^{2}φ_{n}(s, 0)φ_{n}^{N_{n}−1}(s, 0) + N_{n}(N_{n} − 1)(∂_{t}φ_{n}(s, 0))^{2}φ_{n}^{N_{n}−2}(s, 0)] ds \end{matrix}

and thus, by a change of variables and (4.6),

\frac{1}{N_{n}σ_{Y_{n}}^{2}} 𝔼 U_{n}^{2} = Ψ_{n}(0)^{−1} ∫_{−π/β_{nX}}^{π/β_{nX}} σ_{Y_{n}}^{−2}[−∂_{t}^{2}φ_{n}(β_{nX}s, 0)φ_{n}^{N_{n}−1}(β_{nX}s, 0)

− (N_{n} − 1)(∂_{t}φ_{n}(β_{nX}s, 0))^{2}φ_{n}^{N_{n}−2}(β_{nX}s, 0)] ds. (4.14)

Again we apply dominated convergence. First,

−∂_{t}^{2}φ_{n}(β_{nX}s, 0) = 𝔼(e^{iβ_{nX}s(X_{n}−𝔼X_{n})}Y_{n}^{2})

and thus, using Hölder’s inequality and (iii), (vii), for fixed s,

|∂_{t}^{2}φ_{n}(β_{nX}s, 0) + σ_{Y_{n}}^{2}| = |𝔼((1 − e^{iβ_{nX}s(X_{n}−𝔼X_{n})})Y_{n}^{2})|
≤ β_{nX}|s| 𝔼(|X_{n} − 𝔼 X_{n}|Y_{n}^{2}) ≤ β_{nX}|s|∥X_{n} − 𝔼 X_{n}∥_{3}∥Y_{n}∥_{3}^{2}
= o(β_{nX}N_{n}^{1/6}σ_{X_{n}}N_{n}^{2/6}σ_{Y_{n}}^{2}) = o(σ_{Y_{n}}^{2}).

Similarly,

\begin{aligned}∂_{t}φ_{n}(β_{nX}s, 0) & = i 𝔼(e^{iβ_{nX}s(X_{n}−𝔼X_{n})}Y_{n}) \\ & = i 𝔼((e^{iβ_{nX}s(X_{n}−𝔼X_{n})} − 1 − iβ_{nX}s(X_{n} − 𝔼 X_{n}))Y_{n}) \end{aligned}

and thus,

\begin{aligned}|∂_{t}φ_{n}(β_{nX}s, 0)| & ≤ 𝔼 |β_{nX}^{2}s^{2}(X_{n} − 𝔼 X_{n})^{2}Y_{n}| ≤ β_{nX}^{2}s^{2}∥X_{n} − 𝔼 X_{n}∥_{3}^{2}∥Y_{n}∥_{3} \\ & = o(β_{nX}^{2}N_{n}^{2/6}σ_{X_{n}}^{2}N_{n}^{1/6}σ_{Y_{n}}) = o(N_{n}^{−1/2}σ_{Y_{n}}). \end{aligned}

Together with (4.9), this shows that the integrand in (4.14) tends to e^{−s^{2}/2} for every s.

To obtain a suitable domination, we observe that

|∂_{t}^{2}φ_{n}(s, 0)| ≤ 𝔼 Y_{n}^{2} = σ_{Y_{n}}^{2}

and, by (4.13),

|∂_{t}φ_{n}(s, 0)|^{2} = | 𝔼 e^{isX_{n}}Y_{n}|^{2} ≤ 2σ_{Y_{n}}^{2}δ_{n}(s).

Consequently, using (4.11) in the final step,

|σ_{Y_{n}}^{−2} [−∂_{t}^{2}φ_{n}(β_{nX}s, 0)φ_{n}^{N_{n}−1}(β_{nX}s, 0) − (N_{n} − 1)(∂_{t}φ_{n}(β_{nX}s, 0))^{2}φ_{n}^{N_{n}−2}(β_{nX}s, 0)]|

≤ (1 − δ_{n}(β_{nX}s))^{N_{n}−1} + 2N_{n}δ_{n}(β_{nX}s)(1 − δ_{n}(β_{nX}s))^{N_{n}−2}

≤ e^{−(N_{n}−1)δ_{n}(β_{nX}s)} + 2N_{n}δ_{n}(β_{nX}s)e^{−(N_{n}−2)δ_{n}(β_{nX}s)}

≤ C_{1}e^{−N_{n}δ_{n}(β_{nX}s)/2} ≤ C_{2}e^{−c_{4}|s|^{γ}},

for some C_{1}, C_{2}. It now follows from (4.14), and Ψ_{n}(0) → \sqrt{2π} by (4.7), that

\frac{1}{N_{n}σ_{Y_{n}}^{2}} 𝔼 U_{n}^{2} → \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−s^{2}/2} ds = 1.

In other words, 𝔼(U_{n}/N_{n}^{1/2}σ_{Y_{n}})^{2} → 1. In particular, the random variables U_{n}/N_{n}^{1/2}σ_{Y_{n}} are uniformly integrable, and it follows from the already shown

U_{n}/N_{n}^{1/2}σ_{Y_{n}} →^{d} N(0, 1) that 𝔼(U_{n}/N_{n}^{1/2}σ_{Y_{n}}) → 0. Thus also Var(U_{n}/N_{n}^{1/2}σ_{Y_{n}})

→ 1.

This proves the estimates of mean and variance in the theorem, and shows further that (U_{n} − 𝔼 U_{n})/N_{n}^{1/2}σ_{Y_{n}} and (U_{n} − 𝔼 U_{n})/(Var U_{n})^{1/2} too converge in distribution to N(0, 1), which completes the proof of (a).

For part (b) we have that, still assuming 𝔼 Y_{n} = 𝔼 X_{n}Y_{n} = 0,

𝔼 |Y_{n}|^{r} = O(N_{n}^{r/2−1}σ_{Y_{n}}^{r})  (4.15)

holds by assumption for even r ≥ 4, and trivially for r = 2, while if r = 2s+1 ≥ 3 is an odd integer, then Hölder’s inequality yields 𝔼 |Y_{n}|^{r} ≤ (𝔼 Y_{n}^{2s} 𝔼 Y_{n}^{2s+2})^{1/2}, which by (4.15) for r = 2s and r = 2s+2 implies that (4.15) holds for r = 2s+1 too. Thus (4.15) holds for each integer r ≥ 2.

Now, let r be a positive integer. Differentiating (4.5) and (4.4) r times we find

i^{r} 𝔼 U_{n}^{r} = ψ_{n}^{(r)}(0)/ψ_{n}(0) = ψ_{n}(0)^{−1} ∫_{−π}^{π} ∂_{t}^{r}φ_{n}^{N_{n}}(s, 0) ds,

and thus, by a change of variable,

𝔼(U_{n}/N_{n}^{1/2}σ_{Y_{n}})^{r} = i^{−r}Ψ_{n}(0)^{−1} ∫_{−π/β_{nX}}^{π/β_{nX}} N_{n}^{−r/2}σ_{Y_{n}}^{−r}∂_{t}^{r}φ_{n}^{N_{n}}(β_{nX}s, 0) ds. (4.16)

As in the special case r = 2 in (4.14), we can, by differentiating φ_{n}^{N_{n}} r times and expanding, write the integrand as a sum of terms

φ_{n}(β_{nX}s, 0)^{N_{n}−j} ∏_{i=1}^{j}(N_{n} + 1 − i)N_{n}^{−r_{i}/2}σ_{Y_{n}}^{−r_{i}}∂_{t}^{r_{i}}φ_{n}(β_{nX}s, 0),  (4.17)

where 1 ≤ j ≤ r, r_{i} ≥ 1 and ∑_{i} r_{i} = r.

We write the product in (4.17) as ∏_{i}(1 − (i − 1)/N_{n})g_{r_{i}}(β_{nX}s), where

g_{r}(s) := N_{n}^{1−r/2}σ_{Y_{n}}^{−r}∂_{t}^{r}φ_{n}(s, 0) = N_{n}^{1−r/2}σ_{Y_{n}}^{−r}i^{r} 𝔼(e^{is(X_{n}−𝔼X_{n})}Y_{n}^{r}).

By (4.13),

|g_{1}(s)| ≤ \sqrt{2}N_{n}^{1/2}δ_{n}(s)^{1/2}

and for r ≥ 2, by (4.15),

|g_{r}(s)| ≤ N_{n}^{1−r/2}σ_{Y_{n}}^{−r} 𝔼 |Y_{n}|^{r} = O(1).

Consequently, the integrand in (4.16) is bounded by, using (4.11) again,

C_{r}(1−δ_{n}(β_{nX}s))^{N_{n}−r} ∑_{i=0}^{r} |g_{1}(β_{nX}s)|^{i} ≤ C′_{r}e^{−(N_{n}−r)δ_{n}(β_{nX}s)} ∑_{i=0}^{r}(N_{n}δ_{n}(β_{nX}s))^{i/2}

≤ C′′_{r}e^{−N_{n}δ_{n}(β_{nX}s)/2} ≤ C′′′_{r}e^{−c_{4}|s|^{γ}},

and thus the integral is bounded by a constant (depending on r). Since further Ψ_{n}(0) → \sqrt{2π} > 0, (4.16) now shows that 𝔼(U_{n}/N_{n}^{1/2}σ_{Y_{n}})^{r} is bounded for each r, i.e. all moments stay bounded in (2.1).

As is well-known, this implies uniform r:th power integrability of the left hand side in (2.1) for all r > 0, and thus convergence of all moments to the corresponding moments of the limiting normal distribution.

Finally, this easily implies moment convergence in (2.2) too. □

Proof of Corollary 2.1. The assumptions imply that 𝔼 X_{n}^{r} → 𝔼 X^{r} and 𝔼 Y_{n}^{r} → 𝔼 Y^{r} for every r ≥ 1, which immediately implies all conditions except (v) in Theorem 2.1. To verify (v), with γ = 2, we observe that

|φ_{X_{n}}(s)|^{2} = 𝔼 e^{is(X_{n1}−X_{n2})} = 1 − s^{2} Var X_{n} + O(s^{3} 𝔼 |X_{n}|^{3}).

Since Var X_{n} → Var X > 0 and 𝔼 |X_{n}|^{3} → 𝔼 |X|^{3} < ∞, it follows that for some δ > 0 that does not depend on n and |s| ≤ δ, we have |φ_{X_{n}}(s)| ≤ 1− \frac{1}{4}s^{2} Var X. On the other hand, φ_{X_{n}}(s) converges uniformly to φ_{X}(s), and max{|φ_{X}| : δ ≤ |s| ≤ π} < 1 because X has span 1; hence |φ_{X_{n}}(s)| ≤ 1 − ε ≤ 1 − ε(s/π)^{2} for δ ≤ |s| ≤ π, some ε > 0, and large enough n. This implies (v) (for large enough n), and the result follows by Theorem 2.1. □

Proof of Theorem 2.2. First, replacing Y_{n}^{(j)} by Y_{n}^{(j)}/b_{nj}, we may assume that b_{nj} = 1. Secondly, by the Cramér–Wold device, i.e. considering Y_{n} = t_{1}Y_{n}^{(1)} + ⋯+t_{l}Y_{n}^{(l)} where t_{1}, …, t_{l} are fixed real numbers, it is easily seen that it suffices to consider the case l = 1, i.e. when Y_{n} = Y_{n}^{(1)} is real-valued. In this case, with τ_{n}^{2} as in Theorem 2.1, (2.4) may be written

τ_{n}^{2} → σ_{11}.  (4.18)

Assume first that σ_{11} = lim τ_{n}^{2} > 0. Since τ_{n}^{2} ≤ σ_{Y_{n}}^{2} and, by (vi), σ_{Y_{n}}^{2} = O(1), we see that (vi), (vii) and (viii′) in Theorem 2.1 hold (and in part (b) (x) too). The result now follows by Theorem 2.1 and (4.18).

It remains to prove that if τ_{n}^{2} → 0, then N_{n}^{−1/2}(U_{n} − N_{n} 𝔼 Y_{n}) →^{d} 0 (with moment convergence). This can be proved by replacing Y_{n} by Y_{n} + Z, where Z ∈ N(0, 1) is independent of (X_{n}, Y_{n}), and then applying the case τ_{n}^{2} → 1; alternatively, one can modify the proof of Theorem 2.1 (redefining β_{nY} := N_{n}^{−1/2}). We omit the details. □

Proof of Theorem 2.3. In this case, (4.3) shows that, conditioned on S_{nN_{n}} = m_{n}, T′_{nN_{n}} = T_{nN_{n}} −N_{n} 𝔼 Y_{n}−ρ_{n} \frac{σ_{Yn}}{σ_{Xn}} (m_{n}−N_{n} 𝔼 X_{n}). This yields the extra term in (2.7); it further shows that the general case again follows from the special case 𝔼 Y_{n} = 𝔼 X_{n}Y_{n} = 0.

By considering subsequences, we may further assume that

v_{n} := (m_{n} − 𝔼 X_{n})/N_{n}^{1/2}σ_{X_{n}} → v

for some real v. The proof of (2.1) and moment convergence is now as before with minor modifications: We now take ψ_{n}(t) := ∫_{−π}^{π} e^{−i(m_{n}−N_{n} 𝔼X_{n})s}φ_{n}^{N_{n}}(s, t) ds in (4.4); (4.5) still holds but we get an extra factor e^{−iv_{n}s} in the integral in (4.6), and thus the limit in (4.7) becomes ∫_{−∞}^{∞} e^{−isv−s^{2}/2−t^{2}/2} ds = \sqrt{2π}e^{−v^{2}/2−t^{2}/2}, whence Ψ_{n}(t)/Ψ_{n}(0) → e^{−t^{2}/2} still holds. Similarly, we get a factor e^{−iv_{n}s} in the integrals in (4.14) and (4.16). The result follows using the previously established limits and bounds of the integrands. □

References

[1] P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. Preprint, 1999. Available at http://altair.iecn.u-nancy.fr/

∼chassain

[2] D. M. Chibisov, On the normal approximation for a certain class of statistics. Proc. Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics, pp. 153–174. Univ. California Press, Berkeley, Calif., 1972.

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

[4] C. Hipp, Asymptotic expansions for conditional distributions: the lattice case. Probab. Math. Statist. 4 (1984), no. 2, 207–219.

[5] L. Holst, Two conditional limit theorems with applications. Ann. Statist. 7 (1979), no. 3, 551–557.

[6] L. Holst, A unified approach to limit theorems for urn models. J. Appl. Probab. 16 (1979), 154–162.

[7] L. Holst, Some conditional limit theorems in exponential families. Ann. Probab. 9 (1981), no. 5, 818–830.

[8] Sh. A. Ismatullaev, Asymptotic expansions for conditional distributions. (Russian) Dokl. Akad. Nauk UzSSR 1987, no. 4, 12–15.

[9] S. Janson, Asymptotic distribution for the cost of linear probing hashing. Random

Struct. Appl., to appear. Available at http://www.math.uu.se/∼svante/papers/

[10] D. E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed., Addison-Wesley, Reading, Mass., 1998.

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

[12] V. F. Kolchin, B. A. Sevastyanov & V. P. Chistyakov, Random allocations. Nauka, Moscow, 1976 (Russian). English transl.: Winston, Washington, D.C., 1978

[13] E. M. Kudlaev, Teor. Veroyatnost. i Primenen. 29 (1984), no. 4, 743–752. English transl.: Theory Probab. Appl. 29 (1984), no. 4, 776–786.

[14] R. Michel, Asymptotic expansions for conditional distributions. J. Multivariate Anal. 9 (1979), no. 3, 393–400.

[15] Sh. A. Mirakhmedov, Limit theorems for conditional distributions. (Russian) Diskret. Mat. 6 (1994), no. 4, 107–132; English transl.: Discrete Math. Appl. 4 (1994), no. 6, 519–542.

[16] Yu. L. Pavlov, Limit theorems for the number of trees of a given size in a random forest. Mat. Sb. 103(145) (1977), no. 3, 392–403, 464 (Russian). English transl.: Math. USSR Sb. 32 (1977), no. 3, 335–345.

[17] Yu. L. Pavlov, Random forests. Karelian Centre Russian Acad. Sci., Petrozavodsk, 1996 (Russian). English transl.: VSP, Zeist, The Netherlands, 2000.

[18] J. Pitman, Enumerations of trees and forests related to branching processes and random walks. Microsurveys in discrete probability (Princeton, NJ, 1997), 163–180, Amer. Math. Soc., Providence, RI, 1998.

[19] S. Portnoy, Asymptotic efficiency of minimum variance unbiased estimators. Ann. Statist. 5 (1977), no. 3, 522–529.

[20] A. Rényi, Three new proofs and a generalization of a theorem of Irving Weiss. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 203–214.

[21] G. P. Steck, Limit theorems for conditional distributions. Univ. California Publ. Statist. 2 (1957), 237–284.

[22] A. R. Swensen, A note on convergence of distributions of conditional moments. Scand. J. Statist. 10 (1983), no. 1, 41–44.

[23] I. Weiss, Limiting distributions in some occupancy problems. Ann. Math. Statist. 29 (1958), 878–884.

[24] J. G. Wendel, Left-continuous random walk and the Lagrange expansion. Amer. Math. Monthly 82 (1975), 494–499.

[25] S. L. Zabell, Rates of convergence for conditional expectations. Ann. Probab. 8 (1980), no. 5, 928–941.

[26] S. L. Zabell, A limit theorem for expectations conditional on a sum. J. Theoret. Probab. 6 (1993), no. 2, 267–283.

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

E-mail address: svante.janson@math.uu.se