Cheap and Secure Web Hosting Provider : See Now

[Answers] Chazelle's discrepancy book: greedy method

, , No Comments
Problem Detail: 

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.

Asked By : András Salamon

Answered By : András Salamon

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11752

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback