Reflected Brownian Bridge Area Conditioned on its Local Time at the Origin

Guy Louchard

Université libre de Bruxelles, Bruxelles (Belgique)

Algorithms Seminar

June 25, 2001

[summary by Michel Nguyen-The]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).
Abstract
Using properties of the Airy functions, we analyze the reflected Brownian bridge area Wb conditioned on its local time b at the origin. We give a closed form expression of the Laplace transform of Wb, a recurrence equation for the moments, leading to an efficient computation algorithm and an asymptotic form for the density f(x,b) of Wb for x ® 0.



1  Introduction

Let us first introduce the standard Brownian motion denoted by x(t) and a few classical variants: the reflected Brownian motion x+(t)=|x(t)|; the Brownian bridge B(t); the reflected Brownian bridge B+(t) on [ 0,1 ]; the Brownian excursion e(t).

The object of interest in this talk is Wb:=ò01 B+(t) dt, the area of the reflected Brownian bridge conditioned on having a local time at the origin equal to b. This random variable appeared in [4] as the limit law for m-3/2 Dm,m-b(m)1/2, where Dm,m-b(m)1/2 denotes the total displacement for a hash table with m locations and b(m)1/2 empty locations, using linear probing. It also represents the limit law for the total height of random forests with b(m)1/2 trees and m nodes or leaves. The only description of it was given by its moments, related to the classical Airy function Ai(z):= 1/pò0+¥cos(1/3t3+zt) dt (recall Ai''=zAi) in the following way:
E [ Wbk ] =k!
k
å
j=1
æ
ç
ç
è
 
å
k1,...,kj³ 1, S ki=k
j
Õ
i=1
wkj ö
÷
÷
ø
bj-1
j!
q3k-j-2(b),
where the wk are defined by the asymptotic expansion Ai'(z)/Ai(z) ~z®+¥ åk=0+¥wk (-1)kz-3(k-1)/2/2k, and qr(b):=ò0+¥xr/r!e-bx-x2/2 dt.

We will provide a closed form expression for the Laplace transform of Wb, a better way to compute its moments, and an asymptotic form for the density f(x,b) of Wb when x ® 0.

2  Laplace Transform of Wb

Computing the Laplace transform of Wb essentially requires using Kac's formula [3] and a few technicalities. Eq. (30) in [5, p. 491] states that, if we denote by t+(t,a) the local time of x(t) at a,
ó
õ
¥


0
e-a t E0 é
ê
ê
ê
ê
ë		 exp æ
ç
ç
ç
ç
è		 - ó
õ
t


0
x+(u) du-d t+(t,0) ö
÷
÷
÷
÷
ø		 ½
½
½
½
½
½		 x(t)=0 ù
ú
ú
ú
ú
û
dt
( 2p t)1/2
= æ
ç
ç
è		 d -
2*Ai'(2*a)
Ai( 2*a)
ö
÷
÷
ø		 -1,     (1)
where 2*:=21/3. From it we can derive the following theorem:
Theorem 1   The Laplace transform Q(z,b) of Wb has the closed form expression
Q(z,b)=E [ e-zWb ] =
-z1/3eb2/2
i 21/6(p)1/2
ó
õ
i¥


-i¥
eb z1/3 21/3 Ai'(u)/Ai(u)(Ai'(u)/Ai(u))'euz2/3/21/3 du.

Proof. Given [. ò0t x+(u) du |x(t)=0]ºD t3/2Y and t+(t,0) ºD (t)1/2 t+(1,0) (scaling property), Eq. (1) leads to
E 0 ó
õ
¥


0
e-a t ó
õ
¥


0
e-t3/2Wbb e-b2/2e-d (t)1/2 b
db dt
(2p t)1/2
=[d-2*L(a)]-1,
where L(a):=Ai'(2*a)/Ai(2*a). The change of variable v=(t)1/2b and an inversion on d delivers
ó
õ
¥


0
e-b2/2e-a v2/b2E [ e-v3/b3 Wb ]
2 db
(2p)1/2
= ev 2*L(a).     (2)
After setting b= v/(2*s)1/2, u=2*a, differentiating with respect to u and using (Ai'/Ai)'=u-(Ai'/Ai)2:
1
(2p)1/2
ó
õ
¥


0
e-us E [ e-(2)1/2 s3/2Wv/(2*s)1/2 ] e-v2/(24/3s)
ds
(2 s)1/2
=-ev 2*Ai'(u)/Ai(u)(Ai'(u)/Ai(u))'.
The inversion formula for Laplace transforms then writes:
E [ e-(2)1/2 s3/2Wv/(2*s)1/2 ] e-v2/(24/3s)/(4ps)1/2 =
-1
2p i
ó
õ
i¥


-i¥
ev 2*Ai'(u)/Ai(u)(Ai'(u)/Ai(u))'eus du.     (3)
Now set v=b(2*s)1/2, z=(2)1/2s3/2, Q(z,b)=E[e-zWb]. Eq. (3) becomes
21/6Q(z,b)e-b2/2
2(p)1/2
=
-z1/3
2p i
ó
õ
i¥


-i¥
eb z1/3 2*Ai'(u)/Ai(u)(Ai'(u)/Ai(u))'euz2/3/2* du
which proves the theorem.




3  Recurrence Formulae

Using Laplace transforms and inversions of Laplace transforms, we show here how to find an algorithm to compute the moments yk(b):=E[Wbk] by recurrence. We first need:
Lemma 1  Define G(h):=2*L(a)/(a)1/2 and s=1/b2; we have
ó
õ
¥


0
e-1/(2s)e-ws(-1)k s3/2kyk(b)
ds
s3/2(2p)1/2k!
= [hk]
e(w)1/2G0
w3/2k
¥
å
i=1
( (w)1/2 ( G(h)-G0 ) ) i
i!
.     (4)

Proof. Set s:=1/b2, w=a v2, and h=a-3/2. Eq. (2) becomes
ó
õ
¥


0
e-1/(2s)e-wsE [ e-h w3/2s3/2Wb ]
ds
s3/2(2p)1/2
= e(w)1/2G(h),
Set G0:=G(0). Eq. (3) leads to
ó
õ
¥


0
e-1/(2s)e-wsE [ e-h w3/2s3/2Wb-1 ]
ds
s3/2(2p)1/2
= e(w)1/2G(h)-e(w)1/2 G0                  
 
= e(w)1/2 G0
¥
å
i=1
( (w)1/2 ( G(h)-G0 ) ) i
i!
.  
                    (5)
Upon expanding both sides of (5) with respect to h, this gives the desired formula.




To invert the Laplace transforms of the form e-(2w)1/2/w(j+1)/2, we will use the following lemmas:
Lemma 2   Set f(1)(x):=f(x):=1/(2p)1/2ò-¥xe-t2/2 dt (classical Gaussian distribution function) and f(j+1)(x):=ò-¥x f(j)(u) du. Then
ó
õ
¥


0
f(j )(-b) e-ws
(2s)(j+1)/2
s
 ds =
e-(2w)1/2
w(j+1)/2
,   j³ 1,     where b=1/(s)1/2.

Proof.[Sketch of proof] Ones proves the lemma by induction and uses an integration by part and an integration with respect to w to prove it at rank k+1 from rank k.


Lemma 3   The f(j )(x) can be expressed in the form:
f(k )(z)= p1(k,z) f(z)+p2(k,z)e-z2/2/(2p)1/2,
where p1(k,z) is of degree k-1, p2(k,z) is of degree k-2.
Using integration by parts on ò-¥z xj f(x) dx and identification of coefficients, it is possible to prove the following proposition, enabling us to compute nice expressions of the f(j )(x):
Proposition 1   Define, for k³1, j³0, P1[k,j]:=[zj]p1(k,z), and P2[k,j]:=[zj]p2(k,z). Then the sequences (P1[k,j])k³ 1,j³ 0 and (P1[k,j])k,j³ 0 are defined by the initial values P1[1,0]=1, P2[1,0]=0, P1[1,j]=P2[1,j]=0 for j³1, and the recurrence relations, for k³1:
P1[k+1,j] :=P1[k,j-1]/j,   j=1,...,k,                  
P2[k+1,j]
:=
ë (k-1-j)/2 û
å
l=0
P1[k,j+2l]/(j+2l+1)(j+2l+1)l
                 
 
     -
ë (k-3-j)/2 û
å
l=0
P2[k,j+2l+1](j+2l+1)l,    j=0,...,k-1,
                 
P1[k+1,0]
:= -
 
å
l=1,3,...,k-1
P1[k,l]/(l+1) (l+1)(l+1)/2 +
 
å
l=0,2,...,k-2
P2[k,l](l)l/2.
                 

Determining a recurrence relation for the moments yk(b) hence amounts to determining a recurrence relation for the Zj defined by (see (4)):
(-1)j b-3j
Zj
j!
=[hj]
1
w3/2j
¥
å
i=1
( (w)1/2 ( G(h)-G0 ) ) i
i!
.
Indeed, along the mechanical transfer rule 1/w(l+1)/2® f(l)(-b)/bl+1b2 2(l+1)/2, yj(b) is equivalent to Zj(2p)1/2eb2/2/b3. To get a recurrence formula giving Zk in function of the Z1,...,Zj, we introduce
Sk(h):=
k
å
j=1
(-1)j b-3j
Zj
j!
w3j/2hj =
k
å
j=1
hj [hj] æ
ç
ç
ç
ç
ç
è
k
å
l=1
(-1)l (dl-cl) æ
ç
ç
è
3h
23/2
ö
÷
÷
ø		 l
k
å
l=0
(-1)l cl æ
ç
ç
è
3h
23/2
ö
÷
÷
ø		 l
ö
÷
÷
÷
÷
÷
ø		 j
( -(2w)1/2 ) j
j!
,
where the coefficients cl and dl are defined in [1, Eq. (10.4.59) and (10.4.61)] by asymptotic expansions of Ai and Ai' for |z| large, |arg(z)|<p:
Ai(z) ~
1
2(p)1/2
z-1/4e-z
¥
å
k=0
(-1)k ck z-k,   Ai' (z) ~ -
1
2(p)1/2
z1/4e-z
¥
å
k=0
(-1)k dk z-k,
with z:=2/3 z3/2. More explicitly: c0=1, ck=G(3k+1/2)/(G(k+1/2)·54k k!), d0=1, dk=-6k+1/6k-1ck. The relation
[hk]
k
å
j=1
(-1)j b-3j
Zj
j!
w3j/2hj æ
ç
ç
è
k
å
l=0
(-1)l cl æ
ç
ç
è
3h
23/2
ö
÷
÷
ø		 l ö
÷
÷
ø		 k
k
å
j=1
æ
ç
ç
è
-(2)1/2
z
ö
÷
÷
ø		 j
1
j!
æ
ç
ç
è
k
å
l=1
(-1)l (dl-cl) æ
ç
ç
è
3h
23/2
ö
÷
÷
ø		 l ö
÷
÷
ø		 j æ
ç
ç
è
k
å
l=0
(-1)l cl æ
ç
ç
è
3h
23/2
ö
÷
÷
ø		 l ö
÷
÷
ø		 k-j
provides an algorithm that can easily be implemented in Maple and proves more tractable than the general expressions of the moments given by Janson.

4  Asymptotic Form of Density

4.1  Asymptotics of f(x,b) as b ® ¥

Using E[Wb] ~ 1/2b and Var[Wb] ~ 1/4b4 as b ® ¥, already mentioned in [4], asymptotics of (logAi)' and (logAi)', and a saddle point method, we recover the fact that we obtain a density of a Gaussian distribution when b ® ¥.

4.2  Asymptotics of Q(z,b) as |z| ® ¥

Using a saddle point again, setting z=k6, we obtain
Q ~ ek3 µ1 e-a1 k4/2* æ
ç
ç
è
21/2 k3/2
2 b3/4
+
b1/4 21/6 a1
4 k1/2
+O æ
ç
ç
è
1
k3/2
ö
÷
÷
ø		 ö
÷
÷
ø		 .

4.3  Asymptotics of f(x,b) as x®0

The formula f(x,b)=1/2p i òc-i¥c+i¥ exzQ(z,b) dz, c>0, the former asymptotics and a saddle point method lead to:
f(x,b) ~ eµ2/x2
(2)1/2
(p)1/2
æ
ç
ç
è
31/4 a19/4
9 x11/4 b3/4
-
33/4 a13/4
3 x9/4 b1/4
+
b1/431/4(27+16 a13)
x7/4a13/4
+O æ
ç
ç
è
1
x5/4
ö
÷
÷
ø		 ö
÷
÷
ø		 .

5  Open Questions

It remains to find an asymptotic form for the density f(x,b) as x ® ¥---this not even known for the classical Airy density---and an explicit form for the density f(x,b). Are also missing an analysis of the local time t+(t,a) of B+(t) at a, conditioned on its local time b at the origin, and some analytic variations on Wb (see [2] for the classical Airy distribution).

References

[1]
Abramowitz (Milton) and Stegun (Irene A.) (editors). -- Handbook of mathematical functions, with formulas, graphs, and mathematical tables. -- Dover Publications Inc., New York, 1966, xiv+1046p.

[2]
Flajolet (P.) and Louchard (G.). -- Analytic variations on the Airy distribution. Algorithmica, vol. 31, n°3, 2001, pp. 361--377. -- Mathematical analysis of algorithms.

[3]
Itô (Kiyosi) and McKean, Jr. (Henry P.). -- Diffusion processes and their sample paths. -- Springer-Verlag, Berlin, 1974, xv+321p. Second printing, corrected, Die Grundlehren der mathematischen Wissenschaften, Band 125.

[4]
Janson (Svante). -- Asymptotic distribution for the cost of linear probing hashing. Random Structures & Algorithms, vol. 19, n°3-4, 2001, pp. 438--471.

[5]
Louchard (G.). -- Kac's formula, Levy's local time and Brownian excursion. Journal of Applied Probability, vol. 21, n°3, 1984, pp. 479--499.
This document was translated from LATEX by HEVEA.