Uni e si a Poli `ecnica de Ca alunya
Facul a de Ma em`a iques i Es ad´ıs ica
Deg ee in Ma hema ics
Bachelo ’s Deg ee Thesis
Gene a ing Uni o m Spanning T ees
om condi ioned
Bienaym´e-Gal on-Wa son ees
Albe Vi es
Supe ised by O iol Se a
Janua y 2025
I would like o exp ess my hea el g a i ude o my supe iso , O iol Se a. Thank you so much
o guiding me h ough hese pas mon hs and o gi ing me he inc edible oppo uni y o explo e he
ascina ing wo ld o andom ees unde you guidance.
I mus also exp ess my hea el g a i ude o my pa en s, especially my mo he . Thank you o ins illing
in me an admi able sense o discipline in my s udies. Thank you o eaching me o igh un il he e y
end, and o showing me ha no hing is e e uly los . I lo e you, Mom. And hank you, Dad, o being
so inc edibly p oud o me.
I am deeply g a e ul o my iend Lau i a. Thank you o li ing me up e e y ime I needed i h oughou
hese yea s. I would gladly go h ough his deg ee a housand imes i i mean doing i by you side.
I mus also ex end my since e g a i ude o all he p o esso s who ha e guided me a his wonde ul
acul y. Thank you o he knowledge you’ e sha ed and o you pa ience wi h my coun less la e-nigh
emails illed wi h ques ions. I couldn’ ha e asked o a be e place o lea n.
I mus men ion my belo ed he apis . Thank you o eaching me so much abou emo ional manage-
men . Thank you o helping me espec and unde s and mysel . I owe you a g ea deal.
Las ly, I wan o exp ess g a i ude o mysel o pe se e ing h ough challenges, emb acing ailu e as
a lesson, and e using o se le o he i s ”no.” My discipline and de e mina ion ha e been unwa e ing,
bu abo e all, i is my esilience ha has allowed me o ise ime and ime again, ul ima ely b inging me
o whe e I s and oday.
Abs ac
This hesis explo es he p oblem o gene a ing uni o m spanning ees (USTs), which a e essen ial s uc-
u es in combina o ics and p obabili y wi h applica ions in ne wo k heo y and physics. Using condi ioned
Bienaym´e–Gal on–Wa son (BGW) p ocesses, i p oposes a no el me hodology o gene a e USTs uni o mly.
Th ough igo ous p oo s, i shows ha condi ioning hese s ochas ic models on he numbe o e ices
p oduces uni o mly dis ibu ed spanning ees. In addi ion o explo ing s uc u al p ope ies such as heigh ,
wid h, and lea dis ibu ion, he hesis p o ides sha p lowe bounds o he heigh and wid h o he ees,
suppo ed by igo ous p oo s. These indings no only en ich he heo e ical and p ac ical unde s anding o
USTs bu also b idge s ochas ic p ocesses wi h combina o ial applica ions, o e ing new insigh s and ools
o spanning ee gene a ion.
Keywo ds
Random T ees, Bienaym´e-Gal on-Wa son ees
1
Con en s
1 In oduc ion 3
2 A Misleading Me hod o Gene a ing Uni o m Spanning T ees 4
3 Wilson’s algo i hm 6
4 Bienaym´e-Gal on-Wa son ees 11
4.1 Ob aining some uni o m spanning ees om BGW ees . . . . . . . . . . . . . . . . . . 13
5 S udying some pa ame e s o andom ees 16
5.1 SomeP elimina ies ...................................... 16
5.2 Thewid h ........................................... 22
5.3 Theheigh ........................................... 25
5.3.1 A modi ied Bienaym´e-Gal on-Wa son ee . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Thenumbe o lea es..................................... 30
6 Bina y sea ch ees 31
6.1 Heigh o a Random Bina y Sea ch T ee . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7 Conclusions 39
A An example o a B ead h-Fi s Sea ch (BFS) 41
B An example o a Lexicog aphic Dep h-Fi s Sea ch (DFS) 43
2
1. In oduc ion
The gene a ion o uni o m spanning ees (USTs) has become an essen ial p oblem in he ield o com-
bina o ics and p obabilis ic p ocesses, gi en hei widesp ead applica ions in ne wo k analysis, andom
s uc u es, and s a is ical physics. A spanning ee o a g aph is de ined as a connec ed subg aph ha
includes all e ices wi h no cycles. When spanning ees a e sampled uni o mly a andom, each spanning
ee o he g aph has an equal p obabili y o being chosen. This uni o mi y condi ion p esen s signi ican
ma hema ical challenges in de ining an app op ia e andom model suscep ible o being analyzed, d i ing
he sea ch o e ec i e app oaches o sol e he p oblem.
This hesis explo es no el app oaches o gene a ing uni o m spanning ees using condi ioned Bienaym´e-
Gal on-Wa son (BGW) p ocesses. These p ocesses, o iginally concei ed o model he g ow h o popula ions,
a e he e adap ed o gene a e spanning ees unde uni o m dis ibu ions. The in insic andomness o
BGW p ocesses p o ides a na u al amewo k o s udy spanning ees, b idging classical combina o ics wi h
s ochas ic p ocesses. In his hesis, we also p o ide explici and clea e e ences o he commonly accep ed
no ion in he li e a u e ha his me hod is a obus app oach o gene a ing uni o m spanning ees.
The p ojec begins wi h an explo a ion o di e en app oaches o gene a ing uni o m spanning ees,
s a ing wi h an in ui i e, ye undamen ally lawed, me hod ha highligh s he challenges o achie ing
uni o mi y in p obabili y dis ibu ions, in sec ion 2. This se s he s age o a e iew o exis ing obus
me hods, ocusing on Wilson’s algo i hm, in sec ion 3, widely ecognized o i s e iciency and i s heo e ical
ounda ion in loop-e ased andom walks. I s analysis no only highligh s i s s eng hs bu also es ablishes
a benchma k o compa isons wi h he no el echniques p oposed in his s udy.
A cen al ocus o his hesis is he adap a ion o BGW p ocesses o he gene a ion o spanning ees.
De ailed ma hema ical o mula ions and igo ous p oo s show in sec ion 4 ha condi ioning hese p ocesses
on ha ing a ixed numbe o e ices yields uni o m spanning ees. Classical dis ibu ions such as Poisson,
Geome ic, and Be noulli b anching a e in es iga ed o illus a e he e sa ili y and co ec ness o his
amewo k.
In addi ion o he heo e ical aspec s, his wo k del es deeply in o he ypical s uc u al cha ac e is ics o
andom ees using he p oposed model. The ypical heigh and wid h a e analyzed in sec ion 5 as p ima y
me ics o unde s anding he complexi y and a iabili y o hese ees, complemen ed by he analysis o
he numbe o lea es o Cayley ees. The esul s a e classical in he a ea and hey a e usually ob ained
by he use o gene a ing unc ions, see e.g. D mo a [7]. The app oach p esen ed he e uses condi ioned
BGW ees and ollow he ela i ely ecen con ibu ion by Adda io-Be y, De oye and Janson [1]. In ac ,
he esul s ob ained he e apply o a wide class o ees o he han uni o m spanning ees and mo eo e
es ablish igh uppe bounds on he de ia ion o he heigh and wid h o andom ees om which he
classical esul s on hese pa ame e s can be de i ed. Resul s conce ning hese pa ame e s p o ide insigh s
in o he asymp o ic beha io o he s uc u es, suppo ed by igo ous p obabilis ic bounds and illus a i e
examples ha unde sco e hei p ac ical ele ance. The conclusions de i ed om hese analyses con ibu e
o a b oade unde s anding o uni o m spanning ees and hei gene a ion h ough p obabilis ic echniques.
Finally, in sec ion 6, we ocus on he pa icula case o he heigh o bina y sea ch ees, using di e en
me hods om hose in oduced ea lie in his wo k. Addi ionally, we obse e ha b anching p ocesses play
a ole in he p oo , bu in a manne dis inc om hei p e ious applica ions.
3
Random T ees
2. A Misleading Me hod o Gene a ing Uni o m
Spanning T ees
Ou aim is o de elop an algo i hm ha gene a es andom ees such ha he p obabili y o ob aining
any speci ic ee wi h n e ices is 1/nn−2. In o he wo ds, ou goal is o ensu e a uni o m p obabili y
dis ibu ion o e all spanning ees o he comple e g aph Kn. A i s glance, a seemingly na u al app oach
o achie e his migh be he ollowing:
Le V={ 1, ... , n}be a se o n e ices. We andomly choose a e ex om Vwi h p obabili y
1/n, le ’s call i u1, and conside he new se o e ices U={u1}. Nex , we choose ano he e ex wi h
uni o m p obabili y, call i u2, and connec i o u1. We add u2 o U, so ha U={u1,u2}. We i e a e he
same p ocess o selec a e ex u3, and connec i o one e ex om Uchosen andomly. Tha is, in he
i- h i e a ion, we selec a e ex om V Uuni o mly and connec i o one o he i−1 al eady connec ed
e ices, chosen a andom.
P oposi ion 2.1. The p e iously de ined algo i hm gene a es a ee.
P oo . We will p o e his by induc ion on he numbe o i e a ions.
-Base case: Fo i= 1, we ha e a single e ex, which i ially o ms a ee.
-Induc i e hypo hesis: Assume ha a e ii e a ions, he se o e ices {u1, ... , ui}gene a es a ee.
-Induc i e s ep: We need o show ha a e i+ 1 i e a ions, he se o e ices {u1, ... , ui+1}also
o ms a ee.
Conside he ee o med by he e ices {u1, ... , ui}, which, by he induc i e hypo hesis, is a ee. In
he (i+ 1)- h i e a ion, we add he e ex ui+1, connec ing i o exac ly one o he e ices {u1, ... , ui}.
This adds ui+1 as a deg ee-1 e ex o he g aph, so no cycles can be c ea ed by his connec ion.
I a cycle we e o o m, i would ei he al eady exis among {u1, ... , ui}, which con adic s he induc i e
hypo hesis, since he s uc u e is a ee.
Despi e wha in ui ion migh sugges , he p obabili y o ob aining any gi en ee is no uni o m. This
can be easily seen wi h a coun e example. We will calcula e he p obabili y o ob aining he s a wi h ou
e ices cen e ed a e ex u1using he p e iously desc ibed algo i hm.
The algo i hm p oceeds as ollows:
1. We andomly selec a e ex o be u1, he i s e ex in he se . Any e ex can be he cen e o
he s a , so we can assume ha u1is he cen al e ex. We choose i wi h p obabili y equals o 1/4.
4
2. In he second s ep, we choose ano he e ex u2 andomly om he emaining h ee e ices and
connec i o u1. This is he i s s ep owa ds o ming he s a ee. Since he choice o he e ex makes
no di e ence o he s a ee, as u2,u3,u4will ha e deg ee 1, his p obabili y equals 1.
3. In he hi d s ep, we choose he nex e ex u3and connec i o one o he al eady connec ed
e ices (u1o u2). Fo he s a s uc u e o be main ained, u3mus be connec ed o u1( he cen al
e ex). The p obabili y o his happening is 1
2, as he e a e wo e ices connec ed (u1and u2), and we
need u3 o be connec ed o u1.
4. In he ou h s ep, we choose he las e ex u4and connec i o one o he connec ed e ices
(u1,u2,u3). Again, o he s a s uc u e o hold, u4mus be connec ed o u1. The p obabili y o his
happening is 1
3, as he e a e h ee connec ed e ices (u1,u2,u3), and we need u4 o be connec ed o u1.
Thus, he o al p obabili y o ob aining he s a ee is:
P(S a cen e ed a u1) = 1
4×1
2×1
3=1
24.
The e o e, he p obabili y o gene a ing a s a ee wi h 4 e ices is 1
24, which is di e en om 1
16.
Then, we conclude ha no all ees ha e he same p obabili y o occu .
u1
u2
u3
u4
Figu e 1: S a ee wi h 4 e ices cen e ed a u1
5
Random T ees
Di e en p obabili y dis ibu ions o Zlead o di e en BGW ees. I is so in ui i e ha he specie
explodes i he expec ed numbe o child en pe indi idual is g ea e han 1, and bound o ex inc i i is
less han one. Then, his pa ame e is impo an o be s udied.
m=E[Z] = E[Z1] = ∞
X
k=0
kpk= ′(1)
The second equali y holds because, in he i s gene a ion, he e is only one indi idual wi h he ep o-
duc ion p obabili y dis ibu ion Z. Now, le ’s conside he ollowing:
n(s) = E[sZn] (de .)
We aim o ela e he unc ion nwi h he unc ion . Le X(i) deno e he numbe o descendan s
gene a ed by indi idual iin gene a ion n−1. By he de ini ion o he BGW p ocess, he andom a iables
X(i) and X(j) a e independen and iden ically dis ibu ed, each ollowing he p obabili y dis ibu ion Z.
Thus, we ha e:
n(s) = E[sZn] = EhE[sZn|Zn−1]i=EhEhsX(1)+···+X(Zn−1)ii
=E
Zn−1
Y
j=1
E[sX(j)]
=E
Zn−1
Y
j=1
(s)
=E[ (s)Zn−1] = n−1( (s)).
By induc ion:
n(s) = (n)(s)
whe e (n)deno es he n- h composi ion o wi h i sel .
We will show how E[Z] a ec s he p obabili y o ex inc ion in a popula ion. Le αn=P(Zn= 0) be he
ex inc ion p obabili y o gene a ion nand deno e by α=P(∪n≥1{Zn= 0}) = limn→∞ αn he p obabili y
o ex inc ion a some ime n. Then, we ha e:
αn=P(Zn= 0) = n(0) = ( n−1(0)) = (αn−1).
I we conside n→ ∞, hen α= (α). The e o e, he ex inc ion p obabili y is a ixed poin o he
unc ion . Recall ha (0) = p0<1 and (1) = 1. The e o e αis he i s ixed poin in he in e al
[0, 1]. Wi h his, and knowing ha E[Z] = ′(1) and ′′(s) = E(Z(Z−1)sZ−2)>0, so he unc ion is
con ex in [0, 1], i is clea ha we can dis inguish he ex inc ion p obabili y based on he ollowing cases:
•I E[Z]<1, he i s ixed poin is eached a s= 1. Thus, he popula ion is ce ain o become
ex inc . This case is called subc i ical.
12
•I E[Z]>1, he i s ixed poin mus occu be o e s= 1, which means ha he p obabili y o he
species’ su i al is non-ze o. This case is called supe c i ical.
•I E[Z] = 1, we call his case c i ical. We mus conside he alue o p0:
–I p0>0, we ha e a si ua ion analogous o he i s case.
–I p0= 0, i is clea ha
(1) = ′(1) ⇒P(Z= 2) = P(Z= 3) = ··· = 0 ⇒P(Z= 1) = 1.
4.1 Ob aining some uni o m spanning ees om BGW ees
Depending on he p obabili y dis ibu ion go e ning he ep oduc ion o indi iduals, one may ob ain di e en
ypes o ees. Speci ically, we aim o p o e ha i we condi ion a Bienaym´e-Gal on-Wa son ee o ha e
n e ices, and ix ce ain known dis ibu ions, we ob ain a ious ypes o uni o m andom ees. The i s
desc ip ion o andom ees om condi ioning a BGW p ocess by i s o al p ogeny can be aced back o
Kolchin [14] and Aldous [4].
In his chap e , we also p o ide explici p oo s o a ious ounda ional concep s ha a e o en aken o
g an ed in he li e a u e. Many o hese p oo s, while implici ly assumed, a e no always p o ided explici ly,
as hey a e conside ed s anda d esul s wi hin he ield. He e, we aim o p esen hese de i a ions clea ly
and igo ously.
Lemma 4.1. Le X be a BGW(Z) p ocess. Le Tndeno e he class o ees wi h n e ices which can be
gene a ed by he p ocess and le T ∈Tnbe a ee in he class. I he p obabili y ha T is gene a ed by
he p ocess depends only on he numbe o e ices n, hen
P(X=T||X|=n) = 1
|Tn|.
P oo . Le ’s deno e P(T=T) by (n), whe e nis he numbe o e ices o T. Then, he p obabili y o
gene a ing a ee wi h n e ices is:
P(|X|=n) = |Tn| (n)
since he las p obabili y is he sum o he p obabili ies o ob aining each o he ees wi h n e ices.
Now, when condi ioned on ha ing n e ices, all possible ees a e equally likely o occu :
P(X=T| |X|=n) = P(X=T}∩{|X|=n})
P(|X|=n)= (n)
|Tn| (n)=1
|Tn|
We now aim o p o e ha , by selec ing an app op ia e ep oduc ion p obabili y dis ibu ion, i is possible
o gene a e se e al well-known ypes o ees.
13
Random T ees
Rema k 4.2.I Xis a disc e e andom a iable aking alues in nonnega i e in ege s, i is said o ha e a
Poisson dis ibu ion wi h pa ame e λ > 0 i i has he ollowing p obabili y dis ibu ion:
P(X=k) = λke−λ
k!,k= 0, 1, 2, ...
The class o labeled ees wi h nnodes is also called he class o Cayley ees, due o he Cayley o mula
enume a ing hem, i s numbe being nn−2.
Theo em 4.3. Condi ioning a Poisson(1) Bienaym´e-Gal on-Wa son ee on ha ing n e ices esul s in all
Cayley ees wi h n e ices being gene a ed uni o mly.
P oo . E e y oo ed Cayley ee can be gene a ed om a Poisson(1) BGW p ocess by a labeling o i s
e ices. Le Tbe a speci ic Cayley ee wi h n e ices. To p o e ha each ee can be ob ained
uni o mly, we i s need o o de all sibling se s in Tby inc easing e ex labels. Le χ1, ... , χn ep esen
he numbe o child en o each node, lis ed in p eo de a e sal. The i s equi emen o gene a ing T
is ensu ing he co ec numbe o descendan s o each e ex. Since hese andom a iables a e pai wise
independen , he p obabili y o ob aining a speci ic numbe o child en o all e ices is he p oduc o
hei indi idual p obabili ies.
The second equi emen is assigning he co ec labeling, as we a e conside ing labeled ees. Wi h
n e ices, he e a e n! possible ways o label hem. Mo eo e , he child en o he i- h e ex can be
pe mu ed in χi! dis inc ways o each i= 1, ... , n, esul ing in he same ee. Thus, he inal calcula ion
can be exp essed clea ly as ollows:
P(T=T) = n
Y
i=1
1
χi!·e−1!·Qn
i=1 χi!
n!=e−n1
n!
Since he las p obabili y depends only on he numbe o e ices, and i is known ha he e exis nn−2
labeled ees, by lemma 4.1 he heo em is p o ed.
The class Bno Full Bina y T ees o n e ices is he amily o unlabelled oo ed plane ees whe e e e y
node has wo o ze o child en. Being plane means ha ees ha e dis inguished le and igh sub ees.
The ees depic ed in Figu e 4 a e conside ed o be dis inc .
Figu e 4: Two dis inc bina y ees
A ull bina y ee wi h nnodes has an odd numbe no e ices and m= (n+ 1)/2 lea es. I s numbe
is he Ca alan numbe Cm−1.
Theo em 4.4. Condi ioning a 2Be(1/2) Bienaym´e-Gal on-Wa son ee on ha ing n e ices esul s in all
Bina y ees wi h n e ices being gene a ed uni o mly.
14
P oo . I is clea ha one can ob ain e e y bina y ee om a 2Be(1/2) BGW ee and ice e sa. Le T
be a pa icula Bina y ee wi h n e ices. I is known ha in a Bina y ee he e a e (n−1)/2 in e nal
nodes, and (n+ 1)/2 lea s. To apply lemma 4.1, we need o calcula e P(T=T). Le χ∼2Be(1/2).
P(T=T) = P(χ= 0)n+1
2P(χ= 2)n−1
2=1
2n
Since he las p obabili y depends jus on he numbe o e ices, by lemma 4.1 we ha e p o ed he
heo em.
The class Pno o de ed plane ees wi h n e ices is he amily o oo ed unlabelled ees whe e he
child en o e e y node a e o de ed om le o igh in he plane.
Theo em 4.5. Condi ioning a Geom(1/2) Bienaym´e-Gal on-Wa son ee on ha ing n e ices esul s in all
o de ed plane ees wi h n e ices being gene a ed uni o mly.
P oo . I can be obse ed ha e e y o de ed plane ee can be ob ained om a Geom(1/2) BGW ee, and
con e sely, e e y Geom(1/2) BGW ee co esponds o an o de ed plane ee. Le Tbe a speci ic o de ed
plane ee wi h n e ices. To gene a e such a ee, i is necessa y o accoun o bo h in e nal nodes and
lea es.
The p obabili y o an in e nal node ha ing exac ly kchild en is (1/2)k(1/2), whe e he i s ac o
ep esen s he p obabili y o success ully ha ing kchild en, and he second ac o accoun s o he p obabili y
o no addi ional child en. Fo a lea , he equi emen is simply o ha e no child en, which occu s wi h
p obabili y 1/2.
Consequen ly, he p obabili y o achie ing he co ec numbe o child en o each e ex is independen
o whe he he e ex is an in e nal node o a lea . This p obabili y is gi en by (1/2)χi+1, whe e χideno es
he numbe o child en o e ex i. Thus, he ollowing conclusion na u ally a ises:
P(T=T) =
n
Y
i=1 1
2χi+1
=1
2Pn
i=1 χi+1
=1
2n−1+n
=1
22n−1
Fu he mo e, i is usually known ha he numbe o o de ed plane ees wi h n e ices is Cn−1, whe e
Cnis he n- h ca alan numbe . Hence, by lemma 4.1, he heo em has been p o ed.
Figu e 5: A andom ee wi h 7 e ices, gene a ed using a geome ic (1/2) dis ibu ion
15
Random T ees
5. S udying some pa ame e s o andom ees
This chap e is ocused on he s udy o key pa ame e s o andom ees: heigh , wid h, and he numbe
o lea es. All esul s p esen ed in his sec ion a e de i ed om he s udy L. Adda io-Be y, L. De oye,
and S. Janson did in [1]. The app oach in [1] applies no only o andom Cayley ees, bu o any amily
o ees a ising om a BGW(χ) ee as long χhas expec a ion 1 and ini e a iance (c i ical BGW ees).
Fu he mo e, explici p oo s a e p o ided o ce ain concep s ha a e o en assumed wi hou u he
jus i ica ion in he li e a u e. The explo a ion o hese pa ame e s o e s a deepe unde s anding o andom
ees, con ibu ing new insigh s in o es ablished esul s in his ield.
5.1 Some P elimina ies
Be o e s a ing wi h he p oo s, we need some p elimina ies.
Rema k 5.1.The B ead h-Fi s Sea ch (BFS) on a BGW ee is an algo i hm used o explo e he ee le el
by le el, s a ing om he oo . BFS explo es he ee by isi ing all nodes a one le el be o e mo ing o
he nex , ensu ing ha nodes a e p ocessed in inc easing dis ance om he oo . Hence, his sea ch keeps
a queue Qwi h Qinodes a he i− h s ep, wi h Q0= 1. Du ing he explo a ion o a e ex, i s o sp ing
a e added o he back o he queue. Then, one can easily ob ain he ollowing ecu sion:
Qi=Qi−1−1 + χi
whe e χiis an independen and iden ically dis ibu ed copy o he ep oduc ion dis ibu ion χ. Hence, by
his ecu sion, Qj= 1 + ˜
Sj, whe e ˜
Sj:= Pj
i=1(χi−1) = Sj−j. The ee is comple ely explo ed when
Qj= 0. In his case, ˜
Sn=−1
To aid he eade ’s unde s anding, we p o ide a conc e e example o a BFS pe o med on a speci ic
ee in Appendix A. This illus a ion se es o o e a clea e pe spec i e on he p inciples and me hods
discussed h oughou he chap e .
We now p esen h ee key lemmas ha a e no p o ed in [1] bu a e necessa y o s udying he expec ed
wid h o a andom ee.
Lemma 5.2. (Raney’s Lemma) Le a1,a2, ... , anbe a sequence o in ege s such ha
n
X
i=1
ai=−1.
Then he e exis s a unique index s such ha he cyclic pa ial sums
Sk=
k−1
X
j=0
a(s+j) mod n o k = 1, 2, ... , n,
sa is y:
16
1. Sk>0 o 1≤k<n,
2. Sn=−1.
P oo . De ine he p e ix sums o he sequence as
Tk=
k
X
i=1
ai, o k= 0, 1, ... , n,
whe e T0= 0. F om he assump ion Pn
i=1 ai=−1, i ollows ha Tn=−1.
Le m= min0≤k≤nTk, and le sbe he smalles index such ha Ts=m. By cons uc ion, Tk≥Ts
o all k, and Tsis he i s occu ence o he minimum alue.
We now de ine he cyclic pa ial sums Sks a ing om sas:
Sk=T(s+k) mod n−Ts, o k= 1, 2, ... , n.
1. Fo 1 ≤k<n, since Tsis he minimum alue o he p e ix sums and sis he i s occu ence o
his minimum, we ha e T(s+k) mod n>Ts. Thus,
Sk=T(s+k) mod n−Ts>0, o 1 ≤k<n.
2. Fo k=n, since Pn
i=1 ai=−1, we ha e:
Sn=T(s+n) mod n−Ts=Ts+
n
X
i=1
ai−Ts=−1.
Lemma 5.3. Suppose ha he indi iduals in a BGW p ocess ep oduce acco ding o a andom a iable χ,
wi h E[χ]=1and Va (χ)<∞. Then, he e is a cons an c10 ∈Rsuch ha , o all n su icien ly la ge,
P˜
Sn=−1≥c10n−1/2.
P oo . Le ’s emind ˜
Snis de ined as:
˜
Sn=
n
X
i=1
(χi−1)
whe e χia e independen and iden ically dis ibu ed (i.i.d.) andom a iables wi h mean µ= 1 and
a iance σ2<∞.
Le Xi=χi−1. These andom a iables Xia e i.i.d. wi h mean:
E[Xi] = E[χi−1] = µ−1,
and a iance:
Va (Xi) = Va (χi) = σ2.
17
Random T ees
Thus, ˜
Sn=Pn
i=1 Xi.
To apply he Cen al Limi Theo em (CLT), we no malize ˜
Snas:
Zn=˜
Sn−n(µ−1)
√nσ2,
which, by he cen al limi heo em, con e ges in dis ibu ion o a s anda d no mal:
Zn
d
−→ N(0, 1), as n→ ∞.
Rew i ing ˜
Snin e ms o Zn, we ge :
˜
Sn=n(µ−1) + √nσ2Zn.
We a e in e es ed in he p obabili y:
P(˜
Sn=−1).
F om he abo e, he e en ˜
Sn=−1 implies:
−1 = n(µ−1) + √nσ2Zn.
Sol ing o Zn, we ge :
Zn=−1−n(µ−1)
√nσ2.
Then, he ollowing equali y is clea :
P(˜
Sn=−1) = PZn=−1−n(µ−1)
√nσ2.
Since Zn
d
−→ N(0, 1) o la ge n, by he Local Cen al Limi Theo em he p obabili y can be app ox-
ima ed by he densi y o he no mal dis ibu ion a ha poin . The densi y o a s anda d no mal a z
is:
N(0,1)(z) = 1
√2πe−z2/2.
Thus, he p obabili y P(˜
Sn=−1) is p opo ional o he no mal densi y e alua ed a z=−1−n(µ−1)
√nσ2:
P(˜
Sn=−1) ∝1
√2πnσ2exp −(−1−n(µ−1))2
2nσ2!.
When he mean o he ep oduc ion dis ibu ion is µ= 1, he linea e m n(µ−1) anishes, and:
Zn=−1
√nσ2.
18
The p obabili y becomes:
P(˜
Sn=−1) ∝1
√nexp −1
2nσ2
Hence, i is clea ha he e is an absolu e cons an csuch ha o e e y su icien ly la ge nwe ha e
P(˜
Sn=−1) ≥cn−1/2.
Lemma 5.4. Suppose ha χia e i.i.d., non-nega i e and in ege - alued andom a iables, wi h E[χi]=1
and Va [χi]<∞, and le Sn=Pn
i=1 χi. Then, o all n ≥1and m ≥0,
P(Sn=n−m)≤C7
√ne−c7m2/n,
whe e C7>0and c7>0a e eal cons an s.
P oo . Since χia e i.i.d. andom a iables wi h mean E[χi] = 1 and a iance Va [χi] = σ2<∞, by
cen al limi heo em, he sum Sn=Pn
i=1 χisa is ies
Sn−n
√nσ2
d
−→ N(0, 1), as n→ ∞.
Rew i ing Sn=n−mand de ining Znas ollows, we ge
Zn=Sn−n
√nσ2=−m
√nσ2.
Unde he no mal app oxima ion, he p obabili y P(Sn=n−m) can be app oxima ed using he no mal
densi y N(0,1)(z):
P(Sn=n−m)≈1
√2πnσ2exp −Z2
n
2,
Subs i u ing Zn, we ind
P(Sn=n−m)≈1
√2πnσ2exp
−−m
√nσ22
2
.
Simpli ying he exponen ,
P(Sn=n−m)≈1
√2πnσ2exp −m2
2nσ2.
Now, de ine C7=1
√2πσ2and c7=1
2σ2. The p obabili y bound becomes wha we seek:
19
Random T ees
P(Sn=n−m)≤C7
√ne−c7m2/n.
whe e C7>0 and c7>0 depend on he a iance σ2o χi. This comple es he p oo .
Lemma 5.5. Le χbe a disc e e andom a iable aking alues in nonnega i e in ege s. Suppose ha
E(χ)=1and 0<Va (χ)<∞. Le Tbe a BGW(χ) ee. Then, P(|T | =n)≥n−3/2.
P oo . We obse e ha he e en |T | =nis equi alen o χ1+χ2+···+χn=n−1 and χ1+χ2+···+χi>0
o all 1 ≤i<n. The i s e en is ˜
Sn=−1. Le Undeno e he second one.
By Lemma 5.2, unde he condi ion ha ˜
Sn=−1, he e is a single o de ing o he a iables χ1, ... , χn
such ha all ini ial pa ial sums a e posi i e. Thus,
P(Un|˜
Sn=−1) = 1
n.
I ollows ha
P(|T| =n) = P({˜
Sn=−1}∩Un) = P(˜
Sn=−1)P(Un|˜
Sn=−1) = 1
nP(˜
Sn=−1) ≥c10n−3/2,
whe e he las inequali y ollows om Lemma 5.3.
We will also use he ollowing Che no ype inequali y.
Lemma 5.6. Le X1,X2, ... , Xnbe independen andom a iables such ha Xi−E[Xi]≤b o e e y i,
whe e b ∈R. Le V := Pn
i=1 Va (Xi). Then,
P n
X
i=1
(Xi−EXi)≥ !≤exp − 2
2V+2b
3!.
P oo . Le Sn:= Pn
i=1(Xi−E[Xi]). Using Ma ko ’s inequali y, we ha e:
P(Sn≥ ) = P(eλSn≥eλ )≤E[eλSn]
eλ ,
whe e λ > 0 is a pa ame e o be chosen la e . Since X1,X2, ... , Xna e independen , he ollowing is clea :
E[eλSn] =
n
Y
i=1
Eheλ(Xi−E[Xi])i.
Le Yi:= Xi−E[Xi], and we suppose ha Yi≤b. Fo any andom a iable Yisuch ha Yi≤b, we
can bound E[eλYi] using he Taylo expansion o eλYi. Speci ically:
E[eλYi]≤1 + λE[Yi] + λ2E[Y2
i]
2+λ3E[Y3
i]
6+··· .
20
Since E[Yi] = 0, and E[Y2
i] = Va (Xi), he leading con ibu ions a e:
E[eλYi]≤exp λ2Va (Xi)
2+λ3b2
6.
E[eλSn]≤
n
Y
i=1
exp λ2Va (Xi)
2+λ3b2
6.
Since Pn
i=1 Va (Xi) = V, his simpli ies o:
E[eλSn]≤exp λ2V
2+λ3b2n
6.
Subs i u ing his in o Ma ko ’s inequali y gi es:
P(Sn≥ )≤exp λ2V
2+λ3b2n
6−λ .
We now choose λ > 0 o minimize he exponen :
λ2V
2+λ3b2n
6−λ .
Igno ing he cubic e m empo a ily, we i s minimize:
λ2V
2−λ .
Taking he de i a i e wi h espec o λand se ing i o ze o:
d
dλλ2V
2−λ =λV− = 0 =⇒λ=
V.
Howe e , he cubic e m λ3b2n
6becomes signi ican when λis la ge. To con ol his, we modi y λ o
balance all e ms:
λ=
V+2b
3
.
This choice ensu es ha he quad a ic and cubic e ms emain balanced while maximizing he nega i e
linea e m −λ . Subs i u ing λ=
V+2b
3
in o he exponen , he p oo is done:
P(Sn≥ )≤exp − 2
2V+2b
3!.
21
Random T ees
I is clea ha , i he heigh o he ee is h, ei he he e exis s a jsuch ha Qd
j=h, o he e exis s a k
such ha Q
k=h.
Le p1=P(χ= 1) and le q1= 1−p1. Le ∈Tnsuch ha h( ) = h. Le j( esp. k) be he index o
in lexicog aphic ( esp. e e se-lexicog aphic) o de . Le Xbe he numbe o nodes which ha e mo e han
one child in P. Each ances o o wi h mo e han one child con ibu es o a leas one uni o Qd
jo o Q
k.
We dis inguish wo cases, ei he max(Qd
j,Q
k)≥q1
3ho max(Qd
j,Q
k)<q1
3h. In he second case, by he
abo e ema k, he numbe o ances o s o wi h exac ly one child is a leas (1−2q1/3)h= (p1+q1/3)h.
Now, i is no use ul o hink abou he queues because when he algo i hm p ocesses a node which
has jus 1 child, he size o he queue does no inc ease, so i is no a well ep esen a ion o he heigh o
he ee. Le Sbe he se o ees Twi h |T|=nand con aining a node such ha h( ) = hand has
(p1+q1/3)h( ) ances o s in Pwi h exac ly one child. Then, le δ:= {Tn∈S}=ST∈S{Tn=T}.
Then, we can apply hese wo cases desc ibed o he calculus o he ollowing p obabili y. The i s wo
e ms co espond o he i s case, while he emaining e m co esponds o he second case:
P(H(Tn)≥h)≤Pmax
jQd
j≥q1
3h+Pmax
kQ
k≥q1
3h+P(δ)
= 2Pmax
iQi≥q1
3h+P(δ)≤C11e−c11h2/n+P(δ)
whe e he las inequali y has been seen in he p oo o heo em 5.8.
Then, we only need o bound P(δ). To achie e i , we will use 2:
P(T ∈ S) = X
T∈S
P(T=T) = X
T∈S
P(ˆ
T(h)=Twi h γTas spine)
=P [
T∈S{ˆ
T(h)=Twi h γTas spine}!≤P h−1
X
i=0
1ˆχi=1 ≥(p1+q1/3)h!.
whe e he las inequali y is due o he ac ha he e en o he le -hand side is included in he igh -hand
side e en .
Since 1ˆχi=1 a e Be noulli(p1), by Lemma 5.6, and aking =q1h/3, V=p1q1h,b=q1, we ha e he
ollowing bound:
P h−1
X
i=0
1ˆχi=1 ≥(p1+q1/3)h!≤exp −(q1h/3)2
2p1q1h+ 2q2
1h/9
= exp −h
18p1/q1+ 2.
Fu he mo e, he ollowing equali y is clea :
P(T ∈ S) = P(δ)·P(|T | =n)
28
By Lemma 5.5, P(|T| =n)≥n−3/2and we can s ablish an uppe bound o P(δ).
P(δ) = P(T ∈ S)
P(|T| =n)≤C12n3/2exp −h
18p1/q1+ 2≤C12n3/2exp h
18p1/q1+ 2
h
√n
≤C13e−c12h2/n
o all h≥√n. Taking e e y hing in o accoun , wha we ha e is he ollowing bound o he heigh o a
BGW ee:
P(H(Tn)≥h)≤C11e−c11h2/n+C13e−c12h2/n
Now, aking
C2:= max{C11,C13},c2:= min{c11,c12}
P(H(Tn)≥h)≤C2e−c2h2/n
Ha ing p o ed ha , we le he ollowing esul wi hou p oo due o i s analogy wi h heo em 5.9.
Theo em 5.16. Le χbe a disc e e andom a iable aking alues in nonnega i e in ege s. Suppose ha
E[χ]=1and 0<Va χ < ∞. Then,
E[H(Tn)] = O(√n)
o all n ≥1.
Figu e 6: We illus a e all possible o de ed plane ees wi h 5 e ices. One can e i y ha he a e age
alues o heigh and wid h app oxima e √5.
29
Random T ees
5.4 The numbe o lea es
This subsec ion is based on Goldsmi h [9]. We will s udy he expec ed numbe o lea es in a andom
Cayley ee wi h n e ices, ocusing on he dis ibu ion o he numbe o lea es and i s expec ed alue as
a unc ion o he ee’s pa ame e s.
Rema k 5.17.A sequence o andom a iables Xncon e ges in p obabili y o X, deno ed as Xn
P
−→ X, i
o e e y ϵ > 0,
lim
n→∞
P(|Xn−X|> ϵ) = 0.
Rema k 5.18.Chebyshe ’s Inequali y:
Le Xbe a andom a iable wi h ini e mean µ=E[X] and a iance Va (X). Then, o any ϵ > 0,
P(|X−µ| ≥ ϵ)≤Va (X)
ϵ2.
Theo em 5.19. Le Nnbe he numbe o lea es in he andom Cayley ee Tn. Then,
Nn
n
P
−→ e−1
P oo . Le 1ibe he ollowing indica o unc ion:
1i=(1, i iis a lea
0, i iis no a lea
I is clea ha Nn=Pn
i=1 1i.
To p o e his con e gence in p obabili y, we will use Rema k 5.18. Hence, we need o calcula e
E[1i] = P(1i= 1)
To ge he p obabili y in ques ion, we i s need o de e mine how many ees on he se [n] ha e ias a
lea . Each such ee can be iewed as a ee on [n−1] labeled e ices, wi h an addi ional edge connec ing
one o he o he e ices o i. Since he numbe o ees on (n−1) labeled e ices is (n−1)n−3, and we
can add he edge men ioned o each e ex, i ollows ha he numbe o ees wi h ias a lea is (n−1)n−2.
The e o e, he p obabili y ha iis a lea is gi en by:
P(iis a lea ) = (n−1)n−2
nn−2=1−1
nn−2
→e−1
whe e we ha e aken he limi as napp oaches in ini y.
I is clea ha 1i, 1ja e no independen i i=j, bu one can show ha hey a e asymp o ically
independen :
P(iis a lea and jis a lea ) = (n−2)2(n−2)n−4
nn−2=1−2
nn−2
→e−2
30
whe e we ha e used he same a gumen as be o e. In pa icula , i is no di icul o calcula e hei
co a iance:
co (1i, 1j) = 1−2
nn−2
−1−1
n2(n−2)
→0
We also ha e:
Va (1i) = 1−1
nn−2
−1−1
n2(n−2)
=
1−1
nn−2 1−1−1
nn−2!→e−11−e−1
Hence, he ollowing is clea :
Va Nn
n=1
n2
n
X
i=1
Va (1i) + 2
n2X
i<j
Co (1i, 1j)
=1
nVa (11) + n−1
nCo (11, 12)→0
So ha , we al eady ha e all we need o apply Chebyshe ’s inequali y and inish he p oo :
P
Nn
n−e−1
> ϵ≤Va (Nn/n)
ϵ2→0
6. Bina y sea ch ees
Ou goal in his chap e is o ensu e cla i y and accessibili y in he analy ic s udy o he heigh o a bina y
sea ch ee, u ilizing BGW ees as a key componen in he main p oo . To achie e his, we closely ollow
Luc De oye’s p oo om [17], supplemen ing i wi h de ailed demons a ions o concep s o en le implici
in ela ed wo ks.
De ini ion 6.1. A bina y sea ch ee o dis inc eal numbe s x1, ... , xnis a bina y ee in which x1is he
oo , whose le sub ee is a bina y sea ch ee o {x2, ... , xn} ∩ (−∞,x1) and whose igh sub ee is a
bina y sea ch ee o {x2, ... , xn}∩(x1,∞).
Rema k 6.2.A bina y sea ch ee depends on he o de in which i s e ices a e p esen ed.
Rema k 6.3.I he le sub ee has kpoin s, hen in he o al o de ing o he e ices, he ank o he oo
is k+ 1.
By his de ini ion, we ha e a clea way o add a new e ex. I we wan o g ow he ee wi h a e ex
xn+1, we can compa e xn+1 wi h he cu en oo and choose le o igh sub ee as app op ia e. The
inse ion ime is equal o he dep h o xn+1, which is he dis ance be ween he oo and he inse ed node.
31
Random T ees
One can easily ob ain a uni o m bina y sea ch ee. We can ake a pe mu a ion o {1, ... , n}wi h each
pe mu a ion equally p obable. Fo each pe mu a ion, we will ge a di e en bina y sea ch ee. All o hem
will be equally likely o occu because hei s uc u e depends only on he pe mu a ion assigned, and we
ake e e y pe mu a ion uni o mly.
4
2
1 3
5
Figu e 7: Bina y sea ch ee wi h 5 e ices.
6.1 Heigh o a Random Bina y Sea ch T ee
Be o e del ing in o he p oo o e ed by Luc De oye in [17], we will p o ide explici demons a ions o
he essen ial p elimina ies equi ed o he p oo . These ounda ional esul s, o en aken as gi en in he
li e a u e, a e c ucial o a comple e and igo ous unde s anding o he a gumen .
Theo em 6.4. The a e age dep h o a node in a andomly cons uc ed bina y sea ch ee is O(log n).
P oo . The sum o he dep hs o all he nodes is called he in e nal pa h leng h. Le ’s deno e i by D(n).
Since o each inse ion o a e ex, he ee has inodes in i s le side, and n−i−1 in i s igh side, and
bo h ees ha e i s oo one le el down, we ha e he ollowing ecu ence:
D(n) = D(i) + D(n−i−1) + n−1
Hence, he a e age in e nal pa h node can be desc ibed as ollows:
1
n
n
X
i=0
(D(i) + D(n−i−1) + (n−1)) = (n−1) + 2
n
n−1
X
i=0
D(i)
Le ’s use his o p o e ha D(n) = O(n·log(n)). Then, i i holds, i is clea ha he a e age dep h o
a node in a andom BST is O(log n). We will p o e i by induc ion on n. We need o ind some cons an
Csuch ha D(n)≤C·n·log(n)
•I n= 1, D(1) = 0. Since C·0 = 0 o each cons an C, he esul holds.
•Assume D(m)≤C·m·log(m) o all m<n. Le ’s ind he igh C o D(n).
(n−1) + 2
n
n−1
X
i=0
D(i)HI
≤(n−1) + 2
n
n−1
X
i=0
C·i·log(i)≤(n−1) + 2
nZn
1
C·x·log(x)dx =
32
2
nCn2
2log(n)−1
2 ln(2) Zn
1
x dx+ (n−1) = C·n·log(n)−C(n2−1)
2n·ln(2) + (n−1)
≤C·n·log(n)
whe e we ha e conside ed C>2·ln(2) and nsu icien ly la ge.
Be o e s a ing wi h he s udy o he heigh o a bina y sea ch ee, we need o make some ema ks:
Lemma 6.5. Le U1,U2, ... , Ukbe k independen andom a iables, each uni o mly dis ibu ed on (0, 1).
De ine X as he p oduc o hese a iables:
X=U1·U2·... ·Uk.
Then X is a andom a iable ha ollows a Gamma dis ibu ion wi h shape pa ame e k and scale pa ame e
1, deno ed X ∼Gamma(k, 1).
P oo . To p o e his, we will p oceed by examining he loga i hm o he p oduc X.
De ine Y=−ln(X). Then,
Y=−ln(U1·U2·... ·Uk) = −(ln(U1) + ln(U2) + ... + ln(Uk)) .
Since Ui∼Uni o m(0, 1), we know ha each −ln(Ui) ollows an exponen ial dis ibu ion wi h a e pa am-
e e 1. Then, −ln(Ui)∼Exponen ial(1).
Because Yis he sum o kindependen exponen ial andom a iables wi h a e 1, Yi sel has a Gamma
dis ibu ion wi h shape pa ame e kand scale pa ame e 1, deno ed:
Y∼Gamma(k, 1).
Since Y=−ln(X), we can exp ess Xas:
X=e−Y.
The e o e, X ollows a Gamma dis ibu ion wi h pa ame e s k(shape) and 1 (scale), as equi ed.
Lemma 6.6. Le Gk∼Gamma(k, 1) deno e a gamma-dis ibu ed andom a iable wi h shape pa ame e
k and scale pa ame e 1. The ollowing inequali y holds:
1≤P(Gk≤y)
yke−y
k!≤1
1−y
k+1
.
33
Random T ees
P oo . The p obabili y dis ibu ion unc ion o Gkis gi en by:
P(Gk≤y) = Zy
0
xk−1e−x
(k−1)! dx.
Fo y>0, i is clea ha (y) = yk−1e−y
(k−1)! >0, hen:
P(Gk≤y)≥0.
Thus, i ollows ha :
P(Gk≤y)
yke−y
k!≥0,
which i ially implies, o k>> 0:
1≤P(Gk≤y)
yke−y
k!
.
Now we need o p o e P(Gk≤y)≤1
1−y
k+1
. To ind an uppe bound, we ew i e P(Gk≤y) as ollows:
Using in eg a ion by pa s k imes and p ope ies o he gamma unc ion, we can exp ess:
P(Gk≤y) = 1 −e−y
k−1
X
j=0
yj
j!.
Thus, we can easily ob ain he ollowing:
P(Gk≤y)
yke−y
k!
=k!(1 −e−yPk−1
j=0
yj
j!)
yke−y.
Fo y<k+ 1, we can use he se ies expansion o e−yand ob ain he ollowing inequali y:
1−e−y
k−1
X
j=0
yj
j!≤yke−y
k!(k+ 1 −y),
Then, we i ially ha e:
P(Gk≤y)
yke−y
k!≤1
1−y
k+1
.
Once all he p elimina ies ha e been es ablished, we ha e he necessa y ools o unde ake he p oo
o e ed in [17] o he heigh o a bina y sea ch ee wi h n e ices in ull de ail. This comp ehensi e
app oach ensu es a ho ough unde s anding o each s ep in he a gumen .
34
Theo em 6.7. Le Hnbe he heigh in a andom bina y sea ch ee on n nodes. Then,
Hn
log(n)
P
−→ γ= 4.331107 ...
whe e P
−→ means con e gence in p obabili y.
P oo . To s a wi h i , we need o in oduce a new ep esen a ion o a bina y sea ch ee. Le Tbe a
andom BST. Augmen he ee Tassocia ing wi h each node he size o he sub ee oo ed a ha node.
Le T′be his las ee.
The ank o he oo elemen o Tis equally likely o be 1, ..., n. Hence, he numbe o nodes Nin he
le sub ee o he oo o Tis uni o mly dis ibu ed on {0, 1, ... , n−1}. Wha is mo e, i Uis a andom
a iable uni o mly dis ibu ed on [0, 1], we can ead N=⌊nU⌋. Then, he numbe o nodes in he igh
sub ee o he oo o T, which is n−1−N, is dis ibu ed as ⌊n(1 −U)⌋.
This is an embedding a gumen . All subsequen spli s can be ep esen ed simila ly by in oducing
independen uni o m [0, 1] andom a iables. Fu he mo e, gi en an in ini e bina y ee, and a node whose
assigned alue is Vand whose copy o Uis U′, he alue o he wo child en a e dis ibu ed by ⌊VU′⌋and
⌊V(U′−1)⌋. I is no di icul o ob ain a mo e gene al o m o he dis ibu ion o he alue o a e ex
a dis ance k om he oo o T′:
⌊... ⌊⌊nU1⌋U2⌋... Uk⌋
,
whe e U1, ..., Uka e independen copies o U.
Wi h his ep esen a ion, we can s a o alk abou heigh Hn. The s uc u e o he p oo is as ollows:
i s , we will p o e ha γlog(n) se es as an uppe asymp o ic bound o Hn. Subsequen ly, we will show
ha γlog(n) is also a lowe asymp o ic bound o Hn. Toge he , hese esul s es ablish he equali y.
We s a wi h he uppe bound. To know i he heigh o a andom BST is a leas k, i is su icien o
go o he k- h le el and see i he e exis s some node wi h any sub ee oo ed a i . A mos , we can ha e
2knodes a ha le el. Hence, his condi ion can be desc ibed as ollows:
Hn≥k⇐⇒ max
1≤i≤2kVi≥1
I is clea ha Vi’s a e dependen , jus conside he alues Viand Vj o nodes nea one ano he .
We will analyze he p obabili y o ha ing a andom ee whose heigh is, a leas , k.
P(Hn≥k) = P(
2k
[
i=1
[Vi≥1]) ≤2k·P(V1≥1),
35
Random T ees
whe e he inequali y holds by Bon e oni’s inequali y and he symme y o he a iables Vi. This can
be u he bounded as ollows:
2k·P(V1≥1) ≤2k·P n
k
Y
i=1
Ui≥1!,
whe e we use he independence and iden ical dis ibu ion o he a iables U1, ... , Uk.
Now, applying lemma 6.5, we ha e:
2k·P n
k
Y
i=1
Ui≥1!= 2k·Pne−Gk≥1= 2k·P(Gk≤log(n)) .
The poin now is o ind he smalles ksuch ha he uppe bound ends o ze o. I is clea ha , i we
ake k= log(n), he uppe bound is O(2k). This is due o, o k= log(n),
P(Glog(n)≤log(n)) ≈1−e−log(n)
log(n)−1
X
j=0
(log(n))j
j!⇒P(Glog(n)≤log(n)) ≈1,
i n>> 0. Then, wha we sea ch is some kmuch la ge han log(n) o cancel he e ec o ha 2k.
Le ’s y k≈c·log(n) o some c>1.
Hence, by lemma 6.6, we ha e he ollowing:
1≤P(Gk≤y)
yke−y
k!≤1
1−y
k+1
whe e he lowe bound is alid o all y>0, and uppe bound jus o 0 <y<k+ 1. In pa icula ,
P(Gk≤log(n)) ≤log(n)k
nk!×1
1−log(n)
k+1
which is alid o log(n)<k+1. Hence, aking k=⌈c·log(n)⌉, and using S i ling’s inequali y (k!≥(k
e)k),
we ha e he ollowing:
P(Hn≥k)≤(2 log(n))k
nk!×1 + o(1)
1−1
c≤n−12elog(n)
kk
×1 + o(1)
1−1
c
≤1
e2e
cclog(n)
×1 + o(1)
1−1
c→0
whe e he las exp ession ends o 0 i 1
e2e
cc<1. Fo c=γ= 4.31107... we ob ain he equali y.
So ha , we conclude he ollowing:
∀c> γ, lim
n→∞
P(Hn> γ log(n)) = 0
36
as we wan ed o p o e.
A his poin , we ha e p o ed ha γlog(n) se es as an uppe asymp o ic bound o he heigh o a
andom bina y sea ch ee. Le ’s show i is also a lowe asymp o ic bound. Pick ϵ > 0. We will p o e he
ollowing:
lim
n→∞
P(Hn≥(γ−ϵ) log(n)) = 1
To p o e i , we will use b anching p ocesses. Fi s ly, we need o ack down nodes wi h la ge alues
in he augmen ed ee. Le ’s de ine V=nU1U2... Uk o a node a dis ance k om he oo , whe e he
Ui’s a e de ined as be o e and desc ibe he spli s on he pa h o he oo . We aim o cons uc a su i ing
BGW p ocess. Clea ly, he oo o Tbecomes he ze o h gene a ion o he BGW p ocess.
Le ’s conside all descendan s in Twhich a e Lle els away, and iden i y hese nodes as BGW child en
i he p oduc o uni o m spli ing andom a iables encoun e ed in he pa h om he oo o he possible
child is g ea e ha dL, o a gi en cons an d. I is clea ha he numbe o BGW child en pe node is
bounded be ween 0 and 2L. I Twe e in ini e, i is ob ious ha we can ind a node a any dis ance om
he oo . Mo eo e , he co esponding BGW p ocess would su i e wi h p obabili y 1 −q>0, whe e qis
he ex inc ion p obabili y, i he expec ed numbe o BGW child en pe node we e g ea e han one. Le ’s
see ha we can ge i o a la ge Land igh cons an s:
Le Ijbe an indica o a iable o he j- h node, whe e:
Ij=(1 i he node is a BGW child
0 i he node is no a BGW child
E
N
X
j=1
Ij
= 2L·PU1... UL>dL= 2L·P(GL<L·log(1/d))
≥(2Ld ·log(1/d))L
L!∼(2ed ·log(1/d))L
√2πL>1
i 2ed ·log(1/d)>1. Choosing d=e−1/c, whe e cis a cons an close o γ, we ge i . I can be
p o ed nume ically. Fu he mo e, we ha e used S i ling’s app oxima ion o la ge L, and lemmas 6.5, 6.6.
In conclusion, wi h p obabili y 1 −q>0, he e exis s a e ex a dis ance kL om he oo wi h alue
V≥ndkL =ne−kL/c. Taking unca ions in o accoun , i is clea ha , a mos , one uni can be los a
wo s in e e y unca ion. Hence, we ha e he ollowing lowe bound:
P(Hn≥kL)≥1−q
i ne−kL/c−kL ≥1. Taking kL =c′·log(n)−θL, o c′a bi a ily close o cand θ∈[0, 1) depending
on n, he las condi ion is e i ied o la ge n:
ne−kl/c−kL ≥n1−c′/c−c′·log(n)>1
Since c,c′ha e been aken a bi a ily close o γ, we ha e he ollowing ∀ϵ > 0:
37
Random T ees
•Mo e o node 5.
•Queue: [3, 5].
4. P ocessing Node 5:
•Cu en node: 5.
•Child en o node 5: None (lea node).
•Back ack o node 4.
•Queue: [3].
5. Back ack:
•All child en o node 4 ha e been isi ed.
•Back ack o node 2.
•All child en o node 2 ha e been isi ed.
•Back ack o node 1.
•Queue: [3].
6. Back ack o Node 1 and Mo e o Node 3:
•Cu en node: 1.
•Mo e o he nex child: Node 3.
•Cu en node: 3.
•Child en o node 3: None (lea node).
•Queue: [].
The lexicog aphic DFS a e sal o de o he ee is:
[1, 2, 4, 5, 3]
44
