Markov Chain N-Step Distribution

Problem

Distribution of a Markov chain after n steps.

Given an initial probability vector state and transition matrix matrix[i][j] = P(i -> j), multiply the vector by the matrix n times. n = 0 returns the initial vector converted to floats.

Hint

Repeat the one-step update n times, reusing the previous result.

Test cases

case 1

in: [[1,0],[[0.5,0.5],[0.2,0.8]],2]

expected: [0.35,0.65]

case 2

in: [[0,1],[[0.5,0.5],[0.2,0.8]],1]

expected: [0.2,0.8]

case 3

in: [[1,0],[[0.5,0.5],[0.2,0.8]],0]

expected: [1,0]

case 4

in: [[0.3,0.7],[[1,0],[1,0]],5]

expected: [1,0]

case 5

in: [[1,0,0],[[0.5,0.25,0.25],[0.1,0.6,0.3],[0,0,1]],2]

expected: [0.275,0.275,0.45]

Starter codePython

def markov_n_step(state, matrix, n):
    # Your code here
    pass

5 test cases · run your code against them in the editor