# Are random walk variations Markov-Chains?

Let $S_{n}:= S_0 + \sum_{i=1}^{n}X_i$ be a simple random walk, $X_i$ are independent random variables with $P[X_i=1] = p, P[X_i = -1] = 1-p$.
Let $M_n:=\max\{S_0, \dots, S_n\}$.

The task at hand is to prove or disprove that the following items are Markov-chains.

(a) $(M_n)_{n\in \mathbb{N}_0}$
(b) $(|S_n|)_{n\in \mathbb{N}_0}$
(c) $(S_n, M_n)_{n\in \mathbb{N}_0}$

I was able to show that (a) is no Markov-chain with a counter example but I don't know how to show the other two.

(c) is a Markov chain, since the transition at step $n+1$ only depends on the value of the sum up to $n$ (the endpoint of the random walk) and the maximum thus far.
(b) is not a markov chain unless $p=\frac{1}{2}$ and a counter-example is to take $n=1$; then $|S_n| = 1$ but $P(|S_2|=2) = p$ if the first step was to $-1$ but is $1-p$ if the first step was to $+1$.
• Actually, if $S_0=0$ then the process $|S|$ is a Markov chain. Yes, at first, this is a surprising fact, but one can compute the conditional distributions and indeed they are Markov. For every $i\geqslant1$, the transition probability $i\to i+1$ is $(p^{i+1}+q^{i+1})/(p^i+q^i)$. (This is what makes (b) a bad question unless the course is an advanced one.) – Did Jul 1 '14 at 18:32
• I believe you are right about that ... my counterexample is flawed because the distribution of $S_2$, while depending on the "hidden" variable of the direction of the first step, does not depend on the history of $S_i$, which in both cases is identical. – Mark Fischler Jul 3 '14 at 5:12
• Yes--I might add as a complement that, if $S_0$ is deterministic and non zero, then $|S|$ is not Markov anymore... For example the transition probabilities from 2 after the path 1232 and after the path 1012 are not the same. (Which confirms that, unless one is ready to enter these subtleties, asking (b) is a terrible idea.) – Did Jul 3 '14 at 5:20