 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/probability-and-computing/2/c/solution

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

x_{5} = \frac{1}{16} > 2 2^{- 2^{5 - 2}} = \frac{1}{128} .

The supplied premise

x_{2} \leq n /2

does hold in this example:

x_{2} = 1/2 \leq 1

. Thus the problem is the invalid recurrence in part (b), rather than failure of the supplied starting estimate.^[ref]

The intended mathematical induction is valid 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 n 2^{- 1}

. If

y_{j} \leq n 2^{- 2^{j - 2}}

, then

y_{j + 1} \leq \frac{( n 2 ^{- 2^{j - 2}} ) ^{2}}{n} = n 2^{- 2^{j - 1}} .

This proves the proposed form for

y_{j}

but cannot identify

y_{j}

with

E B_{j}

 New to topics? Read the docs here!