 Solution

ID: 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/b/iv/solution

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

E (I_{i} I_{j}) = q_{n}

. Thus

cov (I_{i}, I_{j}) = q_{n} - p_{n}^{2} = (1 - \frac{2}{n})^{n} - (1 - \frac{1}{n})^{2 n} < 0.

Indeed

0 \leq 1 - 2/ n < (1 - 1/ n)^{2}

for

n \geq 2

n

preserves this strict inequality. This proves the negative covariance directly.

 New to topics? Read the docs here!