Two-State Chain Convergence Distance

Problem

A two-state Markov chain moves from state 0 to state 1 with probability p and from state 1 to state 0 with probability q. Starting from state 0, iterate n steps and return the total variation distance between the resulting distribution and the stationary distribution [q / (p + q), p / (p + q)], computed as half the sum of absolute component differences. When p + q is 0 use the stationary distribution [1.0, 0.0] and treat n < 0 as zero steps.

Hint

Iterate the two-state update on the row vector, then compare with the stationary distribution.

Test cases

case 1

in: [0.5,0.5,0]

expected: 0.5

case 2

in: [0.5,0.5,1]

expected: 0

case 3

in: [0.6,0.2,1]

expected: 0.14999999999999997

case 4

in: [0.6,0.2,3]

expected: 0.00599999999999995

case 5

in: [0,0,1]

expected: 0

Starter codePython

def two_state_chain_convergence_distance(p, q, n):
    # Your code here
    pass

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