The Discrepancy of Random Points

In other words, I'll show that if you through N points randomly in the s-dimensional unit cube, then there is an aligned rectangle R containing \Omega(\sqrt{sN}) points more than it should (the latter is N \vol(R)).

The proof is elementary and needs nothing else than the, generally good to know, result that if you n times flip a coin showing "heads" with probability p, then with constant probability you see less than pn - \sqrt{pn}/2 "heads".