25 Pages
English

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

-

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 14
Language English

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
(
U
+
t
)
,
sothat:
Theorem2.1
For
U
uniformandindependentof
Z
a
,
Z
a
(
U
+
·
)
la
=
w
Y
a
.
Asaconsequence,
Y
a
isastationaryprocessontheline,oronthecircle
R/Z
,aswasseen
aboveinanotherway.Afarlessobviousresultis:
Theorem2.2
For
U
uniformon
[0
,
1]
andindependentof
X
a
,
X
a
(
U
+
·
)
la
=
w
Y
a
.
Theproofwillbegivenlater.Thecase
a
=0ofTheorem2.2isjustVervaat’spath
transformation,since,asremarkedabove,
X
0
la
=
w
e
.In[10],onecanfindahostofsimilar
pathtransformationsconnectingtheBrownianbridge,excursionandmeander.
Corollary2.3
Theoccupationmeasuresof
X
a
,
Y
a
and
Z
a
coincide,andhavethe
distributionfunction
2
1

e

2
ax

2
x
.
Thisisalsothedistributionfunctionof
Y
a
(
t
)
foranyfixed
t
.
2Recallthatarandomvariable
W
isRayleighdistributedifPr(
W

x
)=
e

x/
2
.The
occupationmeasureof
X
a
(or
Y
a
,
Z
a
)isthe
2
nthelawofhalftheresiduallifeattime
a
of
W
:Pr((
W

a
)
/
2

x
|
W

a
)=
e

2
ax

2
x
.For
a
=0werecovertheDurrett–Iglehart
resultfortheoccupationmeasureoftheBrownianexcursion:itisthelawof
W/
2[15].
ProofofCorollary2.3
.Bydefinition,theoccupationmeasureof
X
a
isthelawof
X
a
(
U
),so,fromTheorem2.2,itisalsothelawof
Y
a
(0).Thesameistruefor
Z
a
by
Theorem2.1,andfor
Y
a
becauseitisstationary.Wehave
Y
a
(0)=sup(
as

b
(
s
))

1

s

0
la
=
w
sup(
b
(
t
)

at
)
1t0≤≤wal=
0
s

u
t

p
1
((1

t
)
B
1

tt

at
)

B
u

au

=
0

s
u
u

p
+

1+
u.

4

Forpositivenumbers
λ
and
µ
,set
T
λ,µ
=inf
{
u

0;
B
u

λu
+
µ
}
.
Usingtheexponentialmartingaleexp(2
λB
u

2
λ
2
u
),itiseasytoderivethat
Pr(
T
λ,µ
<
+

)=
e

2
λµ
,
see[28,ExerciseII.3.12].Wehavethus:

B
u

au
Pr(
Y
a
(0)

x
)=Pr

u

0suchthat

x
u+1=Pr(
T
a
+
x,x
<
+

)
2=
e

2
ax

2
x
.

Problem2.4
Whatarethelawsof
X
a
(
t
)
and
Z
a
(
t
)(
whichdependon
t
)
?
Weneedanadditionalnotationtodefinearandomshiftfrom
Y
a
or
Z
a
to
X
a
:let
T
(
X
)denotetheinverseprocessof
L
(
X
).
Theorem2.5
Suppose
a>
0
.Let
U
beuniformlydistributedon
[0
,
1]
andindependent
of
Z
a
or
Y
a
.Set
τ
=
T
aU
(
Z
a
)
,
τ
˜=
T
aU
(
Y
a
)
.

Wehave:

X
ala
=
w
Z
a
(
τ
+
·
)
la
=
w
Y
a
(
τ
˜+
·
)
.
NotethatasadifferencewithTheorems2.1and2.2,here
τ
(resp.
τ
˜)dependson
Z
a
(resp.
.)YaThusweobtain
X
a
byshiftinganyoftheprocessesuniformlyinlocaltime,whilewe
haveseenabovethatweobtain
Y
a
byshiftinguniformlyinrealtime.
Theorem2.6
Suppose
a>
0
.
(i)
.Almostsurely,
t

L
t
(
X
a
)

at
reachesitsmaximumatauniquepoint
V
in
[0
,
1)
and
law
X
a
(
V
+
·
)=
Z
a
.
(ii)
.Almostsurely,
t

L
t
(
Y
a
)

at
reachesitsmaximumatauniquepoint
V
˜
in
[0
,
1)
dnaY
a
(
V
˜+
·
)
la
=
w
Z
a
.
Moreover,
V
˜
isuniformon
[0
,
1]
andindependentof
Y
a
(
V
˜+
·
)
.

5

Incontrast,andasanexplanation,
t

L
t
(
Z
a
)

at
reachesitsmaximumat0,seethe
proofinSection11.Itiseasilyverifiedthat
V
is
not
uniformlydistributed.
Remark2.7
For
a
=0,Theorems2.5and2.6holdifweinsteaddefine
τ
=0,
V
=0
and
τ
˜=
V
˜astheuniquepointswhere
Z
0
,
X
0
and
Y
0
,respectively,attaintheirminimum
value0,seeRemark1.1.
Finally,weobservethatitispossibletoinvertΨ
a
andrecovertheBrownianbridge
b
from
Y
a

a
b
andtheexcursion
e
from
Z
a

a
e
usinglocaltimes.
Theorem2.8
Forany
t
,
b
(
t
)=
Y
a
(
t
)

Y
a
(0)

L
t
(
Y
a
)+
at
dnae
(
t
)=
Z
a
(
t
)

L
t
(
Z
a
)+
at.
CombiningTheorems2.6and2.8,wecanconstructBrownianexcursionsfrom
X
a
and
Y
a
too.
Corollary2.9
Let
V
and
V
˜
beasinTheorem
2.6
.Then
e

(
t
)=
X
a
(
V
+
t
)+
at

L
V
+
t
(
X
a
)+
L
V
(
X
a
)
dnae

(
t
)=
Y
a
(
V
˜+
t
)+
at

L
V
˜+
t
(
Y
a
)+
L
V
˜
(
Y
a
)
,
respectively,definenormalizedBrownianexcursions.
Inthecaseof
Y
a
,inaddition,
e

and
V
˜
areindependent.
Theproblemofpossibleothershiftsisaddressedintheconcludingremarks.

3Parkingschemesandassociatedspaces
A
parkingscheme
ω
describeshow
m
cars
c
1
,c
2
,...,c
m
parkon
n
places
{
1
,
2
,...,n
}
.
Wewrite
ω
=(
ω
k
)
1

k

m
,
whereeach
ω
k
∈{
1
,...,n
}
.Accordingto
ω
,car
c
1
parksonplace
ω
1
.Thencar
c
2
parks
onplace
ω
2
if
ω
2
isstillempty,elseittries
ω
2
+1,
ω
2
+2,...,untilitfindsanempty
place,andsoon.Weadopttheconventionthat
n
+1=1,andmoregenerally
n
+
k
=
k
.
Weconsideronlythecase1

m<n
.
TheinterestofcombinatoristsinparkingschemeswasbornfromapaperbyKonheim
&Weiss[21],in1966,abouthashingwithlinearprobing,apopularsearchmethod,that
hadalsobeenstudied,notably,byDonKnuth,in1962(seethehistoricalnotesinhis1999
paper[19],orpages526–539inhisbook[18]).Themetaphoreofparkingwasalreadyused
byKonheim&Weiss.ThetworecentandbeautifulpapersbyFlajolet,Poblete&Viola
[17]andKnuth[19]drewtheattentionoftheauthorstotheconnectionbetweenparking
schemesandBrownianmotion(seealso[13,14]).Forasimilarconnectionbetweentrees
andBrownianmotion,see[2,6,25,30],amongothers.

6

13
20
14
129
13
166
1111
14
148
17
15
192
1
185
12
7
9
1310
1620
4
6
311
13
21
14
2121212121129
13
166
1111
14
148
17
15
192
1
18
21
5
12
7
9
1310
1620
4
6
311
13
22
14
22
2121212121129
13
166
1111
14
14
22
8
17
15
192
1
18
21
5
12
7
9
1310
1620
4
6
311

232323232323
13
23
23
14
3222
2121212121
23
12
239
13
23
166
1111
14
14
22
8
17
15
192
1
18
21
5
127
9
13
2310
1620
4
6
311

242424242424
23
24
24
422323232323
24
23
2413
23
2414
22
24242121212121
23
12
239
13
23
24166
1111
14
14
22
8
17
15
192
1
18
21
5
127
9
13
23
24
10
1620
4
6
311
Figure1:Elementsof
P
25
,m
,
m
=20
,
···
,
24.

Let
P
n,m
denotethesetofallparkingschemesof
m
carson
n
places,andlet
CP
n,m
denotethesubsetof
confined
parkingschemes,
confined
meaningthatthelastplaceis
assumedtobeleftempty.Wehave
#
P
n,m
=
n
m
and#
CP
n,m
=
n
m

1
(
n

m
);
thelastcanbeseenasfollows.For
ω

P
n,m
,wedefinetheshift(rotation)

=(

1+
ω
k
)
1

k

m
,
movingallcarsbackoneplace(modulo
n
);theactionof
r
on
P
n,m
draws
n
m

1
orbitsof
n
elements,eachofthemcontaining
n

m
elementsof
CP
n,m
.
Let
Y
k
(
ω
)bethenumberofcarswhosefirsttryisonplace
k
,accordingto
ω

P
n,m
.
Foranynaturalinteger
k
,set
S
k
+1
(
ω
)=
S
k
(
ω
)+
Y
k
+1
(
ω
)
,
with
S
0
(
ω
)=0.Ourconventionextendsto
Y
k
+
n
=
Y
k
,sothat
S
k
+
n
=
S
k
+
m
.Set:
mW
(
ω,i
)=
S
i
(
ω
)

in,
(3.1)
andnotethat
W
(
ω,k
+
n
)=
W
(
ω,k
).Wehave

7

Proposition3.1
Thereexistsatleastanelementof
CP
n,m
,
x
(
κ
)
,ineachorbit
κ
,
suchthat
W
(
x
(
κ
)
,
·
)
isnonnegative.
Proof.
Let
ω
denoteanelementof
P
n,m
.Since
S
(
r
j
ω,k
)=
S
(
ω,k
+
j
)

S
(
ω,j
)
andthus
W
(
r
j
ω,k
)=
W
(
ω,k
+
j
)

W
(
ω,j
),
W
(
r
j
ω,
·
)isnonnegativeifandonlyif
W
(
ω,j
)=min
k
W
(
ω,k
).Thisprovesthat
x
(
κ
)=
r
j
ω
existsin
P
n,m
.Wepostponethe
proofthatinfact
r
j
ω

CP
n,m
toProposition5.4(seealso[13]).

Ingeneral,inthesameorbit
κ
,thereareseveralelements
z
suchthat
W
(
z,
·
)is
nonnegative:welet
x
(
κ
)beoneparticularchoice,andlet
E
n,m
bethesetofthe
n
m

1
elements
x
(
κ
).(Thissetisthustosomeextentarbitrary,buttheresultsbelowholdfor
anychoice.)

4Convergenceresults
For
ω
in
P
n,m
,let
H
k
(
ω
)denotethenumberofcarsthattry,successfullyornot,topark
onplace
k
.(Weregard
H
k
asdefinedforallintegers
k
,with
H
k
+
n
=
H
k
.)Werescale
H
k
3141129
13
166
1111
14
14815
2
1
5
12
7
9
1310
16
4
6
311

(h)tn

√t

Figure2:Profile.
anddefine
h
n
(
k/n,ω
)=
H
k
(
ω
)
/n
;
h
n
isthenextendedtoacontinuousperiodicfunction
on
R
,thatwecallthe
profile
of
ω
,bylinearinterpolation,i.e.
(1+

nt

nt
)
H

nt

(
ω
)+(
nt

nt

)
H
1+

nt

(
ω
)
h
n
(
t,ω
)=

.
nLet
µ
n,
(resp.
µ
˜
n,
,
µ
ˆ
n,
)denotethelawof(
h
n
(
t
))
0

t

1
when
ω
isdrawnatrandomin
P
n,n


(resp.
CP
n,n


,
E
n,n


).
Centraltoourresultsarethefollowingtheorems:
√Theorem4.1
If
-/n

a

0
,then
µ
n,w

ea

kly
Y
a
.
√Theorem4.2
If
-/n

a

0
,then
µ
˜
w

ea

kly
X
a
.
,n√Theorem4.3
If
-/n

a

0
,then
µ
ˆ
n,we

a

kly
Z
a
.

8

Theorem4.3wasalsoproved,bysimilarmethods,in[13,Theorem3.1&Lemma3.7].
Aswillbeseenindetaillater,Theorems2.1and2.2canbeseenasconsequencesof
theprecedingconvergenceresults,combinedwiththeevidentrelation
jh
n
(
t,r
j
ω
)=
h
n
t
+

nandwiththefollowingobviousstatement:therandomrotationofarandomelementof
CP
n,m
orof
E
n,m
givesarandomelementof
P
n,m
.Moreformally:
Proposition4.4
If
ω
israndomuniformon
P
n,m
,
CP
n,m
oron
E
n,m
,and
U
is
uniformon
[0
,
1]
andindependentof
ω
,then
r

nU

ω
israndomuniformon
P
n,m
.
AdifferentkindofrandomrotationgivesTheorem2.5:let
ω
berandomin
P
n,m
orin
E
n,m
andchooserandomlyanemptyplace
j
of
ω
.Then
r
j
ω
israndomin
CP
n,m
.More
formally,letusdefineanoperator
R
from
P
n,m
to
CP
n,m
asshiftingtothenextempty
place:

=
r
j
ω,
where
j

1isthefirstplaceleftemptyby
ω
.Thus
R

(
n

m
)
U

ω
(with
U
randomuniform)
isarotationof
ω
toarandomemptyplace,i.e.toarandomelementofthecorresponding
orbitin
CP
n,m
,andwehave:
Proposition4.5
If
ω
israndomuniformon
P
n,m
,
CP
n,m
oron
E
n,m
,and
U
is
uniformon
[0
,
1]
andindependentof
ω
,then
R

(
n

m
)
U

ω
israndomuniformon
CP
n,m
.
ForTheorem2.5weusealsotheconvergenceofthenumberofemptyplacesinagiven
intervalof
{
1
,
2
,...,n
}
tothelocaltimeof
X
a
,
Y
a
or
Z
a
inthecorrespondingintervalof
[0
,
1].
Moreprecisely,let
V
j,k
(
ω
)denotethenumberofemptyplacesintheset
{
j
+1
,j
+
2
,...,k
}
,accordingtotheparkingscheme
ω
,anddefine,inanalogywith
h
n
above,a
correspondingcontinuousfunction
v
n
on[0
,
1]byrescalingandlinearinterpolationso
√that
v
n
(
k/n
)=
V
0
,k
/n
forintegers
k
,i.e.
v
(
t,ω
)=(1+

nt

nt
)
V
0
,

nt

(
ω
)

+(
nt

nt

)
V
0
,
1+

nt

(
ω
)
,
0

t

1
.
nnWethenhavethefollowingextensionofTheorems4.1–4.3,yieldingjointconvergenceof
theprocesses
h
n
and
v
n
.
Theorem4.6
Suppose
-/n

a

0
.On
[0
,
1]
,thefollowinghold:
(i)
.If
ω
isdrawnatrandomin
P
n,n


,then
(
h
n
(
·

)
,v
n
(
·

))
l

aw

(
Y
a
,L
(
Y
a
))
.
(ii)
.If
ω
isdrawnatrandomin
CP
n,n


,then
(
h
n
(
·

)
,v
n
(
·

))
l

a

w
(
X
a
,L
(
X
a
))
.
wal(iii)
.If
ω
isdrawnatrandomin
E
n,n


,then
(
h
n
(
·

)
,v
n
(
·

))
−→
(
Z
a
,L
(
Z
a
))
.

√9

5Resultsonparkingschemes
Considerafixed
ω

P
n,m
.Asremarkedabove,weregardthefunctions
Y
k
,
S
k
,
W
(
ω,k
)
and
H
k
asdefinedforallintegers
k
;
S
k
+
n
=
S
k
+
m
andthethreeothershaveperiod
n
.
Notethat,amongthecarsthatvisitplace
k
,onlyonewillnotvisitplace
k
+1,so:
Proposition5.1
H
k
+1
=(
H
k

1)
+
+
Y
k
+1
.
Thisrecursiondoesnotdefinefully
H
k
,given(
Y
k
)
0

k

n
,astherecursionstartsnowhere.
Inordertocircumventthisdifficulty,wehavetofindaplaceleftemptyby
ω
.Let

k
=
i
m

a
k
x(
i

S
i
)=

n
+
m
k
a
<
x
i

k
(
i

S
i
)
.
(5.1)
Proposition5.2
Foragiven
ω
andplace
k
,therearetwocases:
(i)
.
k
isleftempty,
H
k
=0
,
k

S
k
=∆
k

1
+1
and

k
=∆
k

1
+1
.
(ii)
.
k
isoccupied,
H
k

1
,
k

S
k


k

1
and

k
=∆
k

1
.
Proof.
Clearly
k
isleftemptyifandonlyif
H
k
=0.
Next,observethatif
S
k

S
j

k

j
forsome
j<k
,thenatleast
k

j
carshavetried
toparkafter
j
,andthereisnotroomenoughforallofthemtoparkon
{
j
+1
,...,k

1
}
,
sooneofthemwillparkon
k
.Conversely,supposethatsomecarparkson
k
,andlet
j
be
thelastemptyplacebefore
k
.Thenthe
k

j
places
{
j
+1
,...,k
}
arealloccupied,and
thecarsonthemmustallhavemadetheirfirsttryinthesameset,so
S
k

S
j

k

j
.
Consequently,
k
isemptyifandonlyif
S
k

S
j
<k

j
forall
j<k
,whichisequivalent
to
k

S
k
>
max
j<k
(
j

S
j
)=∆
k

1
andthusalsoto∆
k
>

k

1
.
Finally,notethatalways
k

S
k

k

S
k

1

1+∆
k

1
,andthus∆
k

1


k


k

1
+1.
Thisleadstoanexplicitformulafor
H
k
,given
Y
k
.
Proposition5.3
Foranyinteger
k
,
H
k
=1+
S
k

k
+∆
k

1
.
Proof.
FirstobservethatbyProposition5.2,bothsidesvanishif
k
isempty.Wethen
proceedbyinduction,beginningatanyemptyplace(bothsideshaveperiod
n
).Going
from
k
to
k
+1,if
k
isoccupied,thenthelefthandsideincreasesbyProposition5.1by
H
k
+1

H
k
=
Y
k
+1

1whiletherighthandsideincreasesby
Y
k
+1

1+∆
k


k

1
,which
byProposition5.2equals
Y
k
+1

1too.Similarly,if
k
isempty,thenbothsidesincrease
by
Y
k
+1
.Hencetheequalityholdsforevery
k
.

WecanalsonowcompletetheproofofProposition3.1.
Proposition5.4
If
W
(
ω,i
)=min
k
W
(
ω,k
)
,thenplace
i
isempty.

♦01