Balls and bins
Recall the balls and bins setting where we randomly put balls into bins. The sample space is and the distribution is uniform. Let be the number of balls in the first bin, so we can write as the sum of the indicators where indicates whether the -th ball goes into the first bin.
Exercise 111
Show that .
Therefore, we have that . 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 .