Moment inequalities for random variables in computational geometry

Abstract

LetX ₁,...,X _n be independent identically distributedR ^d -valued random vectors, and letA _n =A(X ₁,...,X _n ) be a subset of {X ₁,...,X _n }, invariant under permutations of the data, and possessing the inclusion property (X ₁ ∈A _n impliesX ₁ ∈A _i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN _n be the cardinality ofA _n . We show that for allp≥1, there exists a universal constantC _p >0 such thatE(N _n ^p )≤C _p max (1,E ^p ) where . This complements Jensen's lower bound for thep-th moment:E(N _n ^p )≥E ^p (N _n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N _n ) for linear expected time behaviour of divide-and-conquer methods for findingA _n . X ₁,...,X _n seien unabhängige und gleichartig verteilte Zufallsvektoren imR ^d , ferner seiA _n =A(X ₁,...,X _n ) eine Teilmenge von {X ₁,...,X _n }, die invariant ist gegenüber einer Permutation der Daten und die die Inklusionseigenschaft (X ₁ ∈A _n ⇒X ₁ ∈A _i füri≤n) besitzt. Beispielsweise erfüllen die konvexe Hülle, die Menge der Maximal-Vektoren, die Menge der isolierten Punkte und andere Strukturen diese Bedingungen. SeiN _n die Kardinalzahl vonA _n . Wir zeigen, daß es für jedesp≥1 eine universelle KonstanteC _p gibt, so daßE(N _n ^p )≤C _p max (1,E ^p ) gilt, mit . Dies ist das Gegenstück zur unteren Schranke in Jensen für dasp-te Moment: E(Nn/p)≥E^p(N_n). Die Ungleichung wird zur Analyse der erwarteten Laufzeit von Algorithmen für geometrische Berechnungen verwendet. Ferner werden notwendige und hinreichende Bedingungen bezüglich (E(N _n ) angegeben, damit ein lineares Laufzeitverhalten bei Divide-and-Conquer-Methoden zur Berechnung vonA _n zu erwarten ist.