A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0

Philippe Chassaing^{1} & Svante Janson^{2}

October 19, 1999

Abstract

We describe a Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0: up to random shifts, this process equals the two processes constructed from a Brownian bridge and a Brownian excursion by adding a drift and then taking the excursions over the current minimum. As a consequence, these three processes have the same occupation measure, which is easily found.

The three processes arise as limits, in three different ways, of profiles associated to hashing with linear probing, or, equivalently, to parking functions.

1 Introduction

We regard the Brownian bridge b(t) and the normalized (positive) Brownian excursion e(t) as defined on the circle R/Z, or, equivalently, as defined on the whole real line, being periodic with period 1. We define, for a ≥ 0, the operator Ψ_{a} on the set of bounded functions on the line by

Ψ_{a}f(t) = f(t) − at − inf_{−∞<s≤t}(f(s) − as)
= sup_{s≤t}(f(t) − f(s) − a(t − s)).  (1.1)

If f has period 1, then so has Ψ_{a}f; thus we may also regard Ψ_{a} as acting on functions on R/Z. Evidently, Ψ_{a}f is nonnegative.

In this paper, we prove that, for every a ≥ 0, the three following processes can be obtained (in law) from each other by random shifts, that we will describe explicitly:

• X_{a}, which denotes the reflecting Brownian bridge |b| conditioned to have local time at level 0 equal to a;

• Y_{a} = Ψ_{a}b ;

• Z_{a} = Ψ_{a}e.

We will find convenient to use the following formulas for Y_{a} and Z_{a}:

Y_{a}(t) = b(t) − at + sup_{t−1≤s≤t}(as − b(s)),  (1.2)
Z_{a}(t) = e(t) − at + sup_{t−1≤s≤t}(as − e(s)).  (1.3)

1Institut Elie Cartan, BP 239, 54 506 Vandoeuvre Cedex, France.

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

For t ∈ [0, 1], we also have

Z_{a}(t) = e(t) − at + sup_{0≤s≤t}(as − e(s)),  (1.4)

consistently with the notations of [13].

Given a stochastic process X and a positive number t, we let L_{t}(X) denote the local time of the process X at level 0, on the interval [0, t], defined as in [10, p.154] by:

L_{t}(X) = lim_{ε↓0} \frac{1}{2ε} ∫_{0}^{t} 1_{\{−ε<X_{s}<ε\}}ds;

with this convention, e.g., b and |b| have the same local time at 0, while, according to the usual convention [28, §VI.2], the local time at 0 of |b| is twice the local time at 0 of b. When possible, we extend L(X) to t ∈ (−∞, 0), in such a way that L_{b}(X) − L_{a}(X) is the local time of the process X at level 0, on the interval [a, b], for any choice −∞ < a < b < +∞.

The definition above of X_{a} is formally not precise enough, since it involves conditioning on an event of probability 0. However, there exists on C[0, 1] a unique family of conditional distributions of |b| (or b) given L_{1}(b) = a which is weakly continuous in a ≥ 0 [25, Lemma 12], and this can be taken as defining the distribution of X_{a}. The process X_{a} has been an object of interest in a number of recent papers in the domain of stochastic calculus: its distribution is described in [27, Section 6] by its decomposition in excursions. The sequence of lengths of the excursions is computed in [7], using [24]. The local time process of X_{a} is described through an SDE in a recent paper [25] by Pitman, who in particular proves that, up to a suitable random time change, the local time process of X_{a} is a Bessel(3) bridge from a to 0 [25, Lemma 14]. (See also [5], where a Brownian bridge conditioned on its whole local time process is decribed.)

While X_{a} appears as a limit in the study of random forests [25], Z_{a} appears as a limit in the study of parking problems, or hashing (see [13]), an old but still hot topic in combinatorics and analysis of algorithms, these last years [1, 14, 17, 19, 26, 31, 32]. The fragmentation process of excursions of Z_{a} appears in the study of coalescence models [8, 9, 13], an emergent topic in probability theory and an old one in physical chemistry, astronomy and a number of other domains [4, Section 1.4]. See [4] for background and an extensive bibliography, and also [3, 6, 16] among others. As explained later, Y_{a} is tightly related to Z_{a} through a path transformation, due to Vervaat [33], connecting e and b.

Remark 1.1 For a = 0, we have X_{0} =^{law} e [25, Lemma 12] and, trivially, Y_{0} = b−min b and Z_{0} = e, and the identity up to shift of these reduces to the result by Vervaat [33].

For a positive, the three processes X_{a}, Y_{a} and Z_{a} do not coincide without shifting. This can be seen by observing first that a.s. Y_{a} > 0, while X_{a}(0) = Z_{a}(0) = 0, and secondly that Z_{a} a.s. has an excursion beginning at 0, i.e. inf{t > 0 : Z_{a}(t) = 0} > 0 (see [8], where the distribution of this excursion length is found), while this is false for X_{a} (as a consequence of [27, Section 6]). It also follows that Z_{a} is not invariant under time reversal (while X_{a} and Y_{a} are).

We mention two further constructions of the processes above. First, let B be a standard one-dimensional Brownian motion started at 0, and define:

τ_{t} = inf{s ≥ 0 : L_{s}(B) = t}.

Then X_{a} can also be seen as the reflected Brownian motion |B| conditioned on τ_{a} = 1, see e.g. [25, the lines following (11)] or [27, identity (5.a)].

Secondly, define b̃(t) = b(t) − ∫_{0}^{1} b(s) ds. It is easily verified that b̃ is a stationary Gaussian process (on R/Z or on R), for example by calculating its covariance function

Cov(b̃(s), b̃(t)) = \frac{1 − 6|s − t|(1 − |s − t|)}{12}, |s − t| ≤ 1.

Since b and b̃ differ only by a (random) constant, Y_{a} = Ψ_{a}(b̃) too. This implies that Y_{a} is a stationary process. (X_{a} and Z_{a} are not, again because they vanish at 0.)

We may similarly define ẽ(t) = e(t) − ∫_{0}^{1} e(s) ds, and obtain Z_{a} = Ψ_{a}(ẽ), but we do not know any interesting consequences of this.

Precise statements of the relations between the three processes X_{a}, Y_{a} and Z_{a} are given in Section 2. The three processes arise as limits, under three different conditions, of profiles associated with parking schemes (also known as hashing with linear probing). This is described in Sections 3 and 4. The proofs are given in the remaining sections.

2 Main results

In this section we give precise descriptions of the shifts connecting the three processes X_{a}, Y_{a} and Z_{a}, in all six possible directions. Let a ≥ 0 be fixed.

First, assume that the Brownian bridge b is built from e using Vervaat’s path transformation [10, 11, 33]: given a uniform random variable U, independent of e,

b(t) = e(U + t) − e(U).  (2.1)

Then

Ψ_{a}b(t) = Ψ_{a}e(U + t),

so that:

Theorem 2.1 For U uniform and independent of Z_{a},

Z_{a}(U + ·) =^{law} Y_{a}.

As a consequence, Y_{a} is a stationary process on the line, or on the circle R/Z, as was seen above in another way. A far less obvious result is:

Theorem 2.2 For U uniform on [0, 1] and independent of X_{a},

X_{a}(U + ·) =^{law} Y_{a}.

The proof will be given later. The case a = 0 of Theorem 2.2 is just Vervaat’s path transformation, since, as remarked above, X_{0} =^{law} e. In [10], one can find a host of similar path transformations connecting the Brownian bridge, excursion and meander.

Corollary 2.3 The occupation measures of X_{a}, Y_{a} and Z_{a} coincide, and have the distribution function

1 − e^{−2ax−2x^{2}}.

This is also the distribution function of Y_{a}(t) for any fixed t.

Recall that a random variable W is Rayleigh distributed if Pr(W ≥ x) = e^{−x^{2}/2}. The occupation measure of X_{a} (or Y_{a}, Z_{a}) is then the law of half the residual life at time a of W: Pr((W − a)/2 ≥ x | W ≥ a) = e^{−2ax−2x^{2}}. For a = 0 we recover the Durrett–Iglehart result for the occupation measure of the Brownian excursion: it is the law of W/2 [15].

Proof of Corollary 2.3. By definition, the occupation measure of X_{a} is the law of X_{a}(U), so, from Theorem 2.2, it is also the law of Y_{a}(0). The same is true for Z_{a} by Theorem 2.1, and for Y_{a} because it is stationary. We have

Y_{a}(0) = sup_{−1≤s≤0}(as − b(s))
=^{law} sup_{0≤t≤1}(b(t) − at)
=^{law} sup_{0≤t≤1}((1 − t)B_{\frac{t}{1−t}} − at)
= sup_{0≤u≤+∞}(\frac{B_{u} − au}{1 + u}).

For positive numbers λ and μ, set

T_{λ,μ} = inf{u ≥ 0; B_{u} ≥ λu + μ}.

Using the exponential martingale exp(2λB_{u} − 2λ^{2}u), it is easy to derive that

Pr(T_{λ,μ} < +∞) = e^{−2λμ},

see [28, Exercise II.3.12]. We have thus:

Pr(Y_{a}(0) ≥ x) = Pr(∃ u ≥ 0 such that \frac{B_{u} − au}{1 + u} ≥ x)
= Pr(T_{a+x,x} < +∞)
= e^{−2ax−2x^{2}}.  ♢

Problem 2.4 What are the laws of X_{a}(t) and Z_{a}(t) (which depend on t)?

We need an additional notation to define a random shift from Y_{a} or Z_{a} to X_{a}: let T (X) denote the inverse process of L(X).

Theorem 2.5 Suppose a > 0. Let U be uniformly distributed on [0, 1] and independent of Z_{a} or Y_{a}. Set

τ = T_{aU}(Z_{a}),
τ̃ = T_{aU}(Y_{a}).

We have:

X_{a} =^{law} Z_{a}(τ + ·)
=^{law} Y_{a}(τ̃ + ·).

Note that as a difference with Theorems 2.1 and 2.2, here τ (resp. τ̃) depends on Z_{a} (resp. Y_{a}).

Thus we obtain X_{a} by shifting any of the processes uniformly in local time, while we have seen above that we obtain Y_{a} by shifting uniformly in real time.

Theorem 2.6 Suppose a > 0.

(i). Almost surely, t ↦ L_{t}(X_{a}) − at reaches its maximum at a unique point V in [0, 1)

and

X_{a}(V + ·) =^{law} Z_{a}.

(ii). Almost surely, t ↦ L_{t}(Y_{a}) − at reaches its maximum at a unique point Ṽ in [0, 1)

and

Y_{a}(Ṽ + ·) =^{law} Z_{a}.

Moreover, Ṽ is uniform on [0, 1] and independent of Y_{a}(Ṽ + ·).

In contrast, and as an explanation, t ↦ L_{t}(Z_{a}) − at reaches its maximum at 0, see the proof in Section 11. It is easily verified that V is not uniformly distributed.

Remark 2.7 For a = 0, Theorems 2.5 and 2.6 hold if we instead define τ = 0, V = 0 and τ̃ = Ṽ as the unique points where Z_{0}, X_{0} and Y_{0}, respectively, attain their minimum value 0, see Remark 1.1.

Finally, we observe that it is possible to invert Ψ_{a} and recover the Brownian bridge b from Y_{a} = Ψ_{a}b and the excursion e from Z_{a} = Ψ_{a}e using local times.

Theorem 2.8 For any t,

b(t) = Y_{a}(t) − Y_{a}(0) − L_{t}(Y_{a}) + at

and

e(t) = Z_{a}(t) − L_{t}(Z_{a}) + at.

Combining Theorems 2.6 and 2.8, we can construct Brownian excursions from X_{a} and Y_{a} too.

Corollary 2.9 Let V and Ṽ be as in Theorem 2.6. Then

e′(t) = X_{a}(V + t) + at − L_{V +t}(X_{a}) + L_{V} (X_{a})

and

e′′(t) = Y_{a}(Ṽ + t) + at − L_{Ṽ +t}(Y_{a}) + LṼ (Y_{a}),

respectively, define normalized Brownian excursions.

In the case of Y_{a}, in addition, e′′ and Ṽ are independent.

The problem of possible other shifts is adressed in the concluding remarks.

3 Parking schemes and associated spaces

A parking scheme ω describes how m cars c_{1}, c_{2}, … park on n places {1, 2, …, n}. We write

ω = (ω_{k})_{1≤k≤m},

where each ω_{k} ∈ {1, …, n}. According to ω, car c_{1} parks on place ω_{1}. Then car c_{2} parks on place ω_{2} if ω_{2} is still empty, else it tries ω_{2} + 1, ω_{2} + 2, …, until it finds an empty place, and so on. We adopt the convention that n + 1 = 1, and more generally n + k = k. We consider only the case 1 ≤ m < n.

Figure 1: Elements of P_{25,m}, m = 20, ⋯, 24.

The interest of combinatorists to parking schemes is born from a paper by Konheim & Weiss [21], in 1966, about hashing with linear probing, a popular search method, that had also been studied, notably, by Don Knuth, in 1962 (see the historical notes in his 1999 paper [19], or pages 526–539 in his book [18]). The metaphore of parking was already used by Konheim & Weiss. The two recent and beautiful papers by Flajolet, Poblete & Viola [17] and Knuth [19] drew the attention of the authors to the connection between parking schemes and Brownian motion (see also [13, 14]). For a similar connection between trees and Brownian motion, see [2, 6, 25, 30], among others.

Let P_{n,m} denote the set of all parking schemes of m cars on n places, and let CP_{n,m} denote the subset of confined parking schemes, confined meaning that the last place is assumed to be left empty. We have

#P_{n,m} = n^{m} and #CP_{n,m} = n^{m−1}(n − m);

the last can be seen as follows. For ω ∈ P_{n,m}, we define the shift (rotation)

rω = (−1 + ω_{k})_{1≤k≤m},

moving all cars back one place (modulo n); the action of r on P_{n,m} draws n^{m−1} orbits of n elements, each of them containing n − m elements of CP_{n,m}.

Let Y_{k}(ω) be the number of cars whose first try is on place k, according to ω ∈ P_{n,m}. For any natural integer k, set

S_{k+1}(ω) = S_{k}(ω) + Y_{k+1}(ω),

with S_{0}(ω) = 0. Our convention extends to Y_{k+n} = Y_{k}, so that S_{k+n} = S_{k} + m. Set:

W (ω, i) = S_{i}(ω) − i\frac{m}{n},  (3.1)

and note that W (ω, k + n) = W (ω, k). We have

Proposition 3.1 There exists at least an element of CP_{n,m}, x(κ), in each orbit κ, such that W (x(κ), ·) is nonnegative.

Proof. Let ω denote an element of P_{n,m}. Since S(r^{j}ω, k) = S(ω, k + j) − S(ω, k) and thus W (r^{j}ω, k) = W (ω, k + j) − W (ω, k), W (r^{j}ω, ·) is nonnegative if and only if W (ω, j) = min_{k} W (ω, k). This proves that x(κ) = r^{j}ω exists in P_{n,m}. We postpone the proof that in fact r^{j}ω ∈ CP_{n,m} to Proposition 5.4 (see also [13]). ♢

In general, in the same orbit κ , there are several elements z such that W (z, ·) is nonnegative: we let x(κ) be one particular choice, and let E_{n,m} be the set of the n^{m−1} elements x(κ). (This set is thus to some extent arbitrary, but the results below hold for any choice.)

4 Convergence results

For ω in P_{n,m}, let H_{k}(ω) denote the number of cars that try, successfully or not, to park on place k. (We regard H_{k} as defined for all integers k, with H_{k+n} = H_{k}.) We rescale H_{k}

Figure 2: Profile.

and define h_{n}(k/n, ω) = H_{k}(ω)/\sqrt{n}; h_{n} is then extended to a continuous periodic function on R, that we call the profile of ω, by linear interpolation, i.e.

h_{n}(t, ω) = \frac{(1 + ⌊nt⌋ − nt)H_{⌊nt⌋}(ω) + (nt − ⌊nt⌋)H_{1+⌊nt⌋}(ω)}{\sqrt{n}}.

Let μ_{n,ℓ} (resp. μ̃_{n,ℓ}, μ̂_{n,ℓ}) denote the law of (h_{n}(t))_{0≤t≤1} when ω is drawn at random in P_{n,n−ℓ} (resp. CP_{n,n−ℓ}, E_{n,n−ℓ}).

Central to our results are the following theorems:

Theorem 4.1 If ℓ/\sqrt{n} → a ≥ 0, then

μ_{n,ℓ} ⟶^{weakly} Y_{a}.

Theorem 4.2 If ℓ/\sqrt{n} → a ≥ 0, then

μ̃_{n,ℓ} ⟶^{weakly} X_{a}.

Theorem 4.3 If ℓ/\sqrt{n} → a ≥ 0, then

μ̂_{n,ℓ} ⟶^{weakly} Z_{a}.

Theorem 4.3 was also proved, by similar methods, in [13, Lemma 5.11].

As will be seen in detail later, Theorems 2.1 and 2.2 can be seen as consequences of the preceding convergence results, combined with the evident relation

h_{n}(t, r^{j}ω) = h_{n}(t + \frac{j}{n}, ω)

and with the following obvious statement: the random rotation of a random element of CP_{n,m} or of E_{n,m} gives a random element of P_{n,m}. More formally:

Proposition 4.4 If ω is random uniform on P_{n,m}, CP_{n,m} or on E_{n,m}, and U is uniform on [0, 1] and independent of ω, then r^{⌈nU⌉}ω is random uniform on P_{n,m}.

A different kind of random rotation gives Theorem 2.5: let ω be random in P_{n,m} or in E_{n,m} and choose randomly an empty place j of ω. Then r^{j}ω is random in CP_{n,m}. More formally, let us define an operator R from P_{n,m} to CP_{n,m} as shifting to the next empty place:

Rω = r^{j}ω,

where j ≥ 1 is the first place left empty by ω. Thus R^{⌈(n−m)U⌉}ω (with U random uniform) is a rotation of ω to a random empty place, i.e. to a random element of the corresponding orbit in CP_{n,m}, and we have:

Proposition 4.5 If ω is random uniform on P_{n,m}, CP_{n,m} or on E_{n,m}, and U is uniform on [0, 1] and independent of ω, then R^{⌈(n−m)U⌉}ω is random uniform on CP_{n,m}.

For Theorem 2.5 we use also the convergence of the number of empty places in a given interval of {1, 2, …, n} to the local time of X_{a}, Y_{a} or Z_{a} in the corresponding interval of [0, 1].

More precisely, let V_{j,k}(ω) denote the number of empty places in the set {j + 1, j + 2, …, k}, according to the parking scheme ω, and define, in analogy with h_{n} above, a corresponding continuous function v_{n} on [0, 1] by rescaling and linear interpolation so that v_{n}(k/n) = V_{0,k}/\sqrt{n} for integers k, i.e.

v_{n}(t, ω) = \frac{(1 + ⌊nt⌋ − nt)V_{0,⌊nt⌋}(ω) + (nt − ⌊nt⌋)V_{0,1+⌊nt⌋}(ω)}{\sqrt{n}}, 0 ≤ t ≤ 1.

We then have the following extension of Theorems 4.1–4.3, yielding joint convergence of the processes h_{n} and v_{n}.

Theorem 4.6 Suppose ℓ/\sqrt{n} → a ≥ 0. On [0, 1], the following hold:

(i). If ω is drawn at random in P_{n,n−ℓ}, then (h_{n}(·, ω), v_{n}(·, ω)) ⟶^{law} (Y_{a}, L(Y_{a})).

(ii). If ω is drawn at random in CP_{n,n−ℓ}, then (h_{n}(·, ω), v_{n}(·, ω)) ⟶^{law} (X_{a}, L(X_{a})).

(iii). If ω is drawn at random in E_{n,n−ℓ}, then (h_{n}(·, ω), v_{n}(·, ω)) ⟶^{law} (Z_{a}, L(Z_{a})).

5 Results on parking schemes

Consider a fixed ω ∈ P_{n,m}. As remarked above, we regard the functions Y_{k}, S_{k}, W (ω, k) and H_{k} as defined for all integers k; S_{k+n} = S_{k} + m and the three others have period n.

Note that, among the cars that visit place k, only one will not visit place k + 1, so:

Proposition 5.1

H_{k+1} = (H_{k} − 1)_{+} + Y_{k+1}.

This recursion does not define fully H_{k}, given (Y_{k})_{0≤k≤n}, as the recursion starts nowhere. In order to circumvent this difficulty, we have to find a place left empty by ω. Let

Δ_{k} = max_{i≤k}(i − S_{i}) = max_{−n+k<i≤k}(i − S_{i}).  (5.1)

Proposition 5.2 For a given ω and place k, there are two cases:

(i). k is left empty, H_{k} = 0, k − S_{k} = Δ_{k−1} + 1 and Δ_{k} = Δ_{k−1} + 1.

(ii). k is occupied, H_{k} ≥ 1, k − S_{k} ≤ Δ_{k−1} and Δ_{k} = Δ_{k−1}.

Proof. Clearly k is left empty if and only if H_{k} = 0.

Next, observe that if S_{k} − S_{j} ≥ k − j for some j < k, then at least k − j cars have tried to park after j, and there is not room enough for all of them to park on {j + 1, …, k − 1}, so one of them will park on k. Conversely, suppose that some car parks on k, and let j be the last empty place before k. Then the k − j places {j + 1, …, k} are all occupied, and the cars on them must all have made their first try in the same set, so S_{k} − S_{j} ≥ k − j.

Consequently, k is empty if and only if S_{k} −S_{j} < k −j for all j < k, which is equivalent to k − S_{k} > max_{j<k}(j − S_{j}) = Δ_{k−1} and thus also to Δ_{k} > Δ_{k−1}.

Finally, note that always k−S_{k} ≤ k−S_{k−1} ≤ 1+Δ_{k−1}, and thus Δ_{k−1} ≤ Δ_{k} ≤ Δ_{k−1}+1. ♢

This leads to an explicit formula for H_{k}, given Y_{k}.

Proposition 5.3 For any integer k,

H_{k} = 1 + S_{k} − k + Δ_{k−1}.

Proof. First observe that by Proposition 5.2, both sides vanish if k is empty. We then proceed by induction, beginning at any empty place (both sides have period n). Going from k to k + 1, if k is occupied, then the left hand side increases by Proposition 5.1 by H_{k+1} − H_{k} = Y_{k+1} − 1 while the right hand side increases by Y_{k+1} − 1 + Δ_{k} − Δ_{k−1}, which by Proposition 5.2 equals Y_{k+1} − 1 too. Similarly, if k is empty, then both sides increase by Y_{k}. Hence the equality holds for every k. ♢

We can also now complete the proof of Proposition 3.1.

Proposition 5.4 If W (ω, j) = min_{k} W (ω, k), then place j is empty.

Proof. For every i < j,

S_{j} − S_{i} = W (ω, j) − W (ω, i) + (j − i)\frac{m}{n} ≤ (j − i)\frac{m}{n} < j − i

and thus j−S_{j} > max_{i<j}(i−S_{i}) = Δ_{j}, so the result follows by Proposition 5.2. ♢

Let V_{j,k}(ω) denote the number of empty places in the set {j +1, j +2, …, k}, according to the parking scheme ω. As another immediate consequence of Proposition 5.2 we obtain:

Proposition 5.5 For j ≤ k,

V_{j,k} = Δ_{k} − Δ_{j}.

Further similar results are given in [13, Section 5].

We end this section with a discrete analog of Theorem 2.6, which would lead to a proof of Theorem 2.6 through the convergence theorems of Section 4. The proof of Theorem 2.6 that we give is however more direct, and we will not use this result in the sequel.

For ω in P_{n,m}, and k ≥ 0, let C(ω, k) be defined by:

C(ω, k) = \frac{k(n − m)}{n} − V_{0,k}(ω).

Clearly C(ω, k + n) = C(ω, k), and we may use this to extend the definition to all integers k.

Proposition 5.6 For ω in P_{n,m}, assertions C(ω, j) = min_{k} C(ω, k) and W (ω, j) = min_{k} W (ω, k) are equivalent. For ω in E_{n,m}, C(ω, ·) is nonnegative.

Proof. According to Proposition 5.4, W (ω, j) = min_{k} W (ω, k) insures that place j is empty. The first assertion also insures that place j is empty, since it implies C(ω, j − 1) ≥ C(ω, j) and thus V_{0,j} > V_{0,j−1}.

As a simple consequence of Propositions 5.2 and 5.5, see also [13], for an empty place j and for k ≥ j, we have:

V_{j,k} = max_{j≤i≤k}(i − S_{i}) − j + S_{j}
= max_{j≤i≤k}(W (ω, j) − W (ω, i) + (i − j)\frac{n − m}{n}).

As a consequence, for k ≥ j, we have:

C(ω, k) − C(ω, j) = \frac{(k − j)(n − m)}{n} − V j, k
= min_{j≤i≤k}(\frac{(k − i)(n − m)}{n} + W (ω, i) − W (ω, j))
≤ W (ω, k) − W (ω, j).

By periodicity, the inequality persists for all integers j and k. This shows first that if j is a minimum point for C, so that the left hand side is nonnegative for all k, then j is a minimum point for W too. Moreover, if there is another minimum point k for W, then W (ω, k) = W (ω, j), and the inequality shows that C(ω, k) = C(ω, j), so k is another minimum point for C too.

The final assertion follows because if ω ∈ E_{n,m}, then 0 is a minimum point for W, and thus also for C, and C(ω, 0) = 0. ♢

6 Convergence results: proofs

6.1 Proof of Theorem 4.1.

Let U^{(m)} = (U_{k}^{(m)})_{1≤k≤m} denote a sequence of m independent random variables, uniform on [0, 1]. For m ≤ n, the sequence U^{(m)} generates the parking scheme ω^{(m)} ∈ P_{n,m} defined by

ω_{k}^{(m)} = ⌈nU_{k}^{(m)}⌉.

The n^{m} possible parking schemes generated this way are clearly equiprobable. Consider the empirical process α_{m}(t) associated with U^{(m)}, defined on [0, 1] by

α_{m}(t) = m^{−1/2}(#{k : U_{k}^{(m)} ≤ t} − mt).  (6.1)

As m → ∞, the processes α_{m} converge in distribution, as random elements of the space D[0, 1], to a Brownian bridge [12, Theorem 16.4]. Due to the Skorohod representation theorem, see e.g. [29, II.86.1], we may thus assume that the variables U^{(m)} are such that, as m → ∞,

α_{m}(t) → b(t),  uniformly on [0, 1].  (6.2)

We have m = n − ℓ = n − a_{n}\sqrt{m}, where a_{n} → a. Then, by (3.1), for any integer j (extending α_{m} periodically),

W (ω^{(m)}, j) = \sqrt{m} α_{m}(\frac{j}{n}),  (6.3)
S_{j} − j = \sqrt{m} (α_{m}(\frac{j}{n}) − a_{n} \frac{j}{n}).  (6.4)

Hence, as n → ∞ and thus m → ∞ too,

\frac{1}{\sqrt{n}}(S_{⌊nt⌋} − ⌊nt⌋) → b(t) − at,

uniformly on [−1, 1], say. By (5.1), this implies

\frac{1}{\sqrt{n}}Δ_{⌊nt⌋} → sup_{t−1≤s≤t}(as − b(s)) = sup_{s≤t}(as − b(s)),  (6.5)

uniformly on [0, 1], and thus by Proposition 5.3 and (1.2) we obtain:

\frac{1}{\sqrt{n}}H_{⌊nt⌋}(ω^{(m)}) → b(t) − at + sup_{s≤t}(b(s) − as) = Y_{a}(t),

uniformly for all real t (by periodicity), which implies that:

Proposition 6.1 With the assumptions above, there is almost surely uniform convergence of h_{n}(·, ω^{(m)}) to Y_{a}(·).

6.2 Proof of Theorem 4.3.

We draw a random element ω^{(m)} in P_{n,m} using U^{(m)}, as in Subsection 6.1. Let p(ω^{(m)}) = r^{J}ω^{(m)} be its projection in E_{n,m}. Thus J is one of the points where W (ω^{(m)}, ·) attains its minimum, and by (6.1) and (6.3), it follows that α_{m} almost attains its minimum at J/n; more precisely,

α_{m}(J/n) = inf_{k} α_{m}(k/n) < inf_{t} α_{m}(t) + m^{−1/2}.  (6.6)

We can always assume that 1 ≤ J ≤ n.

Moreover, we may assume that b is constructed from a Brownian excursion e by Vervaat’s relation (2.1). This entails that b has almost surely a unique minimum in [0, 1] at the point 1 − U. Still assuming m = n − ℓ = n − a_{n}\sqrt{m}, the uniform convergence (6.2) of α_{m}(t) to b(t) and (6.6) imply that

lim_{n→∞} \frac{J}{n} = 1 − U.  (6.7)

Since H_{k}(p(ω^{(m)})) = H_{k+J}(ω^{(m)}) and thus h_{n}(t, p(ω^{(m)})) = h_{n}(t + J/n, ω^{(m)}), which by Proposition 6.1 and (6.7) converges uniformly to Ψ_{a}b(t + 1 − U) = Ψ_{a}e(t), we have

Proposition 6.2 With the assumptions above, there is almost surely uniform convergence of h_{n}(·, p(ω^{(m)})) to Z_{a}(·).

See Subsections 5.1 and 5.2 of [13] for more details.

6.3 Proof of Theorem 4.2.

The sequence S_{j} − j may be seen as a certain random walk (with fixed endpoint S_{n} − n = m − n.) Considering only parking sequences means conditioning the random walk S_{j} − j on ending at a minimum at S_{n} − n. This random walk should, after rescaling, converge to a Brownian bridge b(t) − at from 0 to −a, conditioned on its minimum being −a, or, equivalently, a Brownian motion B(t) conditioned on B(1) = M(1) = −a, with M(t) = min_{s≤t} B(s); the corresponding process h_{n} would then, through Proposition 5.3, converge to B −M with the same condition. By Lévy [28, Theorem VI.2.3], (B −M, −M) equals (in law) (|B|, L), so this is the same as |B(t)| conditioned on B(1) = 0, L(1) = a, or, equivalently, |b(t)| conditioned on L(1) = a.

However we have not been able to make such an argument rigorous, and we rather proceed as in [6, Section 5]: we use the fact that the sequence of excursion lengths of X_{a} is the weak limit of the sequence of block lengths, suitably normalized, in a random confined parking scheme of CP_{n,n−ℓ}. Then we take advantage of the fact that the excursions of X_{a} appear in random order, independently of their shape and length, as explained in [27, Section 6], while the blocks of a random confined parking scheme have the same property. This allows us to build on the same space a sequence of random variables g_{n} = (g_{n}(t))_{0≤t≤1}, distributed according to μ̃_{n,ℓ}, and a random variable X = (X(t))_{0≤t≤1}, with the same distribution as X_{a}, in such a way that we can prove g_{n} → X.

Sizes of blocks and lengths of excursions

For y ∈ P_{n,m}, let us define R(y) = (R^{(k)}(y))_{k≥1} as the sequence of block lengths when the blocks are sorted by increasing date of birth (in increasing order of first arrival of a car: for instance, on the next figure, for n = 25 and m = 16, R(y) = (2, 5, 5, 1, 2, 1, 0, …)).

Figure 3: Elements of P_{25,m}, m = 13, ⋯, 19.

Let δ_{n} denote the law of R(y)/n when y is drawn at random in P_{n,n−ℓ} or in CP_{n,n−ℓ}. Theorems 1.1 and 1.2 of [13] assert that, assuming i/\sqrt{n} → a,

δ_{n} ⟶^{weakly} J^{⋆} = (J_{k}^{⋆})_{k≥1},

in which J^{⋆} is defined, for k ≥ 1, given a sequence of independent standard Gaussian distributed random variables (N_{k})_{k≥1}, by

J_{1}^{⋆} + J_{2}^{⋆} + ⋯ + J_{k}^{⋆} = \frac{N_{1}^{2} + N_{2}^{2} + ⋯ + N_{k}^{2}}{a^{2} + N_{1}^{2} + N_{2}^{2} + ⋯ + N_{k}^{2}} .  (6.8)

Assume a > 0 and let τ_{a} = T_{a}(B), where B is the standard linear Brownian motion started at 0. It is well known that (τ_{t})_{t≥0} is a stable subordinator with index 1/2, meaning that, for any k and any k-tuple of positive numbers (t_{i})_{1≤i≤k}:

(τ_{t_{1}+t_{2}+...+t_{i}})_{1≤i≤k} =^{law} (\frac{t_{1}^{2}}{N_{1}^{2}} + \frac{t_{2}^{2}}{N_{2}^{2}} + ⋯ + \frac{t_{i}^{2}}{N_{i}^{2}} )_{1≤i≤k}.

Setting τ̃_{t} = τ_{at}/a^{2}, an immediate consequence is

(τ̃_{t})_{t≥0} =^{law} (τ_{t})_{t≥0}.

It is also well known that (τ_{t})_{t≥0} is a pure jump process, whose jump-sizes in the interval [0, t] are precisely the lengths of excursions, of the underlying Brownian motion, that end before time τ_{t} [28, §XII.2].

Let J̃_{1} ≥ J̃_{2} ≥ ⋯ (resp. J_{1} ≥ J_{2} ≥ ⋯ and Ĵ_{1} ≥ Ĵ_{2} ≥ ⋯) be the ranked jump-sizes of τ̃ over the interval [0, 1] (resp. the ranked jump-sizes of τ over the interval [0, a] and the ranked excursion lengths of X_{a} over the interval [0, 1]). As we have τ̃_{1} = τ_{a}/a^{2} and J̃_{k} = J_{k}/a^{2},

(\frac{J̃_{1}}{τ̃_{1}} , \frac{J̃_{2}}{τ̃_{1}} , … | τ̃_{1} = \frac{1}{a^{2}} ) =^{law} (\frac{J_{1}}{τ_{a}} , \frac{J_{2}}{τ_{a}} , … | τ_{a} = 1)
=^{law} (J_{1}, J_{2}, … | τ_{a} = 1)
=^{law} (Ĵ_{1}, Ĵ_{2}, …),

the last identity due to the fact that, as remarked in Section 1, X_{a} has the same distribution as the reflected Brownian motion conditioned on τ_{a} = 1 [27, (5.a)]. In view of these identities, [7, Corollary 5] asserts that the size-biased random permutation of (Ĵ_{1}, Ĵ_{2}, ⋯) has the same distribution as J^{⋆} given by (6.8).

Incidentally, Theorem 1.4 of [13] shows that the sequences of excursion lengths of X_{a} and Z_{a} have the same distribution, suggesting partly Theorems 2.5 and 2.6 of this paper. The fact that the sequence of lengths of excursions has the same distribution for Z_{a} as for X_{a} was noticed simultaneously in [8, 13], and leads to conjecture an interesting alternative (through the fragmentation process of excursions of Ψ_{a}e) for the original construction, given by Aldous and Pitman in [6], of the additive coalescent (see [8, 2nd version] for the proof). In [13], it is shown that the process, with time parameter a, of blocks lengths of a random element ω ∈ P_{n,n−⌊a\sqrt{n}⌋}, converges to the same fragmentation process. This parallels the behavior observed in [3] for the sizes of connected components of the random graph during the phase transition.

Order of excursions

Let us adopt the notation of [34, Lecture 4] for the Brownian scaling of a function f over the interval [a, b]:

f^{[a,b]} = (\frac{1}{\sqrt{b − a}}f(a + t(b − a)), 0 ≤ t ≤ 1).

According to the theory of excursions (see [27, Section 6] for details and references), we can build a copy X of X_{a} by applying the infinite analog of a random shuffle to the excursions of X_{a}.

More formally, let (e_{k})_{k≥1} be a sequence of independent random variables distributed as the normalized Brownian excursion e, and let (U_{k})_{k≥1} be a sequence of independent random variables, uniform on [0, 1]. Moreover J^{⋆}, (e_{k})_{k≥1} and (U_{k})_{k≥1} are assumed to be independent. Set

G(k) = ∑_{i: U_{i}<U_{k}} J_{i}^{⋆}  (6.9)
D(k) = ∑_{i: U_{i}≤U_{k}} J_{i}^{⋆}.  (6.10)

With probability 1, U_{i} = U_{j} ⟹ i = j and the terms of J^{⋆} add up to 1, so the stochastic process X that is zero outside ∪_{k≥1} [G(k), D(k)], and satisfies

X^{[G(k),D(k)]} = e_{k},

for k ≥ 1, is well defined and continuous, and has the same distribution as X_{a} [27]. Note that a.s.

L_{G(k)}(X) = L_{D(k)}(X) = aU_{k},

with the notations of Theorem 2.6. The definition of G(k) and D(k) reflects the fact that the excursions of X are ranked from left to right in increasing order of their number U_{k}, generating thus a random shuffle of the excursions, independently of their shapes e_{k} and their lengths J_{k}^{⋆}.

Order of blocks

Let us give a different formulation, more convenient for our purposes, of the well known fact that a random shuffle of the blocks of a random confined parking scheme still produces a random confined parking scheme: we only keep track of this shuffle on the profile of the parking scheme.

Let H_{k} = (h_{j}^{(k)})_{j≥1} be independent sequences of possibly dependent random variables h_{j}^{(k)}, distributed according to μ̃_{j,1}. Assuming y is drawn at random in CP_{n,n−ℓ}, independently of the sequences H_{k}, let us add 1 to each of the ℓ first coordinates of R(y): this operation produces a new sequence of random variables j_{n} = (j_{n}(k))_{k≥1}, whose terms add up to n; these can be regarded as lengths of blocks including a final empty place (allowing empty blocks consisting only of one empty place). Note that j_{n}(k) > 0 if and only if k ≤ ℓ, and that J_{n}(k) = j_{n}(k)/n still satisfies

J_{n} ⟶^{weakly} J^{⋆}.

Let, in analogy with (6.9) and (6.10),

G(k, n) = ∑_{i: U_{i}<U_{k}} J_{n}(i)  (6.11)
D(k, n) = ∑_{i: U_{i}≤U_{k}} J_{n}(i),  (6.12)

and let g_{n} be defined by:

g_{n}^{[G(k,n),D(k,n)]} = h_{j_{n}(k)}^{(k)}, k ≤ ℓ.

The h_{j_{n}(k)}^{(k)} are thus sorted by increasing order of the attached U_{k}. It is easily seen that a random shuffle of the blocks (including a trailing empty place) in a random confined parking scheme produces a new random confined parking scheme with the same distribution, and that the structure of each block of length j is distributed according to CP_{j,j−1}. Hence, checking that our scalings match properly, g_{n} is distributed according to μ̃_{n,ℓ}.

Proof of Theorem 4.2

From [14] (or as a very special case of Theorem 4.3, since CP_{n,n−1} = E_{n,n−1}), we know that

μ̃_{n,1} ⟶^{weakly} e,

so the Skorohod representation theorem provides the existence, on some probability space Ω̃, of a Brownian excursion e and of a sequence H = (h_{j})_{j≥1} of possibly dependent random variables h_{j}, distributed according to μ̃_{j,1}, such that, almost surely, h_{j} converges uniformly to e. The same Theorem provides the existence, on some probability space Ω̂, of random variables J_{n} and J^{⋆}, distributed as above, and such that, almost surely, for any k ≥ 1,

lim_{n} J_{n}(k) = J_{k}^{⋆}.  (6.13)

Finally, by a denumerable product of copies of [0, 1], Ω̃ and Ω̂, we build on some space Ω, simultaneously, random variables e_{k}, H_{k} = (h_{j}^{(k)})_{j≥1}, U_{k}, J_{n} and J^{⋆}, where k, n = 1, 2, …, with the distributions given above, such that for each k ≥ 1 (6.13) holds and

h_{j}^{(k)} ⟶^{uniformly} e_{k},  as j → ∞;  (6.14)

moreover, the variables (e_{k}, H_{k}), U_{k}, and ((J_{n})_{n≥1}, J^{⋆}) are all independent of each other.

Define X and g_{n} as above, and define further, for N ≥ 1, X_{N} and g_{n,N} in the same way, but using only excursions (blocks) with index k ≤ N. Thus e.g. X_{N} = X on ∪_{1}^{N}[G(k), D(k)], while X_{N} = 0 outside this set. Since the excursion lengths D(k)−G(k) → 0, and X is (uniformly) continuous on [0, 1], X_{N} → X in C[0, 1] (i.e. uniformly) as N → ∞.

Note that as both J_{n} and J^{⋆} have nonnegative terms that add up to 1, (6.13) yields ℓ^{1}-convergence of J_{n} to J^{⋆}; and thus by (6.9), (6.10), (6.11), (6.12), G(n, k) → G(k) and D(n, k) → D(k) for every k, which together with (6.14) and j_{n}(k) = nJ_{n}(k) → ∞ easily implies that, for fixed N, g_{n,N} → X_{N} a.s. in C[0, 1] as n → ∞.

Informally, we now let N → ∞. In order to justify this, we need the following estimate, which will be proved below.

Proposition 6.3 For every ϵ > 0,

lim_{N→∞} lim sup_{n→∞} Pr(∥g_{n,N} − g_{n}∥ > ϵ) = 0,

where ∥f∥ = sup_{t} |f(t)| denotes the norm in C[0, 1].

Now, let ϵ > 0. Then

Pr(∥g_{n} − X∥ > 3ϵ) ≤ Pr(∥g_{n} − g_{n,N}∥ > ϵ) + Pr(∥g_{n,N} − X_{N}∥ > ϵ) + Pr(∥X_{N} − X∥ > ϵ),

where by Proposition 6.3 and the comments above, all three terms on the right hand side can be made arbitrarily small by first choosing N and then n large enough. Consequently, g_{n} → X (uniformly) in probability, which completes the proof of Theorem 4.2. (See also [12, Theorem 4.2] where the same type of argument is stated for convergence in distribution.)

Proof of Proposition 6.3. The Dvoretsky-Kiefer-Wolfowitz inequality implies

sup_{j} E∥h_{j}∥^{2} < ∞

(see [14, Section 3.2]). Denote this supremum by A. Then, given J_{n}, by Chebyshev’s inequality,

Pr(∥g_{n,N} − g_{n}∥ > ϵ) = Pr(max_{k>N} \sqrt{J_{n}(k)}∥h_{j_{n}(k)}^{(k)}∥ > ϵ)
≤ ∑_{k>N} Pr(\sqrt{J_{n}(k)}∥h_{j_{n}(k)}^{(k)}∥ > ϵ)
≤ ∑_{k>N} ϵ^{−2}AJ_{n}(k),

and thus, unconditionally,

Pr(∥g_{n,N} − g_{n}∥ > ϵ) ≤ E(min(1, Aϵ^{−2} ∑_{k>N} J_{n}(k))).

Hence, by dominated convergence,

lim sup_{n→∞} Pr(∥g_{n,N} − g_{n}∥ > ϵ) ≤ lim_{n→∞} E(min(1, Aϵ^{−2} ∑_{k>N} J_{n}(k)))
= E(min(1, Aϵ^{−2} ∑_{k>N} J_{k}^{∗})),

which tends to 0 as N → ∞ by dominated convergence again. ♢

7 Proof of Theorem 2.2

Due to the Skorohod representation theorem, and to Theorem 4.2, there exist on some probability space, a sequence f_{n} of random variables distributed according to μ̃_{n,⌊a\sqrt{n}⌋+1}, and a continuous copy X of X_{a} such that, almost surely, f_{n}(t) converges, uniformly for t ∈ [0, 1], to X(t). Possibly at the price of enlarging the probability space, consider a random variable U, uniform on [0, 1] and independent of (f_{n})_{n≥1} and X.

On the one hand, almost surely:

f_{n}(t + \frac{⌈nU⌉}{n}) ⟶^{uniformly} X(t + U).

On the other hand, according to Proposition 4.4, f_{n}(· + \frac{⌈nU⌉}{n}) is distributed according to μ_{n,⌊a\sqrt{n}⌋+1}. Thus, owing to Theorem 4.1,

X(· + U) =^{law} Y_{a}. ♢

8 Proof of Theorem 2.8

Theorem 2.8 follows from (1.1)–(1.4) and the following formulas for the local times of Y_{a} and Z_{a}.

Proposition 8.1 With Y_{a} = Ψ_{a}b, for any t,

L_{t}(Y_{a}) = sup_{−∞≤s≤t}{as − b(s)} − sup_{−∞≤s≤0}{as − b(s)}.  (8.1)

With Z_{a} = Ψ_{b}e, for any t,

L_{t}(Z_{a}) = sup_{−∞≤s≤t}{as − e(s)}  (8.2)

and for t ∈ [0, 1],

L_{t}(Z_{a}) = sup_{0≤s≤t}{as − e(s)}.  (8.3)

Proof. By a well known theorem of Paul Lévy [28, Theorem VI.2.3], a.s., on [0, +∞)

L_{t}(B_{t} − inf_{0≤s≤t} B_{s}) = − inf_{0≤s≤t} B_{s},

or, with the notation Φ_{0}(X)_{t} = − inf_{0≤s≤t} X_{s},

L_{t}(B + Φ_{0}(B)) = Φ_{0}(B)_{t}.

On any interval [0, 1 − δ], the Brownian bridge b has an absolutely continuous distribution w.r.t. the distribution of B, and so has b(t) − at. Consequently, for 0 ≤ t < 1, writing b^{(a)} = b(t) − at,

L_{t}(b^{(a)} + Φ_{0}(b^{(a)})) = Φ_{0}(b^{(a)})_{t}.  (8.4)

This extend by continuity to t = 1. Now, define

Φ(X)_{t} = − inf_{−∞≤s≤t} X_{s},

and observe that

Φ_{0}(b^{(a)})_{t} ≤ Φ(b^{(a)})_{t}

with equality if and only if t is larger or equal than the first nonnegative zero t_{0} of the process Y_{a} = b^{(a)} + Φ(b^{(a)}). On [t_{0}, 1], we have thus

Y_{a}(t) = b^{(a)}(t) + Φ_{0}(b^{(a)})_{t}.

As a consequence, on [t_{0}, 1], (8.4) yields

L_{t}(Y_{a}) = L_{t}(Y_{a}) − L_{t_{0}}(Y_{a})
= Φ_{0}(b^{(a)})_{t} − Φ_{0}(b^{(a)})_{t_{0}}
= Φ(b^{(a)})_{t} − Φ(b^{(a)})_{t_{0}}
= Φ(b^{(a)})_{t} − Φ(b^{(a)})_{0}.  (8.5)

This proves (8.1) for t ∈ [t_{0}, 1]. The formula extends easily to [0, 1], since both sides vanish on [0, t_{0}], and due to the periodicity of Y_{a} and b, to the whole line.

For the assertions on Z_{a}, let b(t) = e(t + U) − e(U), where as usual U is uniform on [0, 1] and independent of e. Then, Z_{a}(t) = Y_{a}(t − U) and thus, using (8.1) or (8.5) and Φ(b^{(a)}) = Y_{a} − b^{(a)},

L_{t}(Z_{a}) = L_{t−U}(Y_{a}) − L_{−U}(Y_{a})
= Φ(b^{(a)})_{t−U} − Φ(b^{(a)})_{−U}
= Y_{a}(t − U) − b(t − U) + a(t − U) − Y_{a}(−U) + b(−U) − aU
= Z_{a}(t) − e(t) + at,

which yields (8.2) and (8.3). ♢

9 Proof of Theorem 4.6(i,iii)

We assume that a random parking scheme ω^{(m)} in P_{n,m} is constructed as in Subsection 6.1, so that the processes α_{m} defined there converge a.s. uniformly to a Brownian bridge b(t). Then, by Proposition 6.1, h_{n}(·, ω^{(m)}) converges a.s. uniformly to Y_{a} = Ψ_{a}b.

Moreover, by Proposition 5.5 and (6.5),

\frac{V_{0,⌊nt⌋}}{\sqrt{n}} = \frac{Δ_{⌊nt⌋} − Δ_{0}}{\sqrt{n}} → sup_{s≤t}(as − b(s)) − sup_{s≤0}(as − b(s)),

uniformly on [0, 1], and thus v_{n}(t, ω^{(m)}) has the same uniform limit. By Proposition 8.1, the right hand side equals the local time L_{t}(Y_{a}), and we have proved the following complement to Proposition 6.1:

Proposition 9.1 With the assumptions above, there is almost surely uniform convergence of v_{n}(·, ω^{(m)}) to L(Y_{a}) on [0, 1].

Propositions 6.1 and 9.1 together yield Theorem 4.6(i).

For Part (iii), we use the additional assumptions of Subsection 6.2, and obtain then easily from Proposition 9.1, using v_{n}(t, p(ω^{(m)})) = v_{n}(t + J/n, ω^{(m)}) − v_{n}(J/n, ω^{(m)}), the following analogue for Z_{a}:

Proposition 9.2 With the assumptions above, there is almost surely uniform convergence of v_{n}(·, p(ω^{(m)})) to L(Z_{a}) on [0, 1].

10 Proofs of Theorem 2.5 and 4.6(ii)

In view of Theorem 4.2, the proof of Theorem 2.5 reduces to the proof of

Theorem 10.1 If a > 0, and τ and τ̃ are defined as in Theorem 2.5, then

μ̃_{n,⌊a\sqrt{n}⌋} ⟶^{weakly} Z_{a}(τ + ·)
=^{law} Y_{a}(τ̃ + ·).

Proof. Set m = n − ⌊a\sqrt{n}⌋ and define M_{n} and M̃_{n} ∈ [0, 1] by

R^{⌈(n−m)U⌉}p(ω) = r^{nM_{n}}p(ω),
R^{⌈(n−m)U⌉}ω = r^{nM̃_{n}}ω.

By the definition of R and r on P_{n,m}, we have

v_{n}(M̃_{n}, ω) = v_{n}(M_{n}, p(ω)) = \frac{⌈(n − m)U⌉}{\sqrt{n}}.  (10.1)

Due to Proposition 8.1, s ⟶ ℓ(s) = L_{s}(Z_{a}), s ∈ [0, 1], is continuous and nondecreasing from 0 to a, with the consequences that the set A = {x ∈ [0, a] : #ℓ^{−1}(x) > 1} is denumerable, and that, furthermore, for x ∉ A, ℓ^{−1} is uniquely defined and continuous: if y_{n} ∈ [0, 1] with ℓ(y_{n}) → x ∉ A, then y_{n} → ℓ^{−1}(x). Assume again that ω = ω^{(m)} is as in Subsections 6.1 and 6.2. Due to (10.1),

|ℓ(M_{n}) − aU| ≤ \frac{2}{\sqrt{n}} + ∥v_{n}(·, p(ω)) − ℓ∥_{∞},

which a.s. converges to zero as n → ∞ by Proposition 9.2, and thus, if aU ∉ A, that is, almost surely,

lim_{n→∞} M_{n} = ℓ^{−1}(aU) = τ.

For the same reasons

lim M̃_{n} = τ̃ a.s..

As a consequence, using Propositions 6.1 and 6.2 again, almost surely, h_{n}(R^{⌈(n−m)U⌉}ω, ·) [resp. h_{n}(R^{⌈(n−m)U⌉}p(ω), ·)] converges uniformly to Y_{a}(τ̃+·) [resp. Z_{a}(τ +·)]. On the other hand, according to Proposition 4.5, R^{⌈(n−m)U⌉}ω and R^{⌈(n−m)U⌉}p(ω) are random uniform on CP_{n,m}, with the consequence that both h_{n}(R^{⌈(n−m)U⌉}ω, ·) and h_{n}(R^{⌈(n−m)U⌉}p(ω), ·) are distributed according to μ̃_{n,⌊a\sqrt{n}⌋}. ♢

Similarly, for Theorem 4.6 (ii), we consider a copy X = Y_{a}(τ̃ + ·) of X_{a}, and we note that, due to Proposition 9.1, v_{n}(R^{⌈(n−m)U⌉}ω, t) converges uniformly to L_{τ̃+t}(Y_{a})−Lτ̃(Y_{a}) = L_{t}(X). ♢

11 Proof of Theorem 2.6

If 0 < t < 1, Proposition 8.1 yields

L_{t}(Z_{a}) = sup_{0≤s≤t}{as − e(s)} < at,

since s ↦ as − e(s) is a continuous function and as − e(s) < at for every s ∈ [0, t]. As a consequence, t ↦ χ(t) = L_{t}(Z_{a}) − at, which has period 1, reaches its maximum 0 exactly at the integers.

By Theorem 2.1, we can assume that Y_{a} = Z_{a}(U + ·), and then

L_{t}(Y_{a}) − at = L_{U+t}(Z_{a}) − L_{U}(Z_{a}) − at
= χ(U + t) − χ(U).

Hence L_{t}(Y_{a}) − at reaches its maximum exactly at {n − U : n ∈ Z}, so Ṽ = 1 − U and Y_{a}(Ṽ + t) = Z_{a}(t), which proves (ii).

The proof for X_{a} is done the same way, using either Theorem 2.5, or the result just proved for Y_{a} and Theorem 2.2. ♢

12 Concluding remarks

Concerning the problem of possible other shifts, note that there exist only one shift from X_{a} or Y_{a} to Z_{a}. Actually there is no nontrivial shift from Z_{a} to itself, while Y_{a} is stationary, i.e. invariant under any nonrandom shift, and X_{a} is invariant under shifts T_{x}(X_{a}) for any x. This last point follows from Theorem 2.5, but it can also be seen more directly on the definition of X_{a} based on the sequences (e, J, U) of shapes, lengths and sorting numbers of its excursions: if we replace the sorting numbers U = (U_{i})_{i≥1} by U^{(x)} = ({U_{i} − x})_{i≥1}, it produces a new process which is just X_{a}(T_{x}(X_{a}) + ·). But

U =^{law} U^{(x)}.

This paper deals with more or less the same stochastic processes as [6, 7, 25]. Maybe less apparent, but somewhat expected, they deal with combinatorial notions that are tightly related: the one-to-one correspondence between labeled trees and elements of

Figure 4: Correspondence CP_{13,21} ↔ Pavlov’s forests.

CP_{n,n−1} (see [14] and the references therein) extends easily to a one-to-one correspondence between random forests à la Pavlov [20, 22, 23] with n−m roots and m leaves and elements of CP_{n,m}, in which trees are in correspondence with parking blocks (see Figure 4). These random forests can be seen as the set of genealogical trees of a Galton-Watson branching process started with n − m individuals, with Poisson offspring, conditioned to have total progeny equal to n [20]. As such, they are also considered in [6, Lemma 18] and [25, Section 3].

Finally we remark that the shifts studied in this paper, together with the construction in Section 6, imply the following improved version of Theorem 4.1 in [13].

Let U be a random variable uniformly distributed on [0, 1] and independent of a process X that stands indifferently for X_{a}, Y_{a} or Z_{a}. Let D (resp. F) denote the last zero of X before U (resp. the first zero of X after U), and let Ξ = F − D. Set, using Brownian scaling as in Section 6, f = X^{[D,F]} and r = X^{[F,D+1]}.

Theorem 12.1 We have:

(i). Ξ has the same distribution as \frac{N^{2}}{a^{2}+N^{2}} , in which N is standard Gaussian;

(ii). f is a normalized Brownian excursion, independent of (F, D);

(iii). Given (Ξ, f), r is distributed as X_{a/\sqrt{1−Ξ}}.

Acknowledgements

Thanks to Philippe Flajolet for putting the two authors in contact with each other, and to Don Knuth for making this possible by first putting the second author in contact with Philippe Flajolet. A starting point of this paper were discussions with Marc Yor, and specially one about the possible relation between parking and process X_{a}. Thanks also to him for pointing to us many interesting papers, such as [8, 25, 27]. Thanks to Jean Bertoin for giving an early access to the second version of [8] and to [9].

References

[1] D. Aldous, Hashing with linear probing, under non-uniform probabilities. Probab. Eng. Inform. Sci., 2 (1988), 1-14.

[2] D. Aldous, The continuum random tree. II: An overview. Stochastic Analysis, Proc. Symp., Durham/UK 1990, Lond. Math. Soc. Lect. Note Ser. 167 (1991), 23–70.

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

[4] D.J. Aldous, Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists. Bernoulli 5 (1999), no. 1, 3–48.

[5] D.J. Aldous, Brownian excursion conditioned on its local time. Electron. Comm. Probab. 3 (1998), no. 10, 79–90.

[6] D.J. Aldous & J. Pitman, Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 (1994), no. 4, 487–512.

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

[8] J. Bertoin, A fragmentation process connected with Brownian motion. Prépublication 487, Laboratoire de Probabilités, Université de Paris VI & VII, 4, pl. Jussieu, Feb. 1999, available at: http://www.proba.jussieu.fr/mathdoc/textes/PMA-487.dvi

[9] J. Bertoin, Clustering statistics for sticky particles with Brownian initial velocity. Prépublication 514, Laboratoire de Probabilités, Université de Paris VI & VII, 4, pl. Jussieu, June 1999, available at: http://www.proba.jussieu.fr/mathdoc/textes/PMA-514.dvi

[10] J. Bertoin & J. Pitman, Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 (1994), no. 2, 147–166.

[11] Ph. Biane, Relations entre pont et excursion du mouvement brownien réel. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 1, 1–7.

[12] P. Billingsley, Convergence of Probability Measures. John Wiley & Sons, Inc., New York-London-Sydney, 1968.

[13] P. Chassaing & G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence. In preparation, 1999, available at: http://altair.iecn.unancy.fr/∼chassain

[14] P. Chassaing & J.F. Marckert, Parking functions, empirical processes and the width of rooted labelled trees. Prépublication 99/22 de l’Institut Elie Cartan, Apr. 1999, available at: http://altair.iecn.u-nancy.fr/∼chassain

[15] R. Durrett & D.L. Iglehart, Functionals of Brownian meander and Brownian excursion. Ann. Probab. 5 (1977), 130–135.

[16] S.N. Evans & J. Pitman, Construction of Markovian coalescents. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998), no. 3, 339–383.

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

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

[19] D.E. Knuth, Linear probing and graphs. Algoritmica 22 (1998), no. 4, 561–568.

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

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

[22] Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest. Th. Probab. Appl. 22 (1977), 509–520.

[23] Yu. L. Pavlov, Random forests. Karelian Centre Russian Acad. Sci., Petrozavodsk 1996 (Russian).

[24] M. Perman, J. Pitman, M. Yor, Size-biased sampling of Poisson point processes and excursions. Probab. Th. Rel. Fields 92 (1992), no. 1, 21–39.

[25] J. Pitman, The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest. Ann. Probab. 27 (1999), no.1, 261–283.

[26] J. Pitman & R. Stanley, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. Technical Report 560, Dept. Statistics, U.C. Berkeley, June 1999, available at: http://statwww.berkeley.edu/users/pitman/bibliog.html

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

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

[29] L.C.G. Rogers & D. Williams, Diffusions, Markov Processes, and Martingales. Vol. 1. Foundations. Second edition. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester, 1994.

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

[31] R. Stanley, Parking functions and noncrossing partitions. Electron. J. Comb. 4 (1997), no. 2.

[32] R. Stanley, Hyperplane arrangements, parking functions, and tree inversions, in Mathematical Essays in Honor of Gian-Carlo Rota (B. Sagan and R. Stanley, eds.), Birkhäuser, Boston/Basel/Berlin (1998), 259-375.

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

[34] M. Yor, Local times and excursions for Brownian motion: a concise introduction. Lecciones en Matemáticas, Universidad Central de Venezuela (1995).