Paper 2, Section II, F

Probability | Part IA, 2016

We randomly place nn balls in mm bins independently and uniformly. For each ii with 1im1 \leqslant i \leqslant m, let BiB_{i} be the number of balls in bin ii.

(a) What is the distribution of BiB_{i} ? For iji \neq j, are BiB_{i} and BjB_{j} independent?

(b) Let EE be the number of empty bins, CC the number of bins with two or more balls, and SS the number of bins with exactly one ball. What are the expectations of E,CE, C and SS ?

(c) Let m=anm=a n, for an integer a2a \geqslant 2. What is P(E=0)\mathbb{P}(E=0) ? What is the limit of E[E]/m\mathbb{E}[E] / m when nn \rightarrow \infty ?

(d) Instead, let n=dmn=d m, for an integer d2d \geqslant 2. What is P(C=0)\mathbb{P}(C=0) ? What is the limit of E[C]/m\mathbb{E}[C] / m when nn \rightarrow \infty ?

Typos? Please submit corrections to this page on GitHub.