Hi

First you form a matrix P (dimensions k x k where k is the number of possible states) with entries the probability of going from state i to state j in one step. Then if you raise the matrix to the power of n, the entry of the final matrix in the ith row and jth column will be the probability of going from state i to state j inexactlyn steps. If you want to get the probability of going from state i to step j inat mostn steps, then you need to get the entry from the ith row and the jth column of the matrix: