Suppose $S_n$ is a simple random walk started from $S_0=0$. Denote $M_n$ to be the maximum of the walk in the first $n$ steps, i.e. $M_n=\max_{k\leq n}S_k$. Show that $M_n$ is not a Markov chain, but that $Y_n=M_n-S_n$ is a Markov chain.
I wouldn't call this an "attempt" at solving, but more of a plan. I know $S_n=X_1+X_2+…+X_n$ with $X_i$ iid with probability $\pm1$. I could take a few specific cases, such as $M_7$:
$Pr(M_7=5|M_0=0, M_1=0, M_2=1, M_3=2, M_4=3, M_5=4, M_6=4)\overset{?}{=}Pr(M_7=4|M_6=4).$
I don't see how to show that these are not equal, and as such I don't see how to prove $Y_n$ is a Markov chain, although I suspect the argument will be similar to the one that shows $M_n$ is not Markov. Some direction would be appreciated.
Best Answer
To show that the process $M$ is not a Markov chain, one can consider two different paths of the process $M$ between the times $0$ and $4$:
To summarize, what this specific example shows is that the conditional probability of the step $M_3=1\to M_4=2$ depends not only on the fact that $M_3=1$ but on $(M_k)_{0\leqslant k\leqslant2}$ as well.
To show that the process $Y=M-S$ is a Markov chain, one can note the following:
To summarize, the conclusion follows from the identity $$ Y_{n+1}=\max\{Y_n-X_{n+1},0\} $$