Proving Irreducible Markov Chains not Martingales

[Edwinkumar]

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

 

[quadraphonics]

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?

 

[Edwinkumar]

Thank you very much for your reply.

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.

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

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?

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

 

[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?

 

[quadraphonics]

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?

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.

 

[quadraphonics]

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.

 

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

 

[quadraphonics]

1) How can you assume that S_n=0?

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

2) How can you condition S_n instead of \mathcal{F}_n?

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.

3) Moreover, can you define some stopping time \tau so that the stopped process is a Martingale?

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

 

[Edwinkumar]

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

With respect to the finite state irreducible markov chain.

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?

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.

 

[quadraphonics]

With respect to the finite state irreducible markov chain.

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

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?

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.

 

[Edwinkumar]

Maybe \sum_{i=0}^{n}S_i/n would work?[/itex].

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.

 

[quadraphonics]

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

 

[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?

 

[quadraphonics]

Do you mean either \tau=0 or \tau=m?

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

Moreover, can you give an example of a Martingale which is not a Markov chain?

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

 

[Edwinkumar]

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

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

 

[quadraphonics]

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

Indeed.

 

[Edwinkumar]

Thank you very much quadraphonics.
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)

 

[quadraphonics]

Thank you very much quadraphonics.
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)

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.