# Prove Markov Chain by definition

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!

• 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 – Lost1 Apr 11 '13 at 19:26
• But assume we don't know those criterion. Can you just prove it by definition? – Cancan Apr 11 '13 at 19:58
• 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. – Lost1 Apr 11 '13 at 20:03
• 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. – Lost1 Apr 11 '13 at 20:05
• do you know how to show $S'_n = | S_n |$ is Markov? – 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.

• 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}|)$? – Cancan Apr 11 '13 at 20:18
• 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$ – Lost1 Apr 11 '13 at 20:22
• @Cancan did you see my last comment? – Lost1 Apr 11 '13 at 20:50
• 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. :) – Cancan Apr 11 '13 at 20:57
• 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. – 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}).$$

• 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? – Cancan Apr 11 '13 at 20:21
• Yes essentially you will use induction on the statement being true for $n$ implies the statement for $n+1$. – Alex R. Apr 11 '13 at 20:26
• But do you know how to prove this one? I thought about it but couldn't figure it out. – Cancan Apr 11 '13 at 20:34
• 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. – Cancan Apr 11 '13 at 20:46
• are you showing $|S_n|$ is Markovian? – Pinocchio May 9 at 20:49