Phase transition for parking blocks, Brownian excursion and coalescence.
In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n > m), and places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively finds an empty place. Pittel [42] proves that when /m goes to some positive limit  > 1, the size B1m,1 of the largest block of consecutive cars satisfies 2( converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent.
Introduction
We consider hashing with linear probing for a hashing table with n places f1; 2; :::; ng,
items places. Hashing with
linear probing is a fundamental object in analysis of algorithms: its study goes back
to the 1960's (Knuth [17], or Konheim & Weiss [19]) and is still active (Pittel [27],
Knuth [18], or Flajolet et al. [11]). For a non computer science-minded reader,
we shall use, all along the paper, the metaphore of m(n) cars parking on n places,
leaving E(n) places empty: each car c i chooses a place p i at random, and if p i
is occupied, c i tries successively nds an empty place. We
use the convention that place place 1. Under the name of parking
function, hashing with linear probing has been and is still studied by combinatorists
(Schutzenberger [34], Riordan [30], Foata & Riordan [12], Francon [15] or Stanley
1 Institut Elie Cartan, INRIA, CNRS and Universite Henri Poincare,
BP 239, 54 506 Vandoeuvre Cedex, France.
chassain@iecn.u-nancy.fr
Universite Libre de Bruxelles, Departement d'Informatique,
Campus Plaine, CP 212, Bvd du Triomphe, 1050 Bruxelles, Belgium.
louchard@ulb.ac.be
[35, 36]). There is a nice development on the connections between parking functions
and many other combinatorial objects in Section 4 of [11] (see also [35]). In this
paper, and also in [20], we use mainly a { maybe less exploited { connection between
parking functions and empirical processes of mathematical statistics (see also the
recent paper [25]) .
Pittel [27] proves that when E(n)=n goes to some positive limit , the size of the
largest block of consecutive cars B (1)
converges weakly to an extreme-value distribution. This paper is
essentially concerned with what we would call the "emergence of a giant block" (see
[5, 7] for an historic of the emergence of the giant component of a random graph,
and also [2, 14, 16]):
Theorem 1.1 For n and m(n) going jointly to+1, we have:
in which B (1)
belongs almost surely to ]0; 1[.
So the threshold phenomenon is less pronounced than in the random graph pro-
cess. However, the behaviour during the transition is reminiscent of the random
graph process: while Aldous [2] observed a limiting behaviour of connected components
for the random graph process related to the multiplicative coalescent, here, it
rather seems that the additive coalescent (cf. Aldous & Pitman [4]) comes into play.
Theorem 1.3 describes the random variable B 1 ().
k1 be the decreasing sequence of sizes of blocks, ended by an
innite sequence of 0's. Dene analogously R n;n (R (k)
k1 as the sequence
of sizes of blocks when the blocks are sorted by increasing date of birth (in increasing
order of rst arrival of a car: for instance, on Figure 1, for
Theorem 1.2 If lim E(n)
The law of X() is characterized by the fact that (X 1 ()+X 2 ()+ ::: +X k ()) k1
is distributed as the sequence
k1
in which the N k are standard Gaussian and independent.

Figure

1: parking schemes for places.
One recognizes the marginal law of the -valued fragmentation process derived
from the continuum random tree, introduced by Aldous & Pitman in their study of
the standard additive coalescent [4]. In order to describe the limit of Bn
n , we dene
a family of operators  on the space E of continuous nonnegative functions f(x),
y
Let e be a normalized Brownian excursion, that is a 3-Bessel bridge (see [29] Chap.
XI and XII for background). Let k1 be the sequence of widths
of excursions of  e, sorted in decreasing order. By excursion of a function f , we
understand the restriction of the function f to an interval [a; b] in which f does
not have any change of sign, and more precisely, such that
b[. The Brownian motion is known to have innitely many
excursions in the neighborhood of any of its zeros. This property holds true for  e,
with the exception of 0, that is a.s. an isolated point in the set of zeroes of  e.
Nevertheless  e has, almost surely, innitely many excursions in the interval [0; 1]
(it can be seen as a consequence of Theorem 4.1, or more generally, of Cameron-
Martin-Girsanov formula). We have:
Theorem 1.3 If lim E(n) p
Incidentally, the length L() of the excursion of  e beginning at 0 is studied by
Bertoin [6] in a recent paper: he gives the transition kernel of the Markov process

Figure

2: parking schemes for places.
Theorem 1.1 is the width of the largest excursion of  e. The
fact that B 1 () belongs almost surely to ]0; 1[, and has a density, follows from the
next Theorem about the Brownian excursion, that was in turn suggested by the
more combinatorial in nature Theorem 1.2:
Theorem 1.4 The law of the size-biased permutation Y () of B() satises
law
k1
in which the N k are standard Gaussian and independent.
The size-biased permutation of a random probability distribution such as B() is
constructed as follows. Consider a sequence of independent, positive, integer-valued
random variables distributed according to B():
With probability 1 each positive integer appears at least once in the sequence (I k ) k1 .
Erase each repetition after the rst occurence of a given integer in the sequence:
remains a random permutation ((k)) k1 of the positive integers. Set:
Size-biased permutations of random discrete probabilities have been studied by
Aldous [3] and Pitman, [23], [24]. The most celebrated example is the size-biased
permutation of the sequence of limit sizes of cycles of a random permutation. While
the limit distribution of the sizes of the largest, second largest . cycle have a complicated
expression (see Dickman [9], Shepp & Lloyd [32]), the size-biased permutation
k1
in which the U k are uniform on [0; 1] and independent. See also the beautiful developments
about Poisson-Dirichlet distributions, in [3], [21], [22], [24] and [26].
Actually, Theorem 1.4 gives a implicit description of the law of B(), for instance
it proves that almost surely each Y k () is positive, and thus a.s.
1. There exist even formulas, due to Perman [21], giving the joint distribution
of the k th largest weights of a random discrete probability in term of the joint
densities of its size-biased permutation, in the special case where the random discrete
probability comes from the order statistics for jumps of normalised subordinators
these formulas do not seem to apply here. Flajolet & Salvy [13] have a direct
approach, to the computation of the density of B 1 (), by methods based on Cauchy
coe-cient integrals to which the saddle point method is applied: the density is a
variant of the Dickman function. Note that Bertoin [6] studies the stochastic process
as a tool for the study of the excursions of the re
ected Brownian
motion with a varying drift. He establishes interesting properties of , for instance
Markov property.
Finally, set:
We have
Theorem is the stable subordinator with exponent 1=2,
meaning that, for any k and any k-tuple of positive numbers
Thus, as a stochastic process, S has the same law as the process of hitting times
of the Brownian motion. With Theorem 1.4, this is still another feature that Y ()
shares with the stochastic additive coalescent. Theorems 1.5 and 1.4 suggest that
the process (Y ()) 0 has the same law as the -valued fragmentation process,
providing an alternative construction of the stochastic additive coalescent. A formal
proof is out of the scope of this paper (however see the concluding remarks).
Theorem 1.5 has interest in itself, but it is is relevant to the study of parking
schemes only if we are able to prove weak convergence of the process "size of the
block containing car c 1 " to the process (Y 1 ()) 0 . The next Theorem lls incompletely
this gap. Let (R (1)
the sequence of successive widths R (1)
n;k of
the block containing car c 1 when cars are parked on n places, and k
places are still empty. If k  n, set R (1)
R (1)
n;d
ne
We are able to build on the same space a Brownian excursion e and a sequence of
parking schemes of n cars on n places, in such a way that:
Theorem 1.6
Pr
We would need an almost sure convergence for the Skorohod topology, in order
to ll completely the gap. The fact that S() is a pure jump process makes sense in
the parking scheme context, since the block of car c 1 is known to increase by O(n)
while only O(
n) cars arrived: it can only be explained by coalescence with other
blocks of size O(n), that is, by instantaneous jumps.
The paper is organized as follows. Section 2 analyses the block containing a
given car or a given site, leading to a proof of Theorem 1.1 (i),(ii). Section 3
provides a combinatorial proof of Theorem 1.2. Section 4 uses a decomposition of
sample paths of  e (cf. Theorem 4.1) which, we believe, has interest in itself, to
provide a simple proof of Theorems 1.4 and 1.5. Theorem 4.1 is proven at Section
5, with the help of the combinatorial identity (2.2). Proofs of Theorem 1.3 and 1.1
(iii) are also given in Section 5, where we exhibit a close coupling between empirical
processes of mathematical statistics and the prole associated with a parking scheme
(see previous gures, and for a denition of the prole see Section 5). Section 6 is
devoted to the proof of Theorem 1.6 . Section 7 concludes the paper.
2 On the block containing a given car, or a given site
In this Section,we give the proof of Theorem 1.1((i) and (ii)). In order to do that,
we give a partial proof of Theorem 1.2, concerning the size R (1)
n;E(n) of the block
containing car c 1 : we have
Theorem 2.1 If n 1=2 E(n) !  > 0,
R (1)
law
in which N is standard Gaussian.
Proof : The probability that, when parking m cars on n places, the block containing
car c 1 has k elements, denoted Pr(R (1)
Clearly, the number of parking schemes for m cars on n places is n m . One has to
choose the set of k 1 cars that belong to the same block as c 1 , giving the factor
the place where this block begins, giving the factor n, the way these k cars
are allocated on these k places, giving the factor nally one has to
park the m k remaining cars on the n k 2 remaining places, leaving one empty
place at the beginning and at the end of the block containing car c 1 , and this gives
the factor (n Flajolet et al. (1998) or Knuth (1998)
for justication of the third and of the last factor). Note that these computations
would hold for any given car instead of c 1 .
At the end of this Section, we shall prove that:
Lemma 2.2 For any 0 <  < 1=2 there exists a constant C() such that,
whenever , simultaneously,   k
, we have:
'(n; m; k)n f
Proof of Theorem 2.1. Owing to
Lemma 2.2 yields, for 0 < a < b < 1, that
Pr(an  R (1)
a
Doing
Z +1e y=2 dy
Thus, is a density of probability, and R (1)
n;E(n) =n has for limit
law (x)dx. Furthermore, the previous change of variable entails that if some random
variable W has the density (x), then  2 W=(1 W ) has a
1=2;1=2 law, that
is,  2 W=(1 W ) has the same law as the square of a standard Gaussian random
variable. }
As a consequence of Theorem 2.1, we prove now (i) and (ii) of Theorem 1.1.
Considering (ii), provided that E(n)
n  R (1)
n;d ne :
As
n), for any  > 0 and for n large
n;d
ne < nx):
Due to Theorem 2.1, we obtain that for any  > 0
lim sup
Clearly, for x < 1,
Pr
0:
As regards (i), let L n be the length of the block of cars containing
place 1 (resp. the length of the largest block) when car c bn  p nc arrives. We
have, for k > 0,
Pr(R (1)
and place 1 is empty with probability:
ne
We have also
and thus
Assuming p
we obtain that for any ,
when n is large enough, not depending on !, so that:
lim sup
nally yielding (i). }
We prove (iii) of Theorem 1.1 in Section 5, together with Theorem 1.3.
Proof of Lemma 2.2. Setting, for brevity, E(n), we can
in
We obtain
n) +O(
and nally:
exp
3 Proof of Theorem 1.2
We rst provide a useful identity leading to the proof of Theorem 1.2. Set
We have
Theorem 3.1
Y
Proof : The choice of the elements in each of the blocks can be done in
Y
ways, and they can be arranged inside each of these blocks in
Y
ways.
It is more convenient to argue in terms of conned parking schemes, as in Knuth
(1998) or in Flajolet et al. (1998): that is, we can assume the last place to be empty,
since rotations does not change the sizes of blocks. The total number of conned
parking schemes is n m 1 (n m). We obtain a conned parking scheme with sizes k 1 ,
. , for the i rst blocks, respectively, by inserting these i blocks successively,
with an empty place attached to the right of them, insertion taking place at the
front of the conned parking scheme for the remaining cars, or just after one of
the empty places of the conned parking scheme for the remaining cars. There are
possible insertions
for the rst possible insertions for the second block, and so on
. Finally, the probability p(k) on the left hand of Theorem 3.1 is given by
Y
It is not hard to check that this last expression is the same as the right hand of
Theorem 3.1. }
Proof of Theorem 1.2. Set:
Using the same line of proof as in Theorem 2.1, the approximations of Lemma 2.2
for '(n; m; k) and Theorem 3.1 yield the joint density of (X 1
Y
f
Equivalently, the conditional law of X j has the
f
in
Equivalently again, X j is distributed as
in which N j is standard Gaussian and independent of (X 1
We have:
and
so a straightforward induction gives Theorem 1.2. }
4 On the excursions of  e
In this Section, we give the proofs of our last two main theorems, Theorem 1.4 and
Theorem 1.5.
4.1 Decomposition of paths of  e
These results are simple consequences of a property of decomposition of sample paths
of  e that, we believe, has interest in itself: let U 1 be a random variable uniformly
distributed on [0; 1] and independent of e and let D (resp. F ) denote the last zero
of  e before U 1 (resp. the rst zero of  e after U 1 ), so that Y 1
We have:
Theorem 4.1 We have:
has the same distribution as N 2
, in which N is standard Gaussian ;
(ii) f is a normalized Brownian excursion, independent of Y 1
(iii) Let W be uniformly distributed on [0; 1] and independent of e. Given (f; V )
distributed as T
The introduction of W is a rather unpleasant feature. Actually, the study of h n
suggests that, if '(t) denote the local time of r at 0, on the interval [0; t], point (iii)
should be replaced by
reaches its unique minimum at a point
distributed as T
If we could prove this last point, a second problem would arise: we do not know
uniformly distributed on [0; 1] and independent of (f; Y 1 ()).
However, fV + Wg has surely these properties. On the other hand, for the purpose
of proving Theorem 1.2, the introduction of W is harmless, as the law of the
length of the excursion that straddles U 1 is the same for T
Theorem 4.1 is proven at Subsection 5.4. The starting point of the proof is the
combinatorial identity:
4.2 Proof of Theorem 1.4
It should not be di-cult, following the line of proof of Theorem 4.1, subsection
5.4, to exhibit a
on which there is almost sure convergence ofn (R (1)
for each k, yielding Theorem 1.4.
We prefer to borrow the nice idea of Section 6.4 in Pitman & Yor [26], that uses
the decomposition of sample paths of a Brownian bridge to prove distributional
properties of a sample from a Poisson-Dirichlet distribution.
We introduce, as in [26], a sequence
U being independent of e : with probability 1, U k falls inside some excursion (D
of  e ; if this excursion has width B j (), we dene
I
yielding a size-biased permutation of B(), as explained in the introduction. Set:
The random variables U T (k) are independent and uniformly distributed on [0; D] [
[F; 1], and there exist a unique number V k 2]0; 1[ such that
k1 is a sequence of independent random variables, uniform on [0; 1], and
independent of (e; U 1 ).
In view of Theorem 4.1, this leads to
Lemma 4.2 Given that Y 1 the sequence Y distributed
as (1 x)Y (
Actually, but among the (U i ) i2 , only the U T (k) are useful
to determine Y (). Actually Y () is a size-biased permutation of the sequence of
widths of excursions of r: more precisely it is the size-biased permutation built with
the help of the sequence V . As a consequence, it is also the size-biased permutation
of the sequence of widths of excursions of q, built with the help of the sequence
~
k1 . This ends the proof of Lemma 4.2, as ~
V is a sequence of
independent and uniform random variables, independent of (r; W ).
Using Lemma 4.2, we prove, by induction on k, the two following properties
has the distribution asserted in Theorem 1.4 ;
distributed as (1 s k )Y (
The conditional law of  is the conditional
law of (1 s k )Y (
Thus, due to
Lemma 4.2, it has the same law as
in
giving point(2) for k + 1. Set:
Due to point(2) for k, and to point (i) of Theorem 4.1, given that (Y j
or equivalently
giving
4.3 Proof of Theorem 1.5
There exists a similar result in a seemingly dierent setting, that is, for the standard
additive coalescent (cf. [4]).
Given that (D; F distributed as a+xU in which U is uniform
on ]0; 1[. On the other hand, it is easy to see that, for t 2 [0; 1],
x
Thus given (D; F distributed as
Since this last distribution does not depend on a, it is also the conditional distribution
of (Y Equivalently, by change of variables,
the conditional distribution of (S( y, is the same as
the unconditional distribution of
1+y
This last statement yields (1.1), by induction on k: assuming that property at
we see that, given that S( 1 y,
Owing to Theorem 4.1,
5 Proof of Theorems 1.3 and 4.1
denote the number of cars that tried to park on place k, successfully or not.
The proof of Theorem 1.3 will be in three steps: in Subsection 5.2, using Theorems
of Doob and Vervaat we shall prove that
Theorem 5.1 If lim n
weakly
in which h  is dened, with the help of a uniform random variable U independent
of e, by:
As a rst result, we shall establish in Subsection 5.1 a close coupling between
H k and the empirical processes of mathematical statistics. Theorem 5.1 is a generalization
of a similar Theorem established in Marckert & Chassaing, for the case
In Subsection 5.3 we shall prove the convergence of the widths
of excursions of h n to that of  e, using essentially results of Section 2.3 in Aldous
(1997).

Figure

3: Prole.
As only if place k is empty, the width of an excursion of h n turns
out to be the length of some block of cars, normalized by 1=n. We shall call h n the
prole of the parking scheme.
5.1 Connection between parking and empirical processes
Propositions 5.3, 5.4 and 5.5 at the end of this subsection, are the key points for the
convergence of blocks' sizes.
The model of cars parking on places can be described by a sequence (U k ) k1 of
independent uniform random variables, car c k being assumed to park (or to try to
on place p i if U k falls in the interval
. Let Y k denote the number of
cars that tried rst to park on place k. We have:
since either place k is occupied by car c i and, among the H k cars that tried place
k, only car c i won't visit place k place
k is empty and H We understand this equation, when
This induction alone does not give the H k 's, since we do not have any starting
value. We have thus to nd an additional relation, and this is the purpose of
Proposition 5.2, that gives a rst connection between hashing (or parking) and
the empirical process. Let V be dened by
ng
in which m is the empirical process of mathematical statistics (see Shorack &
Wellner [33], Csorgo & Revesz [8] or Pollard [28] for background). We just recall that,
given a sample (U almost all interesting statistics
are functionals of the empirical distribution
and that the empirical process m is dened by:
The process m gives a measure of the accuracy of the approximation of the true
distribution function t by the empirical distribution function Fm (t), and was, as
such, extensively studied in mathematical statistics.
Proposition 5.2 In the hashing table, place V (n) is empty.
Proof of Proposition 5.2. Let:
Since we have:
clearly:
Thus
is nonnegative, in which we understand that Y
. (while S is not a convention).
Obviously some place k is empty if and only if H To end the proof,
we shall assume that H V (n) is positive and we shall deduce, by induction on k, that
so that no place is empty, in contradiction
with m < n. Due to (5.4) for thus, due to (5.3):
so that H V (n) 1  2, and that is the starting point of our induction. Now we assume
that for any i  k, H V (n) i  2. From (5.3) we obtain that for any i  k,
so that due to (5.4),
Now that we know the true value of H k for some point k, namely (n), we can
use (5.3) to compute each value of H k . Sizes of blocks of cars will follow, as blocks of
cars are in correspondence with blocks of indices k such that H k > 0 (blocks that we
call also later excursions of H k ). We nd the following explicit connection between
empirical processes and H k , in the same spirit as in Marckert & Chassaing [20].
Proposition 5.3 For any k 2 f1; 2; ::: ; n 1g,
that can be rewritten in terms of the empirical process:
Proposition 5.4 For any k 2 fV (n)
Proof of Proposition 5.3. Set:
places in the set fV (n);
and:
Using (5.3) we obtain:
To obtain Proposition 5.3, we only have to prove that R
We already have
There exist a last index j < k such that Z As a consequence,
is the last empty place before including
Now R acording to place V (n) being empty or not. But due
to (5.3) and the fact that V (n) is the last empty place before place
we have H V
Two cases arise: either H V In the rst case we have
simultaneously R In
the second case H V (n)+k  1 entails both R and also W j+1 (=
This ends the tedious proof by induction, but
these facts will prove useful as Z k will be easier to handle than R k , when dealing
with uniform convergence in the next subsection. }
We notice, for further use, that we just proved that
Proposition 5.5 A record of W k or of Z k means that is an empty
place.
5.2 Convergence to  e
Let us recall that Donsker (1952), following an idea of Doob, proved that:
Theorem 5.6 Let be a Brownian bridge. We have:
weakly
We shall also need the next Theorem to prove Theorem 5.1:
Theorem 5.7 (Verwaat, 1979 [37]) Let V be the almost surely unique point
such that b(V dened by
normalized Brownian excursion, independent of V .
Proof of Theorem 5.1. According to the Skorohod representation theorem (cf.
Rogers & Williams, (1994) II.86.1) we can assume the existence of a
and on this space a sequence  n and a Brownian bridge b, such that, for almost any
converges uniformly on [0; 1] to b(!).
We could
in such a way to build for each m a corresponding
sequence U
independent random vari-
ables, and the corresponding random parking scheme. However this would not really
be needed for the proof, only for the mental picture. Note that such a sequence U (m)
would not necessarily be embedded in U (m+1) .
Each m denes a sequence S m;n
as in the previous
subsection, and denes also the corresponding V (n), as follows:
1kn
Finally, let:
be the corresponding number of cars that tried, successfully or not, place number k,
and set:
z
Assuming lim n
E(n)
Lemma 5.8 For almost any !,
uniformly
Lemma 5.9 For almost any !, V (n; !)=n converges to V (!).
As a consequence, we have
Lemma 5.10 For almost any !,
uniformly
and
z n (t) uniformly
and also:
Lemma 5.11 For almost any !,
uniformly
Taking Theorem 5.1 is a reformulation of Lemma 5.11, since we
e(ft (V (n)=n)g) uniformly
Due to the estimates in the proof of Lemma 5.8, uniform convergence holds also true,
indierently, for continuous and stepwise linear versions of h n , y n , z n or m (bntc=n)
(we shall use this remark in the proof of Theorem 4.1).
Proof of Lemma 5.8. Let M n denote max 0<kn Y k;n , where Y k;n denotes the
number of cars that want to park at place k. We have:
and, as Y k;n is binomially(m; 1=n) distributed:
nE[exp(KY 1;n )] exp( KC log n)
Thus Borel-Cantelli Lemma entails that for a suitable C, with probability 1 the
supremum norm of m (bntc=n) m (t) vanishes as quickly as C log n
Proof of Lemma 5.9. For this proof and the next one, we consider an ! such
that simultaneously m and m (bntc=n) converges uniformly to b, and such that b
reaches its minimum only once (we know that the set of such !'s has measure 1).
We set:
It is then straightforward, >from the continuity property of b, that the rst
minimum of m (bntc=n) (i.e. V (n)=n) converges to the only minimum of b (i.e. V
clearly
Now the minimum of b(t) over the set [0; 1]=[V "; V +"] is b(V )+ for some positive
, and thus, if necessarily jV V (n)=nj < " . }
Proof of Lemma 5.10. Clearly:
Proof of Lemma 5.11.Let
z
According to Proposition 5.3, or to Proposition 5.4, we have:
0st
where
0st
0st
Thus Lemma 5.11 follows from the uniform convergence of z n to z in Lemma 5.10. }
5.3 Proof of Theorem 1.3
The widths of excursions of h n (t) above zero are the sizes of the blocks of cars
of the corresponding parking scheme, normalized by n. Unfortunately, uniform
convergence of h n to h does not entails convergence of sizes of excursions. Using the
line of proof of Aldous (1997, Section 2.3), we shall argue that the excursions of h n
above 0 are also the excursions of z n above its current minimum: now the uniform
convergence of z n to z entails convergence of sizes of excursions of z n above its current
minimum to sizes of excursions of z above its current minimum, provided that z does
never reach its current minimum two times. This last condition is classically satised
for almost each sample path z, so that we have almost sure convergence of sizes of
excursions of z n or equivalently of sizes of blocks. Note that excursions of z above
its current minimum are also excursions of  e above 0.
More precisely, we shall apply to z n and z the following weakened form of Lemma
7, p. 824 of [2]:
Lemma 5.12 Suppose f : [0; +1[ ! R is continuous. Let E be the set of
nonempty intervals I = (l; r) such that:
sl
Suppose that, for intervals I 1 , I 2 2 E with l 1 < l 2 we have
Suppose also that the complement of [ I2E (l; r) has Lebesgue measure 0. Let
uniformly on [0; 1]. Suppose (t n;i , i  1)
satisfy the following:
Write  m(n)g. Then  (n) !  for the vague
topology of measures on [0; 1]  (0; 1].
As we are dealing with point processes, such as  n or , we have:
Proposition 5.13  (n) !  for the vague topology if and only if, for any
y > 0 such that ([0; 1]
(i) for n large enough,  (n) ([0; 1]  [y;
(ii) for any x 2 [0; 1]  [y; 1] such that (fxg) > 0 there is a sequence of points x n ,
0, such that x n ! x.
As an easy consequence, partly due to the fact that second components add up
to 1:
Corollary 5.14 If  (n) !  for the vague topology, then the sequence of second
components of points of  (n) , sorted in decreasing order, converge componentwise
and in ' 1 to the corresponding sequence for .
The Lemmata and Propositions of this subsection are hold to be straightforward
by specialists, as well as the stochastic calculus points in the next proof, so we give
their proofs in the annex. If (f the sequence of > second components
of  (n) (resp. of ) is nothing else but 1
Proof of Theorem 1.3. Lemma 5.12 and Corollary 5.14, applied to
of Subsection 5.2, entails Theorem 1.3. Hypothesis of Lemma 5.12,
concerning a regular sample path of z(t), that is, almost surely, for any l 1 < l 2 ,
setting r), the Lebesgue measure of O c is
0, are well known to hold true, as e is solution of:
du;
(see [29], Chp. XI, the whole Section 3, and notably Ex. 3.11).
For the t n;i 's in Lemma 5.12, we choose the records of z n (t) so, due to Lemma
5.5, the nt n;i 's are the empty places, counted starting at V (n). Then, not depending
on i, we have z
n, and hypothesis (iii) of Lemma 5.12 is
satised by z n . }
This last proof is also a proof of Theorem 1.1 is the width of the
widest excursion of  e.
5.4 Proof of Theorem 4.1
Theorem 4.1 is basically a consequence of the following identity (m  n 2):
which is equivalent to relation (2.2).
Let U be uniformly distributed and independent of the Brownian excursion e.
The decomposition of n m according to the length k of the block containing car c m ,
in the identity 5.7, yields the desintegration of  e according to the value x of Y 1 ()
asserted in Theorem 4.1: the factor gives the distribution of the shape
of the (suitably scaled) excursion ~
f n of h n corresponding to the block that contains
car c 1 . Marckert & Chassaing (1999) proved that if if each of the
conned parking schemes are equiprobable, then
weakly
we shall deduce that the shape f of the excursion of  e that contains U 1 , being the
limiting prole of ~
f n , is independent of its width Y 1 and is distributed
as a normalized Brownian excursion.
If we make a random rotation with angle d(n k 1)W e of the parking scheme of
the m k remaining cars on the n k 1 remaining places, we obtain (n
equiprobable parking schemes, with n m '
leading to the fact that r(fW + :g) is distributed as T
Let us give a formal proof:
Proof of Theorem 4.1. Let C be the space of continuous functions on [0; 1], with
the topology of uniform convergence. The triplet of independent random variables
denes the random variable (X 1 (); f; q) and
its law Q, that is a probability measure on the space [0; 1]  C 2 . The normalized
Brownian excursion e
resp. T
denes the probability measure
(resp.  x ) on C. Theorem 4.1 can be written equivalently:
Z 1f(; x)
Z
Z
for any bounded uniformly continuous function  on the space [0; 1]  C 2 . It is
harmless to assume that
In order to prove Theorem 4.1, we shall exhibit a probability
and, on this space, a sequence of [0;
almost surely, in
to (X 1 (); f; q), for the product
topology of [0;
ne;
(iii) the conditional law,  k , of f n given that X
, does not depend on n and
satises:
weakly
(iv) the conditional law,  n;k , of q n given that X
n;k
weakly
As a consequence of (i):
for any bounded uniformly continuous function . We shall prove now that properties
(ii) to (iv) are su-cient to insure that, for any bounded uniformly continuous
function  satisfying
have
Z 1f(; x)
Z
entailing (5.8). We end the proof with the construction of (X
Let M be the bound for jj . Set:
Z 1f(; x)
Z
Z
a
Z
Z
a
Z
Z
(dnxe=n;
Z
Z
'(n; m;
Z
Z
By dominated convergence, owing to (iii) and (iv), lim n B A. By uniform
continuity of f and , lim Finally lim n C n D due to Lemma
2.
Construction of (X
Assume we are in the setting of subsection 5.2, that is we use the Skorohod
Theorem to obtain on some
space
a sequence m that converges almost surely
uniformly to a Brownian bridge We enlarge this space to
in order to obtain two uniform random variables U 1 and W independent
of of b. We set
ne
for sake of brevity. We shall build our sequence (X
will describe, partly, the parking scheme for m(n) cars on n places.
Let us collect some basic facts concerning empirical processes: m has m positive
jumps with height 1
m , at places that we call (V (m)
Between the jumps
m has a negative slope
m. The random vector
uniformly
distributed on the simplex f0 < x 1 < x 2 < ::: < xm < 1g and a random permutation
of its components would yield a sequence (U (m)
independent uniform random variables on [0; 1], car c k trying to park rst on place
l
Unfortunately  is not provided with the
space
It means that, given m , we
know the number of cars that that will park on each place k, say (Y m;n
is the number of jumps of m taking place in the interval
n ]), but we do not
know which car parks on which place. This is a slight di-culty, since we have in
mind to choose nX n as the place where car c 1 parks, so that (ii) follows at once
from relation (2.2).
In order to circumvent this problem, note that a random permutation  can be
described by a random bijection  from f2; 3; 4; :::; mg to f1; 2; 3; :::; m 1g and a
random uniform integer (1), independent of  : rst we choose (1), then we choose
::; (m)) at random from the m 1 remaining integers, renumbered >from 1
to m 1. We shall take
that is
U (m)
car c 1 parks at place dnU (m)
1 e. We shall leave  undened. In addition to the fact
that (1) and U (m)
are random uniform, we get that, almost surely:
U (m)
Incidentally, the remaining jumps are independent of U (m)
1 and uniformly distributed
on the simplex f0 < x 1 < x 2 < ::: < xm 1 < 1g.
the rst empty place on the left of
dnU (m)
e (resp. the rst empty place on the right), that is, the beginning (resp. the
end) of the block containing car c 1 . Easy considerations on the uniform convergence
of z n to z give that, almost surely,
Recall that R (1)
yielding point (ii) and also a part of point (i):
almost surely,
Let
~
R (n)h n
Uniform convergence of h n to  e, uniform continuity of  e(t) and (5.10) entails
the uniform convergence of ~
f n to f and the uniform convergence of
~
to As regards (iii), relation (5.7) tells us that, given that nX
~
f n is the prole associated to one of the parking schemes
of k cars on k places. Accordingly, its conditional law ~  k converges weakly to
. Similarly, due to the random rotation d(n R (n)
e, given that nX
is the prole associated to one of the (n k 1) m k equiprobable parking schemes
of m k cars on n k 1 places: its conditional law ~
n;k converges weakly to  x
under the hypothesis of (iv).
Unfortunately, ~
n;k (C), so we have a little bit of additional work:
we just replace ~
f n and ~
q n by their corresponding piecewise-linear continuous approx-
imations, f n and q n . Relation (5.6) insures that f n (resp. q n ) converges uniformly
to f (resp. g), yielding point (i). Relation (5.6) insures also that their laws  k (resp.
6 Proof of Theorem 1.6
Once again, we use the setting of subsection 5.2, that is we use the Skorohod Theorem
to obtain on some
space
a sequence  n that converges almost surely uniformly
to a Brownian bridge We enlarge again the probability
space, so that we have a sequence of independent uniform random variables (U k ) k1 ,
both independent and independent of the sequence ( m does contain the
information about the number of cars that tried to park on each of the n places,
but it contains no information about the chronology. We shall use (U k ) 2kn to
recover the chronology, that is, to pick at random, one jump after the other, the
jumps of  give the place of car c 1 , through U (n)
1 dened at relation (5.9),
and (U k ) 2kn will generate a random permutation of the rank of the remaining
order statistics f2; 3; :::; ng. As a consequence, from a given  n and (U k ) 2kn , we
can recover the whole history of the process of parking n cars on n places, without
losing the almost sure uniform convergence of  n to a Brownian bridge, needed for
the convergence of sizes of blocks.
Thus for each n; k we dene a prole h n;k (t) associated with the parking of the
rst cars on the n places, and we use the corresponding notation z n;k (t). The
prole h n;k (t) is given by Proposition 5.4, based on the empirical process  n;k (t)
obtained by erasing the k last random choices of order statistics (places of jumps)
of  n .
More precisely, let ~
uniformly distributed on the simplex
denote the remaining jumps of  n , once U (n)
1 has
been erased. Let  be the random permutation generated from (U k the rank
of U k , once (U k ) 2kn is sorted in increasing order, is (k). We assert that if the
rst try of car c 1 is place dnU (n)
e, and the rst try of car c k (k  2) is place dn ~
e,
the n n parking schemes are equiprobable. The k last random choices ( ~
provide a sample of k independent and uniform random variables, with an associated
empirical process ~
n;k (t). We have:
n;k (t)
The DKW inequality gives
Pr(sup
n;k (t)j  x)  4
thus, using Borel-Cantelli lemma, we obtain easily that, for " > 0,
Pr
sup
sup
Accordingly, by a simple glance at the proof of Lemma 5.9, we see that, if V (n;
denotes the rst minimum of
, the convergence of V (n; k)=n to V ,
for
n, is uniform, almost surely. Compared with Lemma 5.9, we just
have to change slightly the denitions of u
sup
By inspection of relation 5.5, we see that the convergence of Z n (;
ne (t)
to Z(; t, uniformly for (; holds true almost
surely, that is
Pr
uniformly
on
Z
owing to 6.12 and to the fact that
sup
ne
ne
0:
R (k)
n;d
ne
Lemma 5.12 yields
Proposition 6.1
Pr
Theorem 1.6 follows at once. }
7 Concluding remarks
The main pending question, in our opinion, is about
does it provide
an alternative construction of the stochastic additive coalescent ? This construction
would then complete the parallel between the additive coalescent and the multiplicative
coalescent, given in the concluding remarks of [4], as the stochastic multiplicative
coalescent was identied by Aldous [2] as the limit of the normalized sequence of
sizes of connected components in the random graph model, and also as the sequence
of widths of excursions of a simple stochastic process.
An easy corrolary of Theorems 4.1, 1.4 and 1.5 is that we have the joint law of
the sequence of shapes and sizes (or widths) of excursions of  e, the sizes being
given by Theorem 1.4: an easy induction proves that the shapes are independent,
distributed as e, and independent of the sizes. An argument in the proof of Theorem
then says that each of the clusters of the fragmentation process B() starts anew
a fragmentation process distributed as
, given that the cluster has
size x. It rises the following questions: is this also a property of the standard additive
coalescent ? Is it a charasteristic property of the standard additive coalescent
Which additional properties are eventually needed to characterize the standard
additive coalescent ?
The scaling factor x in
is easily understood, but the time change
is less clear. However it is explained asymptotically by a property of parking schemes:
the time unit for the discrete fragmentation process associated with parking n cars
on n places, is the departure of p
cars. Due to the law of large numbers, during
one time unit, a given block of cars with size xn loses approximately x
x
xn
cars, meaning that, for the internal clock of this block, p

Acknowledgements

The starting point for this paper was the talk of Philippe Flajolet at the meeting
ALEA in February 1998 at Asnelles (concerning his paper with Viola & Poblete),
and a discussion that Philippe and the authors had in a small cafe of the French
Riviera after the SMAI meeting of September 1998. Some discussions of the rst
author with Marc Yor, and also with Uwe Rossler were quite fruitful. We thank
Philippe Laurencot for calling our attention to the works of Aldous, Pitman &
Evans on coalescence models. The papers of Perman, Pitman, & Yor about random
probability measures and Poisson-Dirichlet processes were also of a great help.



--R

The continuum random tree.
critical random graphs and the multiplicative coalescent.
Exchangeability and related topics.
The standard additive coalescent.
The probabilistic method.
A fragmentation process connected with Brownian motion.


On the frequency of numbers containing prime factors of a certain relative magnitude.

On the Analysis of Linear Probing Hashing
Mappings of acyclic and



The birth of the giant compo- nent
The art of computer programming.
Linear Probing and Graphs


Order statistics for jumps of normalised subordinators.

Exchangeable and partially exchangeable random partitions.
Random discrete distributions invariant under size-biased permuta- tion
A polytope related to empirical distribu- tions
The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
the probable largest search time grows logarithmically with the number of records.
Convergence of stochastic processes.

Ballots and trees.

Ordered cycle lengths in a random permutation.
Empirical processes with applications to statis- tics
On an enumeration problem.

in Mathematical Essays in Honor of Gian-Carlo Rota (B
A relation between Brownian bridge and Brownian excursion
--TR
Linear probing: the probable largest search time grows logarithmically with the number of records
The first cycles in an evolving graph
The art of computer programming, volume 3

--CTR
Philippe Chassaing , Guy Louchard, Reflected Brownian Bridge area conditioned on its local time at the origin, Journal of Algorithms, v.44 n.1, p.29-51, July 2002
Svante Janson, Individual displacements for linear probing hashing with different insertion policies, ACM Transactions on Algorithms (TALG), v.1 n.2, p.177-213, October 2005
Jean Bertoin, Random covering of an interval and a variation of Kingman's coalescent, Random Structures & Algorithms, v.25 n.3, p.277-292, October 2004
brownian excursion;hashing with linear probing;coalescence;empirical processes;parking