Skip to main content

Balls and bins

Recall the balls and bins setting where we randomly put mm balls into nn bins. The sample space is Ωm,n={f:[m][n]}\Omega_{m,n} = \{f: [m] \rightarrow [n]\} and the distribution is uniform. Let XX be the number of balls in the first bin, so we can write XX as the sum of the indicators X=i[m]XiX = \sum_{i \in [m]} X_i where XiX_i indicates whether the ii-th ball goes into the first bin.

Exercise 111

Show that E[Xi]=1/n{\mathbb E}[X_i] = 1/n.

Therefore, we have that E[X]=m/n{\mathbb E}[X] = m/n. This result is quite intuitive since we should expect to see the same number of balls in every bin.

Exercise 112

Prove: The expected number of empty bins is at most n/en/e.