 Solution

ID: past-exam-of-the-options-ii-course-of-the-university-of-oxford/2011/m/m5/a/v/solution

Let

e_{k}

be the expected number of children receiving a sticker when

k

remain. A first-step decomposition gives

e_{0} = 0, e_{k} = 1 + \frac{1}{k} \sum_{j = 0}^{k - 1} e_{j} (k \geq 1) .

Subtracting the equations for

k e_{k}

and

(k - 1) e_{k - 1}

gives

e_{k} - e_{k - 1} = 1/ k

. Hence

e_{k} = H_{k}

, the

k

th harmonic number. In particular

e_{4} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{25}{12} .

Every visit before absorption counts exactly one child who receives at least one sticker.

The same first-step argument applies to the uniform depletion Markov chain at every initial stock size.

 New to topics? Read the docs here!