Question

How to find the period of a Markov chain?
I have the following one-step transition probability matrix:\[P=
\begin{bmatrix}
1/2 & 1/2 & 0 & 0 & 0 \\[0.3em]
1/2 & 1/2 & 0 & 0 & 0 \\[0.3em]
0 & 0 & 1/2 & 1/2 & 0 \\[0.3em]
0 & 0 & 1/2 & 1/2 & 0 \\[0.3em]
1/4 & 1/4 & 0 & 0 & 1/2
\end{bmatrix}\]
FYI, the definition of the period, \(d_i\), is \(d_i={g.c.d.} \left\{n \in \mathbb{Z}^{+} \mid P_{i,i}^{(n)}>0\right\}\), where \(P_{i,i}^{(n)}=P(X_n=j\mid X_0=i)\).

Answer 1

Shouldn't that last one be either \(P_{i,j}^{(n)}\) or \(P_{j,i}^{(n)}\)?

Answer 2

no I checked in different sources and it's definitely \(P_{i,i}^{(n)}\)

Answer 3

But that's odd. If I interpreted it correctly, then \(P_{i,i}^{(n)}\) is the probability that the value of the random variable \(X_n=j\) given that initially \(X_0=i\). I just thought it would make more sense if that were denoted as \(P_{i,j}^{(n)}\), since \(a_{ij}\) (ith row, jth column of P) is the probability that X moves from state i to state j.
To start the solution, consider states 1, 2, and 5 separately from states 3 and 4.

Answer 4

Notice that if X is in state 1, 2, or 5, then it won't go to states 3 and 4. Also, if X is in satate 3 or 4, then it will never states 1, 2, and 5.
Noticing this, we let
\[A=\begin{bmatrix}1/2&1/2&0\\1/2&1/2&0\\1/4&1/4&1/2\end{bmatrix};
B=\begin{bmatrix}1/2&1/2\\1/2&1/2\end{bmatrix}\]
Let us start with B, for now. Our goal is to find \(P_{i,i}^{(n)}\) for B.
Remember that \(B^n\) is the transition matrix from state i to state j in n steps. Thus, finding \(P_{i,i}^{(n)}\) is equivalent to finding \(a_{ii}\) of \(B^n\).

Answer 5

We can use the Cayley-Hamilton Theorem to find a general formula for B^n.
The characteristic equation of B is \(p(\lambda)=\det{(\lambda I-B)}=\lambda^2-\lambda\). Thus, it is true that \(p(B)=0\Rightarrow B^2-B=0\Rightarrow B^2=B\). If we multiply both sides of this last equality by B, we get \(B^3=B^2=B\), etc. Thus, \(B^n=B\) and \(P_{i,i}^{(n)}=1/2\) for states 3 and 4.

Answer 6

Oh dear I am so sorry :( I didn't realize my mistake was in the condition probability notation aye... P(Xn = i | Xo = i) :(

Answer 7

Anyway, my solution was made with that consideration. So don't worry. :)

Answer 8

For the matrix A, the entries \(a_{ii}\) of \(A^n\) can be found by induction.
If you look at A^2:
\[A^2=\begin{bmatrix}1/2&1/2&0\\1/2&1/2&0\\3/8&3/8&1/4\end{bmatrix}\]
then you can see that \(P_{5,5}^{(2)}=1/4\).
Continuing,
\[A^3=\begin{bmatrix}1/2&1/2&0\\1/2&1/2&0\\7/16&7/16&1/8\end{bmatrix}\]
Thus, \(P_{5,5}^{(3)}=1/8\) and generally, \(P_{5,5}^{(n)}=1/2^n>0~\forall n\).
Also, \(P_{1,1}^{(n)}=P_{2,2}^{(n)}=1/2>0.\)
Now, all you have to do is to find the gcd of all n where the probability of X returning to its initial state is nonzero. Since each \(P_{i,i}^{(n)}>0\) for all i and n, the last question to answer is: What is the gcd of 1, 2, 3, ...?

Answer 9

Oh that was very helpful :D thank you!! That was actually an interesting way of using the Cayley-Hamilton theorem (though honestly I barely have any experience using it..)


and the gcd would be 1then

Answer 10

It just so happened that the characteristic polynomial of B was really simple. If it were complicated, I would have resorted to finding a pattern and using induction, like I did with A.

Answer 11

True, but it was a nice result :) I don't think I would have ever though of using it, ever.. :P

Answer 12

thought*