The next Lemma will be used frequently in the proof of Propositions 2.3 and 2.7. Consider an experiment where we randomly throw n balls into m ? n urns. The probability that each ball j enters urn i is and is independent of the position of other balls. Thus, p ? 1 is the success probability that the ball is thrown into any one of the urns. Let B _i, i = 1, m be the number of balls in urn i after n balls are thrown. It is obvious that . The following Lemma shows that, when n is large, with high probability all B _i will concentrate on its mean.

Lemma B.I

As n ? ?,

1. If , where c is a positive constant, then

   

2. If log n and c ? 8, then

   

3. If' , where c > 0 and ? > 0, then

   

4. If log n and c ? 4, then

   

5. If log n and c ? 16, then

   

Proof: By known results on the characteristic function of Bernoulli random variables, we have, for any ? > 0,

where in the last step we have used the inequality that

Using the Markov Inequality [5, p15], for any y > 0,

Hence, by the union bound

To prove part 1, let and log n, then

Let ? = 2/