= Solution
\b[There is no proof of the printed assertion: it is false for the stated <expectations>.] The original explicitly defines $x_j$ as the expected remaining count, so replacing it by a deterministic upper envelope changes the problem.<Probability and Computing examination paper by the University of Oxford (2015)>[Printed p. 2, definition preceding Question 2(b), and Question 2(b)]{ref}
Let $B_j$ be the actual count after $j$ rounds and $x_j=\mathbb E B_j$. The <union bound> gives the valid conditional estimate
$$
\mathbb E[B_{j+1}\mid B_j=b]
\leq\frac{b(b-1)}n.
$$
By the <law of total expectation>, the resulting unconditional bound is
$$
\boxed{x_{j+1}\leq\frac{\mathbb E[B_j(B_j-1)]}{n}
=\frac{x_j^2-x_j+\operatorname{Var}(B_j)}n.}
$$
Discarding the <variance> term is an <expectation closure error for a nonlinear recurrence>. In particular, <Jensen's inequality> says $\mathbb E B_j^2\geq x_j^2$, which cannot justify the requested upper bound.
For an exact <counterexample>, start with two balls and two bins. A round serves both balls if they land separately and serves neither if they collide. Each outcome has <probability> $1/2$, independently in successive rounds while both balls remain. Consequently
$$
\mathbb P(B_j=2)=2^{-j},\qquad
\boxed{x_j=2^{1-j}.}
$$
At $j=2$, the requested inequality would say $x_3\leq x_2^2/2$, but
$$
\boxed{x_3=\frac14>\frac{(1/2)^2}{2}=\frac18.}
$$
Back to article page
