The infinite limits of the probability transition matrix for Markov chain

[Joe1998]

Consider a Markov chain with state space {1, 2, 3, 4} and transition matrix P given below:

Now, I have already figured out the solutions for parts a,b and c. However, I don't know how to go about solving part d? I mean the question says we can't use higher powers of matrices to justify our answer, then what else can we use to prove that the limit of that transition matrix exist?
Any help would be appreciate it, thanks.

 

[PeroK]

However, I don't know how to go about solving part d? I mean the question says we can't use higher powers of matrices to justify our answer, then what else can we use to prove that the limit of that transition matrix exist?

You could try a little pure mathematics.

 

[Joe1998]

You could try a little pure mathematics.

Can you please explain more and be more specific by giving me clear guidance how to do it?
Thanks

 

[PeroK]

For i) you could notice that:
$$
\begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}^2
=
\begin{bmatrix}
x & 0 & 0 & x \\
0 & x & x & 0 \\
0 & x & x & 0 \\
x & 0 & 0 & x
\end{bmatrix}
$$Where $x$ just stands for not $0$. That should give you a clue.

 

[Joe1998]

For i) you could notice that:
$$
\begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}^2
=
\begin{bmatrix}
x & 0 & 0 & x \\
0 & x & x & 0 \\
0 & x & x & 0 \\
x & 0 & 0 & x
\end{bmatrix}
$$Where $x$ just stands for not $0$. That should give you a clue.

Thanks for that. However, the question says we can't use higher powers of matrices to justify our answer, so how can I use your method in this case?

 

[PeroK]

Thanks for that. However, the question says we can't use higher powers of matrices to justify our answer, so how can I use your method in this case?

It wasn't a method, it was a clue. You were supposed to take the next step and realize that:
$$
P = \begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}$$$$
P^2 =
\begin{bmatrix}
x & 0 & 0 & x \\
0 & x & x & 0 \\
0 & x & x & 0 \\
x & 0 & 0 & x
\end{bmatrix}$$$$
P^3 =
\begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}
$$Where $x$ just stands for not $0$.

Then it depends what you know about limits. If $\lim_{n \to \infty} P^n$ exists then each element of the matrix must converge to some number. But, each element alternates between $0$ and some non-zero values. In any case, the only possible limit for $P^n$ is the zero matrix.

That's most of part i). You just need to show whether all the non-zero values converge to zero or not.

For parts ii) and iii), each martrix in the sequence is involves multiplying by $P^2$. So, you end up with the two subsequences with non-zero entries in the same positions. So, you have to work out whether they converge or not.

In other words, you should have identified that the sequence $P^n$ consists of two alternating subsequences of matrices with entries in complementary positions.

The question, IMO, was indicating that you needed to provide that sort of logic, not just put the matrices into an engine and crunch the numbers.

 

[Joe1998]

It wasn't a method, it was a clue. You were supposed to take the next step and realize that:
$$
P = \begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}$$$$
P^2 =
\begin{bmatrix}
x & 0 & 0 & x \\
0 & x & x & 0 \\
0 & x & x & 0 \\
x & 0 & 0 & x
\end{bmatrix}$$$$
P^3 =
\begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}
$$Where $x$ just stands for not $0$.

Then it depends what you know about limits. If $\lim_{n \to \infty} P^n$ exists then each element of the matrix must converge to some number. But, each element alternates between $0$ and some non-zero values. In any case, the only possible limit for $P^n$ is the zero matrix.

That's most of part i). You just need to show whether all the non-zero values converge to zero or not.

For parts ii) and iii), each martrix in the sequence is involves multiplying by $P^2$. So, you end up with the two subsequences with non-zero entries in the same positions. So, you have to work out whether they converge or not.

In other words, you should have identified that the sequence $P^n$ consists of two alternating subsequences of matrices with entries in complementary positions.

The question, IMO, was indicating that you needed to provide that sort of logic, not just put the matrices into an engine and crunch the numbers.

Oh I see, thanks for that. So using your logic then for parts ii and iii, we will always be alternating between the zero and non-zero numbers for the higher powers of matrices in the form of either P or P^2, right? So in this case, none of the limits actually exist, except for for P^n is the zero matrix, or P^(2n+1) is a zero matrix, or P^2n is the zero matrix, is that correct?
Thanks

 

[PeroK]

Oh I see, thanks for that. So using your logic then for parts ii and iii, we will always be alternating between the zero and non-zero numbers for the higher powers of matrices in the form of either P or P^2, right? So in this case, none of the limits actually exist, except for for P^n is the zero matrix, or P^(2n+1) is a zero matrix, or P^2n is the zero matrix, is that correct?

Completely wrong!

 

[Joe1998]

Completely wrong!

Why?

 

[PeroK]

Why?

Let's just focus on $P_{11}$, the top left entry. That element of $P^n$ is a sequence of numbers:
$$P^n_{11} = 0, x_1, 0, x_2, 0, x_3 \dots$$Part i) asks whether that sequence has a limit. The only possible limit is $0$. But, you might suspect that $\lim_{n \to \infty} x_n \ne 0$. You might suspect that the limit does not exist, but you still have to prove it.

For part ii) you have:
$$P^{2n}_{11} = x_1, x_2, x_3 \dots$$That's the same question as above.

For part iii) you have:
$$P^{2n+1}_{11} = 0, 0, 0 \dots$$That clearly converges to zero, but $P^{2n+1}_{12}$ etc. will be the problem to solve.

 

[PeroK]

PS I don't know what the answer is because I haven't done the work yet!

 

[Joe1998]

Hmmm, I get it now. But if I somehow figure out that the limit does converge, then how would I know to what given that it is just alternating between 0 and 1 randomly? Also, if one of the elements of the matrix diverge to infinity, then it simply means all of the limit does not exist anymore (even if all of the other elements of the matrix converge to a certain value), correct?

 

[PeroK]

Hmmm, I get it now. But if I somehow figure out that the limit does converge, then how would I know to what given that it is just alternating between 0 and 1 randomly? Also, if one of the elements of the matrix diverge to infinity, then it simply means all of the limit does not exist anymore (even if all of the other elements of the matrix converge to a certain value), correct?

You need to do some work to get an expression for these matrix entries. There's nothing random here. Nor is anything going to diverge to infinity.

 

[Joe1998]

You need to do some work to get an expression for these matrix entries. There's nothing random here. Nor is anything going to diverge to infinity.

so if there is nothing random and nothing diverges to infinity, does that mean the limits for parts i,ii and iii do exist?

 

[PeroK]

so if there is nothing random and nothing diverges to infinity, does that mean the limits for parts i,ii and iii do exist?

I don't know. You must put pen to paper.

 

[PeroK]

What I can guess is this. $P^{2n}$ and $P^{2n+1}$ probably both converge. And, it can't be the zero matrix. That means that $P^n$ does not converge.

The main task is to analyse $P^{2n}$ and try to figure out what, if anything, it converges to. Everything else follows from that.

 

[Joe1998]

I don't know. You must put pen to paper.

What I can guess is this. $P^{2n}$ and $P^{2n+1}$ probably both converge. And, it can't be the zero matrix. That means that $P^n$ does not converge.

The main task is to analyse $P^{2n}$ and try to figure out what, if anything, it converges to. Everything else follows from that.

I have been able to figure out that P^2n converges and to where it converges, but then how can we have a situation where P^2n and P^(2n+1) converge but P^n does not converge?

 

[PeroK]

I have been able to figure out that P^2n converges and to where it converges,

I'm impressed by that!

but then how can we have a situation where P^2n and P^(2n+1) converge but P^n does not converge?

You have a sequence comprising alternating convergent subsequences. The subsequences both converge to their respective limits; but the main sequence cannot itself be convergent. Compare the sequence:
$$s_n = 1, 2, 1, 2 \dots$$That sequence does not converge, but it comprises two alternating convergent sequences.

In your example, you have oscillatory behaviour for large $n$. $P^n$ oscillates between $P^{2n}$ and $P^{2n+1}$.

 

[Joe1998]

I'm impressed by that!

You have a sequence comprising alternating convergent subsequences. The subsequences both converge to their respective limits; but the main sequence cannot itself be convergent. Compare the sequence:
$$s_n = 1, 2, 1, 2 \dots$$That sequence does not converge, but it comprises two alternating convergent sequences.

In your example, you have oscillatory behaviour for large $n$. $P^n$ oscillates between $P^{2n}$ and $P^{2n+1}$.

Oh I see! Thanks for this great explanation. So now I have pretty much knocked out both P^n and P^2n, but I am not able to FIGURE OUT P^(2n+1), any suggestions? Thanks.

 

[PeroK]

Oh I see! Thanks for this great explanation. So now I have pretty much knocked out both P^n and P^2n, but I am not able to FIGURE OUT P^(2n+1), any suggestions? Thanks.

That's the easy bit. $P^{2n+1} = PP^{2n}$.

 

[Joe1998]

That's the easy bit. $P^{2n+1} = PP^{2n}$.

Oh ahahahahaha, that's when I try doing this problem late at night, my brain is already dead...anyway thank you very much dude!

 

[pbuk]

You have a sequence comprising alternating convergent subsequences. The subsequences both converge to their respective limits; but the main sequence cannot itself be convergent.

Er, it can if both subsequences converge to the same limit (example: $S = 1, -1, \frac 1 2, -\frac 1 2, \frac 1 3, -\frac 1 3 \dots$). Is this the case here?

 

[PeroK]

Er, it can if both subsequences converge to the same limit (example: $S = 1, -1, \frac 1 2, -\frac 1 2, \frac 1 3, -\frac 1 3 \dots$). Is this the case here?

We've already established that the alternating matrices in the sequence have non-zero values in different entries. The matrices cannot be equal. Unless the limits are the zero matrix. This has all been covered above.

 

[pbuk]

Unless the limits are the zero matrix.

Indeed.

 

[PeroK]

Indeed.

Post #6:

It wasn't a method, it was a clue. You were supposed to take the next step and realize that:
$$
P = \begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}$$$$
P^2 =
\begin{bmatrix}
x & 0 & 0 & x \\
0 & x & x & 0 \\
0 & x & x & 0 \\
x & 0 & 0 & x
\end{bmatrix}$$$$
P^3 =
\begin{bmatrix}
0 & x & x & 0 \\
x & 0 & 0 & x \\
x & 0 & 0 & x \\
0 & x & x & 0
\end{bmatrix}
$$Where $x$ just stands for not $0$.

Then it depends what you know about limits. If $\lim_{n \to \infty} P^n$ exists then each element of the matrix must converge to some number. But, each element alternates between $0$ and some non-zero values. In any case, the only possible limit for $P^n$ is the zero matrix.

That's most of part i). You just need to show whether all the non-zero values converge to zero or not.

For parts ii) and iii), each martrix in the sequence is involves multiplying by $P^2$. So, you end up with the two subsequences with non-zero entries in the same positions. So, you have to work out whether they converge or not.

In other words, you should have identified that the sequence $P^n$ consists of two alternating subsequences of matrices with entries in complementary positions.

The question, IMO, was indicating that you needed to provide that sort of logic, not just put the matrices into an engine and crunch the numbers.