Große Abweichungen und das Pusher-Chooser-Game

Thomas Friedrich 23. Juni 1998

Seminar über Graphentheorie Universität zu Köln

1 Große Abweichungen

Lemma 1: Seien X_{1}, …, X_{n} paarweise unabhängige Zufallsvariablen mit

prob[X_{i} = 1] = prob[X_{i} = −1] = \frac{1}{2} (i = 1, …, n)

und S_{n} := X_{1} + … + X_{n}. Dann gilt für jedes λ > 0:

prob[S_{n} > λ] < exp (\frac{−λ^{2}}{2n} ) .

Beweis: Da E[X_{i}] = prob[X_{i} = 1] · 1 + prob[X_{i} = −1] · (−1) = \frac{1}{2} · 1 + \frac{1}{2} · (−1) und exp(αt) für alle α > 0 streng monoton steigt, ist

E[exp(αX_{i})] = \frac{1}{2} · exp(α · 1) + \frac{1}{2} · exp(α · (−1))

= \frac{1}{2} · (exp(α) + exp(−α))

= cosh(α).

Durch Potenzreihenentwicklung erhält man

cosh(α) = ∑_{n=0}^{∞} \frac{α^{2n}}{(2n)!} < ∑_{n=0}^{∞} \frac{α^{2n}}{2^{n} · n!} = ∑_{n=0}^{∞} \frac{(\frac{α^{2}}{2} )n}{n!} = exp (\frac{α^{2}}{2} )

und somit

E[exp(αX_{i})] = cosh(α) < exp (\frac{α^{2}}{2} ) .  (1)

Weiter ist

E[exp(αS_{n})] =_{Def. S_{n}} E [exp (α · ∑_{i=1}^{n} X_{i})] =_{Add. Th.} E [∏_{i=1}^{n} exp(αX_{i})]

=_{X_{i} unabh.} ∏_{i=1}^{n} E[exp(αX_{i})] <_{(1)} ∏_{i=1}^{n} exp (\frac{α^{2}}{2} )

= exp (\frac{α^{2}}{2} )^{n} = exp (\frac{n · α^{2}}{2} ) .

(2)

Es gilt also

prob[S_{n} > λ] = prob[exp(αS_{n}) > exp(αλ)] ≤_{Tschernoff} E[exp(αS_{n})] · exp(−αλ)

<_{(2)} exp (\frac{n · α^{2}}{2} ) · exp(−αλ) =_{Add. Th.} exp (\frac{n · α^{2}}{2} − αλ) .

Wählt man α := \frac{λ}{n} > 0, ergibt sich

prob[S_{n} > λ] < exp (\frac{−λ^{2}}{2n} ) .

q. e. d.

Bemerkung: Lemma 1 läßt sich wie folgt verallgemeinern: Seien Y_{1}, …, Y_{n} paarweise verschiedene Zufallsvariablen mit

prob[Y_{i} = 1] = p_{i}, prob[Y_{i} = −1] = 1 − p_{i} (i = 1, …, n),

X_{i} := Y_{i} − p_{i} (i = 1, …, n), p := \frac{p_{1}+...+p_{n}}{n} und X := X_{1} + … + X_{n}. Dann gelten

(i) prob[X > a] < exp (\frac{−2a^{2}}{n} )

(ii) prob[X < −a] < exp (\frac{−a^{2}}{2pn} )

(iii) prob[X > a] < exp (\frac{−a^{2}}{2pn} + \frac{a^{3}}{2·(pn)^{3}} ).

(Dies sei hier ohne Beweis angegeben.)

Definition: Sei A ⊆ 2^{Ω} eine beliebige Familie endlicher Mengen über der Grundmenge Ω. Dann heißt χ : Ω ⟶ {+1, −1} eine Zweifärbung von Ω. Sei χ(A) := ∑_{a∈A} χ(a) für A ∈ A. Definiere dann die Diskrepanz wie folgt:

disc(χ) := max_{A∈A} |χ(A)|
disc(A) := min_{χ} disc(χ).

Dabei ist disc(A) ≤ k gleichbedeutend damit, daß es eine Zweifärbung χ von Ω gibt mit |χ(A)| ≤ k für alle A ∈ A.

Satz 2: Wenn |A| = |Ω| = n gilt, dann ist

disc(A) ≤ \sqrt{2n ln(2n)}.

Beweis: Wenn χ zufällig gewählt wird und r := |A| ist, genügt χ(A) der Verteilung S_{r} (wie in Lemma 1 definiert). Da für alle A ⊆ Ω |A| ≤ |Ω| = n gilt, ist nach Lemma 1

prob[|χ(A)| > λ] < 2 · exp (\frac{−λ^{2}}{2n} ) .

Deswegen ist

prob[disc(χ) > λ] < ∑_{A∈A} prob[|χ(A)| > λ] < 2n · exp (\frac{−λ^{2}}{2n} ) =^{!} 1

mit Wahl von λ := \sqrt{2n ln(2n)}. Also ist prob[disc(χ) ≤ λ] > 0 und damit existiert ein χ mit disc(χ) ≤ λ. q. e. d.

Korollar: (zu Satz 2) Seien u_{j} ∈ IR^{n} mit ||u_{j}||_{∞} ≤ 1 (j = 1, …, n). Dann gibt es ε_{j} ∈ {−1, +1} derart, daß für u := ε_{1}u_{1} + … + ε_{n}u_{n} gilt: ||u||_{∞} ≤ \sqrt{2n ln(2n)}.

Beweis: Sei A ⊆ Ω; bezeichne die Elemente von Ω mit 1, …, n und die Mengen mit A_{1}, …, A_{n}. Die Matrix A enthalte zeilenweise die charakteristischen Vektoren der A_{i}. Betrachte die Spalten von A jetzt als die u_{j}. Eine Zweifärbung χ : Ω ⟶ {+1, −1} von Ω bestimmt jetzt die Belegung der ε_{j} = χ(j) und umgekehrt. Analog entspricht disc(A_{i}) der i-ten Koordinate und disc(χ) der ∞-Norm von u. Also läßt sich eine leichte Modifikation (wegen a_{ij} ∈ [−1, +1]) des Beweises von Satz 2 anwenden. q. e. d.

Bemerkung: Jetzt haben wir einen probabilistischen Beweis dafür, daß solche ε_{j} existieren. Wie aber können wir sie bestimmen ?

Algorithmus I: Probiere sämtliche 2^{n} Möglichkeiten, die ε_{j} zu setzen, durch.

Bemerkung: Natürlich hat dieser Algorithmus eine nicht akzeptable exponentielle Laufzeit. Es bietet sich auch eine randomisierte Methode an.

Algorithmus II: Setze die ε_{j} zufällig gleichverteilt auf -1 oder +1.

Bemerkung: Randomisierte Algorithmen produzieren i. a. nur im Erwartungswert gute Lösungen. Wir wollen aber eine garantierte, deterministische Lösung haben. Deshalb werden wir im folgenden Algorithmus II mit einer Standardtechnik derandomisieren. Diese ist auch auf andere Algorithmen anwendbar, die mit ”Münzwurf“ arbeiten.

Alle n-Tupel (ε_{1}, …, ε_{n}), ε_{i} ∈ {−1, +1} seien gleichwahrscheinlich. Ferner

seien A_{1}, …, A_{m} schlechte Eigenschaften mit ∑_{i=1}^{m} A_{i} < 1. (In unserem Fall ist

n = m, und A_{i} heißt: |u^{(i)}| ≥ λ, wobei u^{(i)} die i-te Komponente von u sei.

Gesucht sind jetzt ε_{1}, …, ε_{n}, so daß ⋀_{i=1}^{m} \overline{A_{i}} erfüllt ist.

Wir bestimmen die ε_{j} sukzessive. Seien ε_{1}, …, ε_{j−1} bereits gesetzt. Sei

W_{i} := prob[A_{i} | ε_{1}, …, ε_{j−1}].

Dies ist die Wahrscheinlichkeit, daß A_{i} auftritt, wenn ε_{1}, …, ε_{j−1} so gesetzt und die restlichen ε_{k} noch zufällig gewählt werden.

Durch Wahl von ε_{j} kann sich W_{i} nun auf zwei Arten ändern. Setze dazu

W_{i}^{+} := prob[A_{i} | ε_{1}, …, ε_{j−1}; ε_{j} := +1]
W_{i}^{−} := prob[A_{i} | ε_{1}, …, ε_{j−1}; ε_{j} := −1].

Es gilt W_{i} = \frac{1}{2} · (W_{i}^{+} + W_{i}^{−}). Seien jetzt

W^{alt} := ∑_{i=1}^{m} W_{i}, W^{alt+} := ∑_{i=1}^{m} W_{i}^{+}, W^{alt−} := ∑_{i=1}^{m} W_{i}^{−}.

Es gilt W^{alt} = \frac{1}{2} · (W^{alt+} + W^{alt−}).

Algorithmus III: Wenn W^{alt−} ≤ W^{alt+}, setze ε_{j} := −1, sonst ε_{j} := +1.

Lemma 3: Algorithmus III produziert eine Lösung mit ||u||_{∞} ≤ \sqrt{2n ln(2n)}.

Beweis: Nach obiger Bemerkung reicht zu zeigen, daß nach Wahl der ε_{1}, …, ε_{n} gemäß

Algorithmus III ⋀_{i=1}^{m} \overline{A_{i}} erfüllt ist.

Nach der Wahl von ε_{j} sei

W^{neu} := ∑_{i=1}^{m} prob[A_{i} | ε_{1}, …, ε_{j−1}, ε_{j}]

und daher

W^{neu} = min\{W^{alt+}, W^{alt−}\} ≤ \frac{1}{2} · (W^{alt+} + W^{alt−}) = W^{alt},

d. h. die W -Werte fallen monoton.

Wenn W^{initial} bzw. W^{final} den W -Wert vor der Wahl von ε_{1} bzw. nach der Wahl von ε_{n} bezeichnet, gilt also W^{final} ≤ W^{initial}. Da nach Voraussetzung

W^{initial} = ∑_{i=1}^{m} prob[A_{i}] < 1, ist W^{final} < 1. Da zu diesem Zeitpunkt aber alle ε_{j}

gesetzt sind, ist die Wahrscheinlichkeit, daß ein A_{i} aufgetreten ist, entweder

0 oder 1, also 0. Daher ist ⋀_{i=1}^{m} \overline{A_{i}} erfüllt. q. e. d.

Bemerkung: Algorithmus III läuft nicht unbedingt polynomiell, da die Berechnung der bedingten Wahrscheinlichkeiten für beliebige a_{ij} ∈ [−1, +1] zu komplex ist. Jedoch läuft er polynomiell bei unserem Ausgangsproblem mit a_{ij} ∈ {−1, +1}, weil sich hier die bedingten Wahrscheinlichkeiten einfach durch entsprechende Binomialkoeffizienten ausdrücken und daher schneller berechnen lassen.

2 Das Pusher-Chooser-Game

Betrachten wir nun ein Nullsummen-Spiel für zwei Spieler. Gespielt wird über n Runden. Es geht darum, einen Punkt P ∈ IR^{n}, der zu Beginn auf 0 gesetzt ist, durch den Raum zu bewegen.

Dazu wählt der erste Spieler, genannt Pusher, einen beliebigen Vektor v ∈ IR^{n} mit ||v|| ≤ 1 aus. Der zweite Spieler, genannt Chooser, darf nun bestimmen, ob P auf P + v oder P − v gesetzt wird. Sei P^{final} das P nach der n-ten Runde. Chooser bezahlt ||P^{final}|| Einheiten. Sei val(n) der Wert des Spieles für Pusher.

Lemma 4: Das Pusher-Chooser-Game mit || · || := || · ||_{2} (euklidische Norm) ist öde; der Wert des Spieles beträgt val(n) = \sqrt{n}.

Beweis: Pusher kann immer einen Vektor v orthogonal zu P bestimmen, so daß Chooser keine Wahl hat. Nach Pythagoras gilt: ||P^{neu}||_{2}^{2} = ||P^{alt}||_{2}^{2} + ||v||_{2}^{2} und daher val(n) = ||P^{final}||_{2} = \sqrt{n}. q. e. d.

Wir betrachten im folgenden das Pusher-Chooser-Game mit || · || := || · ||_{∞}.

Eine Strategie für Chooser

Satz 5:

val(n) ≤ \sqrt{2n ln(2n)}.

Beweis: Sei α > 0 fest, aber zunächst beliebig. Sei G(x) := cosh(αx). Dann ist für jedes a ∈ [−1, +1]

\frac{1}{2} · (G(x + a) + G(x − a)) = G(x) · G(a)  (3)

≤ G(x) · cosh(α) ≤_{(1)} G(x) · exp (\frac{α^{2}}{2} ) .

Für x ∈ IR^{n}, x = (x_{1}, …, x_{n}), sei G(x) := ∑_{i=1}^{n} G(x_{i}).

Für alle P ∈ IR^{n} und v ∈ IR^{n} mit ||v||_{∞} ≤ 1 ergibt (3) über die Koordinaten summiert

\frac{1}{2} · (G(P + v) + G(P − v)) ≤ G(P) · exp (\frac{α^{2}}{2} ) .

Wählt Chooser nun immer das Vorzeichen, bei dem der neue G(P)-Wert minimiert wird, und bezeichnet P^{alt} bzw. P^{neu} den Wert von P vor bzw. nach einem einzelnen Zug von Chooser, so ist

G(P^{neu}) = min{G(P^{alt} + v), G(P^{alt} − v)}

≤ \frac{1}{2} · (G(P^{alt} + v) + G(P^{alt} − v))

≤ G(P^{alt}) · exp (\frac{α^{2}}{2} ) .

Da am Anfang des Spieles G(P) = G(0) = n ist, gilt G(P^{final}) < n·exp (\frac{α^{2}}{2} ).

Da G(x) ≥ cosh(α||x||_{∞}) > \frac{1}{2} · exp(α||x||_{∞}) für alle x, ist daher

\frac{1}{2} · exp(α||P^{final}||_{∞}) ≤ n · exp (\frac{α^{2}}{2} ).

Wählt man nun α := \sqrt{\frac{2 ln(2n)}{n}}, ergibt sich

val(n) ≤ ||P^{final}||_{∞} < \sqrt{2n ln(2n)}.

q. e. d.

Bemerkung: Die Berechnung von G(P) kann schnell erledigt werden. Deshalb erhält man hiermit auch einen besseren Algorithmus zum Bestimmen der ε_{1}, …, ε_{n} aus Kapitel 1. Jede Zahl val(n) gibt dabei eine Schranke für || ∑_{j} ε_{j}u_{j}||_{∞} an, die

mit einem (nicht mehr notwendigerweise schnellen) Algorithmus erreichbar ist.

Eine Strategie für Pusher

Satz 6:

val(n) > \sqrt{n ln n} · (1 − o(1)).

Zum Beweis von Satz 6 benötigen wir noch einige Vorbereitungen.

Da Pusher auf Maximalität bedacht ist, wähle er o. B. d. A. nur Vektoren v mit ganzzahligen Komponenten. Dadurch gilt immer P ∈ ZZ^{n}.

Sortiere die Komponenten von P. Koordinaten mit gleichen Einträgen bilden eine Gruppe. Setze nun in jeder Gruppe die Hälfte der Komponenten von v auf 1, die andere Hälfte auf -1. Ist die Anzahl der Elemente der Gruppe ungerade, setze eine Komponente von v aus dieser Gruppe 0.

Beispiel:

Wenn P = 0 0 0 0 0 1 1 1 1 2 2 2 3 4 4
setze v := + + − − 0 + + − − + − 0 0 + −

Wenn Pusher nach dieser Strategie vorgeht, hat Chooser keine Wahlmöglichkeit mehr. Bis auf Permutation der Koordinaten ergibt sich

P ± v = -1 -1 1 1 0 2 2 0 0 3 1 2 3 5 3

Startet man mit P = 0 und berechnet mit diesem Vorgehen P^{final}, so ergibt ||P^{final}||_{∞} eine untere Schranke für val(n). Aber wie groß ist ||P^{final}||_{∞} ?

Wir interessieren uns jetzt nur noch für die Verteilung der Koordinatenwerte von P und führen dazu folgende Schreibweise ein: Zu P = (x_{1}, …, x_{n}) ∈ ZZ^{n} definiere P̂ : ZZ ⟶ IN, wobei P̂(x) die Anzahl der i angibt mit x_{i} = x. Dabei wird P̂(0) unterstrichen.

Im obigen Beispiel wäre vor dem Zug P̂ = \underline{5} 4 3 1 2, danach P̂ = 2 \underline{3} 3 3 3 0 1. Die Transformation von P̂ während eines Zuges sei T.

Wir können uns P̂ als ein eindimensionales Feld vorstellen, bei dem P̂(x) Chips auf Feld x liegen. Die Strategie von Pusher (und damit die Transformation T) kann dann wie folgt beschrieben werden: Lege von jedem Feld die Hälfte der Chips nach links, die andere Hälfte nach rechts; bei ungerader Anzahl Chips lasse einen Chip auf dem Feld liegen.

Definiere supp(P̂) := max{i | es liegen Chips auf i oder − i}, den Support von P̂. Ferner bezeichne \overline{n} genau die Situation, in der n Chips auf der 0 liegen. Dann gilt offenbar:

val(n) ≥ supp(T^{n}(\overline{n})).

Beispiel: Sei n = 20; dann sind die Werte von T^{i}(\overline{20})

i=0  \underline{20}
i=1  10 \underline{0} 10
i=2  5 0 \underline{10} 0 5
i=3  2 0 7 \underline{1} 7 0 2
⋮  ⋮
i=20 1 1 1 1 1 3 1 \underline{2} 1 3 1 1 1 1 1

und somit val(20) ≥ 7.

Sei a := supp(T^{n}(\overline{n})). Wir versuchen nun, a mittels einer Approximation von T durch einen linearen Operator S abzuschätzen. Wir betrachten dabei den Raum Ω := {−a, …, a}∪{∞}. (∞ dient als Schranke.) Definiere dazu S auf Ω wie folgt:

(Sx)(i) := \frac{1}{2} · (x(i − 1) + x(i + 1)) (|i| < a)
(Sx)(a) := \frac{1}{2} · x(a − 1)
(Sx)(−a) := \frac{1}{2} · x(−a + 1)
(Sx)(∞) := x(∞) + \frac{1}{2} · x(a) + \frac{1}{2} · x(−a).

S entspricht also im wesentlichen T, nur daß auch der ungerade Chip geteilt wird. S beschreibt einen zufälligen Spaziergang durch Ω.

Lemma 7:

(S^{n} − T^{n})(\overline{n})(∞) ≤ 2a + 1.

Beweis:

(S^{n} − T^{n})(\overline{n})(∞) = ∑_{i=0}^{n−1} S^{i}(S − T)T^{n−1−i}(\overline{n})(∞).

Hat T^{n−1−i}(\overline{n}) an Position j a_{ij} Chips (−a ≤ j ≤ a), so bewirken S und T auf gerader Anzahl Chips genau dasselbe; bei ungerader Anzahl wird ein Chip von S geteilt, während ihn T liegenläßt. u_{j} bezeichne einen einzelnen Chip an Position j. Dann gilt

(S − T)T^{n−1−i}(\overline{n}) = ∑_{j∈A_{i}} Su_{j} − u_{j},

wobei A_{i} die Menge der j sei mit ungeradem a_{ij}. Es folgt

(S^{n} − T^{n})(\overline{n})(∞) = ∑_{i=0}^{n−1} ∑_{j∈A_{i}}(S^{i+1} − S^{i})(u_{j})(∞)

≤ ∑_{i=0}^{n−1} ∑_{|j|≤a}(S^{i+1} − S^{i})(u_{j})(∞),

weil für alle i, j (S^{i+1}−S^{i})(u_{j})(∞) ≥ 0 gilt. (Deshalb wurde ∞ ∈ Ω definiert.) Damit ergibt sich

(S^{n} − T^{n})(\overline{n})(∞) ≤ ∑_{|j|≤a} ∑_{i=0}^{n−1}(S^{i+1} − S^{i})(u_{j})(∞)

= ∑_{|j|≤a}(S^{n} − I)(u_{j})(∞)

≤ ∑_{|j|≤a}(1 − 0) = 2a + 1.

q. e. d.

Beweis: (von Satz 6) Betrachte die asymptotische Entwicklung von a: Es war a so gewählt, daß T^{n}(\overline{n})(∞) = 0, und nach Lemma 7 ist S^{n}(\overline{n})(∞) ≤ 2a + 1, so daß (wegen Linearität)

S^{n}(\overline{1})(∞) ≤ \frac{2a + 1}{n}  (4)

gilt. Aber S^{n}(\overline{1})(∞) ist die Wahrscheinlichkeit, auf dem zufälligen Spaziergang durch Ω, angefangen bei 0, ±(a + 1) zum Zeitpunkt n zu erreichen. Ist jetzt a := K · \sqrt{n} mit langsam gegen ∞ laufendem K, so ist diese Wahrscheinlichkeit exp (\frac{−K^{2}}{2·(1+o(1))}).

Für jedes feste ε > 0 gilt (4) bei Wahl von a := \sqrt{n ln n} · (1 − ε) nicht. Somit ist

val(n) > \sqrt{n ln n} · (1 − o(1)).

q. e. d.