Paper 2, Section II, F

Probability | Part IA, 2016

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

(a) What is the distribution of BiB_{i} ? For i≠ji \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 a⩾2a \geqslant 2. What is P(E=0)\mathbb{P}(E=0) ? What is the limit of E[E]/m\mathbb{E}[E] / m when n→∞n \rightarrow \infty ?

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

Typos? Please submit corrections to this page on GitHub.