The "maximum" of a simple random walk

Question

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.

Answer 1

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\} $$