# The “maximum” of a simple random walk

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.

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

• First assume that $$(M_n)_{0\leqslant n\leqslant4}=(0,1,1,1,2)$$. Then $$S_2=0$$ hence $$S_3$$ is conditionally uniformly distributed on $$\{-1,1\}$$ and the last step $$1\to2$$ has conditional probability $$\frac12\cdot P(X_4=1)=\frac14$$.
• Now assume that $$(M_n)_{0\leqslant n\leqslant4}=(0,0,0,1,2)$$. Then $$S_3=1$$ with full conditional probability hence the last step $$1\to2$$ has conditional probability $$P(X_4=1)=\frac12$$.

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:

• If $$Y_n=0$$, then $$S_n=M_n$$ hence:
• Either $$X_{n+1}=1$$ and then $$M_{n+1}=M_n+1$$ and $$S_{n+1}=S_n+1$$, thus $$Y_{n+1}=0$$.
• Or $$X_{n+1}=-1$$ and then $$M_{n+1}=M_n$$, $$S_{n+1}=S_n-1$$ and $$Y_{n+1}=1$$.
• If $$Y_n\geqslant1$$, then $$S_n\leqslant M_n-1$$ hence $$S_{n+1}\leqslant M_n$$ thus $$M_{n+1}=M_n$$ and $$Y_{n+1}=Y_n-X_{n+1}$$.

To summarize, the conclusion follows from the identity $$Y_{n+1}=\max\{Y_n-X_{n+1},0\}$$