Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 2 / b / Solution

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.^[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 estimateBy the law of total expectation, the resulting unconditional bound isDiscarding the variance term is an expectation closure error for a nonlinear recurrence. In particular, Jensen's inequality says $\mathbb{E}{B}_j^2\ge 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. ConsequentlyAt $j=2$, the requested inequality would say $x_3\le x_2^2/2$, but