Discrepancy I |

Joel Spencer

Consider a set system, a.k.a. hypergraph, $(V,\mathcal{F})$ where $V=[n]$ is the ground set and $\mathcal{F}=\{A_1,\ldots,A_m\}$ where $A_i \subseteq V$ . We wish to color the ground set $V$ with two colors, say red and blue, in
such way that all sets in the family are colored in a “balanced” way, i.e., each set has nearly the same number of red and blue points.
As it can be seen from the family $\mathcal{F}=2^{[n]}$ this is not possible, since by the pidgeonhold principle at least one color will appear at least $n/2$ times and all the possible subsets of those points will be monochromatic. We formalize the above ideas immediately. It shall be convenient to use in the place of red/blue colorings, the coloring $\chi:V\rightarrow\{-1,+1\}$ . For any $A \subseteq V$ define $\chi(A) =\sum_{i \in A} \chi(i)$ . Define the discrepancy of $\mathcal{F}$ with respect to $\chi$ by $\text{disc}_{\chi}(\mathcal{F}) = \max_{A_i \in \mathcal{F}} |\chi(A_i)|$ . The discrepancy of $\mathcal{F}$ is $\text{disc}(\mathcal{F})=\min_{\chi}\text{disc}_{\chi}(\mathcal{F})$ . It is worth outlining that the discrepancy can be defined in a linear algebraic way. Specifically, let $A$ be the $m \times n$ incidence matrix of $\mathcal{F}$ . Then, $\text{disc}(\mathcal{F}) = \min_{x \in \{-1,+1\}} ||Ax||_{+\infty}$ . We start with the following theorem, which is an easy one as long as you know Chernoff bounds.

Theorem: Let $|V|=n,|\mathcal{F}|=m$ . Then, $\text{disc}(\mathcal{F}) \leq \sqrt{2n \log{(2m)}}$ .

Proof: Select a coloring $\chi$ uniformly at random from the set of all possible random colorings. Let us call $A_i$ bad if its discrepancy exceeds $t=\sqrt{2n\log{2m}}$ . Applying the Chernoff bound for set $A_i$ we obtain:

$\text{Prob}(A_i \text{~is bad})=\text{Prob}(|\chi(A_i)| > t)<$

$2\exp{\Big( -\frac{t^2}{2|A_i|} \Big)} \leq 2\exp{\Big( -\frac{t^2}{2n} \Big)}=\frac{1}{m}$ .

Using a simple union bound we see that $\text{Prob}(\text{disc}(\mathcal{F})>t )= \text{Prob}(\exists \text{~bad~}A_i )< m \times \frac{1}{m}=1$ . This suggests that with positive probability there exists a coloring that achieves discrepancy less than $t$ . QED

The above theorem is non-constructive but with little effort can be turned into a randomized algorithm. Specifically, if we set $t=\sqrt{3n\log{2m}}$ and do the same analysis as above we see that the failure probability is $\frac{1}{\sqrt{m}}$ . If we generate $k$ times a random coloring then with probability at least $1-\frac{1}{m^{k/2}}$ we succeed in finding at least one coloring which achieves discrepancy at most $t$ . The next natural question is whether this randomized algorithm can be turned into a deterministic algorithm. The answer is yes, and specifically through the method of conditional expectation. Here is a sketch of how to do it.

We assign colors $\chi(1),\chi(2),...$ successively in a greedy manner. The criterion of greediness here will be the conditional expectation of $B=\sum_{i=1}^m B_i$ , where $B_i$ is an indicator variable taking value 1 if set $A_i$ is “bad”.
Specifically we know $E[B] < \frac{1}{\sqrt{m}}$ . Let $\epsilon_1=\pm 1$ be such that $E[B|\chi(1)=\epsilon_1] \leq E[B|\chi(1)=-\epsilon_1]$ . Notice that this suggests $latex E[B]=E[E[B|\chi(1)]] \geq E[B|\chi(1)=\epsilon_1]$. In general pick $\epsilon_k=\pm 1$ in such way that minimizes the function of $x$ $E[B|\chi(1)=\epsilon_1,\ldots,\chi(k-1)=\epsilon_{k-1},\chi(k)=x]$ . At the end $1>\frac{1}{\sqrt{m}}>E[B]\geq E[B|\chi(1)=\epsilon_1,\ldots,\chi(n)=\epsilon_n]$ . Notice that since the right-hand side is a non-negative integer less than 1, it is unavoidably equal to 0. It is easy to check that this procedure can be done in polynomial time. Check it yourselves. QED

In the next post we will discuss Spencer’s beautiful result known as “6 standard deviations suffice”. Neat staff.

Appendix

Chernoff bound: Let $X_i, 1 \leq i \leq n$ be mutually independent random variables with $\text{Prob}(X_i=+1)=\text{Prob}(X_i=-1)=\frac{1}{2}$ and set following the usual convention $latex S_n=X_1+..+X_n$ . Let $\alpha>0$ . Then, $\text{Prob}(S_n > \alpha)< e^{-\tfrac{\alpha^2}{2n}}$ .