Libro de discrepancia de Chazelle: método codicioso

Question

En el libro de Bernard Chazelle El método de discrepancia, cual es Disponible gratis como PDF del sitio web del autor, la primera declaración que requiere el pensamiento del lector (en la página 3, justo antes del Teorema 1) se obtiene mediante un argumento de probabilidad simple. Desafortunadamente, no puedo seguir el argumento previsto. ¿Alguien podría iluminarme?

Aquí $ chi (s_i) = sum_ {v en s_i} chi (v) $ es el discrepancia del conjunto $ s_i $ con respecto a una función $ chi $ que asigna pesos a cada elemento.

Dado un sistema establecido $ (v, s) $, con $ | v | = n $ y $ | s | = m $, elige un color aleatorio $ chi $, lo que significa que por cada $ v_j $, el "color" $ chi (v_j) $ se elige aleatoriamente, de manera uniforme e independiente, en $ {-1,1 ps Decimos que $ s_i $ es malo Si $ | chi (s_i) | > sqrt {2 | s_i | ln (2m)} $. Por Chernoff's Bound, inmediatamente derivamos $$ PR [S_I Text {es malo}] < frac {1} {m}; $$

Y ahora el bit que no sigo:

Por lo tanto, con una probabilidad distinta de cero, no $ S_i $ es malo.

Claramente, esto es necesario si los eventos de $ M $ "$ S_i $ no es malo" son mutuamente independientes. También se mantiene por una forma del Lema local de Lovász Si estos eventos forman los bordes de un hipergrafo (con $ V $ como vértices), eso es "lo suficientemente agradable". Pero no veo por qué esto es evidente de inmediato en todos los casos, como parece implicar el autor. Si los valores de $ n $ individuales $ chi (v_j) $ son IID, entonces simplemente no veo que los eventos $ m $ "$ s_i $ no es malo" son necesariamente de una forma lo suficientemente agradable como para usar el método probabilístico , y ciertamente no parecen ser IID.

¿Qué me estoy perdiendo?

Cualquier contraejemplo debe ser bastante grande (con el tamaño de $ m $ exponencial en $ | s_i | $), por lo que creo provisionalmente la declaración. Pero me gustaría una prueba convincente o un puntero a otra referencia.

Answer 1

Mi supervisión fue que $ | S | = M $, por lo que hay $ M $ eventos del formulario "$ S_i $ es malo". Entonces, dado que $ pr [ cup_ {i = 1}^m a_i] le sum_ {i = 1}^m pr [a_i] $ para cualquier colección de eventos $ {a_i mid i = 1,2, puntos, m } $, se deduce que $ pr [ text {some} s_i text {es malo}] <1 $, entonces $ pr [ text {no} s_i text {es malo}]> 0 $ .