Upload
ngongoc
View
221
Download
0
Embed Size (px)
Citation preview
Die probabilistische Methode
Skript zur Vorlesung im Wintersemester 2004/2005
an der Fakultät für Mathematik und Informatik
der Friedrich-Schiller-Universität Jena
PD Dr. Aicke Hinrichs
2
Inhaltsverzeichnis
1 Einführung in die Methode 3
1.1 Ramsey-Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Summenfreie Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Wahrscheinlichkeitstheoretische Grundbegriffe . . . . . . . . . . . . . 9
2 Elementare Prinzipien bei der Anwendung der probabilistischen
Methode 12
2.1 Die Linearität des Erwartungswerts . . . . . . . . . . . . . . . . . . . 12
2.2 Kleine Modifikationen . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Große Anticliquen . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Graphen mit weiter Taille und großer chromatischer Zahl . . 17
2.2.3 Packungen konvexer Mengen . . . . . . . . . . . . . . . . . . 20
2.3 Die Zweite-Momenten-Methode . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Mengen mit verschiedenen Summen . . . . . . . . . . . . . . 24
2.3.2 Anzahl von Primfaktoren . . . . . . . . . . . . . . . . . . . . 27
3 Konzentrationsungleichungen 30
3.1 Summen unabhängiger Bernoulli-Variablen . . . . . . . . . . . . . . . 31
3.1.1 Kombinatorische Diskrepanz . . . . . . . . . . . . . . . . . . . 34
3.1.2 Ein Spiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Summen beschränkter unabhängiger Variablen . . . . . . . . . . . . 36
3.3 Geometrische Diskrepanz . . . . . . . . . . . . . . . . . . . . . . . . 39
Kapitel 1
Einführung in die Methode
Die probabilistische Methode ist eine bemerkenswerte Technik für den Beweis der
Existenz von mathematischen Objekten mit vorgegebenen Eigenschaften. Sie benutzt
die Wahrscheinlichkeitstheorie, wird aber oft zum Beweis von Resultaten verwendet,
die überhaupt nichts mit Wahrscheinlichkeiten zu tun haben.
Grundlegender Ansatz: Wir möchten die Existenz eines Objektes mit spezifischen
Eigenschaften zeigen. Unglücklicherweise ist eine explizite Konstruktion schwierig,
vielleicht unmöglich. Wir betrachten nun ein geeignetes Wahrscheinlichkeitsmaß auf
der Klasse aller zulässigen Objekte. Wir zeigen, daß die Wahrscheinlichkeit, daß ein
zufällig ausgewähltes Objekt dieser Klasse die gewünschte Eigenschaft hat, positiv
ist. Folglich muß es ein solches Objekt geben, anderenfalls wäre die Wahrscheinlich-
keit für so ein „gutes“ Objekt ja Null.
Pionier dieser Methode war Paul Erdös1, der ab 1947 eine beachtliche Anzahl von
Resultaten mit dieser Methode erzielt hat. Die erste Anwendung auf ein kombina-
torische Problem stammt von T. Szele 1943. Erdös war allerdings derjenige, der die
ganze Kraft der Methode erkannt und genutzt hat.
Die Methode wird in so verschiedenen Gebieten wie Graphentheorie, Kombinatorik,
Zahlentheorie, Geometrie, Analysis und Numerik angewendet. In der Informatik gibt
es einen ganzen Zweig, der sich mit randomisierten Algorithmen beschäftigt und
ebenfalls grundlegend die probabilistische Methode nutzt. Ziel dieser Vorlesung ist es,
die vielfältigen Anwendungen der Methode zu demonstrieren. Die beste Möglichkeit
11913-1996
4 1.1 Ramsey-Zahlen
dazu ist, konkrete Probleme zu behandeln, womit wir auch gleich beginnen wollen.
1.1 Ramsey-Zahlen
Das Problem: Es sei eine gewisse Anzahl N von Personen gegeben, von denen sich
je zwei entweder gegenseitig kennen oder gegenseitig nicht kennen. Wir möchten
ausschließen, daß sich unter diesen N Personen
• k befinden, die sich alle kennen oder
• l befinden, die sich alle nicht kennen.
Wie groß kann N sein?
Wir wollen das Problem zunächst in ein graphentheoretisches Problem umformulie-
ren. Ein (ungerichteter einfacher) Graph G = (V, E) ist eine Menge V (die Menge der
Knoten - vertices) zusammen mit einer Teilmenge E der zweielementigen Teilmengen
von G (den Kanten - edges). Die Ordnung von G ist |G| := |V |. Eine Clique in G ist
eine Teilmenge C ⊂ V , so daß alle zweielementigen Teilmengen von C Kanten von
G sind. Eine Anticlique oder unabhängige Menge in G ist eine Teilmenge A ⊂ V , so
daß keine der zweielementigen Teilmengen von A Kante von G ist.
Das obige Problem kann nun folgendermaßen in die Graphensprache übersetzt wer-
den. Die Knoten unseres Graphen seien gerade die betrachteten N Personen, wir
haben also einen Graphen der Ordnung N . Zwei Knoten werden genau dann durch
eine Kante verbunden, wenn sich die beiden Personen kennen. Eine Clique ist dann
eine Gruppe von Personen, die sich alle gegenseitig kennen. Eine Anticlique ist eine
Gruppe von Personen, unter denen es überhaupt keine Bekanntschaften gibt.
Problemformulierung: Sei G ein Graph, der weder eine Clique der Größe k noch eine
Anticlique der Größe l enthält. Wie groß kann N = |G| sein?
Der folgende Satz von Ramsey2 gibt eine obere Schranke.
Theorem 1. Für jedes k, l ∈ N gibt es eine kleinste Zahl R(k, l) - die Ramsey-
Zahl zu k, l - so daß jeder Graph der Ordnung R(k, l) eine Clique der Größe k (eine
2Frank Plumpton Ramsey (1903–1930)
Kapitel 1. Einführung in die Methode 5
k-Clique) oder eine Anticlique der Größe l (eine l-Anticlique) enthält. Dabei gilt
R(k, l) ≤(
k + l − 2
k − 1
)
. (1.1)
Beweis. Wir beweisen dies durch Doppelinduktion über k, l. Der Induktionsanfang
R(k, 1) = R(1, l) = 1 für alle k, l ist offensichtlich, da jede einpunktige Knotenmenge
sowohl Clique als auch Anticlique ist. Wir zeigen nun für k, l ≥ 2
R(k, l) ≤ R(k − 1, l) + R(k, l − 1). (1.2)
Durch Induktion folgt dann tatsächlich die Ungleichung (1.1) wegen
R(k, l) ≤ R(k − 1, l) + r(k, l − 1) ≤(
k + l − 3
k − 2
)
+
(
k + l − 3
k − 1
)
=
(
k + l − 2
k − 1
)
.
Zum Beweis der Ungleichung (1.2) betrachten wir einen Graph G = (V, E) mit
|V | = R(k − 1, l) + R(k, l − 1)
und fixieren einen Knoten v ∈ V . Sei V1 ⊂ V die Mengen der Knoten, die durch
eine Kante mit v verbunden sind. Sei V2 die Menge der Knoten, die nicht durch eine
Kante mit v verbunden sind. Wegen
|V1| + |V2| = R(k − 1, l) + R(k, l − 1) − 1
gilt zumindest eine der Ungleichungen |V1| ≥ R(k − 1, l) oder |V2| ≥ R(k − 1, l).
Ist |V1| ≥ R(k − 1, l), so finden wir unter den Knoten von V1 nach Definition von
R(k − 1, l) eine (k − 1)-Clique oder eine l-Anticlique. Tritt das erstere ein, so bildet
diese (k − 1)-Clicqe zusammen mit v eine k-Clique in G. In jedem Fall finden wir
also eine k-Clique oder eine l-Anticlique. Gleiches zeigt man ganz analog im Fall
|V2| ≥ R(k − 1, l), womit der Beweis abgeschlossen ist.
Folgerung: R(k, k) ≤(
2k−2k−1
)
=(
2k−3k−1
)
+(
2k−3k−2
)
≤ 22k−3
Wir wenden uns jetzt dem Problem zu, eine untere Abschätzung für R(k, k) zu
finden. Dazu müssen wir möglichst große Graphen finden, die weder k-Cliquen noch
k-Anticliquen enthalten. Hier kommt die probabilistische Methode zur Anwendung.
Theorem 2. (P. Erdös 1947) Für jedes k ≥ 2 gilt R(k, k) ≥ 2k/2.
6 1.1 Ramsey-Zahlen
Beweis. Man überzeugt sich leicht von R(2, 2) = 2 und R(3, 3) = 6. Sei also jetzt
k ≥ 4 und N < 2k/2. Wir wollen einen Graph G = (V, E) mit N Knoten finden,
der keine k-Clique und keine k-Anticlique enthält. Dazu konstruieren wir G pro-
babilistisch, indem wir für jede potentielle Kante eine Münze werfen und je nach
Ausgang die Kante dazunehmen oder nicht. Mit anderen Worten: Eine Kante taucht
in unserem Graphen genau mit Wahrscheinlichkeit 1/2 auf, alle unabhängig vonein-
ander. Dann erhalten wir also jeden vorgegebenen Graphen G auf den N Knoten mit
Wahrscheinlichkeit 2−(N
2 ).
Sei jetzt A ⊂ V eine Teilmenge mit |A| = k. Die Wahrscheinlichkeit, daß die A eine
Clique in unserem zufälligen Graphen ist, ist 2−(k
2). Da es insgesamt(
Nk
)
Teilmen-
gen der Kardinalität k gibt, ist die Wahrscheinlichkeit, daß es in unserem Graphen
eine k-Clique gibt höchstens(
Nk
)
2−(k
2). Aus Symmetriegründen gilt gleiches für die
Wahrscheinlichkeit, daß es in unserem Graphen eine k-Anticlique gibt. Ist also
2
(
N
k
)
2−(k
2) < 1, (1.3)
so ist die Wahrscheinlichkeit, einen Graphen ohne k-Clique und k-Anticlique zu er-
halten, positiv. Es muß also so einen Graph geben!
Es bleibt also noch (1.3) zu zeigen. Dazu benutzen wir die Abschätzung(
Nk
)
≤ Nk
2k−1 ,
die wir in Lemma 3 beweisen. Dann folgt tatsächlich wegen k ≥ 4 und N < 2k/2
2
(
N
k
)
2−(k
2) ≤ 2Nk
2k−12−(k
2) ≤ 21+k2/2−(k−1)−k(k−1)/2 = 22−k/2 < 1.
Lemma 3. Für N ≥ k ≥ 2 gilt(
Nk
)
≤ Nk
2k−1 .
Beweis.(
N
k
)
=N(N − 1) . . . (N − k + 1)
2 · 3 . . . k≤ Nk
2k−1.
Bemerkungen:
1. Man kann natürlich einwenden, daß man den Beweis ebensogut durch „Ab-
zählen“ durchführen kann. Dieser Einwand trifft auf fast alle Anwendungen
Kapitel 1. Einführung in die Methode 7
der probabilistischen Methode zu. Durch Verwendung von Wahrscheinlichkei-
ten werden solche Beweise aber einerseits oft durchsichtiger, sind einfacher zu
finden, und, was wohl das wichtigste Argument sein dürfte, ermöglichen die
Anwendung tieferliegender Methoden aus der Wahrscheinlichkeitstheorie. Wir
werden noch Gelegenheit haben, dies zu sehen.
2. Auch Abschätzungen für R(k, l) nach unten sind möglich, siehe Aufgabe 3.
3. Nur sehr wenige Ramsey-Zahlen sind explizit bekannt (abgesehen von R(k, 1) =
R(1, k) = 1 und R(k, 2) = R(2, k) = k). Eine Übersicht über den aktuellen
Stand findet man im Web auf der Seite
http://www.combinatorics.org/Surveys/ds1.pdf.
1.2 Summenfreie Mengen
Wir wollen nun ein weiteres einfaches Beispiel für die Anwendung der probabilisti-
schen Methode behandeln. Diesmal handelt es sich um ein Ergebnis aus der Zahlen-
theorie. Untersuchen wollen wir die Existenz großer summenfreier Teilmengen von
beliebigen endlichen Mengen ganzer Zahlen.
Eine Menge A ⊂ Z heißt summenfrei, wenn es keine a1, a2, a3 ∈ A mit a1 + a2 = a3
gibt. Natürlich kann eine solche Menge nicht die 0 enthalten. Ist jetzt B ⊂ Z eine
beliebige Menge, wie große summenfreie Teilmengen von B existieren dann?
Zur Vorbereitung wollen wir den Begriff der Summenfreiheit auf Teilmengen belie-
biger abelscher Gruppen verallgemeinern. Eine Teilmenge A einer abelschen Gruppe
G heißt summenfrei, wenn es keine a1, a2, a3 ∈ A mit a1 + a2 = a3 gibt. Insbeson-
dere benötigen wir die zyklische Gruppe Zp = 0, 1, . . . , p − 1 ausgerüstet mit der
Addition modulo p. Sei jetzt p = 3k + 2 mit einer natürlichen Zahl k. Dann ist die
Menge
C = k + 1, k + 2, . . . , 2k + 1 ⊂ Zp
summenfrei, da für beliebige a1, a2 ∈ C offenbar (Addition modulo p!)
a1 + a2 ∈ 0, . . . , k ∪ 2k + 2, . . . , 3k + 1 = Zp \ C
gilt. C ist also eine summenfreie Teilmenge von Zp mit |C| = k + 1. Diese spezielle
summenfreie Menge werden wir im Beweis des folgenden Theorems verwenden.
8 1.2 Summenfreie Mengen
Theorem 4. (P. Erdös 1965) Jede Menge von n von 0 verschiedenen ganzen Zahlen
enthält eine summenfreie Teilmenge mit mehr als n/3 Elementen.
Beweis. Sei B = b1, . . . , bn eine solche Menge. Sei p = 3k + 2 eine Primzahl
mit p > |bi|. Die Existenz beliebig großer Primzahlen dieser Form folgt aus einem
berühmten zahlentheoretischen Resultat von Dirichlet, welches besagt, daß es zu
beliebigen teilerfremden Zahlen a, b unendlich viele Primzahlen der Form ak+b gibt.
Einen direkten kurzen Beweis dieser Tatsache im benötigten Spezialfall geben wir
im Anschluß an diesen Beweis an.
Wir wählen jetzt zufällig eine Zahl x ∈ 1, 2, . . . , p − 1, jedes x mit gleicher Wahr-
scheinlichkeit 1/p − 1. Wir finden nun di ∈ 1, 2, . . . , p − 1 für i = 1, . . . , n mit
di = xbi mod p.
Wir halten zunächst i fest. Durchläuft x alle Zahlen in 1, . . . , p − 1, so überlegt
man sich leicht, daß di ebenfalls alle Zahlen in 1, . . . , p− 1 ⊂ Zp durchläuft. Ist C
die Menge von oben, so ist also die Wahrscheinlichkeit dafür, daß di ∈ C ist, gleich
|C|p − 1
=k + 1
3k + 1>
1
3.
Folglich ist der Erwartungswert der Anzahl der i ∈ 1, . . . , n mit di ∈ C größer als
n/3. Es gibt also ein x, so daß
|i ∈ 1, . . . , n : di ∈ C| >n
3
gilt. Wir fixieren dieses x und setzen I = i ∈ 1, . . . , n : di ∈ C und A = bi :
i ∈ I. Dann ist |A| > n/3.
Wir zeigen schließlich, daß A summenfrei ist. Anderenfalls gäbe es i, j, k ∈ I mit
bi + bj = bk.
Dies impliziert aber xbi + xbj = xbk und folglich auch di + dj = dk, letzteres in Zp.
Dies ist aber wegen di, dj , dk ∈ C ein Widerspruch zur Summenfreiheit von C.
Bemerkung: N. Alon, D. Kleitman (1990) haben die folgende Aussage über sum-
menfreie Mengen in beliebigen abelschen Gruppen bewiesen: Jede Menge von n von
Kapitel 1. Einführung in die Methode 9
0 verschiedenen Elementen einer abelschen Gruppe enthält eine summenfreie Teil-
menge mit mehr als 2n/7 Elementen. Hier ist der Faktor 2/7 optimal. Die optimale
Konstante in Theorem 4 ist nicht bekannt.
Der Satz von Dirichlet sagt aus, daß es zu gegebenen teilerfremden Zahlen a ≥2, b ≥ 1 unendlich viele Primzahlen der Form ak + b gibt. Dieser allgemeine Satz ist
relativ schwierig zu beweisen. Wie versprochen wollen wir noch ein kurzes Argument
anführen, daß es unendlich viele Primzahlen der Form 3k + 2 gibt. Dieses verläuft
ähnlich wie der Beweis von Euklid für die Unendlichkeit der Menge der Primzahlen.
Nehmen wir also an, daß es nur endlich viele Primzahlen der Form 3k + 2 gibt. Sei
die größte Primzahl dieser Form pn, wobei p0 = 2, p1 = 3, p2, . . . , pn die Folge aller
Primzahlen bis pn ist. Wir setzen nun
N = 2 · 3 · . . . · pn − 1.
Dann läßt N bei Division durch 3 offenbar den Rest 2. Da keine der Primzahlen
p0, p1, . . . , pn ein Teiler von N ist, müssen alle Promteiler von N größer als pn sein
und somit bei Division durch 3 den Rest 1 lassen. Damit läßt aber auch N bei
Division durch 3 den Rest 1, ein Widerspruch.
1.3 Wahrscheinlichkeitstheoretische Grundbegriffe
In diesem Abschnitt wollen wir kurz die Grundlagen der Wahrscheinlichkeitstheorie
wiederholen, die wir in den folgenden Vorlesungen benötigen.
Wahrscheinlichkeitsraum: Ein Wahrscheinlichkeitsraum ist ein Tripel (Ω, Σ, P), wobei
Ω eine Menge, Σ ⊂ 2Ω eine σ-Algebra von Teilmengen von Ω und P ein Wahrschein-
lichkeitsmaß auf Σ ist.
Die Elemente von Σ heißen Ereignisse, die Elemente von Ω Elementarereignisse. Für
A ∈ Σ heißt P(A) die Wahrscheinlichkeit des Ereignisses A.
Wir werden oft endliche Wahrscheinlichkeitsräume betrachten, wo Ω eine endliche
Menge und Σ = 2Ω die σ-Algebra aller Teilmengen von Ω ist. Dann ist ein Wahr-
scheinlichkeitsmaß P auf Ω bestimmt durch eine Funktion p : Ω → [0, 1] mit
∑
ω∈Ω
p(ω) = 1.
10 1.3 Wahrscheinlichkeitstheoretische Grundbegriffe
Beispiel: Sei 0 ≤ p ≤ 1. Der Wahrscheinlichkeitsraum G(n, p) der zufälligen Graphen
hat als Elementarereignisse alle Graphen auf einer fixierten Menge von n Knoten,
wobei die Wahrscheinlichkeit für einen Graph mit m Kanten gegeben ist durch
P(G) = pm(1 − p)(n
2)−m.
Jede potentielle Kante kommt also in G mit der Wahrscheinlichkeit p vor, und alle
diese Kanten sind unabhängig voneinander. Wir haben beim Beweis des Theorems
2 schon mit dem Wahrscheinlichkeitsraum G(n, 1/2) gearbeitet. In diesem sind alle
Graphen gleich wahrscheinlich.
Auch folgende einfache Tatsache haben wir uns bereits zunutze gemacht:
Fakt: Seien A1, . . . , An Ereignisse. Dann gilt
P(
n⋃
i=1
Ai
)
≤n
∑
i=1
P(Ai).
Unabhängigkeit: Ereignisse A1, . . . , An heißen unabhängig, wenn für jede Teilmenge
I ⊂ 1, . . . , nP(
⋂
i∈I
Ai
)
=∏
i∈I
P(Ai).
Intuitiv bedeutet dies, daß man aus der Tatsache, daß einige der Ereignisse A1, . . . , An
aufgetreten sind, nichts über die übrigen Ereignisse schließen kann.
Bedingte Wahrscheinlichkeit: Sind A, B Ereignisse mit P(B) > 0, so heißt der Quo-
tient
P(A |B) =P(A ∩ B)
P(B)
die bedingte Wahrscheinlichkeit für A unter der Voraussetzung, daß B auftritt. Sind
A, B unabhängig, so gilt offenbar P(A |B) = P(A).
Zufallsvariable: Eine reelle Zufallsvariable auf einem Wahrscheinlichkeitsraum (Ω, Σ, P)
ist eine P-meßbare Funktion X : Ω → R. Die Verteilungsfunktion von X ist die Funk-
tion
FX(a) = F (a) = P(X < a) = P(ω ∈ Ω : X(ω) < a).
Der Erwartungswert von X berechnet sich als
EX =
∫
ΩX(ω)dP(ω).
Kapitel 1. Einführung in die Methode 11
Den folgenden einfachen Fakt haben wir ebenfalls bereits benutzt.
Fakt: Es gibt ω1, ω2 ∈ Ω mit X(ω1) ≤ EX und X(ω2) ≥ EX.
Die reellen Zufallsvariablen X1, . . . , Xn heißen unabhängig, wenn für alle a1, . . . , an ∈R
P(X1 < a1, . . . , Xn < an) =n
∏
i=1
P(Xi < ai)
gilt. Eine beliebige Menge reeller Zufallsvariablen heißt unabhängig, wenn jede end-
liche Teilmenge unabhängig ist.
Fakt: Sind X, Y unabhängige reelle Zufallsvariable, so gilt E(XY ) = EX · EY .
12
Kapitel 2
Elementare Prinzipien bei der
Anwendung der probabilistischen
Methode
In diesem Kapitel wollen wir an Beispielen studieren, welche einfachen Prinzipien
wichtig für die Nutzung der probabilistischen Methode sind. Dazu gehören insbeson-
dere
• die Linearität des Erwartungswerts
• kleine Modifikationen
• das zweite Moment - die Chebyshev-Ungleichung
2.1 Die Linearität des Erwartungswerts
Fakt: Sind X, Y reelle Zufallsvariable und a, b ∈ R, so gilt E(aX+bY ) = aEX+bEY .
Beweis.
E(aX + bY )
∫
Ω(aX + bY )dP = a
∫
ΩXdP + b
∫
ΩY dP = aEX + bEY.
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 13
Folgerung: Ist X = X1 + . . . + Xn, so gilt EX = EX1 + . . . + EXn.
Zum Berechnen des Erwartungswerts einer reellen Zufallsvariablen kann man dieses
Prinzip oft nutzen, wenn sich X als eine Summe von Indikatorvariablen darstellen
läßt. Die zu einem Ereignis A gehörige Indikatorvariable ist gegeben durch
IA(ω) =
1 für ω ∈ A
0 für ω /∈ A.
Es gilt EIA = P(A) wegen
EIA =
∫
ΩIA(ω)dP(ω) =
∫
AdP = P(A).
Kann man also X schreiben als
X = IA1+ . . . + IAn
,
so läßt sich der Erwartungswert von X berechnen als
EX = P(A1) + . . . + P(An).
Die Anwendung dieses Prinzips wollen wir an der historisch ersten Nutzung der
probabilistischen Methode in einer Arbeit von T. Szele 1943 illustrieren. Dabei geht
es um folgendes Problem. Ein Wettkampf mit n Teilnehmern sei eine Orientierung
des vollständigen Graphen der Ordnung n ( das ist der Graph auf n Knoten mit allen
möglichen Kanten). Hierbei bedeutet Orientierung, daß wir jeder Kante u, v genau
eine der beiden möglichen Richtungen (u, v) oder (v, u) geben. Von den möglichen
gerichteten Kanten (u, v) und (v, u) ist also genau eine vorhanden.
Ein Hamiltonkreis in einem Wettkampf ist ein gerichteter Weg, der jeden Knoten
genau einmal passiert. Ist die Knotenmenge die Menge 1, 2, . . . , n, so stellt eine
Permutation σ der Menge 1, 2, . . . , n genau dann einen Hamiltonkreis im Wett-
kampf W dar, wenn (σ(i), σ(i + 1)) ∈ W ist für alle i = 1, . . . , n − 1. Wie viele
Hamiltonkreise kann es in einem Wettkampf geben?
Theorem 5. Es gibt einen Wettkampf mit n Teilnehmern und mindestens n!2n−1
Hamiltonkreisen.
14 2.1 Die Linearität des Erwartungswerts
Beweis. Wir betrachten zufällige Wettkämpfe W auf den Knoten 1, . . . , n, indem
wir jeder Kante (unabhängig von den anderen Kanten) eine zufällige Richtung geben,
wobei jede der beiden möglichen Richtungen mit Wahrscheinlichkeit 1/2 auftritt. Sei
X die Anzahl der Hamiltonkreise in unserem zufälligen Wettkampf. X ist eine reelle
Zufallsvariable, die wir nun in eine Summe von Indikatorvariablen zerlegen wollen,
um anschließend den Erwartungswert von X zu berechnen.
Dazu sei σ eine Permutation der Menge 1, 2, . . . , n und Xσ sei die Indikatorvariable
zu dem Ereignis, daß alle Kanten (σ(i), σ(i + 1)) in dieser Richtung in W auftreten.
Wie oben schon beobachtet, ist dies gerade das Ereignis, daß (σ(1), σ(2), . . . , σ(n))
in dieser Reihenfolge einen Hamiltonkreis in W bilden. Dann ist also
X =∑
σ
Xσ
eine Zerlegung von X in Indikatorvariable. Da die Kantenorientierungen unabhängig
voneinander gewählt werden, erhalten wir
EXσ = P(
(σ(i), σ(i + 1)) ∈ W für i = 1, . . . , n − 1)
=n−1∏
i=1
P((σ(i), σ(i + 1)) ∈ W ) =n−1∏
i=1
1
2=
1
2n−1.
Nun folgt mit der Linearität des Erwartungswerts
EX =∑
σ
EXσ =n!
2n−1.
Es muß also einen Wettkampf W geben, der mindestens diese Anzahl von Hamilton-
kreisen hat.
Wir wollen ein weiteres Beispiel für die Anwendung der Linearität des Erwartungs-
wertes anführen. Diesmal stammt die Motivation aus der Algorithmentheorie.
Wir betrachten das MAXCUT-Problem. Ist G = (V, E) ein Graph, so fragt dieses
Problem nach der Zerlegung (CUT) der Knotenmenge V in zwei Mengen A, B =
V \ A, so daß die Anzahl der Kanten, die zwischen A und B verlaufen, maximiert
wird (MAX). Dieses Problem ist algorithmisch schwer (NP-vollständig). Das folgende
Theorem sagt aus, daß man immer einen CUT mit der Hälfte aller Kanten findet.
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 15
Theorem 6. Zu jedem Graph mit m Kanten gibt es einen CUT mit mindestens m/2
Kanten zwischen den beiden Mengen des CUTs.
Beweis. Sei G = (V, E) der betrachtete Graph mit |E| = m. Wir wählen eine zufälli-
ge Teilmenge A ⊂ V , indem wir jeden Knoten aus V mit Wahrscheinlichkeit 1/2 zu A
hinzunehmen, alle Knoten unabhängig voneinander. Zu jeder Kante e = u, v ∈ E
betrachten wir die Zufallsvariable
Xe =
1 falls genau einer der Knoten u, v in A ist
0 sonst.
Dies ist offenbar eine Indikatorvariable mit
EXe = P((u ∈ A & v /∈ A) oder (u /∈ A & v ∈ A)) =1
4+
1
4=
1
2.
Ist nun X die Zahl aller Kanten mit genau einem Knoten in A, also gerade die Anzahl
der Kanten des CUTs A, B = V \ A, so gilt
EX =∑
e∈E
EXe =m
2.
Es muß also eine Menge A geben, für die die Anzahl der Kanten zwischen A und
V \ A mindestens m/2 ist.
2.2 Kleine Modifikationen
Häufig kommt es vor, daß die Anwendung der probabilistischen Methode nicht ganz
das gewünschte „gute“ Objekt liefert. Wenn das Objekt aber „fast gut genug“ ist,
kann man versuchen, es deterministisch so abzuändern, daß man schließlich doch
bekommt, worauf man eigentlich aus war. Dies ist ein weiteres Prinzip, auf daß man
oft trifft und dessen Anwendung wir in diesem Abschnitt studieren wollen.
An dieser Stelle ist es sinnvoll, eine einfache Ungleichung aus der Wahrscheinlichkeits-
theorie einzuführen, die abschätzt, wie wahrscheinlich es ist, daß eine Zufallsvariable
ihren Erwartungswert übertrifft. In den folgenden Kapiteln werden wir noch weit
schärfere Ungleichungen dieser Art beweisen und benutzen. Für die Beispiele dieses
Abschnitts genügt uns die
16 2.2 Kleine Modifikationen
Markov-Ungleichung. Sei X eine nichtnegative reelle Zufallsvariable und sei a > 0.
Dann gilt
P(X ≥ a) ≤ EX
a.
Beweis. Aus der Nichtnegativität von X folgt
EX =
∫
Ω
XdP ≥∫
ω:X≥a
XdP ≥∫
ω:X≥a
adP = aP(X ≥ a).
2.2.1 Große Anticliquen
Wir wollen uns in diesem Beispiel überlegen, wie große Anticliquen ein Graph mit n
Knoten und m Kanten haben kann. Dazu führen wir einige weitere Begriffe aus der
Graphentheorie ein.
Sei also G = (V, E) ein Graph. Der Grad d(v) eines Knotens v ∈ V ist die Anzahl
der Kanten, die v enthalten. Der durchschnittliche Grad des Graphen G ist d = 2mn ,
wobei m = |E| die Anzahl der Kanten und n = |V | die Anzahl der Knoten von G ist.
Die Anticliquenzahl bzw. Unabhängigkeitszahl α(G) ist die Kardinalität der größten
Anticlique in G.
Ein berühmtes Theorem von Turán beinhaltet die Abschätzung
α(G) ≥ n
d + 1.
Extremale Graphen für ganzzahliges d findet man übrigens als disjunkte Vereinigun-
gen von (d+1)-Cliquen. Wir zeigen mit einem einfachen probabilistischen Argument
etwa die Hälfte des Turán-Theorems.
Theorem 7. α(G) ≥ n
2d.
Beweis. Wir wählen wieder eine zufällige Teilmenge A ⊂ V , diesmal nehmen wir
jeden Knoten mit Wahrscheinlichkeit p, unabhängig voneinander. Das konkrete p
bestimmen wir später.
Wir definieren zwei Zufallsvariablen X und Y . Sei X = |A|. Y sei die Anzahl der
Kanten von G in dem von G auf A induzierten Graphen. Dies ist einfach der Graph
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 17
mit der Knotenmenge A, der alle Kanten aus G enthält, die Knoten in A haben.
Dann gilt
EX = pn und EY = mp2 =1
2ndp2.
Es folgt
E(X − Y ) = pn(1 − pd/2).
Dann muß es also eine Teilmenge A der Knotenmenge V geben, für die die Differenz
aus der Anzahl der Knoten (|A|) und der Kanten in A
≥ pn(1 − pd/2)
ist.
Wir modifizieren nun A, indem wir einfach von jeder Kante, die sich noch im von
G induzierten Graph befindet, einen Knoten entfernen. Dadurch ändert sich die
Differenz aus Anzahl der Knoten und Anzahl der Kanten nicht. Übrig bleibt aber
eine Menge B, in der G keine Kanten mehr hat - eine Anticlique. Außerdem ist
|B| ≥ pn(1 − pd/2).
Wir müssen schließlich nur noch p = 1/d (optimal) wählen, um |B| ≥ n/(2d) zu
erhalten.
2.2.2 Graphen mit weiter Taille und großer chromatischer Zahl
Unser nächstes Beispiel stammt ebenfalls aus der Graphentheorie. Dazu benötigen
wir zwei weitere graphentheoretische Invarianten. Die chromatische Zahl χ(G) ei-
nes Graphen G ist die kleinste Anzahl von Farben, mit denen man die Knoten des
Graphen so färben kann, daß die Endpunkte jeder Kante verschiedene Farben erhal-
ten. Man könnte vermuten, daß ein Graph mit hoher chromatischer Zahl auch einen
großen vollständigen Teilgraphen enthalten muß, da es ja schwierig ist, ihn mit we-
nigen Farben zu färben. Wir wollen in diesem Abschnitt einsehen, daß das Gegenteil
der Fall ist.
Ein erstes Ergebnis in diese Richtung wurde von B. Descartes um 1940 gefunden,
die Graphen mit beliebig hoher chromatischer Zahl konstruiet hat, die trotzdem kei-
ne Dreiecke enthalten. Diese Beispiele enthielten allerdings viele Kreise der Länge
4. Ein Kreis in einem Graphen G = (V, E) ist eine Folge v1, . . . , vn von paarweise
18 2.2 Kleine Modifikationen
verschiedenen Knoten, so daß vi, vi+1 ∈ E und vn, v1 ∈ E sind. Die Taillenweite
γ(G) eines Graphen G ist die Länge eines kürzesten Kreises. Es gibt natürlich kreis-
freie Graphen, sogenannte Wälder, deren chromatische Zahl 2 ist, die also für unsere
Betrachtungen hier keine Rolle spielen.
Können wir Graphen finden, die keine Kreise kleiner Länge haben, aber trotzdem
viele Farben zum Färben benötigen? Die positive Antwort gibt das folgende Theorem
von P. Erdös (1959).
Theorem 8. Zu jedem k ≥ 3 gibt es einen Graphen mit chromatischer Zahl min-
destens k und Taillenweite mindestens k.
Zur Vorbereitung überlegen wir uns, daß für jeden Graph G mit n Knoten und
Anticliquenzahl α(G)
χ(G) ≥ n
α(G)
gilt. Tatsächlich müssen ja bei einer zulässigen Färbung von G die Knoten, die eine
gemeinsame Farbe erhalten, eine Anticlique bilden und somit Kardinalität höchstens
α(G) haben. Dann folgt aber α(G)χ(G) ≥ n. Um das Theorem zu beweisen, genügt
es also, Graphen mit relativ kleiner Anticliquenzahl, aber großer Taillenwmeite zu
konstruieren.
Außerdem benötigen wir die elementare Ungleichung
1 + x ≤ ex für alle reellen x,
die sich sofort aus der Konvexität der Exponentialfunktion f(x) = ex und f(0) =
f ′(0) = 1 ergibt.
Beweis. Wir benutzen unseren Wahrscheinlichkeitsraum G(n, p) mit
p = n− k
k+1 .
Für eine feste Menge aus r Knoten ist die Wahrscheinlichkeit, daß diese Menge eine
Anticlique bildet, gleich (1 − p)(r
2). Damit erhalten wir
P(α(G) ≥ r) ≤(
n
r
)
(1 − p)(r
2) ≤(
n(1 − p)r−1
2
)r.
Mit der Abschätzung 1 − p ≤ e−p erhalten wir
P(α(G) ≥ r) ≤(
ne−p(r−1)/2)r
.
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 19
Wir zeigen jetzt, daß
P(
α(G) ≥ n
2k
)
<1
2(2.1)
für genügend großes n gilt. Dazu beobachten wir, daß n1
k+1 ≥ 6k log n für genügend
großes n gilt, was dann
p = n− k
k+1 ≥ 6k log n
n
impliziert. Mit r = d n2ke folgt pr ≥ 3 log n und somit
ne−p(r−1)/2 = ne−pr/2ep/2 ≤ ne−3 log n/2e1/2 =
√
e
n.
Dies geht für n → ∞ gegen 0, somit auch
P(α(G) ≥ r) ≤( e
n
)r/2.
Wir schauen uns nun die Taillenweite von G an. Zunächst wollen wir zeigen, daß
G „nicht zuviel“ Kreise der Länge ≤ k enthält. Sei also 3 ≤ h ≤ k und A ⊂ V
eine Menge mit |A| = h. Die Zahl der möglichen Kreise der Länge h, die aus den
Knoten aus A gebildet werden können, ist gleich der halben Anzahl der zyklischen
Permutationen von A:(h − 1)!
2.
Jeder dieser Kreise hat Wahrscheinlichkeit ph. Ist nun X die Gesamtzahl der Kreise
mit einer Länge ≤ k, so erhalten wir mittels Linearität des Erwartungswerts
EX =
k∑
h=3
(
n
h
)
(h − 1)!
2ph ≤ 1
2
k∑
h=3
nhph ≤ 1
2(k − 2)nkpk
wegen np = n1
k+1 ≥ 1. Schließlich wenden wir noch die Markov-Ungleichung an:
P(
X ≥ n
2
)
≤ EX
n/2≤ (k − 2)nkpk
n= (k − 2)n− 1
k+1 .
Also gilt für genügend großes n auch
P(
X ≥ n
2
)
<1
2.
Zusammen mit (2.1) liefert uns die letzte Ungleichung also einen Graphen G mit
20 2.2 Kleine Modifikationen
• α(G) < n2k
• Die Anzahl der Kreise in G mit Länge ≤ k ist kleiner als n2 .
Wir modifizieren nun noch den Graphen G, indem wir aus jedem tatsächlich vor-
kommenden Kreis der Länge ≤ k einen Knoten entfernen und somit alle Kreise der
Länge ≤ k beseitigen. Den resultierenden Graphen wollen wir H nennen. Dann hat
H offenbar
• ≥ n2 Knoten
• Taillenweite γ(G) > k
• α(H) < n2k , also auch
χ(H) ≥ n/2
α(H)>
n/2
n/2k= k.
Solch einen Graphen haben wir gerade gesucht!
2.2.3 Packungen konvexer Mengen
Ein wichtiges Teilgebiet der Geometrie beschäftigt sich mit guten Packungen und
Überdeckungen von Räumen (wie etwa des euklidischen Raumes Rd oder der Sphäre
Sd−1 = x ∈ R
d : ‖x‖2 = 1) mit Kugeln oder allgemeineren Mengen, z.B. konve-
xen Mengen. Zwei typische Beispiele sind das Kepler-Problem und das Diktatoren-
Problem.
Kepler-Problem: Gesucht ist die dichteste Packung von Kugeln mit Radius 1 in
Rd. (J. Kepler hat das Problem für d = 3 formuliert und die tatsächlich optimale
Packung vermutet.)
Diktatoren-Problem: Man verteile n Punkte (Diktatoren) auf der Sphäre Sd−1
derart, daß der minimale Abstand zwischen verschiedenen Punkten maximiert wird.
Die optimale Lösung für das Kepler-Problem kennt man nur für d = 2 und d =
3. Letzteres wurde erst vor ein paar Jahren unter massivem Computereinsatz von
T. Hales bewiesen. Auch die optimale Lösung des Diktatorenproblems ist nur für
wenige Paare (d, n) mit d ≥ 3 bekannt.
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 21
Gute Packungen und Überdeckungen in Räumen großer Dimension kann man oft
mittels der probabilistischen Methode finden. Wir wollen uns hier das folgende allge-
meine Packungsproblem anschauen. Sei K ⊂ Rd eine beliebige beschränkte meßbare
Menge. Wie dicht kann man kongruente Kopien von K ohne Überlappungen packen?
Zur genauen Problemformulierung sei W (x) der Würfel [0, x]d mit Seitenlänge x. Eine
Packung von K in W (x) ist eine Familie paarweise disjunkter kongruenter Kopien
von K, die alle in W (x) enthalten sind. Sei f(x) die maximale Kardinalität einer
Packung von K in W (x). Die Packungsdichte definieren wir dann als
δ(K) = limx→∞
f(x)
xd.
Man kann zeigen, daß dieser Limes existiert. Ohne diese Tatsache könner wir in
folgendem Theorem einfach den Limes durch den Limes inferior ersetzen.
Theorem 9. Sei K ⊂ Rd eine beschränkte konvexe zentralsymmetrische Menge mit
Mittelpunkt 0. Dann gilt
δ(K) ≥ 2−d−1.
Beweis. Wir wählen Punkte P1, . . . , Pn in W (x) zufällig unabhängig voneinander
mit uniformer Verteilung, d.h.
P(Pi ∈ A) =|A|
|W (x)| =|A|xd
für jede meßbare Menge A ⊂ W (x). Unsere Kopien von K seien Ki = Pi + K, i =
1, . . . , n. Wir haben zwei Probleme. Einerseits können sich einige der Ki überlappen,
außerdem können einige der Ki über den Rand von W (x) hinausragen.
Behandel wir zunächst das erste Problem. Wir berechnen zunächst die Wahrschein-
lichkeit, daß sich Ki und Kj für i 6= j überlappen. In diesem Fall muß es Qi, Qj ∈ K
mit Pi +Qi = Pj +Qj geben. Also gilt wegen der Konvexität und Symmetrie von K
Pi − Pj = Qj − Qi = 2Qj − Qi
2∈ 2K.
Folglich ist Pi ∈ Pj + 2K, was mit Wahrscheinlichkeit |2K|xd eintritt. Wir folgern
P(Ki ∩ Kj 6= ∅) ≤ P(Pi ∈ Pj + 2K) =|2K|xd
=2d|K|
xd.
22 2.3 Die Zweite-Momenten-Methode
Sei nun X die Anzahl der Paare (i, j) mit i < j, für die sich Ki und Kj überlappen.
Die Linearität des Erwartungswertes liefert nun
EX =∑
1≤i<j≤n
P(Ki ∩ Kj 6= ∅) ≤(
n
2
)
2dx−d|K| ≤ n22d−1x−d|K|.
Folglich gibt es Punkte K1, . . . , Kn mit höchstens dieser Anzahl von sich überlap-
penden Ki, Kj . Für je zwei sich überlappende Ki ∩ Kj 6= ∅ nehmen wir entweder
Ki oder Kj aus unserer Familie von Kopien heraus und erhalten eine Packung aus
mindestens
n − n22d−1x−d|K|
Kopien von K. Zum Maximieren setzen wir n = xd2−d|K|−1, wobei wir nur noch
solche x betrachten, für die dies eine ganze Zahl liefert. Wir erhalten eine Packung
aus mindestens
xd2−d−1|K|−1
Kopien.
Nicht alle diese Kopien liegen aber ganz in W (x). Um dieses Problem zu behandeln,
sei s > 0 so, daß K ⊂ [−s, s]d gilt. Dann liegen alle unsere Kopien Ki in [−s, x + s]d
und somit in einem Würfel mit Kantenlänge x + 2s. Wir erhalten
f(x + 2s) ≥ xd2−d−1|K|−1
und folglich
δ(K) ≥ limx→∞
|K|f(x + 2s)
(x + 2s)d≥ lim
x→∞
(
x
x + 2s
)d
2−d−1.
2.3 Die Zweite-Momenten-Methode
In diesem Abschnitt wollen wir neben dem Erwartungswert die nächste wichtige
Charakteristik einer Zufalssvariable benutzen - ihere Varianz. Sie ist ein Maß dafür,
wie sehr eine Zufallsvariable um ihren Erwartungswert schwankt. Für eine konstante
Zufallsvariable ist die Varianz 0.
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 23
Die Varianz einer reellen Zufallsvariable X ist definiert als
Var X = E(X − EX)2 = EX2 − (EX)2.
EX2 heißt zweites Moment und σ = σ(X) =√
Var X Standardabweichung von X.
Die Varianz ist nicht linear wie der Erwartungswert. Wollen wir die Varianz einer
Summe zweier Zufallsvariablen berechnen, so müssen wir etwas über ihre Abhängig-
keit wissen. Dazu brauchen wir die Covarianz
Cov (X, Y ) = E((X − EX)(Y − EY )) = E(XY ) − EX · EY.
Sind X und Y unabhängig, so ist ihre Covarianz 0.
Lemma 10.
Varn
∑
i=1
Xi =n
∑
i=1
Var Xi + 2∑
1≤i<j≤n
Cov (Xi, Xj).
Beweis.
Varn
∑
i=1
Xi = E
(
n∑
i=1
Xi ·n
∑
j=1
Xj
)
−(
E
n∑
i=1
Xi
)
·(
E
n∑
j=1
Xj
)
=n
∑
i,j=1
E(XiXj) −n
∑
i,j=1
EXi · EXj
=n
∑
i=1
(EX2i − (EXi)
2) + 2∑
1≤i<j≤n
(E(XiXj) − EXi · EXj)
=n
∑
i=1
Var Xi + 2∑
1≤i<j≤n
Cov (Xi, Xj).
Sind also X1, . . . , Xn unabhängig (hier genügt sogar paarweise Unabhängigkeit), so
gilt
Varn
∑
i=1
Xi =n
∑
i=1
Var Xi.
Die Zweite-Momenten-Methode besteht in der Anwendung der
24 2.3 Die Zweite-Momenten-Methode
Chebyshev-Ungleichung: Ist X eine reelle Zufallsvariable mit endlicher Varianz
und t > 0, dann gilt
P(|X − EX| ≥ t) ≤ Var X
t2=
σ2
t2.
Die Chebyshev-Ungleichung ist nichts anderes als die Markov-Ungleichung für die
Zufallsvariable (X − EX)2 und a = t2.
Verlangt man von der Zufallsvariablen X nichts als Endlichkeit der Varianz, so ist
die Chevbyshev-Ungleichung optimal. Um dies einzusehen, kann man die dreiwertige
Zufallsvariable
X =
a mit Wahrscheinlichkeit p
a ± t mit Wahrscheinlichkeit 1−p2
betrachten. X hat Erwartungswert a, Varianz (1 − p)t2 und erfüllt
P(|X − a| ≥ t) = 1 − p,
also Gleichheit in der Chevbyshev-Ungleichung.
Für viele Zufallsvariable ist die Chevbyshev-Ungleichung aber sehr schlecht. Ist X
eine normalverteilte Zufallsvariable mit Erwartungswert µ und Varianz σ2, dann gilt
P(|X − µ| ≥ t) =2√2π
∫ ∞
t/σe−t2/2dt,
was asymptotisch zu 2√π
σt e−t2/2σ2
und somit für großes t wesentlich kleiner als σ2
t2
ist.
2.3.1 Mengen mit verschiedenen Summen
Diesmal wenden wir uns zur Demonstration der zweiten Momentenmethode wieder
einem Problem aus der additiven Zahlentheorie zu. Wir wollen sagen, daß eine Menge
x1, . . . , xk von natürlichen Zahlen verschiedene Summen hat, falls alle Summen∑
i∈S
xi ; S ⊂ 1, . . . , k
paarweise verschieden sind. Ein offensichtliches Beispiel erhält man mit xi = 2i.
Sei nun f(n) die maximale Kardinalität einer Teilmenge von 1, 2, . . . , n mit ver-
schiedenen Summen. Das gerade angeführte Beispiel zeigt, daß sicherlich
f(n) ≥ 1 + blog2 nc
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 25
gilt. Wie gut ist diese Abschätzung? Für die Lösung des folgenden Problems hat P.
Erdös 300 $ offeriert.
Problem: Gibt es eine Konstante C, so daß
f(n) ≤ log2 n + C
für alle n ist?
Wir wollen zunächst (ohne die probabilistische Methode) die Abschätzung
f(n) ≤ log2 n + log2 log2 n + C
beweisen. Dazu sei also eine Menge der Kardinalität k in 1, 2, . . . , n, die verschie-
dene Summen hat. Es gibt also 2k verschiedene Summen, die man aus Elementen
der Menge bilden kann, und alle diese Summen sind offenbar natürliche Zahlen (ein-
schließlich der 0) kleiner als kn. Folglich ist
2k ≤ kn. (2.2)
Ist nun
k > log2 n + log2 log2 n + 2, (2.3)
so erhalten wir aus der Monotonie der Funktion 2x
x ( für genügend großes x)
2k
k>
2log2 n+log2 log2 n+2
log2 n + log2 log2 n + 2≥ 4n log2 n
2 log2 n= 2n
für genügend großes n im Widerspruch zu (2.2). Also kann (2.3) nur für endlich viele
n gelten, was die Behauptung beweist.
Mit der probabilistischen Methode und der Chebyshev-Ungleichung kann man dieses
Resultat verbessern zu folgendem
Theorem 11. Es gibt eine Konstante C, so daß für alle n
f(n) ≤ log2 n +1
2log2 log2 n + C
gilt.
26 2.3 Die Zweite-Momenten-Methode
Beweis. Seien δ1, . . . , δk unabhängige 0, 1-wertige Zufallsvariable mit
P(δi = 0) = P(δi = 1) =1
2.
Solche Zufallsvariablen bezeichnet man oft als Selektoren, da eine gewisse Teilmenge
i : δi = 1 der Menge 1, . . . , k ausgewählt wird. Ist nun x1, . . . , xk ⊂ 1, . . . , neine Menge mit verschiedenen Summen, so betrachten wir die zufällige Summe
X = δ1x1 + δ2x2 + . . . + δkxk.
Der Erwartungswert von X ergibt sich mittels Linearität des Erwartungswerts als
EX =
k∑
i=1
Eδixi =1
2
k∑
i=1
xi
und die Varianz wegen der Unabhängigkeit der Variablen δi als
Var X =k
∑
i=1
Var (δixi) =k
∑
i=1
x2i Var δi =
1
4
k∑
i=1
x2i ≤ kn2
4.
Dann liefert die Chebyshev-Ungleichung für jedes t > 0
P(|X − EX| ≥ t) ≤ kn2
4t2. (2.4)
Weiter erhalten wir
P(|X − EX| ≤ t) =EX+t∑
s=EX−t
P(X = s). (2.5)
Jede Summe s kann aber nach Voraussetzung nur auf höchstens eine Art angenom-
men werden. Also ist
P(X = s) =
2−k falls s angenommen wird
0 sonst.
Folglich erhalten wir wegen (2.5)
P(|X − EX| ≤ t) ≤ 2−k(2t + 1),
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 27
was zusammen mit (2.4) zu der Ungleichung
1 = P(|X − EX| ≥ t) + P(|X − EX| < t) ≤ kn2
4t2+ 2−k(2t + 1)
führt. Wir setzen nun (optimal) t =√
3kn2 und erhalten
1 ≤ 2−k(√
3kn + 1) +1
3
oder umgestellt
n ≥232k − 1√
3k.
Benutzt man dies wie oben (2.2), so erhält man die Behauptung des Theorems.
2.3.2 Anzahl von Primfaktoren
Für eine natürliche Zahl n sei f(n) die Anzahl der verschiedenen Primzahlen, die
n teilen. Wie groß ist f(n) für eine „typische “ natürliche Zahl n? Die Antwort,
die in folgendem Theorem gegeben wird, besagt, daß „fast alle “ n etwa log log n
Primteiler haben. Dies wurde 1920 von G. Hardy und S. Ramanujan mit einem recht
komplizierten Argument bewiesen. Der folgende Beweis mittels der probabilistischen
Methode stammt von P. Turan 1934.
Theorem 12. Sei φ(n) ein beliebig langsam gegen unendlich strebende Funktion. Ist
A(n) = #x ∈ 1, . . . , n : |f(x) − log log n| > φ(n)√
log log n,
so gilt A(n) = o(n).
Vorbemerkung: Wir wollen hier eine Anleihe aus der Zahlentheorie machen, die wir
nicht beweisen. Beweise der folgenden Abschätzung für die Summe von Reziproken
von Primzahlen finden sich in Bücher zur Zahlentheorie, in denen der Primzahlsatz
beweisen wird. Der Beweis ist aber wesentlich einfacher als der Beweis des Primzahl-
satzes.∑
p≤x
1
p= log log x + O(1) (2.6)
Hierbei läuft die Summe über alle Primzahlen p ≤ x.
28 2.3 Die Zweite-Momenten-Methode
Beweis von Theorem 12. Sei x ∈ 1, . . . , n zufällig gewählt mit P(x = k) = 1/n für
k = 1, . . . , n. Wir setzen für jede Primzahl p
Xp =
1 falls p Teiler von x ist
0 sonst.
Weiter sei M = n1/10. Der Exponent 1/10 ist nicht wichtig, jede kleine Potenz von
n geht ebenfalls. Außerdem sei
X =∑
p≤M
Xp = Anzahl der Primteiler ≤ M von x.
Da jedes x höchstens 10 Primteiler haben kann, die größer als M sind, erhalten wir
f(x) − 10 ≤ X(x) ≤ f(x).
Es genügt also, das Theorem mit X(x) anstelle von f(x) zu zeigen. Die Behauptung
geht dann über in
P(|X(x) − log log n| > φ(n)√
log log n) = o(1). (2.7)
Um diese Ungleichung mittels der Chebyshev-Ungleichung zu beweisen, benötigen
wir Erwartungswert und Varianz von X. Wir berechnen zunächst
EXp =
⌊
np
⌋
n=
1
p+ O(n−1),
was mittels Linearität des Erwartungswerts und (2.6)
EX =∑
p≤M
EXp =∑
p≤M
1
p+ O(Mn−1) = log log M + O(1) = log log n + O(1)
liefert. Für die Varianz von X benutzen wir die Formel
Var X =∑
p≤M
Var Xp + 2∑
p<q≤M
Cov (Xp, Xq).
Mittels (2.6) erhalten wir zunächst
V arXp = EX2p − (EXp)
2 = EXp − (EXp)2 =
1
p− 1
p2+ O(n−1).
Kapitel 2. Elementare Prinzipien für die probabilistische Methode 29
Um die Covarianzen zu berechnen, beobachten wir zunächst
XpXq =
1 falls pq Teiler von x ist
0 sonst.
Folglich ist
Cov (Xp, Xq) = E(XpXq) − EXp · EXq =
⌊
npq
⌋
n−
⌊
np
⌋
n·⌊
nq
⌋
n
≤ 1
pq−
(
1
p− 1
n
) (
1
q− 1
n
)
≤(
1
p+
1
q
)
1
n.
Aufsummieren ergibt unter nochmaliger Verwendung von (2.6)
2∑
p<q≤M
Cov (Xp, Xq) ≤2
n
∑
p<q≤M
(
1
p+
1
q
)
≤ 2M
n
∑
p≤M
1
p= 2n−9/10(log log n+O(1)) = o(1).
Analog zeigt man
2∑
p<q≤M
Cov (Xp, Xq) ≥ −o(1).
Die Covarianzen beeinflussen also die Varianz nicht:
Var X =∑
p ≤ M
(
1
p− 1
p2
)
+ o(1) = log log n + O(1).
Mittels des errechneten Erwartungswerts und der Varianz von X ergibt sich schließ-
lich aus der Chebyshev-Ungleichung
P(|X(x) − log log n| > φ(n)√
log log n) ≤ log log n + O(1)
φ(n)2 log log n= o(1).
30
Kapitel 3
Konzentrationsungleichungen
Wir betrachten zur Einleitung in dieses Kapitel das folgende Beispielproblem: Wie
groß ist der typische maximale Grad eines zufälligen Graphen in G(n, 1/2)? Wir
müssen also die Zufallsvariable
dmax(G) = maxu∈V
d(u)
für einen zufälligen Graphen G = (V, E) behandeln. Es ist erst einmal nicht klar, wie
sich diese Zufallsgröße verhält, insbesondere wie groß ihr Erwartungswert ist. Was
wir natürlich wissen, ist der durchschnittliche Grad für einen festen Knoten u:
Ed(u) =n − 1
2=: d.
Das sagt aber noch nichts über Edmax aus. Hätten wir aber eine Ungleichung (für
festes u) der Form
P(d(u) ≥ d + t) ≤ 1
n2,
so erhalten wir
P(dmax ≥ d + t) = P(maxu
d(u) ≥ d + t) ≤∑
u∈V
P(d(u) ≥ d + t) ≤ 1
n,
also
P(dmax < d + t) ≥ 1 − 1
n,
d.h. “fast alle„Graphen haben maximalen Grad höchstens d + t. Wir werden später
sehen, daß man t = c√
n log n wählen kann.
Kapitel 3. Konzentrationsungleichungen 31
Man braucht also hier wie auch in vielen anderen Anwendungen Abschätzungen der
Form
P(X ≥ EX + t) ≥ . . .
oder auch
P(X ≥ EX − t) ≤ . . .
bzw.
P(|X − EX| ≥ t) ≤ . . .
Solche Abschätzungen nennt man Konzentrationsungleichungen oder auch Unglei-
chungen für große Abweichungen (large deviation inequalities, tail estimates). Die-
se Bezeichnung kommt daher, daß die Werte der Zufallsvariable sich um den Er-
wartungswert konzentrieren, also mit großer Wahrscheinlichkeit im Intervall (EX −t, EX + t) liegen.
Wir kennen bereits die Chebyshev-Ungleichung als eine Ungleichung dieser Form:
P(|X − EX| ≥ t) ≤ Var X
t2.
Benutzen wir diese Ungleichung für unser Beispielproblem, erhalten wir
Var d(u) = Ed(u)2 − (Ed(u))2 =n − 1
4
und somit
P(|d(u) − d| ≥ t) ≤ n − 1
4t2.
Damit dies kleiner als 1/n ist, brauchen wir t > (n − 1)/2, somit liefert uns die
Chebyshev-Ungleichung überhaupt keine brauchbare Aussage. In den folgenden Ab-
schnitten wollen wir einsehen, wie man bessere Konzentrationsungleichungen für
Summen unabhängiger Zufallsvariablen beweisen und anwenden kann.
3.1 Summen unabhängiger Bernoulli-Variablen
Wir betrachten zunächst wieder unser Beispielproblem aus der vorhergehenden Ein-
leitung. Hier ist
d(u) =∑
v 6=u
Xv
32 3.1 Summen unabhängiger Bernoulli-Variablen
mit den unabhängigen Indikatorvariablen
Xv =
1 falss u, v eine Kante ist
0 sonst
Wir haben es also mit einer Summe unabhängiger 0, 1-wertiger Zuvallsvariablen
zu tun, wobei die Werte 0 und 1 jeweils mit Wahrscheinlichkeit 1/2 angenommen
werden. Um die folgenden Betrachtungen zu vereinfachen, zentrieren wir diese Varia-
blen, so daß sie Erwartungswert 0 bekommen. Dann erhalten wir Bernoulli-Variablen
(auch Rademacher-Variablen genannt. Das sind unabhängige +1,−1-wertige Va-
riable X1, . . . , Xn mit
P(Xi = +1) = P(Xi = −1) =1
2.
Durch einfache Reskalierung kann man Konzentrationsungleichungen für Bernoulli-
Variablen auf die Variablen aus unserem Beispielproblem umrechnen. Hier ist nun
eine solche Konzentrationsungleichung:
Theorem 13 (Chernoff-Ungleichung). Seien X1, . . . , Xn unabhängige Bernoulli-
Variable und sei
Sn = X1 + X2 + . . . + Xn.
Dann gilt für jedes t > 0
P(Sn ≥ t) < exp(
− t2
2σ2
)
und P(Sn ≤ −t) < exp(
− t2
2σ2
)
mit σ2 = VarSn = n. Insbesondere hat man auch
P(|Sn| ≥ t) < 2 exp(
− t2
2σ2
)
.
Beweis. Wir beweisen nur die erste Ungleichung. Die zweite folgt aus Symmetrie-
gründen. Die dritte ist nur eine Zusammenfassung der beiden ersten.
Statt direkt die Variable Sn zu betrachten, schauen wir uns die Variable Y = eαSn
an, wobei wir den Parameter α später wählen. Auf diese Variable wenden wir die
Markov-Ungleichung an und erhalten
P(Sn ≥ t) = P(Y ≥ eαt) ≤ EY
eαt. (3.1)
Kapitel 3. Konzentrationsungleichungen 33
Wir berechnen zunächst unter Benutzung der Unabhängigkeit der Xi
EY = E
(
exp(αn
∑
i=1
Xi
)
= E
n∏
i=1
eαXi =n
∏
i=1
EeαXi =n
∏
i=1
eα + e−α
2=
(
eα + e−α
2
)n
.
Durch Taylorentwicklung sieht man leicht die Ungleichung
eα + e−α
2≤ eα2n/2
ein, die dann mit (3.1) die Abschätzung
P(Sn ≥ t) ≤ exp(α2n
2− αt
)
liefert. Schließlich setzen wir noch α = t/n, um bei der Chernoff-Ungleichung anzu-
kommen.
Wir wollen nun die gerade bewiesene Chernoff-Ungleichung auf unser Beipielproblem
des maximalen Grades eines zufälligen Graphen anwenden. Dazu beobachten wir, daß
die Variablen 2Xv − 1 Bernoulli-Variablen sind, womit sich auch
Sn−1 = 2∑
v 6=u
Xv − (n − 1) = 2d(u) − (n − 1)
ergibt. Die Chernoff-Ungleichung liefert nun für jeden festen Knoten u
P(d(u) ≥ d + t) = P(Sn−1 ≥ 2t) ≤ exp(
− 2t2
n − 1
)
.
Setzen wir noch t =√
(n − 1) log n, so erhalten wir
P(
d(u) ≥ (n − 1)/2 +√
(n − 1) log n)
≤ 1
n2
und somit auch
P(
maxu∈V
d(u) ≥ (n − 1)/2 +√
(n − 1) log n)
≤ 1
n.
34 3.1 Summen unabhängiger Bernoulli-Variablen
3.1.1 Kombinatorische Diskrepanz
Als weitere Anwendung der Chernoff-Ungleichung wollen wir die kombinatorische
Diskrepanz betrachten. Ist X eine n-elementige Menge, A ⊂ X eine Teilmenge und
χ : X → −1, +1 eine Färbung von X mit zwei Farben, so ist die Diskrepanz von
X auf A gegeben durch
disc (A, χ) =∑
x∈A
χ(x).
Sie gibt die Abweichung von der „ausgeglichenen Färbung“ an, die die gleiche Anzahl
von Punkten von A mit jeder der beiden Farben färbt. Ist F ein gegebenes System
von Teilmengen von X, so heißt
disc (F , χ) = maxA∈F
disc (A, χ)
die Diskrepanz von F bei der Färbung χ und
discF = minχ
disc (F , χ)
die Diskrepanz von F . Hierbei läuft das letzte Minimum über alle möglichen Fär-
bungen χ.
Ist F = 2X das System aller Teilmengen von X, so ist offenbar
discF =⌈n
2
⌉
.
Wir wollen jetzt zeigen, daß die Diskrepanz viel kleiner wird, wenn F nicht zu viele
Mengen enthält.
Theorem 14. Sei |X| = n, F ⊂ 2X , |F| = m. Dann gilt
discF ≤√
2n log(2m).
Enthält F nur höchstens s-elementige Teilmengen, so gilt
discF ≤√
2s log(2m).
Beweis. Wir beweisen nur die zweite Ungleichung, die erste ist ein Spezialfall. Wir
färben X zufällig, wobei wir die Farben der Punkte unabhängig voneinander mit
P(χ(x) = +1) = P(χ(x) = −1) =1
2
Kapitel 3. Konzentrationsungleichungen 35
wählen. Sei A ⊂ X fixiert. Dann ist
disc (A, χ) =∑
x∈A
χ(x)
eine Summe von |A| unabhängigen Bernoulli-Variablen. Die Chernoff-Ungleichung
liefert dann
P(|disc (A, χ)| ≥ t) < 2 exp(
− t2
2|A|)
≤ 2 exp(
− t2
2s
)
.
Für t =√
2s log(2m) liefert dies
P(|disc (A, χ)| ≥ t) <1
m.
Folglich gilt
P(disc (F , χ) ≥ t) ≤∑
A∈FP(|disc (A, χ)| ≥ t) < 1.
Es gibt also eine Färbung χ mit disc (F , χ) < t).
3.1.2 Ein Spiel
Wir wollen ein weiteres Beispiel für die Anwendung der Chernoff-Ungleichung be-
trachten. Diesmal geht es um ein Beispiel aus der Spieltheorie.
Das Spiel wird von den zwei Spielern Walter der Wähler und Dieter der Drücker
gespielt. Eine natürliche Zahl n ≥ 1 ist vorgegeben. Das Spiel findet im Rn statt und
läuft über n Runden. Es gibt nach jeder Runde einen Positionsvektor P ∈ Rn, der
vor dem ersten Zug auf 0 gesetzt wird. Eine Runde besteht aus je einem Zug jedes
Spielers:
1. Dieter sucht sich einen Vektor v ∈ +1,−1n aus.
2. Walter wählt als neuen Positionsvektor P entweder P + v oder P − v aus.
Nach der n-ten Runde erhält Dieter als Auszahlung max1≤k≤n |Pk|, den maximalen
Absolutbetrag der Koordinaten des Positionsvektors.
Sei Wert (n) der Wert dieses Spiels für Dieter, d.h. die maximale Auszahlung, die er
bei optimaler Gegenwehr von Walter erreichen kann. Sei Sn wieder die Summe von
n unabhängigen Bernoulli-Variablen. Dann gilt
36 3.2 Summen beschränkte runabhängiger Variablen
Theorem 15. Falls P(|Sn| > t) < 1n ist, dann gilt Wert (n) ≤ t.
Beweis. Wir wollen sagen, daß Dieter gewinnt, falls die Auszahlung nach Runde n
größer als t ist. Nehmen wir nun an, daß Walter als Strategie in jeder Runde durch
einen Münzwurf bestimmt, ob er P + v oder P − v als neuen Positionsvektor wählt.
Sei xi die i−te Koordinate des Positionsvektors nach der n-ten Runde. Sei weiter Wi
das Ereignis |xi| > t und W = ∪ni=1 das Ereignis, daß Dieter gewinnt. Unabhängig
von der Spielweise von Dieter hat xi immer die Verteilung Sn einer Summe von n
unabhängigen Bernoulli-Variablen. Somit folgt aus der Voraussetzung
P(W ) ≤n
∑
i=1
P(|Sn| > t) < 1.
Also kann Dieter das Spiel nicht immer gewinnen. Da dies ein Spiel mit vollständiger
Information und ohne Unentschieden ist, hat einer der beiden Spieler aber eine Ge-
winnstrategie. Dies kann nur Walter sein. Also gewinnt Walter bei optimalem Spiel
immer und es gilt Wert (n) ≤ t.
Aus der Chernoff-Ungleichung ergibt sich dann sofort die
Folgerung: Wert (n) ≤√
2n log(2n).
Bemerkung: Es gilt auch Wert (n) ≥ c√
n log n mit einer von n unabhängigen
Konstanten c > 0. Ein Beweis findet sich im Buch von N. Alon/ J. Spencer im
Abschnitt 14.4.
3.2 Summen beschränkter unabhängiger Variablen
Exponentielle Konzentrationsungleichungen gelten in viel größerer Allgemeinheit als
in Abschnitt 3.1. bewiesen. In diesem Abschnitt wollen wir nur die Beschränktheit
der Zufallsvariablen Xi fordern.
Theorem 16 (Hoeffding-Ungleichung). Seine X1, . . . , Xn unabhängige Zufalls-
variable mit EXi = 0 und Xi ∈ [ai, bi] fast sicher, wobei ai < 0 < bi für i = 1, . . . , n
ist. Mit Sn = X1 + . . . + Xn gilt dann für alle t ≥ 0
P(Sn ≥ t) < exp(
− 2t2∑n
i=1(bi − ai)2
)
und P(Sn ≤ −t) < exp(
− 2t2∑n
i=1(bi − ai)2
)
Kapitel 3. Konzentrationsungleichungen 37
mit σ2 = VarSn = n. Insbesondere hat man auch
P(|Sn| ≥ t) < 2 exp(
− 2t2∑n
i=1(bi − ai)2
)
.
Bemerkung: Sind die Xi Bernoulli-Variablen, so erhält man gerade die Chernoff-
Ungleichung.
Beweis. Wir brauchen wieder nur die erste Ungleichung zu zeigen. Wir setzen wieder
Y = eαSn und erhalten
P(Sn ≥ t) = P(Y ≥ eαt) ≤ EY
eαt(3.2)
mit
EY =n
∏
i=1
EeαXi . (3.3)
Nun gilt wegen der Konvexität der Exponentialfunktion und Xi ∈ [ai, bi]
eαXi = exp(bi − Xi
bi − aiαai +
Xi − ai
bi − aiαbi
)
≤ bi − Xi
bi − aieαai +
Xi − ai
bi − aieαbi .
Nehmen wir nun den Erwartungswert und beachten EXi = 0, so bekommen wir
EeαXi ≤ bi
bi − aieαai +
−ai
bi − aieαbi .
Wir werden unten zeigen, daß für beliebige a < 0 < b und α > 0 die Ungleichung
b
b − aeαa +
−a
b − aeαb ≤ exp
α2(b − a)2
8(3.4)
gilt. Benutzen wir dies in der vorhergehenden Ungleichung und setzen die erhaltene
Abschätzung für den Erwartungswert zunächst in (3.3) und dann in (3.2) ein, landen
wir bei
P(Sn ≥ t) ≤ exp(
− αt +α2
8
n∑
i=1
(bi − ai)2)
.
Setzt man in dieser Ungleichung (optimal)
α =4t
∑ni=1(bi − ai)2
erhält man gerade die im Theorem behauptete Ungleichung.
38 3.2 Summen beschränkte runabhängiger Variablen
Es bleibt also (3.4) zu zeigen. Dazu substituieren wir
λ =−a
b − a∈ (0, 1) und u = α(b − a) > 0
und erhalten
b
b − aeαa +
−a
b − aeαb = e−λu(1 − λ + λeu) =: f(u)
und
eα2(b−a)2/8 = eu2/8.
Setzen wir noch L(u) = log f(u) = −λu + log(1 − λ + λeu), so haben wir
L(u) ≤ u2
8(3.5)
zu zeigen. Dazu berechnen wir zunächst
L′(u) = −λ +λ
λ + (1 − λ)e−u
L′′(u) =λ(1 − λ)e−u
(λ + (1 − λ)e−u)2.
Für ein gewisses v ∈ [0, u] haben wir nun
L(u) = L(0) + L′(0)u + L′′(v)u2
2= L′′(v)
u2
2.
Es genügt also
L′′(v) =λ(1 − λ)e−v
(λ + (1 − λ)e−v)2≤ 1
4
oder, äquivalent ungeformt,
4λ(1 − λ)e−v ≤ (λ + (1 − λ)e−v)2
zu beweisen. Letzteres ist aber äquivalent zu der offensichtlichen Ungleichung
0 ≤ (λ − (1 − λ)e−v)2.
Bemerkung: Man findet in der Literatur eine Reihe ähnlicher Konzentrationsun-
gleichungen, z.B. unter dem Namen Bernstein-Ungleichung. Mitunter ist die eine
oder andere Ungleichung schärfer, meist aber nur unwesentlich.
Kapitel 3. Konzentrationsungleichungen 39
3.3 Geometrische Diskrepanz
Als Beispiel für die Anwendung der Hoeffding-Ungleichung wollen wir uns wieder
ein Diskrepanzproblem anschauen. Das Problem in diesem Abschnitt ist motiviert
durch sogenannte Quasi-Monte-Carlo-Methoden für die numerische Integration, die
oftmals in der Praxis eingesetzt werden.
Wir wollen endliche Punktmengen finden, die möglichst gut das Volumen von Qua-
dern im d-dimensionalen Einheitswürfel [0, 1]d approximieren. Sei T = t(1), . . . , t(n) ⊂[0, 1]d. Für gegebenes x ∈ [0, 1]d sei
Bx = y ∈ Rd : 0 ≤ yi ≤ xi für i = 1, . . . , d
der achsenparallele Quader (Box mit linker unterer Ecke in 0 und rechter oberer Ecke
in x. Mit |Bx| = x1 . . . xd bezeichen wir das Volumen von Bx. Dann heißt
D(T, x) =1
n|T ∩ Bx| − |Bx|
die Diskrepanz der Menge T in der Box Bx. Dies ist offenbar ein Maß dafür, wie nahe
die Anzahl der Punkte von T in Bx gerade dem Anteil der Punkte ist, die die Box
Bx bei „gleichverteilten “ Punkten erhalten sollte. Die (Stern)-Diskrepanz von T ist
nun definiert durch
D∗(T ) = supx∈[0,1]d
|D(T, x)|.
Wir wollen kurz die Bedeutung dieses Begriffs für die numerische Integration kom-
mentieren. Dazu betrachten wir das Quadraturverfahren
Q(f) =1
n
n∑
i=1
f(t(i)
für die näherungsweise Berechnung des Integrals
I(f) =
∫
[0,1]df(x)dx
für Funktionen f : [0, 1]d → R. Ziel ist es dann, den Fehler e(f) = |I(f) − Q(f)| für
gewisse Klassen von Funktionen f möglichst klein zu machen. Für die charakteris-
tischen Funktionen 1IBxerhält man gerade e(f) = |D(T, x)|. Um diese Funktionen
40 3.3 Geometrische Diskrepanz
möglichst gut zu integrieren benötigt man also Punktmengen T mit kleiner Diskre-
panz. Dies wird in der sogenannten Koksma-Hlawka-Ungleichung
e(f) ≤ D∗(T )V (f)
auf eine größere Klasse von Funktionen verallgemeinert. Hier ist V (f) eine Variation
von f , die so genannte Variation nach Hardy und Krause.
Wir wollen nun mit der probabilistischen Methode die Existenz von Punktmengen
mit kleiner Diskrepanz auch für große Dimension d zeigen. Dazu wollen wir zunächst
das Problem der Berechnung der Diskrepanz diskretisieren. Sei Γm das äquidistante
Gitter in [0, 1]d mit Seitenlänge 1/m bestehend aus den (m + 1)d Punkten der Form
(k1/m, . . . , kd/m) mit k1, . . . , kd = 0, 1, . . . , m. Wir setzen
D∗m(T ) = max
x∈Γm
|D(T, x)|.
Dann gilt das folgende Lemma:
Lemma. D∗(T ) ≤ D∗m(T ) + d
m .
Beweis. Sei x ∈ [0, 1]d. Wähle x∗, y∗ ∈ Γm mit
x∗i ≤ xi ≤ x∗
i +1
m=: y∗i für i = 1, . . . , d.
Dann ist
|By∗ | − |Bx| = y∗1 . . . y∗d − x∗1 . . . x∗
d =d
∑
k=1
x∗1 . . . x∗
k−1y∗k . . . y∗d − x∗
1 . . . x∗ky
∗k+1 . . . y∗d
≤d
∑
k=1
(y∗k − x∗k) =
d
m.
Folglich ist
|B∗y | −
d
m≤ |Bx| ≤ |Bx∗ | + d
m.
Insbesondere erhalten wir
D(T, x) =1
n|T ∩Bx|−|Bx| ≤
1
n|T ∩By∗ |−|By∗ |+ d
m= D(T, y∗)+
d
m≤ D∗
m(T )+d
m
Kapitel 3. Konzentrationsungleichungen 41
und
−D(T, x) = |Bx|−1
n|T∩Bx| ≤ |Bx∗ |− 1
n|T∩Bx∗ |+ d
m= −D(T, x∗)+
d
m≤ D∗
m(T )+d
m.
Zusammen liefert das |D(T, x)| ≤ D∗m(T ) + d
m und, da dies für beliebiges x ∈ [0, 1]d
gilt, die Behauptung des Lemmas.
Theorem 17. Zu natürlichen Zahlen n, d mit 2 ≤ d ≤ n gibt es eine Punktmenge
T ⊂ [0, 1]d mit |T | = m und
D∗(T ) ≤ 10
√
d
nlog(dn).
Beweis. Seien t(1), t(2), . . . , t(n) gleichmäßig verteilt in [0, 1]d und unabhängig, d.h.
t(i) = (t(i)1 , . . . , t
(i)d ) mit t
(i)j ist gleichverteilt in [0, 1] und alle t
(i)j , i = 1, . . . , n; j =
1, . . . , d sind unabhängig. Wir betrachten zu jedem x ∈ [0, 1]d die Zufallsvariable
Y(x)i = 1IBx
(t(i)) − |Bx|.
Wegen
E1IBx(t(i)) =
∫ 1
0. . .
∫ 1
01IBx
(t(i)1 , . . . , t
(i)d )dt
(i)1 . . . t
(i)d =
∫ xd
0. . .
∫ x1
0dt
(i)1 . . . t
(i)d = |Bx|
haben wir
EY(x)i = 0 für i = 1, . . . , d; x ∈ [0, 1]d.
Setzen wir T = t(1), t(2), . . . , t(n), so haben wir
1
n
n∑
i=1
Y(x)i =
1
n
n∑
i=1
(1IBx(t(i)) − |Bx|) =
1
n|Bx ∩ T | − |Bx| = D(T, x).
Da auch Y(x)i ∈ [−1, 1] gilt, folgern wir aus der Hoeffding-Ungleichung
P(|D(T, x)| ≥ ε) = P
(
∣
∣
∑n
i=1Y
(x)i
∣
∣ ≥ nε)
≤ 2 exp(
− 2n2ε2
4n
)
= 2e−nε2/2.
Folglich ist
P(D∗m(T ) ≥ ε) ≤ 2|Γm|e−nε2/2 = 2(m + 1)de−nε2/2.
Unter der Voraussetzung
2(m + 1)de−nε2/2 < 1 (3.6)
42 3.3 Geometrische Diskrepanz
gibt es also sicher eine Menge T mit D∗m(T ) < ε und folglich wegen des oben bewie-
senen Lemmas
D∗(T ) < ε +d
m.
Das Theorem ist also bewiesen, wenn wir ε und m so finden können, daß
(i) ε + dm < 10
√
dn log(dn)
(ii) log 2 + d log(m + 1) < nε2/2
gilt. Wir wählen zunächst ε = dm . Dann gehen (i) und (ii) über in
(i′) m > 15
√
dnlog(dn)
(ii′) 2m2(log 2 + d log(m + 1)) < nd2.
Zur Vereinfachung wollen wir in den nächsten Abschätzungen davon absehen, daß
wir m eigentlich ganzzahlig wählen müssen. Dann können wir (i′) und (ii′) erfüllen,
sofer nur2
25
dn
log(dn)
(
log 2 + d log(1
5
√
dn
log(dn)+ 1
))
< nd2
ist, was offenbar äquivalent zu
log 2 + d log(1
5
√
dn
log(dn)+ 1
)
<25
2d log(dn)
ist. Offenbar ist aber unter den Voraussetzungen an d, n
log 2 <1
2d log(dn)
und
log(1
5
√
dn
log(dn)+ 1
)
< 12 log(dn) ⇐⇒ 1
5
√
dn
log(dn)+ 1 < (dn)12,
womit alles bewiesen ist.