Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 2 / 10F (Probability)

For any fixed bin, each ball supplies an independent Bernoulli distribution indicator with success probability $1/m$. Summing the $n$ indicator variables givesThe full occupancy vector has a multinomial distribution, the basic uniform balls-in-bins allocation. Distinct bin counts are not independent when $n\ge 1$ and $m\ge 2$. To see this, write $B_i={\sum }_{r=1}^n{I}_{r,i}$. For the same ball, $I_{r,i}{I}_{r,j}=0$ if $i\ne j$, while indicators from distinct balls are independent. Their covariance is thereforeWith no balls the counts are deterministic; with one bin there are no distinct bin pairs. These degenerate cases do not contradict the conclusion.

Express the three counts as sums of indicator variables for $B_i=0$, $B_i=1$ and $B_i\ge 2$. The linearity of expectation applies even though the bin counts are dependent. The binomial distribution givesThusThe relation $E+S+C=m$ checks the sum of these expectations. For $m=1$, use the direct deterministic occupancies, or the usual binomial convention $0^0=1$ when $n=1$.

There are more bins than balls, so the pigeonhole principle forces at least one empty bin. In fact $E\ge m-n=(a-1)n$. ConsequentlyFor the expected fraction, substitute $m=an$ into part (b). The elementary exponential limit, obtained by taking logarithms, givesThis is the empty-bin case of the Poisson limit for occupancy fractions, with limiting mean occupancy $1/a$.

If $C=0$, every bin contains at most one ball, so the total number of balls is at most $m$. Since $n=dm>m$, the pigeonhole principle makes that event impossible:As $n\to \infty$ along these values, $m\to \infty$ and the mean occupancy $n/m$ is $d$. Apply part (b):Both powers tend to $e^{-d}$. HenceThe Poisson limit for occupancy fractions interprets the answer as the probability that a Poisson distribution variable with mean $d$ is at least two.