24
$\begingroup$

So I was studying Markov chains and I came across this matrix \begin{align*}P=\left( \begin{array}{ccccc} 0 & \frac{1}{4} & \frac{3}{4} & 0 & 0\\ \frac{1}{4} & 0 & 0 & \frac{1}{4} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{4}& \frac{1}{4}\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ \end{array} \right).\end{align*}

I noticed (by brute force) that \begin{align*}P^2=\left( \begin{array}{ccccc} \frac{7}{16} & 0 & 0 & \frac{1}{4} & \frac{5}{16}\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ \frac{3}{8} & 0 & 0 & \frac{1}{4}& \frac{1}{2}\\ \frac{7}{16} & 0 & 0 & \frac{1}{4} & \frac{5}{16}\\ \end{array} \right),\end{align*} and \begin{align*}P^3=\left( \begin{array}{ccccc} 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ \frac{7}{16} & 0 & 0 & \frac{1}{4} & \frac{5}{16}\\ \frac{7}{16} & 0 & 0 & \frac{1}{4} & \frac{5}{16}\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ \end{array} \right).\end{align*}

In fact; using a computer I found that every even power takes the form of the $P^2$ matrix and every odd power takes the form of the $P^3$ matrix.

I just wanted to know why that oscillation occurs? Is there a special name for the kind of matrix that $P$ is for it to exhibit that kind of behaviour?

$\endgroup$
  • 2
    $\begingroup$ It's really nothing special. It's simply a matrix such that $$P^{2n} = P^2$$ $$P^{2n+1} = P^3$$ $\endgroup$ – Von Neumann Mar 19 '18 at 21:54
  • 8
    $\begingroup$ @VonNeumann second equality comes from your first equality by multiplying by P $\endgroup$ – Isham Mar 19 '18 at 21:58
  • $\begingroup$ @VonNeumann: For that matter, both equalities can be simplified to $P^3 = P$, multiply by $P$, and then alternately multiply by $P^2$ and apply the transitive property. $\endgroup$ – Kevin Mar 20 '18 at 2:27
  • 2
    $\begingroup$ @Kevin But $P^3\neq P$? $\endgroup$ – Teepeemm Mar 20 '18 at 16:15
  • 1
    $\begingroup$ So the above comments say, what is special about $P$ is that its square is idempotent. $\endgroup$ – Jeppe Stig Nielsen Mar 20 '18 at 23:14
26
$\begingroup$

This is a periodic Markov chain (with period $2$). Otherwise, there's not much that's terribly unusual about it.


User "Iwillnotexist Idonotexist" raised an important point in the comments:

Well, something that can be noted for periodic Markov chains is that by definition they cannot be ergodic, another very important property of MCs that you may encounter soon. Roughly speaking, an ergodic MC that runs long enough "forgets" everything about its initial state. If the MC is periodic, then clearly you must remember some information about the contents of the initial state, because you're stuck in a loop of states that you keep on coming back to and aren't forgetting.

$\endgroup$
  • $\begingroup$ I actually had no idea about periodicity in Markov chains; thanks for making me learn something new! $\endgroup$ – thesmallprint Mar 19 '18 at 22:13
  • $\begingroup$ @thesmallprint: You're very welcome! $\endgroup$ – Brian Tung Mar 19 '18 at 22:14
  • 11
    $\begingroup$ @thesmallprint Well, something that can be noted for periodic Markov chains is that by definition they cannot be ergodic, another very important property of MCs that you may encounter soon. Roughly speaking, an ergodic MC that runs long enough "forgets" everything about its initial state. If the MC is periodic, then clearly you must remember some information about the contents of the initial state, because you're stuck in a loop of states that you keep on coming back to and aren't forgetting. $\endgroup$ – Iwillnotexist Idonotexist Mar 20 '18 at 1:16
  • 2
    $\begingroup$ @IwillnotexistIdonotexist: Yes, that's a very good point. (I forget that it isn't obvious to everyone.) $\endgroup$ – Brian Tung Mar 20 '18 at 17:20
  • $\begingroup$ You should incorporate the "note about ergodicity from comments" into the answer itself, because comments aren't supposed to live forever $\endgroup$ – Pedro A Mar 21 '18 at 0:12
22
$\begingroup$

Notice that your matrix $$\begin{align*}P=\left( \begin{array}{ccccc} 0 & \frac{1}{4} & \frac{3}{4} & 0 & 0\\ \frac{1}{4} & 0 & 0 & \frac{1}{4} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{4}& \frac{1}{4}\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ 0 & \frac{1}{4} & \frac{3}{4} & 0& 0\\ \end{array} \right).\end{align*}$$

has a special block decomposition as

$$ P=\begin {pmatrix} 0&A &0\\B&0&C\\0&D&0\end{pmatrix}$$

Where A,B,C,D are non zero submatrices.

To find $P^2$ we use the new form to get

$$ P^2 = \begin {pmatrix} 0&A &0\\B&0&C\\0&D&0\end{pmatrix}\begin {pmatrix} 0&A &0\\B&0&C\\0&D&0\end{pmatrix}=\begin {pmatrix} AB&0 &AC\\0&BA+CD&0\\DB&0&DC\end{pmatrix} $$

As you know we can find powers of P by multiplying the new form of P as many times as we wish.

The alternating repeating form of powers of P is due to the block decomposition form of P.

$\endgroup$
  • 3
    $\begingroup$ The situation would be even easier to understand if the first state were listed after the second and third states of the Markov chain. Then the transition matrix would have the block form $\begin{pmatrix}0&X\\Y&0\end{pmatrix}$, which makes the periodicity easily visible. $\endgroup$ – Andreas Blass Mar 20 '18 at 16:39
  • $\begingroup$ @AndreasBlass Good point Andreas, thanks. $\endgroup$ – Mohammad Riazi-Kermani Mar 20 '18 at 16:50
8
$\begingroup$

It is a matrix such that $P^4= P^2$ and some additional relations. We see that

$$ 0 = P^4 - P^2 = P^2(P^2 - I) = P^2(P-I)(P+I)$$

so the minimal polynomial $\mu_P(x)$ divides $x^2(x-1)(x+1)$.

However, the minimal polynomial is not any of $$x, x^2, x-1, x+1, \underbrace{x(x-1)}_{P^2 \ne P}, \underbrace{x(x+1)}_{P^2 \ne -P}, \underbrace{x^2(x-1)}_{P^3 \ne P^2}, \underbrace{x^2(x-1)}_{P^3 \ne -P^2}, \underbrace{(x-1)(x+1)}_{P^2 \ne I}, \underbrace{x(x-1)(x+1)}_{P^3 \ne P}$$ so it has to be precisely $x^2(x-1)(x+1)$.

The possibilities for the Jordan normal form of $P$ are:

$$\pmatrix{0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0}, \pmatrix{0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1}, \pmatrix{0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1}$$

meaning $5 \times 5$ matrices have the above properties if and only if they are similar to one of the three matrices above.

$\endgroup$
4
$\begingroup$

The entries are all between 0 and 1 and in each row the entries add up to 1. They are called stochastic matrices. They have 1 as an eigen value with $(1,1,\ldots,1)^T$ as corresponding eigenvector. This property is inherited by all the powers of that matrix.

$\endgroup$
  • $\begingroup$ I don't think that's the property he's after. I would guess that he's after why the pattern of $0$'s in the matrix powers repeats. $\endgroup$ – Arthur Mar 20 '18 at 14:52
  • $\begingroup$ @Arthur: You have a point as he has already mentioned Markov chain. But none of the answers mentioned eigenvalues or eigenvectors, and so I thought a pointer in that direction would be helpful. $\endgroup$ – P Vanchinathan Mar 21 '18 at 3:18
0
$\begingroup$

You can draw a graph for which your matrix is the matrix of probabilities of state change (some weights on the edges). Paint states A, D and E as white, and B and C as black. Then any possible move changes the color.

Since P^n is the probablility matrix of moving from X to Y in exacly n steps (or sum of products of weights spotted by any n-step path) then the oscillation occurs because your graph is bipartite. You can produce oscillation with other period if you wish this way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.