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

  • $\begingroup$ 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.) $\endgroup$ – Did Jul 1 '14 at 18:32
  • $\begingroup$ 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. $\endgroup$ – Mark Fischler Jul 3 '14 at 5:12
  • 1
    $\begingroup$ 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.) $\endgroup$ – Did Jul 3 '14 at 5:20

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.