> 
> Let $S\_n$ be a simple random walk. Specifically,
> $$ S\_n = X\_1 + X\_2 + \cdots + X\_n, $$
> where $X\_n$'s are i.i.d. and each takes $+1$ or $-1$ with probability $0.5$ and $0.5$ respectively. Also,
> $$ M\_n = \max(S\_1, S\_2, \ldots, S\_n).$$
> 
> 
> * Is $M\_n$ a Markov chain?
> * Is $M\_n - S\_n$ a Markov chain?
> 
> 
> 

I can see $M\_n - S\_n$ is a Markov chain. But when I show $M\_n$ is not a Markov chain, I am not sure here what is the information we present have, i.e., what we know if we only know the present state. Is it $M\_n$ or $S\_n$?