# Markov chains

1. Nov 18, 2008

### Edwinkumar

Can someone prove that an irreducible markov chain on a finite state space {0,1,...,m} is not a Martingale?

2. Nov 18, 2008

Well, if $S_n$ is some irreduceable Markov chain with finite state space. For it to also be a Martingale would require $E(S_{n+1}|S_n) = S_n$. Consider the case where $S_n = 0$. Then the Martingale condition would be $E(S_{n+1}|S_n=0) = 0$, which would require that $P(S_{n+1}=0|S_n=0)=1$, which violates the assumption of irreducibility. So, an irreducible Markov Chain with finite state space cannot be a Martingale.

Notice that this is not the case for Markov Chains with infinite state spaces. Since there is no "edge" to the state space, it's easy to construct non-trivial conditional distributions with the required expected values, which then gives an irreducible chain. Can you think of an example?

Last edited by a moderator: Nov 18, 2008
3. Nov 19, 2008

### Edwinkumar

Why do you assume that $S_n = 0$. Moreover why is $P(S_{n+1}=0|S_n=0)=1$?

I don't understand what do you mean by 'no "edge" to the state space'.

4. Nov 19, 2008

### Boxcar Billy

I'm confused too. I understand the Martingale condition, but why must that imply $P(S_{n+1} = 0| S_{n} = 0) = 1$?

If $P(S_{n+1} = -1 | S_{n} = 0) = 0.5$ and $P(S_{n+1} = 1 | S_{n} = 0) = 0.5$ then the Martingale condition still holds because the expected value is still 0. Is this right or am I missing something?

5. Nov 19, 2008

The issue is that $S_{n+1}=-1$ is not in the state space, which, remember, consists of $\{0, ... , m\}$. If the state-space is infinite, then your approach would always work, as there would always be valid parts of the state space both above and below the current state. But for a finite state space, it's impossible to construct non-trivial conditional distributions for $S_n=0$ and $S_n=m$ that satisfy the Martingale condition.

6. Nov 19, 2008

BTW, the Markov Chain with countable state space and transition probability $P(S_{n+1}=s+1|S_n = s) = P(S_{n+1}=s-1|S_n = s)=1/2$ is the (discrete, symmetric) Random Walk, which is a classic example of a martingale.

7. Nov 19, 2008

### Edwinkumar

Mr.quadraphonics, I have just started learning Martingales in the classical way(i.e. measure theoretic).
The definition for a sequence of integrable random variables $S_n$ to be a Martingale with respect to a filtration $\mathcal{F}_n$, if (1) $S_n$ is $\mathcal{F}_n$ measurable and (2) $E[S_{n+1}|\mathcal{F}_n]=S_n$.

My questions to you are the following:
1) How can you assume that $S_n=0$?
2) How can you condition $S_n$ instead of $\mathcal{F}_n$?
3) Moreover, can you define some stopping time $\tau$ so that the stopped process is a Martingale?

Thank you very much for all your replies.

8. Nov 20, 2008

The irreducibility condition on a Markov Chain is that you can start to any state and, given some finite number of steps, it's possible to get to any state. So, to prove that a Markov Chian is NOT irreducible (which is what we're doing here), you only have to exhibit a single state from which it is not possible to get to some other state. I chose $S_n = 0$, since I happen to know that this is such a state ($S_n=m$ will also work, for the same reasons).

That's basically a shorthand. The underlying, general definition of the martingale works in terms of filtrations, but we sometimes abbreviate this by instead referring to a random variable defined on the same $\sigma$-algebra. If you're taking a measure-theoretic probability class, they'll probably cover this issue explicitly.

A stopping time with respect to what stochastic process? A finite-state Markov Chain? Or a martingale?

9. Nov 20, 2008

### Edwinkumar

With respect to the finite state irreducible markov chain.

I don't understand why is it not working in case of a an irreducible Markov chain with infinite state space. Can you please explain to me?
Thanks.

10. Nov 21, 2008

Maybe $\sum_{i=0}^{n}S_i/n$ would work?

Well, if the state space if (doubly) infinite: $S_n \in \mathbb{Z}$, then the Random Walk construction mentioned in the previous posts is both an irreducible Markov Chain and a martingle. The Random Walk, recall, is when the transition matrix for the Markov Chain is given by $P(S_{n+1}=s+1|S_n=s)=P(S_{n+1}=s-1|S_n=s)=0.5$.

11. Nov 21, 2008

### Edwinkumar

No! I want a stopping time(an integer valued random variable) $\tau$ for my finite state irreducible markov chain $S_n$ such that the stopped process $S_{\tau \wedge n}$ is a Martingale.

12. Nov 21, 2008

What about a random walk that then stops when it hits either 0 or m?

13. Nov 22, 2008

### Edwinkumar

Do you mean either $\tau=0$ or $\tau=m$?
Moreover, can you give an example of a Martingale which is not a Markov chain?

14. Nov 24, 2008

No, $\tau$ will be whatever time step $S_n$ first equals either 0 or m.

Do you mean specifically a discrete-time, finite-state martingale that is not a first-order Markov chain?

15. Nov 24, 2008

### Edwinkumar

Do you mean $\tau(\omega)=min\{n: S_n(\omega)=0 or S_n(\omega)=m\}$?

16. Nov 25, 2008

Indeed.

17. Nov 25, 2008

### Edwinkumar

One final question.
Can you prove that the stopped process $Y_n=X_{\tau \wedge n}$, where $\tau(\omega)=min\{n: S_n(\omega)=0 or S_n(\omega)=m\}$ is a martingale w.r.to the natural filtration $\mathcal{F}_n=\sigma(X_0, X_1,..., X_n)$

18. Nov 25, 2008

Yes, it's a straightforward application of the material I've already presented in this thread. Just show that the proposed stopped Markov Chain satisfies the martingale properties.