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

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$.