Probability of the first transition in k steps

Question

How to find the probability of the first transition in $k$ steps from state $i$ to state $j$. Let me remind you of a few formulas.

In zero steps

$$\hat p^{(0)}_{ij}= \begin{cases} 1 &i = j\\ 0 &i \neq j \end{cases}$$ In one step $$\hat p^{(1)}_{ij}=p_{ij}$$ In two steps $$\hat p^{(2)}_{ij} = \sum\limits_{m\neq j}p_{im}p_{mj}$$

Recursive formula in $k$ steps

$$\hat p^{(k)}_{ij}=\sum\limits_{m\neq j}p_{im}\hat p^{(k-1)}_{mj}$$

How to implement a program this recursive formula in python. I don't really understand what I should substitute there. In the examples that are in the textbook, the Markov chain consists of three elements and everything is trivially deduced by enumerating all the options. I was given a matrix of transition probabilities $n \times m$, and I don't really understand how I can implement this as a program. (In my case $n = m = 12$)

$$ P = ||p_{ij}|| = \begin{pmatrix} p_{11}& p_{12} & \ldots & p_{1m}\\ p_{21}& p_{22} & \ldots & p_{2m}\\ \ldots& \ldots & \ldots & \ldots\\ p_{n1}& p_{n2} & \ldots & p_{nm}\\ \end{pmatrix} \\ \text{where $p_{ij}$ the probability of transition from state $i$ to state $j$} $$

I see it like this, but this case doesn't seem to work

matrix = np.array(...)
sum = 0
def prob(k):
   for i, row in enumerate(matrix):
      for j, element in enumerate(i):
         return matrix[i][j] * prob(k - 1)
sum += prob(9)

The task sounds:

Find the probability of the first transition in 9 steps from state 5 to state 8

Answer 1

As I understand it, since we do not take into probability of the return to itself, we just need to nullify the transitions of the same name and in the loop raising the transition matrix to the power of the calculated step

i = # initial step
j = # final step
k = # necessary step
for s in range(0, k):
    transition_matrix[i][i] = 0
    m = np.linalg.matrix_power(transition_matrix, s+1)
result = m[i][j]