Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Probability / 7

Assume finite second moments and set $Y_i=X_i-\mathbb{E}{X}_i$. By linearity of expectation, centring $X_1+X_2$ gives $Y_1+Y_2$. Expanding its square and using the definitions of variance and covariance,No independence assumption is required for this variance of a sum identity.

For finite second moments, the variance of a sum is

In the uniform balls-in-bins allocation, each ball enters box 1 independently with probability $1/n$. Thus $M_1$ has the binomial distribution $\mathrm{Bin}(n,1/n)$, with probability mass functionand zero outside that range.

For both boxes to be empty, each ball must avoid two specified boxes. The individual avoidance probability is $(n-2)/n$, and the choices of different balls are independent. ThereforeThis also covers $n=2$, when the answer is zero.

Write $p_n=(1-1/n{)}^n$, the probability that all balls avoid a specified box. Each of the empty-box indicators in uniform allocation is an indicator random variable with success probability $p_n$. Since $I_i^2=I_i$, its expectation and variance are

Let $q_n=(1-2/n{)}^n$. The product of two distinct empty-box indicators in uniform allocation is the indicator random variable of both boxes being empty, so $\mathbb{E}(I_i{I}_j)=q_n$. ThusIndeed $0\le 1-2/n<(1-1/n{)}^2$ for $n\ge 2$, and taking the positive integer power $n$ preserves this strict inequality. This proves the negative covariance directly.

By linearity of expectation, $\mathbb{E}{N}_n=n{p}_n$. The variance of a sum and the negative covariance just proved giveApply Chebyshev's inequality to the empty-box indicators in uniform allocation:This proves the required concentration of the empty-box fraction. Since $p_n\to e^{-1}$, it also yields convergence in probability of $N_n/n$ to $e^{-1}$.