How to find the n-step matrix more efficiently?

Is there any clever way to find the n-step matrix of a chain? I have the following transition matrix

However, $$p^{(n)}_{1,2}$$ I spent a lot of time trying to find a way of recurrence along the paths of the graph, but I was not successful. Is there an easier way to get the n-step matrix?

To better clarify my question, consider the case of $$p_{1,2}^{(n)}$$. Opening the matrix path tree I get

$$p_{1,2}^{(1)} = \frac{1}{5}$$ $$p_{1,2}^{(2)} = 0$$ $$p_{1,2}^{(3)} = 0$$ $$p_{1,2}^{(4)} = \frac{1}{5}^2 + \frac{1}{5}\frac{4}{5} = \frac{1}{5}$$ $$p_{1,2}^{(5)} = 0$$ $$p_{1,2}^{(6)} = 0$$ $$p_{1,2}^{(7)} = \frac{1}{5}^3 + 2\frac{1}{5}^2\frac{4}{5} + \frac{1}{5}\frac{4}{5}^2 = \frac{1}{5}\left( \frac{1}{5}^2 + 2\frac{1}{5}\frac{4}{5} + \frac{4}{5}^2 \right) = \frac{1}{5}$$

Apparently the paschal binomial is opening, moreover, from the figure above, it seems that I have a kind of convolution. How do I get to a general formula? Is there a smarter way to do this?

• The standard method diagonalizes the transition matrix $\mathbb{P}=\mathbb{Q}^{-1}\Lambda\mathbb{Q}$ so that $$\mathbb{P}^n=\mathbb{Q}^{-1}\Lambda^n\mathbb{Q}.$$The powers of any diagonal matrix $\Lambda$ are found by taking the powers of its diagonal values, thereby reducing everything to one dimension. In your case a simplification is available because you really only have one state to which you return every three cycles. – whuber Jan 24 at 17:10