Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / M / M5 / a

Given $X_n=k$, the next child takes a fresh uniform choice from $1,\dots ,k$, making $X_{n+1}$ uniform on $0,\dots ,k-1$. At zero the count stays zero. This conditional law depends only on the current count, so $X_n$ is a Markov chain.

The amounts taken do not generally retain that state information. For $N\ge 3$, compare two positive-probability histories with the same current value $Y_2=1$: if $Y_1=N-2$, exactly one sticker remains and $Y_3=1$; if $Y_1=N-1$, none remains and $Y_3=0$. Thus the next amount depends on earlier history even after conditioning on the current amount, violating the Markov property.

The non-Markov assertion needs this nondegenerate range of $N$. With $N=1$ the amount process is trivial; for $N=2$ it is also Markov if time-inhomogeneous transitions are permitted. The history counterexample establishes the intended failure for every $N\ge 3$.

The state space is $\{0,1,\dots ,N\}$. In this increasing ordering, the transition matrix is specified byFor each positive $k$, the $k$ possible amounts taken correspond bijectively to the $k$ possible remaining counts. Each positive-state row therefore sums to one.

A state is a recurrent state if the probability of a return at some positive time, starting there, is one. It is a transient state if that return probability is less than one. It is an absorbing state if its one-step probability of remaining there is one. An absorbing state is recurrent, since every subsequent time is a return.

State zero is absorbing and recurrent. Every positive state is transient: after leaving it, the sticker count strictly decreases until reaching zero and can never return to that positive value. In fact absorption occurs after at most $N$ children who take a positive amount. Hence

Let $e_k$ be the expected number of future children receiving stickers from a box containing $k$, with $e_0=0$. Conditioning on the first uniform remainder givesSubtract the corresponding identity for $k-1$ after multiplying each by its denominator. This gives $k{e}_k=k{e}_{k-1}+1$, so $e_k=e_{k-1}+1/k$. Therefore $e_N={\sum }_{j=1}^{N}1/j$, andThe recurrence counts the current positive recipient once and excludes all later children arriving after the box is empty.

The remainder after the first child, $X_2$, is uniform on $0,\dots ,N-1$. Given $X_2=j\ge 1$, the second child takes an average of $(j+1)/2$ stickers; when $j=0$ the amount is zero. Hence, for $N\ge 1$,The expression gives zero for $N=1$, as expected.