= Solution
\b[The printed bound also fails for the actual <expectations>.] In the two-bin <counterexample> from part (b), at $j=5$ the true value and proposed bound are
$$
\boxed{x_5=\frac1{16}>2\,2^{-2^{5-2}}=\frac1{128}.}
$$
The supplied premise $x_2\leq n/2$ does hold in this example: $x_2=1/2\leq1$. Thus the problem is the invalid recurrence in part (b), rather than failure of the supplied starting estimate.<Probability and Computing examination paper by the University of Oxford (2015)>[Printed p. 2, Question 2(c), including the supplied bound on x_2]{ref}
The intended <mathematical induction> is valid \b[conditionally on the recurrence]. For a deterministic nonnegative sequence $y_j$ satisfying $y_2\leq n/2$ and $y_{j+1}\leq y_j^2/n$, the base case is $y_2\leq n2^{-1}$. If $y_j\leq n2^{-2^{j-2}}$, then
$$
y_{j+1}\leq\frac{(n2^{-2^{j-2}})^2}{n}
=n2^{-2^{j-1}}.
$$
This proves the proposed form for $y_j$ but cannot identify $y_j$ with $\mathbb E B_j$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/probability-computing-2015-survivor-counterexample.png]
{title=Exact two-bin survivor expectation and the invalid printed bound}
Back to article page
