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

Given $X_n=k>0$, the number remaining next time is uniform on $\{0,\dots ,k-1\}$ and is independent of earlier choices; given $X_n=0$, the next state is $0$. Thus the conditional law of $X_{n+1}$ depends only on $X_n$, which is the Markov property.

By contrast, observing only the last number removed generally loses information about the remaining stock. For $N\ge 3$, compare the two positive-probability historiesBoth have $Y_2=1$, but the first leaves $N-2>0$ stickers, so $P(Y_3>0\mid Y_1=1,Y_2=1)=1$, whereas the second leaves none, so $P(Y_3>0\mid Y_1=N-1,Y_2=1)=0$. Hence $(Y_n)$ fails the Markov property.

The qualification $N\ge 3$ is necessary if a Markov chain is allowed to have time-dependent transitions. For $N=1$, the removal sequence is the deterministic, time-homogeneous Markov chain $1,0,0,\dots$. For $N=2$, it is a time-inhomogeneous Markov chain, although it is not time-homogeneous on its observed removal states: a removal of $1$ at the first step forces another removal of $1$, whereas a removal of $1$ at the second step forces $0$ next. The blanket non-Markov claim should therefore be understood in the generic, nondegenerate setting.