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

enter image description here

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

enter image description here

$$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?

Thanks in advance!

  • 1
    $\begingroup$ Quite simply, P(n) = P^n. Use any matrix-friendly language for that calculation, like R, Matlab, Python, etc. $\endgroup$ – stans Jan 24 at 4:26
  • $\begingroup$ Thanks @stans, but it has to be the result in terms of n (step n). $\endgroup$ – Jackson Maike Jan 24 at 10:27
  • 1
    $\begingroup$ Yes, and my formula depends on n. $\endgroup$ – stans Jan 24 at 11:14
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Jan 24 at 17:10

Your Answer

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

Browse other questions tagged or ask your own question.