The Method of Moments Example I Example II Example III Counterexample
112
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
112
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- union-find-algorithms
- procedure quicksort
- universite de paris-nord
- quicksort input string
hTeMteohdfooMemtnsxEmalpeIxEmalpeIIxEmalpeIIISomeapplicationsofthemethodof
momentsintheanalysisofalgorithms
AloisPanholzer
InstituteofDiscreteMathematicsandGeometry
ViennaUniversityofTechnology
Alois.Panholzer@tuwien.ac.at
UniversitedeParis-Nord,16.2.2010
oCnueteraxm1p/el46
hTeMteohdfoMOutline
monestxEmalpeITheMethodofMoments
xEmalpeIIEExampleI
Totaldisplacementinlinearprobinghashing
ExampleII
Subtreevarietiesinrecursivetrees
ExampleIII
Totalcostsof
Union-Find
-algorithms
Counterexample
axpmelIIIoCnueteraxm2p/el46
Teh
Method
fo
Moments
ehT
ExampleI
ExampleII
Method
fo
ExampleIII
Moments
Counterexample
3
/
46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Motivation
Average-caseanalysisof
algorithms
procedure
Quicksort(A:array)
...dne
E.g.,
Quicksort
inputstring:random
permutationofsize
n
I
numberofcomparisons
tosortelements
I
numberofrecursivecalls
tosortelements
xEmalpeIIxEmalpeIIIoCnueterxAnalysisofaveragebehaviourof
parametersinrandomstructures
maE.g.,
randombinarysearchtree
of
ezisnI
numberofleavesintree
I
depthof
j
-thsmallestnodein
eert
4p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Motivation
Average-caseanalysis:
xEmalpeIIxEmalpeIIIX
n
:parameter(i.e.,randomvariable)underconsiderationfor
randomsize-
n
instance
I
Expectation(=meanvalue)
E
(
X
n
)
I
Concentrationresults,Variance
V
(
X
n
)
I
Limitingdistributionresults
X
n
(
d
−
)
→
X
,
X
n
ocvnreegsniidtsrI
Tailestimates(“boundsonrareevents”)
bituoinot.r.vCXuotnrexema5p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Showinglimitingdistributionresults
xEmalpeIIBasis:TheoremofFre´chetandShohat
(Secondcentrallimittheorem)
fI
xEmalpeIIIoCnu(
i
)
allpositive
r
-thintegermomentsof
X
n
convergetothe
r
-th
momentsofar.v.
X
:
E
(
X
nr
)
→
E
(
X
r
)
,
forall
r
≥
1
(
ii
)
thedistributionof
X
isuniquelydefinedbyitsmoments
then
X
n
(
−
d
→
)
X,.i.e,Xn
ocvnreegsniidtsirubitnootXeteraxm6p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Showinglimitingdistributionresults
xEmalpeIIxEPmalpeIIIoCnuThismeans:thedistributionfunction
F
n
(
x
)=
{
X
n
≤
x
}
of
X
n
converges
pointwise
forevery
x
∈
R
tothedistributionfunction
F
(
x
)=
P
{
X
≤
x
}
of
X
.
etrnPConsider
X
n
=
i
=1
Y
n
,
i
,
Y
n
,
i
independentidenticallydistr.as
Y
,
P
{
Y
=1
}
=
P
{
Y
=
−
1
}
=
21
.
xema7p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Showinglimitingdistributionresults
xEmalpeIIxEPmalpeIIIoCnuThismeans:thedistributionfunction
F
n
(
x
)=
{
X
n
≤
x
}
of
X
n
converges
pointwise
forevery
x
∈
R
tothedistributionfunction
F
(
x
)=
P
{
X
≤
x
}
of
X
.
etrnPConsider
X
n
=
i
=1
Y
n
,
i
,
Y
n
,
i
independentidenticallydistr.as
Y
,
P
{
Y
=1
}
=
P
{
Y
=
−
1
}
=
21
.
:01=n
xema7p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Showinglimitingdistributionresults
xEmalpeIIxEPmalpeIIIoCnuThismeans:thedistributionfunction
F
n
(
x
)=
{
X
n
≤
x
}
of
X
n
converges
pointwise
forevery
x
∈
R
tothedistributionfunction
F
(
x
)=
P
{
X
≤
x
}
of
X
.
etrnPConsider
X
n
=
i
=1
Y
n
,
i
,
Y
n
,
i
independentidenticallydistr.as
Y
,
P
{
Y
=1
}
=
P
{
Y
=
−
1
}
=
21
.
:02=n
xema7p/el46
hTeMteohdfooMemtnsxEmalpeITheMethodofMoments
Showinglimitingdistributionresults
xEmalpeIIxEPmalpeIIIoCnuThismeans:thedistributionfunction
F
n
(
x
)=
{
X
n
≤
x
}
of
X
n
converges
pointwise
forevery
x
∈
R
tothedistributionfunction
F
(
x
)=
P
{
X
≤
x
}
of
X
.
etrnPConsider
X
n
=
i
=1
Y
n
,
i
,
Y
n
,
i
independentidenticallydistr.as
Y
,
P
{
Y
=1
}
=
P
{
Y
=
−
1
}
=
21
.
n:04=
xema7p/el46
