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.