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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.