4
$\begingroup$

In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem 1) is obtained by a simple probability argument. Unfortunately, I fail to follow the intended argument. Could someone enlighten me?

Here $\chi(S_i) = \sum_{v\in S_i} \chi(v)$ is the discrepancy of the set $S_i$ with respect to a function $\chi$ that assigns weights to each element.

Given a set system $(V,S)$, with $|V| = n$ and $|S| = m$, pick a random coloring $\chi$, meaning that for each $v_j$, the "color" $\chi(v_j)$ is chosen randomly, uniformly, and independently, in $\{-1,1\}$. We say that $S_i$ is bad if $|\chi(S_i)| > \sqrt{2|S_i|\ln (2m)}$. By Chernoff's bound, we immediately derive $$Pr[S_i \text{ is bad}] < \frac{1}{m};$$

and now the bit I don't follow:

therefore, with nonzero probability, no $S_i$ is bad.

Clearly this holds if the $m$ events "$S_i$ is not bad" are mutually independent. It also holds by a form of the Lovász Local Lemma if these events form the edges of a hypergraph (with $V$ as vertices) that is "nice enough". But I don't see why this is immediately apparent in every case, as the author seems to imply. If the $n$ individual values $\chi(v_j)$ are iid, then I simply don't see that the $m$ events "$S_i$ is not bad" are necessarily of a nice enough form to use the probabilistic method, and they certainly don't seem to be iid.

What am I missing?

Any counterexample must be rather large (with the size of $m$ exponential in $|S_i|$), so I provisionally do believe the statement. But I would like a convincing proof, or a pointer to another reference.

$\endgroup$
3
$\begingroup$

My oversight was that $|S| = m$, so there are $m$ events of the form "$S_i$ is bad". Then since $Pr[\cup_{i=1}^m A_i] \le \sum_{i=1}^m Pr[A_i]$ for any collection of events $\{A_i \mid i=1,2,\dots,m\}$, it follows that $Pr[\text{some }S_i\text{ is bad}] < 1$, so $Pr[\text{no }S_i\text{ is bad}] > 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.