Chazelles Diskrepanzbuch: Gierige Methode

Question

In Bernard Chazelles Buch Die Diskrepanzmethode, welches ist KOSTENLOS als PDF auf der Website des Autors erhältlich, Die allererste Aussage, die den Gedanken des Lesers (auf Seite 3 kurz vor Satz 1) erfordert, wird durch ein einfaches Wahrscheinlichkeitsargument erhalten. Leider folge ich nicht dem beabsichtigten Argument. Könnte mich jemand aufklären?

Hier $ chi (s_i) = sum_ {v in s_i} chi (v) $ ist das Diskrepanz des Satzes $ s_i $ in Bezug auf eine Funktion $ chi $, die jedem Element Gewichte zuweist.

Bei einem festgelegten System $ (v, s) $ mit $ | v | = n $ und $ | S | = m $, wähle eine zufällige Färbung $ chi $ aus, was bedeutet, dass für jeden $ v_j $ die "Farbe" $ chi (v_j) $ zufällig, einheitlich und unabhängig in $ {-1,1 ausgewählt wird } $. Wir sagen, dass $ s_i $ ist Schlecht Wenn $ | chi (s_i) | > sqrt {2 | s_i | ln (2m)} $. Von Chernoffs gebundene sind wir sofort $$ PR [s_i text {ist schlecht}] < frac {1} {m}; $$

Und jetzt folge ich nicht:

Daher ist nein $ s_i $ mit ungleich Null -Wahrscheinlichkeit schlecht.

Dies gilt eindeutig, wenn die $ M $ Ereignisse "$ s_i $ nicht schlecht" sind. " Es gilt auch durch eine Form der Lovász Lokale Lemma Wenn diese Ereignisse die Kanten eines Hypergraphen (mit $ V $ als Scheitelpunkte) bilden, ist das "nett genug". Aber ich verstehe nicht, warum dies in jedem Fall sofort erkennbar ist, wie der Autor zu implizieren scheint. Wenn die $ n $ individuenwerte $ chi (v_j) $ iid sind, dann sehe ich einfach nicht, dass die $ m $ event und sie scheinen sicherlich nicht iid zu sein.

Was vermisse ich?

Jedes Gegenbeispiel muss ziemlich groß sein (mit der Größe von $ m $ exponential in $ | s_i | $), daher glaube ich vorläufig die Aussage. Aber ich hätte gerne einen überzeugenden Beweis oder einen Zeiger auf eine andere Referenz.

Answer 1

Mein Versehen war, dass $ | s | = M $, also gibt es $ M $ Ereignisse des Formulars "$ s_i $ ist schlecht". Dann, da $ pr [ cup_ {i = 1}^m a_i] le sum_ {i = 1}^m pr [a_i] $ für jede Sammlung von Ereignissen $ {a_i mid i = 1,2, Punkte, m } $, folgt, dass $ pr [ text {einige} s_i text {ist schlecht}] <1 $, also $ pr [ text {no} s_i text {ist schlecht}]> 0 $ .