Finding Markov Chain of $Y_n = M_n - S_n$?

Question

Letting $X_n$ be i.i.d taking the value $1$ with probability $p$, and $-1$ with probably $1-p$,how do I show that $Y_n = M_n - S_n$, where $$M_n = \max\{0, S_1, S_2,\ldots,S_n\}$$ and $$S_n = X_1+\ldots+X_n$$ is a Markov Chain? I can see that $M_n$ itself is not a Markov chain, but do not know how to show $Y_n = M_n - S_n$ is?

Answer 1

You need to look at the transition probability. Observe first that since $M_n\geq S_n$, you have $Y_n\geq 0$. If $Y_n = 0$ then there is a $1/2$ probability that $Y_{n+1}=0$ and a $1/2$ probability that $Y_{n+1}=1$. if $Y_n>0$ then there is a $1/2$ probability that $Y_{n+1}=Y_n \pm 1$, this is because $M_{n+1}=M_n$ in this case. These are the transition probability for the normal one sided random walk.