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

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?

• You may verify that from one of the equivalent definitions. Please show us your work and where you're stuck, and avoid asking no-clue questions. – GNUSupporter 8964民主女神 地下教會 Nov 13 '18 at 13:45

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.