How to cube a matrix, specifically a transition (probability) matrix

Question

I am working with a probability transition matrix for a Markov chain. I need to find (P³) _2,2 of the following transition matrix

$$ \begin{matrix} 0 & 1/3 & 2/3 \\ 1/4 & 3/4 & 0 \\ 2/5 & 0 & 3/5 \\ \end{matrix} $$

I do know how to do a basic matrix multiplication, and so I can solve (P²) _2,2 . (P²) _2,2 = 31/48 if I did it right (if you wouldn't mind checking that's right, that would be awesome! But that fraction does appear in the final answer so I'm pretty sure I'm correct).

I was able to solve this using $\sum_{k=1}^3 p_{2,k}*p_{k,2}$.

For what it's worth, it took a while, but I got the right answer, so I'm not sure if there's a quicker way to do even this first step (happy to elaborate on what I did if need be).

Anyway, from there I'm not sure how to multiply again by (P) _2,2 , thus making the final answer P³.

I know Pⁿ=P^rP^n-r so n=3 is P³=P^rP^3-r but I'm not quite sure what to do from there.

The final answer should be 35/64 unless I'm way off track.

Thanks a lot!

Answer 1

You could certainly bash this out by computing $P^3$ in its entirety and then pulling out the required element, but since you’re only interested in one element of the product you can save yourself some unnecessary work.

If you expand the matrix products by component and extract the $(2,2)$ element, you’ll end up with the double summation $$[P^3]_{2,2}=\sum_{1\le i,j\le3}p_{2,i}p_{i,j}p_{j,2},$$ but $\sum_{1\le i\le3}p_{2,i}p_{i,j}$ is the $j$th element of the product of the second row of $P$ with $P$, so this sum becomes $$[P^3]_{2,2} = \sum_{1\le j\le3}[P_2P]_j p_{j,2}$$ (where $P_2$ represents the second row of $P$). This last sum is just the product of $P_2P$ with the second column of $P$. So, $$[P^3]_{2,2} = \begin{bmatrix}\frac14&\frac34&0\end{bmatrix} P \begin{bmatrix}\frac13\\\frac34\\0\end{bmatrix}.$$ For this particular problem, you can take advantage of the zeros to reduce the product to $$[P^3]_{2,2} = \begin{bmatrix}\frac14&\frac34\end{bmatrix} \begin{bmatrix}0&\frac13\\\frac14&\frac34\end{bmatrix} \begin{bmatrix}\frac13\\\frac34\end{bmatrix}.$$

This idea generalizes to other powers: $[P^n]_{i,j}=P_iP^{n-2}p_j$. However, for larger $n$ I don’t think this is of much use since you’ll most likely be computing powers of $P$ by some method other than painstakingly multiplying $n-2$ copies of $P$ together.