I came across this problem in homework:

$X_n$ are i.i.d random variables with $\mathbb{P}[X_n=1]=\mathbb{P}[X_n=-1]=\frac{1}{2}$ and we we also have $S_n=X_1+...+X_n.$ Show that $S_n'=|S_n|$ is a Markov Chain.

I can understand it's indeed a Markov chain. And I know in this question, we should show $S_n$ is a Markov chain first and then $S_n$. But can anyone prove it purely by the definition of Markov Chain? (First how should we show $S_n$ is a Markov Chain?)

Definition: Let $(\Omega, F,\mathbb{P})$ be a probability space and $S$ a countable set. A sequence $X_1,X_2,...$ of $S$-valued random variable is called a Markov chain if for all $n\geq 1$and all $s_1,s_2,s_3,..,s_n\in S$, we have: $\mathbb{P}[X_n=s_n|X_{n-1}=s_{n-1},...,X_1=s_1]=\mathbb{P}[X_n=s_n|X_{n-1}=s_{n-1}]$

It might be a stupid question, but I will really appreciate if you can help me explain this. Thanks!

  • $\begingroup$ you are happy $S_n$ is a Markov Chain? This is probably not what you want to hear, but $f(S_n)$ is a Markov when $S_n$ is Markov, if $f$ satisfies a so-called Dynkin's criterion. $|\cdot |$ is one of the functions which does, for the Markov Chain you wrote down $\endgroup$ – Lost1 Apr 11 '13 at 19:26
  • 1
    $\begingroup$ But assume we don't know those criterion. Can you just prove it by definition? $\endgroup$ – Cancan Apr 11 '13 at 19:58
  • $\begingroup$ yes, i have just done it. it is quite subtle. you see that this works, because no matter if S is 3 or -3, the transition probability of it jump to 4 and -4 is the same, so |S| is the same. So you make your jump up probability and jump down probability different, |S| is no longer markovian. $\endgroup$ – Lost1 Apr 11 '13 at 20:03
  • $\begingroup$ and Dynkin's criterion precisely captures this fact. It says something like for any $x$ in the image, the preimage must have the same transition probability. It is quite nice, you should check it out. I originally did the exercise to prove $|B_t|$ is markovian where $B$ is a brownian motion. $\endgroup$ – Lost1 Apr 11 '13 at 20:05
  • $\begingroup$ do you know how to show $S'_n = | S_n |$ is Markov? $\endgroup$ – Pinocchio May 9 at 20:56

For the second part, it is harder to write down. Consider

$P(|S_n| = x | |S_{n-1}|=,...)$

Now, this thing is always 0, unless $x=|S_{n-1}|-1$ or $x=|S_{n-1}|+1$

If we are to write out this conditional expectation

$P(|S_n| = x | |S_{n-1}|,|S_{n-2}|...)= \dfrac{1}{2} \mathbb{1}_{\{x=|S_{n-1}|+1, |S_{n-1}|\neq 0\}}+\dfrac{1}{2} \mathbb{1}_{\{x=|S_{n-1}|-1, |S_{n-1}|\neq 0\}}+ \mathbb{1}_{\{x=1, |S_{n-1}|= 0\}}$

Well that is independent only dependent on $|S_{n-1}|$, i.e. $\sigma(|S_{n-1}|)$-measurable so $P(|S_n| = x | |S_{n-1}|,|S_{n-2}|...) = P(|S_n| = x | |S_{n-1}|)$

The difference between this and showing $S_n$ is markov is that $S_n$ is a random walk, i.e. the transition probability does not even depend on your current state. here, we lose that property.

  • 1
    $\begingroup$ This idea is very good, but I don't follow properly how do you write that sign function and then suddenly conclude it's equal to $P(|S_n|=x |\quad |S_{n-1}|)$? $\endgroup$ – Cancan Apr 11 '13 at 20:18
  • $\begingroup$ Do you agree "now, the thing is awlays 0, unless ..."? If so, then by symmetry $S_{n-1}=|S_{n-1}|$ and $S_{n-1}=-|S_{n}|$ each with probability 1/2. From each of these, they each give 1/4 probability of jumping to $S_n-1$ and $-S_n+1$. That makes a 1/2. You should try to fill in these gaps yourself. If $|S_{n-1}|=0$, then with proability 1, $|S_n|=1$ $\endgroup$ – Lost1 Apr 11 '13 at 20:22
  • $\begingroup$ @Cancan did you see my last comment? $\endgroup$ – Lost1 Apr 11 '13 at 20:50
  • $\begingroup$ Yea, I am actually still thinking about your solution. but I am still not fully convinced by your solution, because what I really want is that how you gonna prove $|S_n|$ being Markov chain by using the fact that $\mathbb{P}[S_n=m_n|S_{n-1}=m_{n-1},...,S_1=m_1]=\mathbb{P}[S_n=m_n|S_{n-1}=m_{n-1}]$ is implied by $S_n$ (Assume m is the state space of S) . I know there are many ways of proving buy I really want to see the proof that strictly follows the definition. :) $\endgroup$ – Cancan Apr 11 '13 at 20:57
  • $\begingroup$ I am not sure what you mean by 'show $|S_n|$ is markovian by using the fact $S_n$ is Markovian'. As i have mentioned before, $S$ being Markovian is not not sufficient for $|S|$ to be markovian. you need something extra. $\endgroup$ – Lost1 Apr 11 '13 at 21:02

To show $S_n$ is a Markov chain, you need to show that $$P(S_n=x|S_1,\ldots,S_{n-1})=P(S_n=x|S_{n-1}).$$

In other words, to determine the transition probability to $S_n$, all you need is $S_{n-1}$ even if you are given the entire past. To do this, write $S_n=S_{n-1}+X_n$. Conditioning on $S_{n-1}$ fixes it, so the only random thing here is $X_n$, which is implicitely independent of $S_{n-1},S_{n-2},\ldots,S_1$. To put it in the form of math, $P(X_n|S_{n-1},\ldots,S_1)=P(X_n)=P(X_n|S_{n-1})$. So if you are studying $P(S_n=x|S_{n-1},\ldots,S_1)$, it's equivalent to write $$P(X_n=x-S_{n-1}|S_{n-1},\ldots,S_1)=P(X_n=x-S_{n-1}|S_{n-1})=P(S_n=x|S_{n-1}).$$

  • $\begingroup$ Actually, do you think if we can prove $\mathbb{P}(A|B\bigcap C)=\mathbb{P}(A|B)$ and then prove $S_n$ to be a Markov Chain? $\endgroup$ – Cancan Apr 11 '13 at 20:21
  • $\begingroup$ Yes essentially you will use induction on the statement being true for $n$ implies the statement for $n+1$. $\endgroup$ – Alex R. Apr 11 '13 at 20:26
  • $\begingroup$ But do you know how to prove this one? I thought about it but couldn't figure it out. $\endgroup$ – Cancan Apr 11 '13 at 20:34
  • $\begingroup$ sorry, my bad. I figure it out myself now. And think this can be the shortest proof for $S_n$ to be Markov Chain. $\mathbb{P}(A|B\bigcap C)= \frac{\mathbb{P}(C\bigcap (A \bigcap B))}{\mathbb{P}({B\bigcap C})}=\frac{\mathbb{P}(C| (A \bigcap B))\cdot \mathbb{P}(A \bigcap B)}{\mathbb{P}({A\bigcap C})}=\frac{\mathbb{P}(C|A\bigcap B)\cdot \mathbb{P}(A|B)\cdot \mathbb{P}(B)}{\mathbb{P}(C|B)\cdot \mathbb{P}(B)}$ .By our conditions, if $B$ happened then $C$ must have happened; if both $A$ and $B$ happened then $C$ must have happened as well. $\endgroup$ – Cancan Apr 11 '13 at 20:46
  • $\begingroup$ are you showing $|S_n|$ is Markovian? $\endgroup$ – Pinocchio May 9 at 20:49

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.