ASYMPTOTIC DISTRIBUTION FOR THE COST OF LINEAR PROBING HASHING

SVANTE JANSON

Abstract. We study moments and asymptotic distributions of the construction cost, measured as the total displacement, for hash tables using linear probing. Four different methods are employed for different ranges of the parameters; together they yield a complete description. This extends earlier results by Flajolet, Poblete and Viola. The average cost of unsuccessful searches is considered too.

1. Introduction

Hashing with linear probing is a well-known algorithm that can be described as follows; here n and m are integers with 0 ≤ n ≤ m. (For a thorough discussion, see Knuth [15, Section 6.4, in particular Algorithm 6.4.L].)

n items x_{1}, …, x_{n} are placed sequentially into a table with m cells 1, …, m, using n integers h_{i} ∈ {1, …, m}, by inserting x_{i} into cell h_{i} if it is empty, and otherwise trying cells h_{i}+1, h_{i}+2, until an empty cell is found; all positions being interpreted modulo m.

In real applications, h_{i} is computed as h(x_{i}) by some hash function h; in this paper, as in most theoretical analyses, it is assumed that the hash addresses h_{i} are random numbers, uniformly distributed on {1, …, m} and independent. In other words, each of the m^{n} possible hash sequences (h_{i})_{1}^{n} has the same probability m^{−n}.

If item x_{i} is inserted into cell q_{i}, then its displacement (q_{i}−h_{i}) mod m, which is the number of unsuccessful probes when this item is inserted, is a measure of the cost of inserting it; it is also a measure of the cost of later finding the item in the table. The total displacement D_{mn} := ∑_{i=1}^{n}(q_{i} − h_{i}) mod m is thus a measure of both the cost of constructing the table and of using it. (The average number of probes to find an element in the table is D_{mn}/n + 1.) Note that D_{mn} is an integer with 0 ≤ D_{mn} ≤ \binom{n}{2}.

With our assumption that the numbers h_{i} be random, D_{mn} is a random variable, and the main purpose of the present paper is to give the asymptotic distribution of D_{mn} as m, n → ∞. This has earlier been done by Flajolet, Poblete and Viola [9] for the two most important cases: full tables (n = m) (and almost full tables, n = m − 1), and sparse tables (n/m → a, with 0 < a < 1). They found that in the sparse case D_{mn} is asymptotically normal, with both variance and expectation growing like n (or m), while in the full case n^{−3/2}D_{mn} has a non-normal limiting distribution, which equals the distribution of the area under a standard Brownian excursion. (This distribution had earlier been studied by, among others, Louchard [19, 20] and Takács [27]. It is, up to a factor \sqrt{8}, called the Airy distribution in [9].) We extend their results to other ranges of n as follows.

Date: May 17, 2000; revised August 21, 2001.

1991 Mathematics Subject Classification. Primary: 68W40; Secondary: 60F05, 60J65.

Key words and phrases. Hashing, linear probing, parking problem, normal convergence, Poisson convergence, Brownian motion, Brownian excursion area, Airy distribution, Stein’s method.

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

Theorem 1.1. Suppose that m → ∞.

(i) If n/\sqrt{m} → a for some a with 0 ≤ a < ∞, then D_{mn} is asymptotically Poisson distributed: D_{mn} →^{d} Po(a^{2}/2).

(ii) If n ≫ \sqrt{m} and m − n ≫ \sqrt{m}, then D_{mn} is asymptotically normal:

(D_{mn} − 𝔼 D_{mn})/(Var D_{mn})^{1/2} →^{d} N(0, 1).

(iii) If (m − n)/\sqrt{m} → a for some a with 0 ≤ a < ∞, then n^{−3/2}D_{mn} →^{d}

W_{a}, for some non-degenerate random variable W_{a}. In all cases the result holds with convergence of all moments.

Remark 1.2. By saying that X_{k} →^{d} X with convergence of all moments, we mean that besides X_{k} →^{d} X, we also have 𝔼 X_{k}^{r} → 𝔼 X^{r} for each positive integer r. As is well-known, this holds if (and only if) X_{k} →^{d} X and sup_{k} 𝔼 X_{k}^{r} < ∞ for each r ≥ 1. Moreover, it entails the convergence of all absolute moments 𝔼 |X_{k}|^{r} (r positive real), of all central moments 𝔼(X_{k} − 𝔼 X_{k})^{r} (r positive integer) and 𝔼 |X_{k} − 𝔼 X_{k}|^{r} (r positive real), and of all semi-invariants κ_{r}(X_{k}) to the corresponding quantities for X.

Remark 1.3. As in all similar situations, the three cases in Theorem 1.1 do not exhaust all possibilities, since n might oscillate between, for example, m^{1/3} and m − m^{1/3}, but they effectively do so since every sequence (m_{k}, n_{k}) with m_{k} → ∞ has a subsequence belonging to one of the cases.

Theorem 1.1 thus exhibits a “phase transition” at m − n ≍ \sqrt{m}, where we lose asymptotic normality. The reason is that less dense hash tables consist of many small blocks, each of which is negligible, but for m − n ≍ \sqrt{m}, the largest block is of order n and contributes significantly; see the proofs below and Remark 4.2.

The limit random variable W_{0} can by [9] be described as the area under a Brownian excursion. We give a related formula for W_{a} in terms of a Brownian bridge (or a Brownian excursion) in Section 2, and explicit (but complicated) formulae for its moments in Section 3. However, there does not seem to be any simple expression for the distribution of W_{a}, and we do not know any simple relation with other distributions.

It is a consequence of Theorem 1.1 that the distribution of W_{a} approaches a normal distribution as a → ∞. This is an instance of a simple general result on continuity of the limits in this type of situations, but since it apparently is not well-known, we give the details (together with some moment asymptotics) in Section 6.

The expectation of D_{mn} is \frac{n}{2}(Q_{0}(m, n−1)−1) [9, 16], cf. [14], [15, Theorem 6.4.K]. (See [15] or [16] for the definition of Q_{r}.) A similar exact formula for the variance is given by Flajolet, Poblete and Viola [9, Theorem 4], see also [15, Exercise 6.4-68], [16] and (3.16)–(3.17) below.

It follows readily from the exact formula above and the bounds (6.4-43) in [15] that 𝔼 D_{mn} ∼ n^{2}/2(m − n) as n → ∞, provided m − n ≫ \sqrt{m}; this was found for fixed m/n already by Knuth [14]. For the variance, Flajolet, Poblete and Viola [9, Theorem 5] found in the case n/m = α ∈ (0, 1) fixed the asymptotic formula (1.2) below (in a sharper form with a second-order term too). We can extend that to other ranges of m and n as follows. (Note that the cases (i) and (ii) overlap.)

Theorem 1.4. Suppose that n, m → ∞.

(i) If n/m → 0, then 𝔼 D_{mn} ∼ Var D_{mn} ∼ n^{2}/2m.

(ii) If n ≫ \sqrt{m} and m − n ≫ \sqrt{m}, then, with α := n/m,

𝔼 D_{mn} ∼ \frac{α}{2(1 − α)}n = \frac{n^{2}}{2(m − n)},  (1.1)
Var D_{mn} ∼ \frac{6α − 6α^{2} + 4α^{3} − α^{4}}{12(1 − α)^{4}} n = \frac{6n^{2}m^{3} − 6n^{3}m^{2} + 4n^{4}m − n^{5}}{12(m − n)^{4}} . (1.2)

In particular, if n/m → 1 and m − n ≫ \sqrt{m}, then

Var D_{mn} ∼ n^{5}/4(m − n)^{4}.

(iii) If (m − n)/\sqrt{m} → a for some a with 0 ≤ a < ∞, then 𝔼 D_{mn} ∼ n^{3/2} 𝔼 W_{a} and Var D_{mn} ∼ n^{3} Var W_{a}, where 𝔼 W_{a} and Var W_{a} are given by Corollary 3.4.

Remark 1.5. Alternatively, (1.2) can be shown by the method in [9]. It can be verified that the asymptotic expansion [9, (7)] for Q_{0} is valid also if α = n/m is not constant, provided the error term O(m^{−5}) is changed to O((1−α)^{−11}m^{−5}); (1.2) then follows by some algebra involving lots of cancellations. Our method has the advantage, however, of yielding the main term directly. On the other hand, the method in [9] yields any desired number of terms in an asymptotic expansion, while our method, in the present version, yields only the leading term.

A common variation of hashing problems is to consider confined hashing only, meaning that we consider only hash sequences that leave the last position empty (thus we assume n < m). (In particular, there is no wrapping around from m to 1; indeed, confined hashing can equivalently be described as hashing into m − 1 cells, conditioned on never wrapping around.) Confined hashing is also known as the parking problem [18], [15, Exercise 6.4-29].

As is well-known, symmetry and the fact that the hashing table always has m − n empty locations show that the number of confined hash sequences is

\frac{m − n}{m}m^{n} = (m − n)m^{n−1},  (1.3)

and that the distribution of the total displacement is the same for the confined case as for the unrestricted case. Hence Theorem 1.1 and the other results in this paper are valid for confined hashing too. Moreover, when proving any result we can choose between the confined and unrestricted versions. This is very advantageous; it turns out that some of our arguments work for one version and some for the other.

There are also variations of the hashing algorithm above, such as “last-come-first-served” and “Robin Hood” [15, Answer 6.4-67], where the displacements of individual items may differ from the version above but the total displacement is the same; the results in this paper are thus valid for these versions too.

We will prove the three parts of Theorem 1.1 (in reverse order) by four different methods in the next four sections, giving two different proofs of part (iii). There are two reasons for giving both proofs: First, we find both interesting; secondly, they give different information about the limit W_{a}, see Theorems 2.2 and 3.3. The proofs will as a byproduct yield Theorem 1.4(i)(ii) too (Theorem 1.4(iii) is an immediate consequence of Theorem 1.1).

As mentioned above, the average cost of searching for an element in the table (after it has been constructed) is given by D_{mn}/n+1, and is thus asymptotically described by the results above. On the other hand, let U_{mn} be the average cost of an unsuccessful search, i.e. the average number of probes used until giving up when searching for an element not in the table, beginning at a random cell h; we average over h so U_{mn} becomes a function of the table, and thus a random variable. (This average is relevant in applications where a hash table is constructed once, and then used for many searches. The distribution of individual search costs will not be considered in this paper.) Note that U_{mn} is the same as the average number of probes needed to extend the table by one item.

The expectation of U_{mn} is 𝔼 U_{mn} = \frac{1}{2}Q_{1}(m, n) + \frac{1}{2} [15, Theorem 6.4.K]. We give a corresponding exact formula for the variance in Theorem 7.3. (Higher moments could be obtained by the same method.)

For asymptotics, we have the following companion results to Theorems 1.1 and 1.4. The asymptotics for 𝔼 U_{mn} in Theorem 1.7(i)(ii) follow easily from the exact formula above, using [15, (6.4-43)] for (ii). The other results are proved in Section 7.

Theorem 1.6. Suppose that m → ∞.

(i) If n/\sqrt{m} → a for some a with 0 ≤ a < ∞, then mU_{mn} − m − n →^{d} Po(3a^{2}/2).

(ii) If n ≫ \sqrt{m} and m − n ≫ \sqrt{m}, then U_{mn} is asymptotically normal:

(U_{mn} − 𝔼 U_{mn})/(Var U_{mn})^{1/2} →^{d} N(0, 1).

(iii) If (m − n)/\sqrt{m} → a for some a with 0 ≤ a < ∞, then \frac{2}{m}U_{mn} →^{d} V_{a} for some random variable V_{a}, which is non-degenerate for 0 < a < ∞ while V_{0} = 1.

In all cases the result holds with convergence of all moments.

The normalizations in (i) and (iii) are partly explained by the fact, which is an easy consequence of (7.1) below, that mU_{mn} is an integer with m + n ≤ mU_{mn} ≤ \binom{m}{2}, and thus \frac{2}{m}U_{mn} ≤ 1 + \frac{1}{m}.

Theorem 1.7. Suppose that n, m → ∞, with n < m.

(i) If n/m → 0, then 𝔼 U_{mn} = 1 + \frac{n}{m} + \frac{3n(n−1)}{2m^{2}} + o(\frac{n^{2}}{m^{2}} ) and Var U_{mn} ∼ 3n^{2}/2m.

(ii) If n ≫ \sqrt{m} and m − n ≫ \sqrt{m}, then, with α := n/m,

𝔼 U_{mn} ∼ \frac{1}{2} + \frac{1}{2(1 − α)^{2}} = \frac{2m^{2} − 2mn + n^{2}}{2(m − n)^{2}} ,
Var U_{mn} ∼ \frac{3α^{2}}{2(1 − α)^{6}} m^{−1} = \frac{3n^{2}m^{3}}{2(m − n)^{6}} .

In particular, if n/m → 1 and m − n ≫ \sqrt{m}, then 𝔼 U_{mn} ∼ n^{2}/2(m − n)^{2} and Var U_{mn} ∼ 3n^{5}/2(m − n)^{6}.

(iii) If (m − n)/\sqrt{m} → a for some a with 0 ≤ a < ∞, then 𝔼 U_{mn} ∼ \frac{1}{2}n 𝔼 V_{a} and Var U_{mn} ∼ \frac{1}{4}n^{2} Var V_{a}, where 𝔼 V_{a} and Var V_{a} are given by Theorem 7.4.

Finally, in Section 8 we discuss the joint distribution of D_{mn} and U_{mn}.

Acknowledgements. I thank Donald Knuth for drawing my attention to the study of hashing with linear probing, and Philippe Flajolet for helpful comments.

2. The dense case: Brownian limits

In this section we give our first proof of the limit theorem for D_{mn} when (m− n)/\sqrt{m} → a < ∞. The convergence in distribution is an easy consequence of a limit theorem for the profile of hashing in terms of some stochastic processes related to Brownian motion [5, Theorem 4.1]; since that result is given in a technically more complicated context than used here, we sketch the argument in a slightly simpler version.

Let, for i = 1, …, m, X_{i} be the number of items x_{k} with hash address h_{k} = i, and let S_{i} := ∑_{j=1}^{i} X_{j}, 0 ≤ i ≤ m. Thus S_{0} = 0 and S_{m} = ∑_{1}^{m} X_{j} = n. Moreover, let H_{i} be the number of items that make an attempt to be inserted in cell i, whether they succeed or not. We call (H_{i})_{i=1}^{m} the profile of the hashing. Since the total displacement equals the number of unsuccessful probes and the total number of probes is ∑_{i} H_{i}, of which n are successful,

D_{mn} = ∑_{i=1}^{m} H_{i} − n.  (2.1)

It is convenient to extend the definition of X_{i}, S_{i} and H_{i} to all integers i, with X_{i+m} = X_{i}, H_{i+m} = H_{i}, S_{i+m} = S_{i} + n for all i. (Thus S_{i} = ∑_{j=1}^{i} X_{j} for all i ≥ 0 and S_{i} = − ∑_{i+1}^{0} X_{j} for i < 0; in any case S_{i} = X_{i} + S_{i−1}.) Then H_{i} can be computed as follows [5, Proposition 5.3], cf. [15, Exercise 6.4-32].

Lemma 2.1. With X_{i}, S_{i}, H_{i} defined for all integers i as above,

H_{i} = max_{j≤i}(∑_{k=j}^{i} X_{k} − (i − j)) = max_{j≤i}(S_{i} − S_{j−1} − i + j)

= S_{i} − i − min_{k<i}(S_{k} − k) + 1.

Proof. For i − m < j ≤ i, there are ∑_{k=j}^{i} X_{k} items that first try one of the cells {j, …, i}, and at most i−j of them can be accomodated in {j, …, i−1}, so at least ∑_{k=j}^{i} X_{k} − (i − j) try cell i; hence, H_{i} ≥ ∑_{k=j}^{i} X_{k} − (i − j). The periodicity shows that this holds for j ≤ i − m too.

Conversely, if j = j_{0} + 1, where j_{0} is the largest integer less than i where there are no unsuccessful probes, it is easily seen that H_{l} = ∑_{k=j}^{l} X_{k} − (l − j) for j ≤ l ≤ i; in particular H_{i} = ∑_{k=j}^{i} X_{k} − (i − j). □

Consider the random function S_{⌊mt⌋} − nt, 0 ≤ t ≤ 1; note that it vanishes for both t = 0 and t = 1. This function equals n(β_{mn}(t) − t), where β_{mn} is the empirical distribution function of {h_{k}/m}_{k=1}^{n}. Letting U_{1}, …, U_{n} be independent random variables with a uniform distribution on [0, 1], we can take h_{k} = ⌈mU_{k}⌉, and then β_{mn}(t) = β′_{n}(⌊mt⌋/m), where β′_{n} is the empirical distribution function of {U_{k}}_{k=1}^{n}. Now, it is well-known [4, Theorem 16.4] that \sqrt{n}(β′_{n}(t) − t) →^{d} b(t), where b(t) is a standard Brownian bridge, and the convergence is in the Skorohod topology on D[0, 1]. It follows that

\frac{1}{\sqrt{n}}(S_{⌊mt⌋} − nt) = \sqrt{n}(β_{mn}(t) − t))

= \sqrt{n}(β′_{n}(⌊mt⌋/m) − ⌊mt⌋/m + O(1/m))

→^{d} b(t).

Multiplying by \sqrt{n/m} → 1 and adding (nt − ⌊mt⌋)/\sqrt{m} → −at, we obtain

\frac{1}{\sqrt{m}}(S_{⌊mt⌋} − ⌊mt⌋) →^{d} b(t) − at.

Hence, using Lemma 2.1 and the mapping theorem [4, Theorem 5.1], extending b periodically to a function on (−∞, ∞), we have in D[0, 1]

\frac{1}{\sqrt{m}}H_{⌊mt⌋} →^{d} b(t) − at − min_{s≤t}(b(s) − as) = max_{s≤t}(b(t) − b(s) − a(t − s)). (2.2)

Consequently, by the mapping theorem again,

\frac{1}{m^{3/2}} ∑_{i=1}^{m} H_{i} = ∫_{0}^{1} \frac{1}{\sqrt{m}}H_{⌊mt⌋} dt →^{d} ∫_{0}^{1} max_{s≤t}(b(t) − b(s) − a(t − s)) dt. (2.3)

Together with (2.1) and n/m → 1, this proves that n^{−3/2}D_{mn} converges in distribution as asserted, with the following description of the limit distribution.

Theorem 2.2. The limit W_{a} in Theorem 1.1(iii) can be constructed by

W_{a} := ∫_{0}^{1} max_{s≤t}(b(t) − b(s) − a(t − s)) dt

for a Brownian bridge b on [0, 1], periodically extended to (−∞, ∞).

In order to show moment convergence, it suffices by Remark 1.2 to show that each moment 𝔼(D_{mn}/n^{3/2})^{r} is bounded, and since D_{mn} increases with n, it suffices to prove this for n = m. Moreover, by Lemma 2.1, max_{i} H_{i} ≤ 2 max_{i} |S_{i} − i| + 1, and thus by (2.1),

m^{−3/2}D_{mm} ≤ 2m^{−1/2} max_{i} |S_{i} − i| = 2m^{1/2} max_{i} |β_{mm}(i/m) − i/m|

= 2m^{1/2} max_{i} |β′_{m}(i/m) − i/m| ≤ 2m^{1/2} max_{t} |β′_{m}(t) − t|,

and all moments of the latter variable are bounded, for example by the (much stronger) Dvoretzky-Kiefer-Wolfowitz inequality [8], which completes the first proof of Theorem 1.1(iii). We omit the details, since we give another proof of moment convergence in the next section.

Remark 2.3. If a = 0, then W_{0} equals the integral of the stochastic process max_{s}(b(t) − b(s)) = b(t) − min_{s} b(s), which by a theorem by Vervaat [28] has the same distribution as a standard Brownian excursion e(t) up to a random shift. The shift does not affect the integral, and thus we can take W_{0} = ∫_{0}^{1} e(t), the Brownian excursion area, as found by [9]. More generally, it follows from Vervaat’s result that we can take

W_{a} := ∫_{0}^{1} max_{0≤s≤t}(e(t) − e(s) − a(t − s)) dt

too [5]. (This can also be derived by arguing as above with confined hashing instead of the unconfined version, but the details become technically more complicated, cf. [5, 6, 7].) Furthermore, it follows from [5, Theorem 2.2] that W_{a} also can be defined as the integral of a reflecting Brownian bridge |b| conditioned on having local time at 0 equal to a.

3. The dense case: moments

Our second proof of Theorem 1.1(iii) is based on expressions for generating functions given by Knuth [16] (see also [9]). We work with the confined version, and thus assume n < m; the results for n = m follow from the case n = m − 1, since the displacement of the last item is less than n and thus D_{m,m−1} ≤ D_{m,m} < D_{m,m−1} + m.

Following [16], we let F_{mn}(x) be the generating function for the total displacement in the confined version of the problem; thus

𝔼 x^{D_{mn}} = F_{mn}(x)/F_{mn}(1),  (3.1)

where, see (1.3),

F_{mn}(1) = (m − n)m^{n−1}.  (3.2)

Next, using the bivariate generating function

F (x, z) := ∑_{n=0}^{∞} F_{n+1,n}(x)z^{n}/n!,  (3.3)

Knuth [16, (1.5)] showed that

F_{mn}(x) = n![z^{n}]F (x, z)^{m−n}.  (3.4)

By (3.1) and (3.4) we have

𝔼 \binom{D_{mn}}{k} = [w^{k}] 𝔼(1 + w)^{D_{mn}} = [w^{k}z^{n}]F (1 + w, z)^{m−n}/[z^{n}]F (1, z)^{m−n}. (3.5)

Knuth [16, (4.2)] further showed that

F (1 + w, z) = ∑_{k=0}^{∞} w^{k}W′_{k}(z),  (3.6)

where W_{k} is the exponential generating function for the number of connected labelled graphs with k − 1 more edges than vertices, which by Wright [29] can be expressed in terms of the tree function

T (z) := ∑_{i=1}^{∞} \frac{i^{i−1}z^{i}}{i!} .  (3.7)

In the notation of [13] we have W_{k} = Ĉ_{k−1}, where by [13, (8.13)], for r ≥ 1,

Ĉ_{r}(z) = ∑_{d=0}^{3r+2} ĉ_{rd} \frac{T (z)^{3r+2−d}}{(1 − T (z))^{3r−d}} .

Expanding T^{3r+2−d} = (1 − (1 − T))^{3r+2−d} by the binomial theorem, this yields

Ĉ_{r}(z) = ∑_{j=−2}^{3r} c_{rj}^{∗}(1 − T (z))^{−j}

with the leading coefficient c_{r,3r}^{∗} = ĉ_{r0} = c_{r}, where c_{r} is as in [13, §8]. Consequently, using the fact that T′(z) = T (z)/z(1 − T (z)), for r ≥ 1,

Ĉ′_{r}(z) = ∑_{−2}^{3r} jc_{rj}^{∗}(1 − T (z))^{−j−1}T′(z) = \frac{T (z)}{z} ∑_{−2}^{3r} jc_{rj}^{∗}(1 − T (z))^{−j−2}. (3.8)

For r < 1 we instead have, by [13, §3], Ĉ_{−1}(z) = U(z) = T (z) − \frac{1}{2}T (z)^{2} and Ĉ_{0}(z) = V̂(z) = \frac{1}{2} ln(1 − T (z))^{−1} − \frac{1}{2}T (z) − \frac{1}{4}T (z)^{2}, which yield

Ĉ′_{−1}(z) = T′(z)(1 − T (z)) = \frac{T (z)}{z},
Ĉ′_{0}(z) = \frac{T′(z)}{2(1 − T (z))} − \frac{1}{2}T′(z) − \frac{1}{2}T (z)T′(z)
= \frac{T (z)}{z}(\frac{1}{2}(1 − T (z))^{−2} − (1 − T (z))^{−1} + \frac{1}{2}).  (3.9)

Hence, for all k ≥ 0,

W′_{k}(z) = Ĉ′_{k−1}(z) = \frac{T (z)}{z}f_{k}(T (z)),  (3.10)

where f_{k}(t) is a polynomial in (1 − t)^{−1}. Here f_{0}(t) = 1, while for k ≥ 1, f_{k} has degree 3(k − 1) + 2 = 3k − 1 in (1 − t)^{−1}; more precisely

f_{k}(t) = ω_{k}(1 − t)^{−(3k−1)} + …,  (3.11)

where the leading coefficient is given by ω_{1} = \frac{1}{2} and

ω_{k} = 3(k − 1)c_{k−1,3(k−1)}^{∗} = 3(k − 1)c_{k−1},  k ≥ 2.  (3.12)

(These are the same ω_{k} as in [9], as follows e.g. from (3.22) below.) For future use we note that ω_{2} = 3c_{1} = 5/8; this and further numerical values are given in [9, Table 1], see also the table of ĉ_{kd} in [13, §8]. We record also, see [16, (4.5)],

f_{1}(t) = \frac{t^{2}}{2(1 − t)^{2}} ,  f_{2}(t) = \frac{24t^{3} − 11t^{4} + 2t^{5}}{24(1 − t)^{5}} .  (3.13)

Let f(w, t) := ∑_{0}^{∞} w^{k}f_{k}(t). Then (3.6) and (3.10) yield that [16, (4.4)]

F (1 + w, z) = \frac{T (z)}{z}f(w, T (z)),  (3.14)

which using Lagrange inversion leads to, as shown by [16, (5.1)], cf. [9, (31)],

[z^{n}]F (1 + w, z)^{m−n} = [t^{n}]e^{mt}(1 − t)f(w, t)^{m−n}.  (3.15)

Consequently, for k ≥ 1, using f_{0} = 1,

\begin{aligned}[w^{k}z^{n}]F (1 + w, z)^{m−n} & = [w^{k}t^{n}]e^{mt}(1 − t)f(w, t)^{m−n} \\ & = [t^{n}]e^{mt}(1 − t) ∑_{j=1}^{k} \binom{m − n}{j} ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} f_{k_{i}}(t). \end{aligned}

Moreover, by (3.15), or by (3.4) and (3.2),

[z^{n}]F (1, z)^{m−n} = [t^{n}]e^{mt}(1 − t) = \frac{m^{n−1}}{n!} (m − n).

Hence, by (3.5),

𝔼 \binom{D_{mn}}{k} = \frac{m^{1−n}n!}{m − n} ∑_{j=1}^{k} \binom{m − n}{j} ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}}[t^{n}]e^{mt}(1 − t) ∏_{i=1}^{j} f_{k_{i}}(t), (3.16)

where, as shown above, f_{k_{i}} is a polynomial in (1 − t)^{−1}. Now, cf. [16, (5.3)],

[t^{n}]e^{mt}(1 − t)^{−r−1} = m^{n}Q_{r}(m, n)/n!  (3.17)

where

Q_{r}(m, n) = ∑_{j=0}^{n} \binom{r + j}{j}\frac{n!}{m^{j}(n − j)!}.  (3.18)

The right hand side of (3.16) can thus be expressed as a linear combination of a number of different Q_{r}. (See [16, (5.4)–(5.5)] for the first two cases.) We need the following straightforward asymptotics for Q_{r} in our range.

Lemma 3.1. If r ≥ 0 is a fixed integer, and n, m → ∞ with (m − n)/\sqrt{m} → a ≥ 0, then

Q_{r}(m, n) ∼ q_{r}(a)n^{(r+1)/2},

with

q_{r}(a) := \frac{1}{r!} ∫_{0}^{∞} x^{r}e^{−ax−x^{2}/2}dx.  (3.19)

Moreover, Q_{−1}(m, n) = 1 and Q_{−2}(m, n) = 1 − n/m = O(n^{−1/2}).

Proof. Denote the terms in the sum in (3.18) by b_{j}. If j ∼ xn^{1/2} for some x > 0, then

b_{j} = \binom{j + r}{r}m^{−j} \frac{n!}{(n − j)!} = \frac{(j + O(1))^{r}}{r!} (1 − \frac{m − n}{m})^{j} exp(∑_{i=0}^{j−1} ln(1 − \frac{i}{n}))

= \frac{j^{r}}{r!} exp(−j \frac{m − n}{m} − \frac{j^{2}}{2n} + o(1)) ∼ \frac{n^{r/2}x^{r}}{r!} e^{−ax−x^{2}/2}.

Moreover, for all j ≤ n,

b_{j} = \binom{j + r}{r}m^{−j} \frac{n!}{(n − j)!} ≤ (1 + rj^{r}) exp(∑_{i=0}^{j−1} ln (1 − \frac{i}{n}))

≤ (1 + rj^{r}) exp(−\frac{j(j − 1)}{2n})

and dominated convergence yields

\begin{aligned}n^{−(r+1)/2}Q_{r}(m, n) & = n^{−(r+1)/2} ∑_{j=0}^{n} b_{j} = ∫_{0}^{(n+1)n^{−1/2}} n^{−(r+1)/2}b_{⌊n^{1/2}x⌋}n^{1/2} dx \\ & → ∫_{0}^{∞} \frac{x^{r}}{r!} e^{−ax−x^{2}/2} dx = q_{r}(a). \end{aligned}

The formulae for Q_{−1} and Q_{−2} are immediate. □

Lemma 3.1 and (3.17) show that the leading terms in (3.16) come from the highest powers of (1 − t)^{−1}. More precisely, since by (3.11) ∏_{1}^{j} f_{k_{i}} has degree ∑_{i}(3k_{i} − 1) = 3k − j with leading term ∏_{i=1}^{j} ω_{k_{i}}(1 − t)^{j−3k}, (3.16), (3.17) and Lemma 3.1 yield, for some a_{kjl},

𝔼 \binom{D_{mn}}{k} = \frac{m}{m − n} ∑_{j=1}^{k} \binom{m − n}{j}( ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} ω_{k_{i}} · Q_{3k−j−2}(m, n)

+ ∑_{l=0}^{3k−j−1} a_{kjl}Q_{l−2}(m, n))

= m ∑_{j=1}^{k} (\frac{(m − n)^{j−1}}{j!} + O(n^{(j−2)/2}))

· ( ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} ω_{k_{i}} · q_{3k−j−2}(a)n^{(3k−j−1)/2} + o(n^{(3k−j−1)/2}))

= mn^{3k/2−1} ∑_{j=1}^{k} (\frac{a^{j−1}}{j!} + o(1)) ( ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} ω_{k_{i}} · q_{3k−j−2}(a) + o(1)) .

Thus, if we define, for k ≥ 1,

ψ_{k}(a) := k! ∑_{j=1}^{k}( ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} ω_{k_{i}})\frac{a^{j−1}}{j!} q_{3k−j−2}(a),  (3.20)

we have shown

𝔼 \binom{D_{mn}}{k} = n^{3k/2}(\frac{1}{k!}ψ_{k}(a) + o(1)), k ≥ 1,

which implies

n^{−3k/2} 𝔼 D_{mn}^{k} → ψ_{k}(a),  k ≥ 1.  (3.21)

We have thus shown that all moments of n^{−3/2}D_{mn} converge. This gives a proof of Theorem 1.1(iii) by the method of moments, and shows that 𝔼 W_{a}^{k} = ψ_{k}(a), provided we can show that the moments ψ_{k}(a) determine a unique distribution. A sufficient condition for this is that the sum ∑_{k} \frac{λ^{k}}{k!} ψ_{k}(a) converges for all real λ (the sum then equals 𝔼 e^{λW_{a}} − 1). We observe that D_{mn} and thus 𝔼 D_{mn}^{k} are increasing in n for fixed m, and thus (3.21) implies that ψ_{k}(a) is a decreasing function of a. In particular, ψ_{k}(a) ≤ ψ_{k}(0), so it suffices to consider a = 0.

Moreover, (3.20) yields, using the doubling formula for the gamma function,

\begin{aligned}ψ_{k}(0) & = k! ω_{k}q_{3k−3}(0) = \frac{k!}{(3k − 3)!}ω_{k} ∫_{0}^{∞} x^{3k−3}e^{−x^{2}/2}dx \\ & = \frac{k!}{(3k − 3)!}ω_{k} · 2^{3k/2−2}Γ(3k/2 − 1) \\ & = 2^{1−3k/2}π^{1/2}k! ω_{k}/Γ((3k − 1)/2), \end{aligned}  (3.22)

which by (3.12), the asymptotics c_{r} ∼ (3/2)^{r}(r − 1)!/2π as r → ∞ [13, (8.7)] and Stirling’s formula easily implies ∑_{k} λ^{k}ψ_{k}(0)/k! < ∞.

Remark 3.2. The fact that 𝔼 e^{λW_{a}} < ∞ for every real λ is perhaps more simply verified using the results of Section 2; Theorem 2.2 yields 0 ≤ W_{a} ≤ 2 max_{t} |b(t)|, and it is well-known that 𝔼 exp(2λ max_{t} |b(t)|) < ∞, cf. e.g. [4, (11.39) or (11.40)].

The relation (3.22) shows further, since ψ_{k}(0) = 𝔼 W_{0}^{k} > 0, that ω_{k} > 0 for all k ≥ 1; hence ψ_{k}(a) > 0 for all a ≥ 0.

We summarize the results obtained on W_{a}.

Theorem 3.3. The limit random variables W_{a} have the moments 𝔼 W_{a}^{k} = ψ_{k}(a), k ≥ 1, with ψ_{k} defined in (3.20). In particular,

𝔼 W_{a} = ω_{1}q_{0}(a) = \frac{1}{2}q_{0}(a)

and

𝔼 W_{a}^{2} = 2ω_{2}q_{3}(a) + ω_{1}^{2}aq_{2}(a) = \frac{5}{4}q_{3}(a) + \frac{1}{4}aq_{2}(a).

Moreover, the moment generating function 𝔼 e^{λW_{a}} is finite for each λ, and thus the distribution of W_{a} is determined by the moments ψ_{k}(a). □

The functions q_{k}(a), and thus the moments 𝔼 W_{a}^{k} = ψ_{k}(a), can be expressed in terms of the normal distribution function Φ. Indeed, by the change of variable x + a = y,

\begin{aligned}q_{0}(a) & = ∫_{0}^{∞} e^{−ax−x^{2}/2}dx = e^{a^{2}/2} ∫_{a}^{∞} e^{−y^{2}/2}dy = \sqrt{2π}e^{a^{2}/2}(1 − Φ(a)) \\ & = \sqrt{2π}e^{a^{2}/2}Φ(−a). \end{aligned}

Moreover,

q_{1}(a) = ∫_{0}^{∞}(x + a)e^{−ax−x^{2}/2}dx − aq_{0}(a) = 1 − aq_{0}(a)

and, for k ≥ 2, by integration by parts,

kq_{k}(a) = ∫_{0}^{∞} \frac{x^{k−1}}{(k − 1)!}(x + a)e^{−ax−x^{2}/2}dx − aq_{k−1}(a) = q_{k−2}(a) − aq_{k−1}(a).

By induction, any q_{k} can thus recursively be expressed as α_{k}(a) + β_{k}(a)q_{0}(a), where α and β are polynomials of degree k−1 and k, respectively. For example,

q_{2}(a) = \frac{1}{2}((1 + a^{2})q_{0}(a) − a),
q_{3}(a) = \frac{1}{6}((2 + a^{2}) − (3a + a^{3})q_{0}(a)).

Hence, the expressions for the first two moments of W_{a} in Theorem 3.3 can be rewritten:

Corollary 3.4. For any a ≥ 0,

𝔼 W_{a} = \frac{1}{2}q_{0}(a) = \sqrt{\frac{π}{2}}e^{a^{2}/2}Φ(−a),
𝔼 W_{a}^{2} = \frac{5}{4}q_{3}(a) + \frac{1}{4}aq_{2}(a) = \frac{1}{12}(5 + a^{2} − (6a + a^{3})q_{0}(a))
= \frac{1}{12}(5 + a^{2} − (6a + a^{3})\sqrt{2π}e^{a^{2}/2}Φ(−a)).  □

Asymptotics as a → ∞ are considered in Section 6.

4. The sparse case: normality

We exploit, as several other authors [6, 9, 16] the simple fact that a confined hash table with n items in m cells decomposes into m − n blocks, each ending with an empty cell, where each block can be regarded as a separate almost full confined hash table. More precisely, a hash sequence {h_{i}} giving a hash table with block lengths ℓ_{1}, …, ℓ_{N}, where N = m − n and ∑_{i} ℓ_{i} = m, can be constructed by first partitioning {1, …, n} into subsets {A_{j}}_{j=1}^{N} with |A_{j}| = ℓ_{j} − 1, and then for each j choosing (h_{i})_{i∈A_{j}} that after a simple relabelling corresponds to a hash sequence yielding a confined hash table with ℓ_{j} − 1 items and ℓ_{j} cells. (Note that we define the block lenghts to include the final, empty cell.)

Since, by (1.3), there are ℓ^{ℓ−2} confined hash sequences for ℓ − 1 items and ℓ cells, it follows that the number of confined hash sequences for n items in m cells yielding block lengths ℓ_{1},…,ℓ_{N} equals

\binom{n}{ℓ_{1} − 1, …, ℓ_{N} − 1} ∏_{j=1}^{N} ℓ_{j}^{ℓ_{j}−2} = n! ∏_{j=1}^{N} \frac{ℓ_{j}^{ℓ_{j}−2}}{(ℓ_{j} − 1)!} = n! ∏_{j=1}^{N} \frac{ℓ_{j}^{ℓ_{j}−1}}{ℓ_{j}!} .

Consequently, the probability that a random confined hash table has block lengths ℓ_{1}, …, ℓ_{N} is proportional to ∏_{j} ℓ_{j}^{ℓ_{j}−1}/ℓ_{j}! .

However, if λ is any real number with 0 < λ ≤ e^{−1}, so that T (λ) defined by (3.7) is finite, and X_{1}, …, X_{N} are independent random variables with the common Borel distribution

ℙ(X_{j} = ℓ) = \frac{1}{T (λ)} \frac{ℓ^{ℓ−1}}{ℓ!} λ^{ℓ},  ℓ = 1, 2, …,  (4.1)

then the conditional probability that (X_{1}, …, X_{N}) = (ℓ_{1}, …, ℓ_{N}) given that ∑_{j} X_{j} = m is also proportional to ∏_{j} ℓ_{j}^{ℓ_{j}−1}/ℓ_{j}! . Consequently, the proportionality factors have to agree, and the sequence of block lengths in a random confined hash table has the same distribution as (X_{1}, …, X_{N}) conditioned on ∑_{j} X_{j} = m. Moreover, given the block lengths, the blocks can be regarded as independent almost full confined hash tables; in particular, the sums of displacements inside the blocks are distributed as the total displacements for independent almost full hash tables of sizes equal to the given block lengths, and we obtain the following result.

Lemma 4.1. Suppose 0 ≤ n < m and let N = m − n. Let 0 < λ ≤ e^{−1} and let (X_{1}, Y_{1}), …, (X_{N}, Y_{N}) be independent random vectors with a common distribution obtained by first selecting X_{j} according to (4.1) and then, if X_{j} = ℓ, letting Y_{j} be distributed as the total displacement D_{ℓ,ℓ−1}. Then, for a random hash table with n items and m cells, the block lengths and the sums of displacements inside each block are distributed as (X_{1}, Y_{1}), …, (X_{N}, Y_{N}) conditioned on ∑_{j=1}^{N} X_{j} = m. In particular, the distribution of the total displacement D_{mn} equals the conditional distribution of ∑_{j=1}^{N} Y_{j} given ∑_{j=1}^{N} X_{j} = m. □

Remark 4.2. Lemma 4.1 is closely related to the relation (3.4) for generating functions derived in [9, 16], and our proof partly repeats arguments there, but we use a more probabilistic formulation.

There is further a one-to-one correspondence between hash tables and rooted forests, see e.g. [15, Exercise 6.4-31] and [6], and the lemma is essentially the same as a result used by Pavlov [17, 21, 22] to study random rooted forests. In particular, the distribution of the length of the largest block is given by [21].

We will use Lemma 4.1 together with the following general asymptotic result for conditioned distributions, which is proved (in a slightly more general form) in [12]. (The method of proof is similar to the saddle point method analysis of a generating function in [9], but in more probabilistic terms. Related conditional limit theorems, proved by the same method, are given in, for example, [10, 11].)

Lemma 4.3. Suppose that, for each k, (X, Y) = (X(k), Y (k)) is a pair of random variables such that X is integer valued, and that N = N(k) and m = m(k) are integers. Suppose further that for some γ and c (independent of k), with 0 < γ ≤ 2 and c > 0, the following hold, where σ_{X}^{2} := Var X, σ_{Y}^{2} := Var Y and all limits are taken as k → ∞:

(i) 𝔼 X = m/N. (ii) 0 < σ_{X}^{2} < ∞. (iii) For every integer r ≥ 3, 𝔼 |X − 𝔼 X|^{r} = o(N^{r/2−1}σ_{X}^{r}). (iv) σ_{X}^{2} = O(N^{2/γ−1}).

(v) φ_{X}(s) := 𝔼 e^{isX} satisfies 1 − |φ_{X}(s)| ≥ c min(|s|^{γ}, s^{2}σ_{X}^{2}) for |s| ≤ π. (vi) 0 < σ_{Y}^{2} < ∞. (vii) For every integer r ≥ 3, 𝔼 |Y − 𝔼 Y |^{r} = o(N^{r/2−1}σ_{Y}^{r}). (viii) The correlation ρ := Cov(X, Y)/σ_{X}σ_{Y} satisfies lim sup |ρ| < 1.

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

\frac{U − N 𝔼 Y}{N^{1/2}τ} →^{d} N(0, 1).  (4.2)

Moreover, 𝔼 U = N 𝔼 Y + o(N^{1/2}τ) and Var U ∼ Nτ^{2}, and thus also

\frac{U − 𝔼 U}{(Var U)^{1/2}} →^{d} N(0, 1).  (4.3)

The limits (4.2) and (4.3) hold with convergence of all moments.

Remark 4.4. Since 𝔼 |X − 𝔼 X|^{r} ≤ 2^{r} 𝔼 |X − a|^{r} for any real a and r ≥ 1 (a consequence of Minkowski’s inequality), it suffices in (iii) to estimate any 𝔼 |X − a|^{r}, for example 𝔼 |X|^{r}, and similarly in (vii).

Note further that (viii) is equivalent to τ^{2} = Θ(σ_{Y}^{2} ), and that τ^{2} is unchanged if Y is replaced by Y + aX + b for any real constants a and b (which changes U by the constant am + bN only).

It remains to show that the assumptions of Lemma 4.3 are satisfied with (X, Y) as in Lemma 4.1 for a suitable choice of λ. We begin with some estimates; we state them in greater generality than needed here (although we do not strive for maximal generality), partly in order to stress the properties of the random variables that really are important in our proof.

Lemma 4.5. Let X be an integer valued random variable and let p_{j} = ℙ(X = j). Suppose that η > 0 is such that there exists a j_{0} with p_{j_{0}} ≥ η and p_{j_{0}+1} ≥ η. Then | 𝔼 e^{isX}| ≤ 1 − ηs^{2}/5 for |s| ≤ π.

Proof. Let θ = arg 𝔼 e^{isX}. Thus, for |s| ≤ π,

1 − | 𝔼 e^{isX}| = 1 − Re 𝔼 e^{isX−iθ} = 1 − Re ∑_{j} p_{j}e^{isj−iθ} = ∑_{j} p_{j}(1 − cos(js − θ))

≥ η(1 − cos(j_{0}s − θ) + 1 − cos((j_{0} + 1)s − θ))

= 2η(1 − cos \frac{s}{2} cos((j_{0} + \frac{1}{2})s − θ)) ≥ 2η(1 − cos \frac{s}{2})

≥ 2η \frac{s^{2}}{π^{2}} . □

Lemma 4.6. Let 0 < γ < 1, κ > 0 and λ_{0} > 0, and let a_{0}, a_{1}, …, be nonnegative real numbers such that

a_{j} ∼ κj^{−γ−1}λ_{0}^{−j}  as j → ∞.  (4.4)

Let, for 0 < λ ≤ λ_{0}, X_{λ} be a random variable with the distribution

ℙ(X_{λ} = j) = a_{j}λ^{j}/F (λ),

where F (λ) = ∑_{j=0}^{∞} a_{j}λ^{j}. Then 𝔼 X_{λ_{0}} = ∞, but if λ < λ_{0}, then 0 < 𝔼 X_{λ}^{r} < ∞ for every r > 0. Asymptotically, if r > γ is fixed, then as λ ↑ λ_{0}, with κ_{0} = κ/F (λ_{0}),

𝔼 X_{λ}^{r} ∼ κ_{0}Γ(r − γ)(1 − λ/λ_{0})^{−(r−γ)}.  (4.5)

In particular, defining μ_{λ} := 𝔼 X_{λ} and σ_{λ}^{2} := Var X_{λ},

μ_{λ} ∼ κ_{0}Γ(1 − γ)(1 − λ/λ_{0})^{−(1−γ)}  (4.6)

and thus

σ_{λ}^{2} ∼ 𝔼 X_{λ}^{2} ∼ κ_{0}^{−1/(1−γ)}(1 − γ)Γ(1 − γ)^{−1/(1−γ)}μ_{λ}^{(2−γ)/(1−γ)}  (4.7)

and more generally, for every r > γ,

𝔼 X_{λ}^{r} ∼ κ_{0}^{(1−r)/(1−γ)}Γ(r − γ)Γ(1 − γ)^{−(r−γ)/(1−γ)}μ_{λ}^{(r−γ)/(1−γ)}.  (4.8)

Moreover, there exists a positive constant c such that for λ_{0}/2 ≤ λ ≤ λ_{0} and |s| ≤ π,

1 − | 𝔼 e^{isX_{λ}}| ≥ c min(|s|^{γ}, s^{2}σ_{λ}^{2}).  (4.9)

Proof. The assertions about existence of moments are immediate.

Replacing a_{j} by a_{j}λ_{0}^{j} and λ by λ/λ_{0}, we may assume that λ_{0} = 1. Further, let δ = − ln λ; note that δ ∼ 1 − λ as λ ↑ λ_{0} = 1. Then, by dominated convergence,

δ^{r−γ} 𝔼 X_{λ}^{r} = δ^{r−γ}F (λ)^{−1} ∑_{j=0}^{∞} j^{r}a_{j}e^{−δj}

= F (λ)^{−1} ∫_{0}^{∞} δ^{r−γ}⌊x/δ⌋^{r}a_{⌊x/δ⌋}e^{−δ⌊x/δ⌋}δ^{−1} dx
→ F (λ_{0})^{−1} ∫_{0}^{∞} κx^{r−γ−1}e^{−x} dx = κ_{0}Γ(r − γ).

This proves (4.5) and, as a special case, (4.6); together these yield (4.8). It follows further that (𝔼 X_{λ})^{2}/ 𝔼 X_{λ}^{2} ≍ (1 − λ)^{γ} → 0 as λ ↑ 1, whence σ_{λ}^{2} ∼ 𝔼 X_{λ}^{2} and (4.7) holds.

To prove (4.9), let φ_{λ}(s) = 𝔼 exp(isX_{λ}). Let j_{0} ≥ 1 be such that a_{j} > 0 for j ≥ j_{0}, and let c_{1} := inf_{j≥j_{0}} j^{γ+1}a_{j} > 0, s_{0} := j_{0}^{−1}, λ_{1} := exp(−s_{0}). First, for any λ ∈ [1/2, 1], we can apply Lemma 4.5 with η = min(a_{j_{0}}, a_{j_{0}+1})2^{−j_{0}−1}/F (1), which implies that for 1/2 ≤ λ ≤ λ_{1} and |s| ≤ π,

1 − |φ_{λ}(s)| ≥ \frac{1}{5}ηs^{2} ≥ \frac{1}{5}η(𝔼 X_{λ_{1}}^{2})^{−1}s^{2}σ_{λ}^{2},

and for any λ ≥ 1/2 and s_{0} ≤ s ≤ π,

1 − |φ_{λ}(s)| ≥ \frac{1}{5}ηs^{2} ≥ \frac{1}{5}ηs_{0}^{2−γ}s^{γ};

in both cases verifying (4.9) for a suitably small c > 0. It remains to consider the case λ_{1} < λ ≤ 1 and |s| < s_{0}; we may further assume 0 < s < s_{0} because |φ_{λ}(−s)| = |φ_{λ}(s)| and the case s = 0 is trivial. Let θ = arg φ_{λ}(s). Then

1 − |φ_{λ}(s)| = 1 − Re(φ_{λ}(s)e^{−iθ}) = ∑_{j=0}^{∞} F (λ)^{−1}e^{−jδ}a_{j} Re(1 − e^{ijs−iθ}). (4.10)

Let J = min(\frac{1}{s}, \frac{1}{δ}) ≥ j_{0}, I_{1} = [J, 2J] and I_{2} = [4J, 5J]. The sets \{e^{its−iθ} : t ∈ I_{k}}, k = 1, 2, are two intervals of length Js ≤ 1 on the unit circle, separated by 2Js (note that 6Js ≤ 2π); hence at least one of them is disjoint from {e^{iu} : |u| < Js}, which implies that for some choice of k (1 or 2) and every t ∈ I_{k}, cos(ts − θ) ≤ cos(Js) ≤ 1 − \frac{1}{3}J^{2}s^{2}. Consequently, (4.10) yields, for some c_{2}, c_{3} > 0,

1 − |φ_{λ}(s)| ≥ ∑_{j∈I_{k}} e^{−jδ}a_{j}(1 − cos(js − θ))/F (λ) ≥ ∑_{j∈I_{k}} e^{−5}a_{j} \frac{1}{3}J^{2}s^{2}/F (λ_{0})

= c_{2}J^{2}s^{2} ∑_{j∈I_{k}} a_{j} ≥ c_{2}J^{2}s^{2}c_{1} ∑_{j∈I_{k}} j^{−γ−1} ≥ c_{1}c_{2}J^{2}s^{2}⌊J⌋(5J)^{−γ−1}

≥ c_{3}s^{2}J^{2−γ} = c_{3} min(s^{γ}, s^{2}δ^{γ−2}).

Since σ_{λ}^{2} ≍ δ^{γ−2} by (4.5), (4.9) holds in this case too if c > 0 is small enough. □

Proof of Theorem 1.1(ii). We change the notation slightly, and let, for 0 < λ < e^{−1}, (X_{λ}, Y_{λ}) be a random vector with the distribution defined in Lemma 4.1 (there denoted (X_{j}, Y_{j})). Thus X_{λ} has the Borel distribution (4.1), with probability generating function 𝔼 z^{X_{λ}} = T (λz)/T (λ), where T is the tree function (3.7).

It is a well-known fact (also for much more general exponential families of distributions) that λ ↦ 𝔼 X_{λ} is a continuous, strictly increasing function of λ ∈ (0, e^{−1}). [Sketch of proof: 𝔼 X_{λ} = λT′(λ)/T (λ) which shows continuity, and if 0 < λ < λ_{1} < e^{−1} and b = λ_{1}/λ > 1, then 𝔼 X_{λ_{1}} = 𝔼 X_{λ}b^{X_{λ}}/ 𝔼 b^{X_{λ}} > 𝔼 X_{λ} by the FKG-inequality (calculate 𝔼(X′ − X′′)(b^{X′} − b^{X′′}) > 0 for two independent copies X′ and X′′ of X_{λ}).] Since further 𝔼 X_{λ} → 1 as λ ↓ 0 and 𝔼 X_{λ} → ∞ as λ ↑ e^{−1}, there exists for every μ > 1 a unique λ(μ) ∈ (0, e^{−1}) such that 𝔼 X_{λ(μ)} = μ, and the function μ ↦ λ(μ) is continuous.

Similarly, also higher moments 𝔼 X_{λ}^{r} are continuous (and increasing) functions of λ.

For n and m with 0 < n < m, we apply Lemma 4.3 with N = m − n and (X, Y) = (X_{λ}, Y_{λ}) for λ = λ(m/N). Thus condition (i) holds by construction. (Actually, (4.32) below implies the explicit formula λ = (n/m)e^{−n/m}, but we do not need this.) Lemma 4.1 shows that D_{mn} has the same distribution as U, so we may take U = D_{mn}.

In order to verify the remaining conditions, we consider three subcases separately: n/m → 0, n/m → a with 0 < a < 1 (the case studied by [9]), and n/m → 1. (It suffices to consider these three subcases, although they do not exhaust all possibilities, since every sequence (m_{k}, n_{k}) with m_{k} → ∞ has a subsequence belonging to one of the subcases; cf. Remark 1.3.)

Case 1: n/m → 0; m/N → 1. We verify the conditions of Lemma 4.3 with γ = 2.

In this case λ = λ(m/N) → 0, and thus T (λ) ∼ λ. We have

ℙ(X = 1) = λ/T (λ) → 1,
ℙ(X = 2) = λ^{2}/T (λ) ∼ λ,
ℙ(X = 3) = \frac{9}{6}λ^{3}/T (λ) ∼ \frac{3}{2}λ^{2}.

Hence,

\frac{n}{N} = \frac{m}{N} − 1 = 𝔼(X − 1) ∼ ℙ(X = 2) ∼ λ

and thus λ ∼ n/N ∼ n/m. Moreover,

𝔼 |X − 1|^{r} ∼ ℙ(X = 2) ∼ λ ∼ n/m

for every r > 0; in particular

Var X = Var(X − 1) ∼ 𝔼(X − 1)^{2} ∼ n/m,

which implies conditions (ii) and (iv) (with γ = 2), and further, for any r > 2, using λ^{−1} ∼ m/n = o(m),

𝔼 |X − 1|^{r}/σ_{X}^{r} ∼ λ/λ^{r/2} = λ^{−(r/2−1)} = o(m^{r/2−1}) = o(N^{r/2−1}),

which yields (iii), cf. Remark 4.4. Since min(ℙ(X = 1), ℙ(X = 2)) ∼ λ ∼ σ_{X}^{2}, Lemma 4.5 shows that (v) holds too.

For Y we have, from the definition, Y = 0 when X ≤ 2, and ℙ(Y = 0 | X = 3) = 2/3, ℙ(Y = 1 | X = 3) = 1/3; thus, for every r > 0,

𝔼 Y^{r} = \frac{1}{3} ℙ(X = 3) + O(λ^{3}) ∼ \frac{1}{2}λ^{2}.  (4.11)

Hence, σ_{Y}^{2} ∼ \frac{1}{2}λ^{2} ∼ \frac{1}{2}(n/m)^{2}, and for every r > 2, now using λ^{−1} ∼ m/n = o(m^{1/2}) (by the assumption n ≫ m^{1/2})

𝔼 Y^{r}/σ_{Y}^{r} = O(λ^{−(r−2)}) = o(m^{r/2−1}) = o(N^{r/2−1}),

so (vi) and (vii) hold.

Finally, 𝔼(XY) ∼ \frac{1}{3} ℙ(X = 3) · 3 ∼ \frac{3}{2}λ^{2} and thus

ρ = Cov(X, Y)/σ_{X}σ_{Y} = O(λ^{2}/λ^{1/2}λ) = O(λ^{1/2}),

so ρ → 0 and (viii) holds.

Consequently, Lemma 4.3 applies and shows (D_{mn}−𝔼 D_{mn})/(Var D_{mn})^{1/2} →^{d} N(0, 1), with convergence of all moments. Note, for future use, that

τ^{2} ∼ σ_{Y}^{2} ∼ \frac{1}{2}λ^{2} ∼ \frac{n^{2}}{2m^{2}} .  (4.12)

Case 2: n/m → a, 0 < a < 1; m/N → b := 1/(1 − a). Again we take γ = 2. In this case λ = λ(m/N) → λ(b), and thus the distribution of (X, Y) converges to (X_{λ(b)}, Y_{λ(b)}), together with all moments; in particular, σ_{X}^{2} → Var(X_{λ(b)}) > 0. It is easily verified that all assumptions of Lemma 4.3 hold, cf. [12, Corollary 2.1]; note that (v) follows from Lemma 4.5 and that (viii) follows because the correlation coefficient ρ(X_{λ(b)}, Y_{λ(b)}) does not equal ±1 since both {X_{λ(b)} = 3, Y_{λ(b)} = 0} and {X_{λ(b)} = 3, Y_{λ(b)} = 1} have positive probabilities. Thus the result follows from Lemma 4.3. Case 3: n/m → 1; m/N → ∞. In this case, λ → λ_{0} = e^{−1} and we verify the conditions with γ = 1/2.

We are in the set-up of Lemma 4.6, with a_{j} = j^{j−1}/j!, j ≥ 1, and F (λ) = T (λ), the tree function in (3.7). By Stirling’s formula, a_{j} ∼ (2π)^{−1/2}j^{−3/2}e^{j} as j → ∞, so (4.4) holds with γ = 1/2, κ = (2π)^{−1/2} and λ_{0} = e^{−1}; we further have, as is well-known, F (λ_{0}) = T (e^{−1}) = 1, so κ_{0} = κ. Hence, Lemma 4.6 applies, which by (4.9) yields (v). Moreover, it shows that for every r > 1/2,

𝔼 X_{λ}^{r} ∼ \frac{Γ(r − 1/2)}{\sqrt{2π}}(1 − eλ)^{1/2−r}.  (4.13)

In particular, cf. the exact formulae (4.25), (4.30) below,

μ_{λ} = 𝔼 X_{λ} ∼ 2^{−1/2}(1 − eλ)^{−1/2},  (4.14)
σ_{λ}^{2} ∼ 𝔼 X_{λ}^{2} ∼ 2^{−3/2}(1 − eλ)^{−3/2} ∼ μ_{λ}^{3} = (m/N)^{3}.  (4.15)

By assumption, N^{2} ≫ n, and thus μ_{λ} = m/N ∼ n/N ≪ N, which yields σ_{λ}^{2} = O(μ_{λ}^{3}) = O(N^{3}), i.e. (iv). Similarly, for r > 2,

𝔼 X_{λ}^{r}/σ_{λ}^{r} = O(μ_{λ}^{2r−1}/μ_{λ}^{3r/2}) = O(μ_{λ}^{r/2−1}) = o(N^{r/2−1}),

which verifies (iii).

Next, by the construction of Y_{λ},

𝔼(Y_{λ}^{r} | X_{λ} = ℓ) = 𝔼 D_{ℓ,ℓ−1}^{r},

and by the already proved Theorem 1.1(iii), for every r > 0,

ℓ^{−3r/2} 𝔼 D_{ℓ,ℓ−1}^{r} → 𝔼 W_{0}^{r} as ℓ → ∞.

Hence, fixing r, for every ε > 0 there exists ℓ_{ε} such that

| 𝔼 D_{ℓ,ℓ−1}^{r} − ℓ^{3r/2} 𝔼 W_{0}^{r}| < εℓ^{3r/2} for ℓ ≥ ℓ_{ε};

letting C_{ε} be the maximum of the left hand side for 1 ≤ ℓ < ℓ_{ε}, we see that for every ℓ

(𝔼 W_{0}^{r} − ε)ℓ^{3r/2} − C_{ε} ≤ 𝔼(Y_{λ}^{r} | X_{λ} = ℓ) = 𝔼 D_{ℓ,ℓ−1}^{r} ≤ (𝔼 W_{0}^{r} + ε)ℓ^{3r/2} + C_{ε}

and thus

(𝔼 W_{0}^{r} − ε)X_{λ}^{3r/2} − C_{ε} ≤ 𝔼(Y_{λ}^{r} | X_{λ}) ≤ (𝔼 W_{0}^{r} + ε)X_{λ}^{3r/2} + C_{ε},  (4.16)

which yields, by taking the expectation,

(𝔼 W_{0}^{r} − ε) 𝔼 X_{λ}^{3r/2} − C_{ε} ≤ 𝔼 Y_{λ}^{r} ≤ (𝔼 W_{0}^{r} + ε) 𝔼 X_{λ}^{3r/2} + C_{ε}.

Together with (4.8) this easily implies that for every r > 1/3, as λ → e^{−1},

\begin{aligned}𝔼 Y_{λ}^{r} & ∼ 𝔼 W_{0}^{r} 𝔼 X_{λ}^{3r/2} ∼ 𝔼 W_{0}^{r} κ_{0}^{2−3r}Γ(3r/2 − 1/2)Γ(1/2)^{1−3r}μ_{λ}^{3r−1} \\ & = 2^{3r/2−1}π^{−1/2}Γ(3r/2 − 1/2) 𝔼 W_{0}^{r} μ_{λ}^{3r−1}. \end{aligned} (4.17)

More generally, by first multiplying (4.16) by X_{λ}^{s}, it follows similarly that if s, r ≥ 0 with 3r/2 + s > 1/2, then

\begin{aligned}𝔼 X_{λ}^{s}Y_{λ}^{r} & ∼ 𝔼 W_{0}^{r} 𝔼 X_{λ}^{s+3r/2} \\ & ∼ κ_{0}^{2−2s−3r}Γ(s + 3r/2 − 1/2)Γ(1/2)^{1−2s−3r}μ_{λ}^{2s+3r−1} 𝔼 W_{0}^{r} \\ & = 2^{s+3r/2−1}π^{−1/2}Γ(s + 3r/2 − 1/2) 𝔼 W_{0}^{r}μ_{λ}^{2s+3r−1}. \end{aligned} (4.18)

In particular, using 𝔼 W_{0} = \sqrt{π/8} and 𝔼 W_{0}^{2} = 5/12 [20, 9],

𝔼 Y_{λ} ∼ \sqrt{2/π} 𝔼 W_{0}μ_{λ}^{2} = \frac{1}{2}(m/N)^{2}  (4.19)
σ_{Y}^{2} ∼ 𝔼 Y_{λ}^{2} ∼ 4π^{−1/2}Γ(5/2) 𝔼 W_{0}^{2}μ_{λ}^{5} = 3 𝔼 W_{0}^{2}μ_{λ}^{5} = \frac{5}{4}(m/N)^{5}  (4.20)

and, by (4.18),

𝔼 X_{λ}Y_{λ} ∼ 2^{3/2}π^{−1/2}Γ(2) 𝔼 W_{0}μ_{λ}^{4} = μ_{λ}^{4} = (m/N)^{4}.

Thus, Cov(X_{λ}, Y_{λ}) ∼ 𝔼 X_{λ}Y_{λ} ∼ μ_{λ}^{4} = (m/N)^{4} and

ρ ∼ \frac{𝔼 X_{λ}Y_{λ}}{(𝔼 X_{λ}^{2} 𝔼 Y_{λ}^{2})^{1/2}} ∼ \frac{μ_{λ}^{4}}{(μ_{λ}^{3} \frac{5}{4}μ_{λ}^{5})^{1/2}} = \sqrt{\frac{4}{5}},

which shows (viii). Furthermore,

τ^{2} ∼ (3 𝔼 W_{0}^{2} − \frac{8}{π}(𝔼 W_{0})^{2})μ_{λ}^{5} = \frac{1}{4}(\frac{m}{N})^{5}.  (4.21)

Finally, for r ≥ 3, by (4.20) and (4.17),

𝔼 Y_{λ}^{r}/σ_{Y}^{r} = O(μ_{λ}^{3r−1}/μ_{λ}^{5r/2}) = O(μ_{λ}^{r/2−1}) = o(N^{r/2−1}),

which verifies (vii), and again the result follows by Lemma 4.3. □

Proof of Theorem 1.4 (ii). In the case n/m → 0, Lemma 4.3 and (4.11), (4.12) show that

𝔼 D_{mn} = N 𝔼 Y + o(N^{1/2}τ) ∼ \frac{n^{2}}{2m},
Var D_{mn} ∼ Nτ^{2} ∼ \frac{n^{2}}{2m},

verifying Theorem 1.4(i) and (ii) when m^{1/2} ≪ n ≪ m.

Similarly, when n/m → 1 and m − n ≫ m^{1/2}, Lemma 4.3 and (4.19), (4.21) yield Theorem 1.4(ii) for this case.

In the case α = n/m → a ∈ (0, 1), finally, it follows from Lemma 4.3 that 𝔼 D_{mn} and Var D_{mn} are asymptotically proportional to N, and thus to n. In order to obtain explicit expressions, we argue as follows, using the generating functions explored in Section 3. (As stated in Section 1, these asymptotics were found by [14] and [9], respectively, directly from the exact formulae. Nevertheless, we find the alternative proof given here interesting.)

By the definition of Y_{λ}, (3.1), (4.1), (3.2) and (3.3),

\begin{aligned}𝔼 w^{Y_{λ}} & = ∑_{ℓ=1}^{∞} 𝔼 w^{D_{ℓ,ℓ−1}} ℙ(X_{λ} = ℓ) = ∑_{ℓ=1}^{∞} \frac{F_{ℓ,ℓ−1}(w)}{F_{ℓ,ℓ−1}(1)} \frac{ℓ^{ℓ−1}λ^{ℓ}}{ℓ! T (λ)} \\ & = ∑_{ℓ=1}^{∞} F_{ℓ,ℓ−1}(w)\frac{λ^{ℓ}}{(ℓ − 1)! T (λ)} = \frac{λ}{T (λ)}F (w, λ) \end{aligned}

and thus, by (3.6) and (3.10), for k = 0, 1, …,

𝔼 \binom{Y_{λ}}{k} = [w^{k}] 𝔼(1 + w)^{Y_{λ}} = \frac{λ}{T (λ)}[w^{k}]F (1 + w, λ) = \frac{λ}{T (λ)}W′_{k}(λ) = f_{k}(T (λ)).

(4.22)

More generally, we similarly obtain, for j = 0, 1, …,

𝔼(w^{Y_{λ}}X_{λ}^{j}) = ∑_{ℓ=1}^{∞} F_{ℓ,ℓ−1}(w)ℓ^{j} \frac{λ^{ℓ}}{(ℓ − 1)! T (λ)} = \frac{1}{T (λ)}(λ\frac{d}{dλ})^{j}(λF (w, λ))

and thus

\begin{aligned}𝔼(\binom{Y_{λ}}{k}X_{λ}^{j}) & = [w^{k}]\frac{1}{T (λ)}(λ\frac{d}{dλ})^{j}(λF (1 + w, λ)) \\ & = \frac{1}{T (λ)}(λ\frac{d}{dλ})^{j}(T (λ)f_{k}(T (λ))). \end{aligned}  (4.23)

For any differentiable function h, we have

λ\frac{d}{dλ}(h(T (λ)) = λT′(λ)h′(T (λ)) = \frac{T (λ)}{1 − T (λ)}h′(T (λ));  (4.24)

in other words, λ\frac{d}{dλ} = \frac{T}{1−T} \frac{d}{dT}. Hence, (4.22), (4.23) and (3.13) yield by simple calculations, dropping the λ from the notation,

𝔼 X = \frac{1}{T} (λ\frac{d}{dλ})T = \frac{1}{T} \frac{T}{1 − T} \frac{d}{dT} T = \frac{1}{1 − T} ,  (4.25)
𝔼 X^{2} = \frac{1}{T} (\frac{T}{1 − T} \frac{d}{dT} )^{2}T = \frac{1}{(1 − T)^{3}} ,  (4.26)
𝔼 Y = f_{1}(T) = \frac{T^{2}}{2(1 − T)^{2}} ,  (4.27)
𝔼 Y^{2} = 2 𝔼 \binom{Y}{2} + 𝔼 Y = 2f_{2}(T) + f_{1}(T) = \frac{6T^{2} + 6T^{3} + 7T^{4} − 4T^{5}}{12(1 − T)^{5}} , (4.28)

𝔼 XY = \frac{1}{T} \frac{T}{1 − T} \frac{d}{dT} (T f_{1}(T)) = \frac{3T^{2} − T^{3}}{2(1 − T)^{4}} ,  (4.29)

which by further straightforward calculations lead to

Var X = 𝔼 X^{2} − (𝔼 X)^{2} = \frac{T}{(1 − T)^{3}} ,  (4.30)
τ^{2} = Var Y − Cov(X, Y)^{2}/ Var X = \frac{6T^{2} − 6T^{3} + 4T^{4} − T^{5}}{12(1 − T)^{5}} . (4.31)

The condition 𝔼 X = m/N and (4.25) yield 1 − T = N/m and thus

T = n/m = α.  (4.32)

Lemma 4.3 and (4.27), (4.31), (4.32) now yield (1.1) and (1.2). □

5. The very sparse case: Poisson behaviour

Theorem 1.1(i) is much simpler than the other parts and is given mainly for completeness. It too can be shown using Lemma 4.1 (for example using Holst [11, Corollary 3.5]), but we prefer a direct approach, using a related occupancy problem.

Let D′_{mn} be the number of cells where at least two items make their first try, i.e. using the notation of Section 2, the number of j with X_{j} ≥ 2. It is easily seen that if X_{j} + X_{j+1} ≤ 2 for all j, then no item is displaced more than one step and D_{mn} = D′_{mn}. Consequently, using symmetry,

ℙ(D_{mn} ≠ D′_{mn}) ≤ m ℙ(X_{1} + X_{2} ≥ 3) ≤ mn^{3} ℙ(h_{1}, h_{2}, h_{3} ∈ \{1, 2\}) = 8\frac{n^{3}}{m^{2}} → 0.

(5.1)

Moreover, it is easy to check by the method of moments or by Stein’s method, see for example [2, Theorem 6.B], that D′_{mn} →^{d} Po(a^{2}/2). By (5.1), then

D_{mn} →^{d} Po(a^{2}/2) too.

Remark 5.1. The argument shows more generally Poisson convergence in the form d_{TV}(D_{mn}, Po(n^{2}/2m)) → 0, where d_{TV} denotes the total variation distance [2], even for n^{2}/2m → ∞ as long as n = o(m^{2/3}).

Remark 5.2. Instead of approximating D_{mn} by D′_{mn}, we could just as well use the number of pairs (i, j), i < j with h_{i} = h_{j}; this is a variable arising in birthday problems, and again it is easy to prove that it is asymptotically Poisson distributed, see e.g. [2, Theorem 5.G (with Γ the complete graph K_{n})].

To show moment convergence, it suffices by Remark 1.2 to show that 𝔼 D_{mn}^{r} = O(1) for each r. This can presumably be verified by a direct combinatorial analysis, but we argue instead as follows.

Suppose to the contrary that there is an integer r ≥ 1 such that 𝔼 D_{mn}^{r} is unbounded; then there is a sequence (m_{k}, n_{k}) with n_{k}^{2}/m_{k} → a^{2} and a sequence ω_{k} → ∞ such that 𝔼 D_{m_{k}n_{k}}^{r} ≥ ω_{k}^{2r} for all k. We can further assume ω_{k} ≪ \sqrt{m_{k}}. Define n′_{k} = ⌊ω_{k}m_{k}^{1/2}⌋. Then n′_{k} > n_{k} for large k, and thus 𝔼 D_{m_{k}n′_{k}}^{r} ≥ 𝔼 D_{m_{k}n_{k}}^{r} ≥ ω_{k}^{2r}. On the other hand, Theorems 1.1(ii) and 1.4(ii) apply to D_{m_{k}n′_{k}}, and it follows from the moment convergence that

𝔼 D_{m_{k}n′_{k}}^{r} ∼ (𝔼 D_{m_{k}n′_{k}})^{r} ∼ (\frac{(n′_{k})^{2}}{2m_{k}} )^{r} ∼ 2^{−r}ω_{k}^{2r}.

This yields the desired contradiction, proving 𝔼 D_{mn}^{r} = O(1) and completing the proof of Theorem 1.1(i).

The moment estimates in Theorem 1.4(i) now follow for the case n/m^{1/2} → a > 0. The case n/m^{1/2} → ∞ was treated in Section 4, but it remains to consider the rather trivial case n/m^{1/2} → 0, when ℙ(D_{mn} ≠ 0) ∼ n^{2}/2m → 0. As remarked in the introduction, the exact formula for 𝔼 D_{mn} easily yields 𝔼 D_{mn} ∼ n^{2}/2m in this case. We do not know any simple argument for the variance, but the exact formula for 𝔼 D_{mn}^{2} in [9, Theorem 4] yields after straightforward (but tedious) calculations 𝔼 D_{mn}^{2} ∼ n^{2}/2m too, as required.

6. Asymptotics for the limits W_{a}

In this section we study the asymptotics of the distribution of the limit variables W_{a} as a → ∞.

Theorem 6.1. As a → ∞, we have 𝔼 W_{a} ∼ \frac{1}{2}a^{−1}, Var W_{a} ∼ \frac{1}{4}a^{−4} and

\frac{W_{a} − 𝔼 W_{a}}{(Var W_{a})^{1/2}} →^{d} N(0, 1)  (6.1)

with convergence of all moments.

Proof. In this proof we use the notation X̃ := (X − 𝔼 X)/(Var X)^{1/2} for the standardization of a random variable X.

Theorem 1.1(iii) shows that, for any a > 0, m^{−3/2}D_{m,m−⌊am^{1/2}⌋} →^{d} W_{a} with convergence of all moments, and thus also

D̃_{m,m−⌊am^{1/2}⌋} = (m^{−3/2}D_{m,m−⌊am^{1/2}⌋})^{∼} →^{d} W̃_{a}.  (6.2)

The space of all probability distributions on ℝ is metrizable (see e.g. [4, Appendix III]); let d denote a metric on this space (for example the well-known Lévy metric, but any metric will do). If X and Y are random variables, we write d(X, Y) for the distance between their distributions. Then (6.2) shows that for every a > 0, there is an integer m(a) such that defining n(a) := m(a) − ⌊am(a)^{1/2}⌋ we have

d(D̃_{m(a),n(a)}, W̃_{a}) < a^{−1}.  (6.3)

We may further assume m(a) > 4a^{2}, and thus m(a) − n(a) ≤ am(a)^{1/2} ≤ \frac{1}{2}m(a).

Now let a → ∞. Then m(a) → ∞, n(a) ≥ \frac{1}{2}m(a) and m(a) − n(a) ≫ m(a)^{1/2}, and thus by Theorem 1.1(ii)

d(D̃_{m(a),n(a)}, N(0, 1)) → 0.  (6.4)

Combining (6.3) and (6.4) yields d(W̃_{a}, N(0, 1)) → 0, which proves (6.1).

To prove moment convergence, we use the same argument, now taking d(X, Y) := | 𝔼 X^{r} − 𝔼 Y^{r}| for a fixed integer r.

Finally, Theorem 1.4(iii) shows that if m → ∞ and n = m − ⌊am^{1/2}⌋, then

(m − n)n^{−2} 𝔼 D_{m,n} → a 𝔼 W_{a}

and

(m − n)^{4}n^{−5} Var D_{m,n} → a^{4} Var W_{a},

which by a similar argument and Theorem 1.4(ii) yield a 𝔼 W_{a} → 1/2 and a^{4} Var W_{a} → 1/4 as n → ∞. □

More precise estimates of the moments of W_{a} are easily obtained using the formulae in Section 3. Indeed, a Taylor expansion of e^{−x^{2}/2} in the definition (3.19) yields

\begin{aligned}q_{r}(a) & = \frac{1}{r!} ∫_{0}^{∞} x^{r}e^{−ax}(1 − x^{2}/2 + O(x^{4})) dx \\ & = a^{−r−1} − \frac{(r + 1)(r + 2)}{2}a^{−r−3} + O(a^{−r−5}). \end{aligned}  (6.5)

Consequently, Theorem 3.3 yields

𝔼 W_{a} = \frac{1}{2}q_{0}(a) = \frac{1}{2}a^{−1} − \frac{1}{2}a^{−3} + O(a^{−5}),  (6.6)
𝔼 W_{a}^{2} = \frac{5}{4}q_{3}(a) + \frac{1}{4}aq_{2}(a) = \frac{1}{4}a^{−2} − \frac{1}{4}a^{−4} + O(a^{−6}),  (6.7)

and thus

Var W_{a} = 𝔼 W_{a}^{2} − (𝔼 W_{a})^{2} = \frac{1}{4}a^{−4} + O(a^{−6}).  (6.8)

The same method yields further terms in (6.5)–(6.8), giving asymptotic expansions of 𝔼 W_{a} and Var W_{a} in powers of a^{−1} up to an arbitrary degree, but we leave the details to the reader. The method yields asymptotics for higher moments too.

Note that by (6.6) and (6.8), the distributional limit (6.1) can be written

2a^{2}(W_{a} − 1/2a) →^{d} N(0, 1), as a → ∞.

7. Unsuccessful search

In an unsuccessful search, we start searching at a random cell h and probe successive cells until we reach an empty cell when we give up. (We assume throughout this section that n < m so that there is at least one empty cell.) The number of probes used when starting in a block of length ℓ thus ranges from 1 to ℓ, and if the hash tables have block lengths ℓ_{1}, …, ℓ_{N}, with N = m−n and ∑_{i} ℓ_{i} = m, the average unsuccessful search time U_{mn} is given by

U_{mn} = \frac{1}{m} ∑_{j=1}^{N} ∑_{i=1}^{ℓ_{j}} i = \frac{1}{m} ∑_{j=1}^{N} \binom{ℓ_{j} + 1}{2} = \frac{1}{2m}Û_{mn} + \frac{1}{2},  (7.1)

where we for convenience define

Û_{mn} := ∑_{j=1}^{N} ℓ_{j}^{2}.

Note that for given m and n, Û_{mn}, and thus U_{mn}, is largest when one block has length n + 1 and the others length 1, and smallest when all block lengths are as equal as possible, i.e. when all are ⌊m/(m − n)⌋ or ⌈m/(m − n)⌉.

Brownian limits. First, we adapt the Brownian approach in Section 2, assuming n < m and (m − n)/\sqrt{n} → a ≥ 0. The empty cells occur when H_{i} = 0, and thus the block lengths, normalized as (ℓ_{i} − 1)/m, are the lengths of the excursions (i.e. the zero-free intervals) of the random function H_{⌊mt⌋} or m^{−1/2}H_{⌊mt⌋}. By (2.2), the latter random function converges in distribution to Y_{a}(t) := max_{s≤t}(b(t) − b(s) − a(t − s)), and it is reasonable to conjecture that the lengths of its excursions converge to the lengths of the excursions of Y_{a}.

(We consider the excursions in an interval [t_{0}, t_{0} + 1] with Y_{a}(t_{0}) = 0; equivalently, we consider [0, 1] but allow an excursion to wrap around from 1 to 0.) It follows from a result by Vervaat [28], see Remark 2.3, that these have the same distribution as the lengths of the excursions of Z_{a}(t) := max_{0≤s≤t}(e(t) − e(s) − a(t − s)) in [0, 1].

However, the convergence of the lengths does not follow from the argument above alone, since taking the excursion lengths is not a continuous operation; nevertheless, it has been verified by Chassaing and Louchard [6]. More precisely, they show in [6] that if (L_{i})_{i=1}^{∞} is the sequence consisting of the block lengths ℓ_{1}, …, ℓ_{N} arranged in decreasing order, followed by infinitely many zeroes, and (J_{i})_{i=1}^{∞} is the sequence of the excursion lengths of Z_{a} arranged in decreasing order, then (L_{i}/m)_{1}^{∞} →^{d} (J_{i})_{1}^{∞} as random elements of ℓ^{1}. Since (x_{i}) ↦ ∑ x_{i}^{2} is a continuous functional on ℓ^{1}, this immediately yields

Û_{mn}/m^{2} = ∑_{1}^{∞}(L_{i}/m)^{2} →^{d} ∑_{1}^{∞} J_{1}^{2},

which by (7.1) yields Theorem 1.6(iii) with the following description of the limit. (Moment convergence is immediate since 0 ≤ Û_{mn}/m^{2} ≤ 1.)

Theorem 7.1. The limit V_{a} can be constructed as the sum of the squares of the excursion lengths of the stochastic process

Z_{a}(t) := max_{0≤s≤t}(e(t) − e(s) − a(t − s)),  0 ≤ t ≤ 1.  Λ

As remarked above, Z_{a} can here be replaced by Y_{a} defined above. Moreover, the excursion lengths of Z_{a} or Y_{a} have several different, equivalent descriptions, which lead to the following alternative characterizations of V_{a}, see further [1, 3, 5, 6, 23, 24]. (We exclude the trivial case a = 0 when V_{a} = 1.)

Theorem 7.2. Let 0 < a < ∞. The limit V_{a} can be constructed as any of the following random variables.

(i) The sum of the squares of the excursion lengths of a Brownian bridge on [0, 1] conditioned on having local time a at 1.

(ii) The sum of the squares of the excursion lengths of a Brownian motion

on [0, 1] conditioned on having local time a at 1. (iii) The sum of the squares of the jumps of a standard stable subordinator

of index 1/2 on [0, a] conditioned on having value 1 at a. (Note that this value equals the sum of the jumps.)

(iv) The sum of the squares of a^{2} times the jumps of a standard stable subordinator of index 1/2 on [0, 1] conditioned on having value a^{−2} at 1.

(v) The sum ∑ x_{i}^{2} of the squares of the points in a Poisson process {x_{i}}_{1}^{∞} on (0, ∞) with intensity a/\sqrt{2πx^{3}}, conditioned on ∑ x_{i} = a.

(vi) The sum of the squares of the component sizes of X(− log a), where

X(t) denotes the standard additive coalescent [1]. (vii) Let ξ_{1}, ξ_{2}, … be independent standard normal variables and define

S_{k} = ∑_{1}^{k} ξ_{i}^{2} (with S_{0} = 0) and R_{k} = \frac{a^{2}}{S_{k−1}+a^{2}} − \frac{a^{2}}{S_{k}+a^{2}} ; then define V_{a} = ∑_{1}^{∞} R_{k}^{2}.

Proof. The equivalence of the seven constructions is well-known, also on the level of random sequences of lengths, jumps, etc. More specifically, first it is well-known, cf. [25, §VI.2 and §XII.2], that the excursion lengths of a Brownian motion in [0, 1] are the jumps of the inverse τ_{s} := inf{t : T_{t} > s} of the local time process T_{t} in the interval 0 ≤ s ≥ T_{1}, that τ_{s} is a stable subordinator of index 1/2, and that the sizes of the jumps of τ_{s} for 0 ≤ s ≤ a are given by a Poisson process on (0, ∞) with intensity a/\sqrt{2πx^{3}}. The equivalence of (i), (iii) and (v) now follows easily, cf. e.g. [24]. Moreover, a simple rescaling yields the equivalence of (iii) and (iv). By [24, Theorem 5.1], (i) and (ii) are equivalent. The equivalence of (iv), (vi) and (vii) follows by [1, Theorems 3, 4 and Corollary 5].

Finally, these constructions may be connected to Theorem 7.1 in several ways. First, [6] gives a direct proof that the normalized block lengths L_{i}/m, taken in order of arrival of the first item, converge to the the sequence (R_{k}) in (vii), which implies Û_{mn}/m^{2} →^{d} ∑ R_{k}^{2} and thus (vii). Secondly, the equivalence of (i) and Theorem 7.1 follows by [5]. Thirdly, by the equivalence between random hash tables and random forests mentioned in Remark 4.2, (vi) follows easily from the limit result [1, Proposition 2]. □

Moments. For the generating function approach in Section 3, we let F̂_{mn} be the generating function for Û_{mn} in the confined version; thus

𝔼 xÛ_{mn} = F̂_{mn}(x)/F̂_{mn}(1),  (7.2)

where F̂_{mn}(1) = F_{mn}(1) = (m − n)m^{n−1} by (3.2). In the case m = n + 1, there is only a single block of length n + 1, and thus Û_{mn} = (n + 1)^{2} is non-random, so

F̂_{n+1,n}(x) = x^{(n+1)^{2}} F̂_{n+1,n}(1) = (n + 1)^{n−1}x^{(n+1)^{2}}.

We define, as in (3.3),

F̂(x, z) = ∑_{n=0}^{∞} F̂_{n+1,n}(x)\frac{z^{n}}{n!} = ∑_{n=0}^{∞} \frac{(n + 1)^{n−1}}{n!} x^{(n+1)^{2}}z^{n} = ∑_{m=1}^{∞} \frac{m^{m−1}}{m!} x^{m^{2}}z^{m−1},

(7.3)

and (3.4) holds with F̂. It is this time somewhat more convenient to study F̂(e^{w}, z) instead of F̂(1 + w, z). Then, by (7.2) and (3.4), (3.5) is replaced by

\begin{aligned}\frac{1}{k!} 𝔼 Û_{mn}^{k} & = [w^{k}] 𝔼 e^{wÛ_{mn}} = [w^{k}]F̂_{mn}(e^{w})/F̂_{mn}(1) \\ & = [w^{k}z^{n}]F̂(e^{w}, z)^{m−n}/[z^{n}]F̂(1, z)^{m−n}. \end{aligned}  (7.4)

Moreover, we write F̂(e^{w}, z) = ∑_{0}^{∞} w^{k}Ŵ_{k}(z), where the power series Ŵ_{k} are given by, cf. (7.3) and (3.7),

\begin{aligned}Ŵ_{k} & := [w^{k}]F̂(e^{w}, z) = ∑_{m=1}^{∞} \frac{m^{m−1}}{m!} [w^{k}]e^{m^{2}w}z^{m−1} = \frac{1}{k!} ∑_{m=1}^{∞} \frac{m^{m−1+2k}}{m!} z^{m−1} \\ & = \frac{1}{k!}z^{−1}(z \frac{d}{dz} )^{2k}T (z). \end{aligned} (7.5)

By (4.24), for j = 0, 1, …,

\begin{aligned}z \frac{d}{dz} T (1 − T)^{−j} & = \frac{T}{1 − T} ((1 − T)^{−j} + jT (1 − T)^{−j−1}) \\ & = jT (1 − T)^{j−2} − (j − 1)(1 − T)^{−j−1}. \end{aligned}

It follows by induction that

(z \frac{d}{dz} )^{k}T (z) = T (z)g_{k}(T (z)),  (7.6)

where g_{0}(t) = 1 and, for k ≥ 1, g_{k}(t) is a polynomial in (1 − t)^{−1} of degree 2k − 1 with leading coefficient (2k − 3)!! = (2k − 2)!/2^{k−1}(k − 1)! . For future use we record the first cases:

\begin{aligned}g_{0}(t) & = 1, \\ g_{1}(t) & = (1 − t)^{−1}, \\ g_{2}(t) & = (1 − t)^{−3}, \\ g_{3}(t) & = 3(1 − t)^{−5} − 2(1 − t)^{−4}, \\ g_{4}(t) & = 15(1 − t)^{−7} − 20(1 − t)^{−6} + 6(1 − t)^{−5}. \end{aligned}  (7.7)

Consequently, (7.5) shows that we now have, instead of (3.10),

Ŵ_{k}(z) = \frac{T (z)}{z}f̂_{k}(T (z)),

where f̂_{k}(t) = \frac{1}{k!}g_{2k}(t) is a polynomial in (1 − t)^{−1}; if k ≥ 1, then f̂_{k} has degree 4k − 1 and leading coefficient

ω̂_{k} = \frac{(4k − 3)!!}{k!} = \frac{(4k − 2)!}{2^{2k−1}k! (2k − 1)!}.

In particular, ω̂_{1} = 1, ω̂_{2} = 15/2 and, more precisely,

\begin{aligned}f̂_{1}(t) & = g_{2}(t) = (1 − t)^{−3}, \\ f̂_{2}(t) & = \frac{1}{2}g_{4}(t) = \frac{15}{2}(1 − t)^{−7} − 10(1 − t)^{−6} + 3(1 − t)^{−5}. \end{aligned}  (7.8)

Defining f̂(w, t) := ∑_{0}^{∞} w^{k}f̂_{k}(t), the arguments of Section 3 now yield (3.15) with F (1 + w, z) and f(w, t) replaced by F̂(e^{w}, z) and f̂(w, t), and then (3.16) with 𝔼 \binom{D_{mn}}{k} and f_{k_{i}} replaced by \frac{1}{k!} 𝔼(Û_{mn})^{k} and f̂_{k_{i}}.

We pause to observe that (3.17) now yields explicit expressions for the moments of Û_{mn}. In particular, for k = 1 and 2 we obtain, using (7.8),

𝔼 Û_{mn} = m^{1−n}n! [t^{n}]e^{mt}(1 − t)f̂_{1}(t) = m^{1−n}n! [t^{n}]e^{mt}(1 − t)^{−2} = mQ_{1}(m, n)

and

\begin{aligned}𝔼 Û_{mn}^{2} & = m^{1−n}n! [t^{n}]e^{mt}(1 − t)(2f̂_{2}(t) + (m − n − 1)f̂_{1}(t)^{2}) \\ & = 15mQ_{5}(m, n) + m(m − n − 21)Q_{4}(m, n) + 6mQ_{3}(m, n). \end{aligned}

Returning to U_{mn} by (7.1), we obtain the following exact results; the expectation was found already by Knuth [14], [15, Theorem 6.4.K].

Theorem 7.3. If 0 ≤ n < m, then 𝔼 U_{mn} = \frac{1}{2}Q_{1}(m, n) + \frac{1}{2} and

Var U_{mn} = \frac{1}{4m^{2}} Var Û_{mn}

= \frac{1}{4m}(15Q_{5}(m, n) + (m − n − 21)Q_{4}(m, n) + 6Q_{3}(m, n) − mQ_{1}(m, n)^{2}).

□

For asymptotics when (m − n)/\sqrt{m} → a ≥ 0, we use Lemma 3.1 and obtain in analogy with (3.21)

n^{−2k} 𝔼 Û_{mn}^{k} → ψ̂_{k}(a),  k ≥ 1,  (7.9)

where

ψ̂_{k}(a) := k! ∑_{j=1}^{k}( ∑_{\begin{matrix}k_{1},...,k_{j}≥1 \\ ∑ k_{i}=k \end{matrix}} ∏_{i=1}^{j} ω̂_{k_{i}})\frac{a^{j−1}}{j!} q_{4k−j−2}(a).  (7.10)

Since 0 ≤ m^{−2}Û_{mn} ≤ 1, the moment convergence (7.9) implies convergence in distribution m^{−2}Û_{mn} →^{d} V_{a}, for some V_{a} with 0 ≤ V_{a} ≤ 1. This shows Theorem 1.6(iii) with the following characterization of the limit, as well as Theorem 1.7(iii).

Theorem 7.4. The limit random variables V_{a} have the moments 𝔼 V_{a}^{k} = ψ̂_{k}(a), k ≥ 1, with ψ̂_{k} defined in (7.10). In particular,

𝔼 V_{a} = ω̂_{1}q_{1}(a) = q_{1}(a),
𝔼 V_{a}^{2} = 2ω̂_{2}q_{5}(a) + ω̂_{1}^{2}aq_{4}(a) = 15q_{5}(a) + aq_{4}(a).

Moreover, 0 ≤ V_{a} ≤ 1, and thus the distribution of V_{a} is determined by the moments ψ̂_{k}(a). □

Again, the moments can be expressed in terms of the normal distribution function Φ, but we leave the details to the reader.

The normal case. We obtain immediately the following analogue and consequence of Lemma 4.1.

Lemma 7.5. Suppose 0 ≤ n < m and let N = m − n. Let 0 < λ ≤ e^{−1} and let X_{1}, …, X_{N} be independent random variables with the common distribution (4.1). Then the distribution of Û_{mn} equals the conditional distribution of ∑_{j=1}^{N} X_{j}^{2} given ∑_{j=1}^{N} X_{j} = m. □

In the cases n/m → a ∈ (0, 1) and n/m → 1, m − n ≫ m^{1/2}, we apply Lemma 4.3 as before, still with X = X_{λ} but now taking Y = Ŷ := X^{2}. The verification of the conditions is essentially as before; in the case n/m → 1, and thus μ = m/N → ∞, we use that, by (4.13), (4.14) and (4.15),

𝔼 Ŷ = 𝔼 X^{2} ∼ μ^{3},
σ2 ; Ŷ ∼ 𝔼 Ŷ^{2} = 𝔼 X^{4} ∼ 15μ^{7},
Cov(X, Ŷ) ∼ 𝔼 XŶ = 𝔼 X^{3} ∼ 3μ^{5},
τ^{2} ∼ 15μ^{7} − (3μ^{5})^{2}/μ^{3} = 6μ^{7},

and for any r ≥ 3

𝔼 Ŷ^{r}/σr ; Ŷ = O(μ^{4r−1}/μ^{7r/2}) = O(μ^{r/2−1}) = o(N^{r/2−1}).

This yields Theorem 1.6 in these cases.

In the case n/m → 0, n ≫ m^{1/2}, we cannot use Lemma 4.3 as stated with Y = X^{2}, since then ρ → 1. Instead we take Y = Ŷ′ := (X − 1)(X − 2) = X^{2} − 3X + 2, which again vanishes for X = 1 or 2 yielding ρ → 0; the conditions of Lemma 4.3 are easily verified. Note that if ∑_{1}^{j} X_{j} = m, then ∑_{1}^{N} Y_{j} = ∑_{1}^{N} X_{j}^{2}−3m+2N, and thus this Y yields results for Û_{mn}−3m+2N = Û_{mn} − m − 2n, which is just as good.

For the moment estimates in Theorem 1.7(ii), we obtain from Lemma 4.3 in the case n/m → 1, by the estimates above, 𝔼 Û_{mn} ∼ Nμ^{3} and Var Û_{mn} ∼ 6Nμ^{7}, which by (7.1) imply the corresponding estimates for U_{mn} in Theorem 1.7.

To treat also the other cases, we note that by (4.1) and (7.6), for any λ ∈ (0, 1),

𝔼 X^{k} = \frac{1}{T (λ)} ∑_{ℓ=1}^{∞} \frac{ℓ^{ℓ−1+k}}{ℓ!} λ^{ℓ} = \frac{1}{T (λ)}(λ\frac{d}{dλ})^{k}T (λ) = g_{k}(T (λ));  (7.11)

in particular 𝔼 X = g_{1}(T (λ)) = (1 − T (λ))^{−1}, and substituting μ = 𝔼 X = m/N for (1 − T (λ))^{−1} in (7.11), we obtain 𝔼 X^{k} as a polynomial in μ. By (7.7), we have explicitly

𝔼 Ŷ = 𝔼 X^{2} = g_{2}(T (λ)) = (1 − T (λ))^{−3} = μ^{3},
𝔼 Ŷ^{2} = 𝔼 X^{4} = g_{4}(T (λ)) = 15μ^{7} − 20μ^{6} + 6μ^{5},
𝔼 XŶ = 𝔼 X^{3} = g_{3}(T (λ)) = 3μ^{5} − 2μ^{4},

and thus

σ_{X}^{2} = 𝔼 X^{2} − μ^{2} = μ^{3} − μ^{2},
σ2 ; Ŷ = 𝔼 Ŷ^{2} − (𝔼 Ŷ)^{2} = 15μ^{7} − 21μ^{6} + 6μ^{5},
Cov(X, Ŷ) = 𝔼 XŶ − 𝔼 X 𝔼 Ŷ = 3μ^{5} − 3μ^{4},
τ^{2} = σ2 ; Ŷ − (Cov(X, Ŷ))^{2}/σ_{X}^{2} = 6μ^{7} − 12μ^{6} + 6μ^{5}.  (7.12)

Consequently, for α → a > 0 and m − n ≫ m^{1/2}, Lemma 4.3 yields

𝔼 Û_{mn} ∼ N 𝔼 Ŷ = Nμ^{3} = \frac{m^{3}}{(m − n)^{2}} ,

(as is more easily obtained directly from the exact formula mQ_{1}(m, n)) and

Var Û_{mn} ∼ Nτ^{2} = 6N(μ − 1)^{2}μ^{5} = 6N(\frac{n}{N} )^{2}(\frac{m}{N})^{5} = 6\frac{n^{2}m^{5}}{(m − n)^{6}} , (7.13)

which yields the corresponding claims in Theorem 1.7 by (7.1).

In the case n/m → 0, n ≫ m^{1/2}, with Y = (X − 1)(X − 2) = X^{2} − 3X + 2, we still have (7.12), cf. Remark 4.4, and thus (7.13).

Poisson limits. Let M_{ℓ} be the number of blocks of length ℓ. It is easily seen that if X_{j} + X_{j+1} + X_{j+2} ≤ 2 for all j, then all blocks have lengths at most 3 (i.e. they have at most 2 occupied cells), so M_{ℓ} = 0 for ℓ ≥ 4; the constraints ∑ M_{ℓ} = m − n and ∑ ℓM_{ℓ} = m then yield M_{1} = m − 2n + M_{3} and M_{2} = n − 2M_{3}, and thus, by (7.1),

mU_{mn} = M_{1} + 3M_{2} + 6M_{3} = m + n + M_{3}.

Moreover, in this case, M_{3} equals the number V of pairs of items that make their first try in the same cell or in adjacent ones, i.e. V equals the number of pairs (i, j), i < j, such that |h_{i} − h_{j}| ≤ 1 (mod m), cf. Remark 5.2.

Assume now that n/\sqrt{m} → a ≥ 0. Arguing as in (5.1) we then find

ℙ(mU_{mn} − m − n ≠ V) ≤ m ℙ(X_{1} + X_{2} + X_{3} ≥ 3) = O(\frac{n^{3}}{m^{2}} ) → 0.

Furthermore, it is easy to check by the method of moments or by Stein’s method that V →^{d} Po(3a^{2}/2) (this can be regarded as a generalized birthday problem), and Theorem 1.6(i) follows. Moment convergence can be verified as in Section 5.

Asymptotics of V_{a}. The same proof as for Theorem 6.1 now yields the corresponding result for V_{a}.

Theorem 7.6. As a → ∞, we have 𝔼 V_{a} ∼ a^{−2}, Var V_{a} ∼ 6a^{−6} and

\frac{V_{a} − 𝔼 V_{a}}{(Var V_{a})^{1/2}} →^{d} N(0, 1)  (7.14)

with convergence of all moments. □

More refined moment asymtotics follow from Theorem 7.4 and (6.5); for example 𝔼 V_{a} = a^{−2} − 3a^{−4} + O(a^{−6}).

8. Joint limits

The methods in this paper easily yield joint convergence of D_{mn} and U_{mn} (after appropriate normalizations) in all cases. In the normal case, this leads to the following result. (We leave the other cases to the reader.)

Theorem 8.1. If n ≫ \sqrt{m} and m − n ≫ \sqrt{m}, then D_{mn} and U_{mn} are jointly asymptotically normal. Moreover, if α := n/m, then their covariance and correlation have the asymptotics

Cov(D_{mn}, U_{mn}) ∼ \frac{α^{2}}{2(1 − α)^{5}} = \frac{n^{2}m^{3}}{2(m − n)^{5}} ,  (8.1)
Corr(D_{mn}, U_{mn}) ∼ (3 − 3α + 2α^{2} − \frac{1}{2}α^{3})^{−1/2}.  (8.2)

In other words, if further n/m → a ∈ [0, 1], then (D_{mn} −𝔼 D_{mn})/(Var D_{mn})^{1/2} and (U_{mn} − 𝔼 U_{mn})/(Var U_{mn})^{1/2} converge jointly in distribution to a pair of normal variables with means 0, variances 1 and covariance

ρ = (3 − 3a + 2a^{2} − \frac{1}{2}a^{3})^{−1/2}.  (8.3)

Proof. Joint normal convergence follows easily from Lemma 4.3 by the Cramér– Wold device, see [12, Corollary 2.2].

For the asymptotic covariance, this yields, with Y as in Section 4,

Cov(D_{mn}, Û_{mn}) ∼ N(Cov(Y, X^{2}) − Cov(Y, X) Cov(X^{2}, X)/ Var X),

which yields (8.1) by straightforward calculations using (4.23) and (4.32) (most terms are already evaluated in Sections 4 and 7); we omit the details. Finally, (8.2) follows from (8.1) and the asymptotic variances given in Theorems 1.4 and 1.7. □

Remark 8.2. It is easily verified that the limiting correlation (or covariance) in (8.3) is an increasing function of a, which is \sqrt{1/3} for a = 0 and \sqrt{2/3} for a = 1.

References

[1] D.J. Aldous & J. Pitman, The standard additive coalescent. Ann. Probab. 26 (1998), 1703–1726.

[2] A.D. Barbour, L. Holst & S. Janson, Poisson Approximation. Oxford University Press, Oxford, 1992.

[3] J. Bertoin, A fragmentation process connected to Brownian motion. Probab. Th. Rel. Fields 117 (2000), 289–301.

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

[5] P. Chassaing & S. Janson, A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0. Ann. Probab., to appear.

[6] P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. Rand. Struct. Alg., to appear.

[7] P. Chassaing & J.F. Marckert, Parking functions, empirical processes and the width of rooted labelled trees. Electronic J. Combin. 8 (2001), #R14.

[8] A. Dvoretzky, J. Kiefer & J. Wolfowitz, Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist. 27 (1956), 642–669.

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

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

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

[12] S. Janson, Moment convergence in conditional limit theorems. J. Appl. Probab. 38 (2001), 421–437.

[13] S. Janson, D.E. Knuth, T. Łuczak & B. Pittel, The birth of the giant component. Rand. Struct. Alg. 4 (1993), 233–358.

[14] D.E. Knuth, Notes on “open” addressing. Unpublished notes, 1963. Available at

    http://www.wits.ac.za/helmut/first.ps

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

[16] D.E. Knuth, Linear probing and graphs. Algorithmica 22 (1998), 561–568.

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

[18] A.G. Konheim & B. Weiss, An occupancy discipline and applications. SIAM J. Appl. Math. 14 (1966), 1266–1274.

[19] G. Louchard, Kac’s formula, Lévy’s local time and Brownian excursion. J. Appl. Probab. 21 (1984), 479–499.

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

[21] Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest. Teor. Verojatnost. i Primenen. 22 (1977), no. 3, 523–533 (Russian). English transl.: Th. Probab. Appl. 22 (1977), no. 3, 509–520.

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

[23] J. Pitman, Coalescent random forests. J. Combin. Theory A 85 (1999), 165–193.

[24] J. Pitman & M. Yor, Arcsine laws and interval partitions derived from a stable subordinator. Proc. London Math. Soc. (3) 65 (1992), 326–356.

[25] D. Revuz & M. Yor, Continuous Martingales and Brownian Motion. 3^{rd} edition, Springer, Berlin, 1999.

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

[27] L. Takács, A Bernoulli excursion and its various applications. Adv. in Appl. Probab. 23 (1991), 557–585.

[28] W. Vervaat, A relation between Brownian bridge and Brownian excursion. Ann. Probab. 7 (1979), 143–149.

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

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

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