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

Philippe Chassaing1

Description

Niveau: Supérieur, Doctorat, Bac+8
A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0 Philippe Chassaing1 & Svante Janson2 Summary. 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 di?erent ways, of profiles associated to hashing with linear probing, or, equivalently, to parking functions. Key words. Brownian bridge, Brownian excursion, local time, path transformation, profile, parking functions, hashing with linear probing. A.M.S.Classification. 60J65 (primary), 60C05, 68P10, 68R05 (secondary). Running head. Brownian bridge path transformation. 1Institut Elie Cartan, BP 239, 54 506 Vandoeuvre Cedex, France. 2Uppsala University, Department of Mathematics, PO Box 480, 751 06 Uppsala, Sweden 1

• dimensional brownian


• then ?ab


• shifting any


• any interesting


• brownian


• precise statements


• vervaat-like path


• brownian excursion


• xa


• sup

Sujets

• Uppsala University
• Cartan
• Brownian excursion

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 14
• Langue: English

Extrait

AVervaat-likepathtransformation
forthereflectedBrownianbridge
conditionedonitslocaltimeat
0
PhilippeChassaing
1
&SvanteJanson
2

Summary.
WedescribeaVervaat-likepathtransformationforthereflectedBrownian
bridgeconditionedonitslocaltimeat0:uptorandomshifts,thisprocessequalsthetwo
processesconstructedfromaBrownianbridgeandaBrownianexcursionbyaddingadrift
andthentakingtheexcursionsoverthecurrentminimum.Asaconsequence,thesethree
processeshavethesameoccupationmeasure,whichiseasilyfound.
Thethreeprocessesariseaslimits,inthreedifferentways,ofprofilesassociatedto
hashingwithlinearprobing,or,equivalently,toparkingfunctions.
Keywords.
Brownianbridge,Brownianexcursion,localtime,pathtransformation,
profile,parkingfunctions,hashingwithlinearprobing.
A.M.S.Classification.
60J65(primary),60C05,68P10,68R05(secondary).
Runninghead.
Brownianbridgepathtransformation.

1
InstitutElieCartan,BP239,54506VandoeuvreCedex,France.
2UppsalaUniversity,DepartmentofMathematics,POBox480,75106Uppsala,Sweden

1

•••1Introduction
WeregardtheBrownianbridge
b
(
t
)andthenormalized(positive)Brownianexcursion
e
(
t
)asdefinedonthecircle
R/Z
,or,equivalently,asdefinedonthewholerealline,being
periodicwithperiod1.Wedefine,for
a
≥
0,theoperatorΨ
a
onthesetofbounded
functionsonthelineby
Ψ
a
f
(
t
)=
f
(
t
)
−
at
−
−∞
in
<
f
s
≤
t
(
f
(
s
)
−
as
)
=sup(
f
(
t
)
−
f
(
s
)
−
a
(
t
−
s
))
.
(1.1)
ts≤If
f
hasperiod1,thensohasΨ
a
f
;thuswemayalsoregardΨ
a
asactingonfunctionson
R/Z
.Evidently,Ψ
a
f
isnonnegative.
Inthispaper,weprovethat,forevery
a
≥
0,thethreefollowingprocessescanbe
obtained(inlaw)fromeachotherbyrandomshifts,thatwewilldescribeexplicitly:
X
a
,whichdenotesthereflectingBrownianbridge
|
b
|
conditionedtohavelocaltime
atlevel0equalto
a
;
Y
a
=Ψ
a
b
;
Z
a
=Ψ
a
e
.
Wewillfindconvenienttousethefollowingformulasfor
Y
a
and
Z
a
:
Y
a
(
t
)=
b
(
t
)
−
at
+sup(
as
−
b
(
s
))
,
t
−
1
≤
s
≤
t
Z
a
(
t
)=
e
(
t
)
−
at
+sup(
as
−
e
(
s
))
.
t
−
1
≤
s
≤
t
For
t
∈
[0
,
1],wealsohave
Z
a
(
t
)=
e
(
t
)
−
at
+sup(
as
−
e
(
s
))
,
(1.4)
ts0≤≤consistentlywiththenotationsof[13].
Givenastochasticprocess
X
andapositivenumber
t
,welet
L
t
(
X
)denotethelocal
timeoftheprocess
X
atlevel0,ontheinterval[0
,t
],definedasin[10,p.154]by:
t1L
t
(
X
)=l
ε
i
↓
m
0
1
{−
ε<X
s
<ε
}
ds
;
ε20withthisconvention,e.g.,
b
and
|
b
|
havethesamelocaltimeat0,while,accordingtothe
usualconvention[28,
§
VI.2],thelocaltimeat0of
|
b
|
istwicethelocaltimeat0of
b
.When
possible,weextend
L
(
X
)to
t
∈
(
−∞
,
0),insuchawaythat
L
b
(
X
)
−
L
a
(
X
)isthelocal
timeoftheprocess
X
atlevel0,ontheinterval[
a,b
],foranychoice
−∞
<a<b<
+
∞
.
Thedefinitionaboveof
X
a
isformallynotpreciseenough,sinceitinvolvesconditioning
onaneventofprobability0.However,thereexistson
C
[0
,
1]auniquefamilyofconditional
distributionsof
|
b
|
(or
b
)given
L
1
(
b
)=
a
whichisweaklycontinuousin
a
≥
0[25,Lemma
12],andthiscanbetakenasdefiningthedistributionof
X
a
.Theprocess
X
a
hasbeenan
objectofinterestinanumberofrecentpapersinthedomainofstochasticcalculus:its

2

1()2.)3.1(

distributionisdescribedin[27,Section6]byitsdecompositioninexcursions.Thesequence
oflengthsoftheexcursionsiscomputedin[7],using[24].Thelocaltimeprocessof
X
a
isdescribedthroughanSDEinarecentpaper[25]byPitman,whoinparticularproves
that,uptoasuitablerandomtimechange,thelocaltimeprocessof
X
a
isaBessel(3)
bridgefrom
a
to0[25,Lemma14].(Seealso[5],whereaBrownianbridgeconditionedon
itswholelocaltimeprocessisdecribed.)
While
X
a
appearsasalimitinthestudyofrandomforests[25],
Z
a
appearsasa
limitinthestudyofparkingproblems,orhashing(see[13]),anoldbutstillhottopic
incombinatoricsandanalysisofalgorithms,theselastyears[1,14,17,19,26,31,32].
Thefragmentationprocessofexcursionsof
Z
a
appearsinthestudyofcoalescencemodels
[8,9,13],anemergenttopicinprobabilitytheoryandanoldoneinphysicalchemistry,
astronomyandanumberofotherdomains[4,Section1.4].See[4]forbackgroundandan
extensivebibliography,andalso[3,6,16]amongothers.Asexplainedlater,
Y
a
istightly
relatedto
Z
a
throughapathtransformation,duetoVervaat[33],connecting
e
and
b
.
Remark1.1
For
a
=0,wehave
X
0
la
=
w
e
[25,Lemma12]and,trivially,
Y
0
=
b
−
min
b
and
Z
0
=
e
,andtheidentityuptoshiftofthesereducestotheresultbyVervaat[33].
For
a
positive,thethreeprocesses
X
a
,
Y
a
and
Z
a
donotcoincidewithoutshifting.This
canbeseenbyobservingfirstthata.s.
Y
a
>
0,while
X
a
(0)=
Z
a
(0)=0,andsecondly
that
Z
a
a.s.hasanexcursionbeginningat0,i.e.inf
{
t>
0:
Z
a
(
t
)=0
}
>
0(see[8],
wherethedistributionofthisexcursionlengthisfound),whilethisisfalsefor
X
a
(asa
consequenceof[27,Section6]).Italsofollowsthat
Z
a
isnotinvariantundertimereversal
(while
X
a
and
Y
a
are).
Wementiontwofurtherconstructionsoftheprocessesabove.First,let
B
beastandard
one-dimensionalBrownianmotionstartedat0,anddefine:
τ
t
=inf
{
s
≥
0:
L
s
(
B
)=
t
}
.
Then
X
a
canalsobeseenasthereflectedBrownianmotion
|
B
|
conditionedon
τ
a
=1,see
e.g.[25,thelinesfollowing(11)]or[27,identity(5.a)].
Secondly,define
b
˜(
t
)=
b
(
t
)
−

01
b
(
s
)
ds
.Itiseasilyverifiedthat
b
˜isa
stationary
Gaussianprocess(on
R/Z
oron
R
),forexamplebycalculatingitscovariancefunction
Cov(
b
˜(
s
)
,b
˜(
t
))=1
−
6
|
s
−
t
|
(1
−|
s
−
t
|
)
,
|
s
−
t
|≤
1
.
21Since
b
and
b
˜differonlybya(random)constant,
Y
a
=Ψ
a
(
b
˜)too.Thisimpliesthat
Y
a
is
astationaryprocess.(
X
a
and
Z
a
arenot,againbecausetheyvanishat0.)
Wemaysimilarlydefine
e
˜(
t
)=
e
(
t
)
−
01
e
(
s
)
ds
,andobtain
Z
a
=Ψ
a
(
e
˜),butwedo
notknowanyinterestingconsequencesofthis.
Precisestatementsoftherelationsbetweenthethreeprocesses
X
a
,
Y
a
and
Z
a
are
giveninSection2.Thethreeprocessesariseaslimits,underthreedifferentconditions,
ofprofilesassociatedwithparkingschemes(alsoknownashashingwithlinearprobing).
ThisisdescribedinSections3and4.Theproofsaregivenintheremainingsections.

3

2Mainresults
Inthissectionwegiveprecisedescriptionsoftheshiftsconnectingthethreeprocesses
X
a
,
Y
a
and
Z
a
,inallsixpossibledirections.Let
a
≥
0befixed.
First,assumethattheBrownianbridge
b
isbuiltfrom
e
usingVervaat’spathtrans-
formation[10,11,33]:givenauniformrandomvariable
U
,independentof
e
,
b
(
t
)=
e
(
U
+
t
)
−
e
(
U
)
.
(2.1)
nehTΨ
a
b
(
t
)=Ψ
a
e