KL of Markov Stationary to Uniform

Problem

Find the stationary distribution of a Markov chain with row-stochastic transition matrix transitions using 1000 steps of lazy power iteration (mixing in 0.5 of the identity each step), then return the KL divergence in bits from the stationary distribution to the uniform distribution.

Hint

Doubly stochastic chains are already uniform, so their KL term is zero.

Test cases

case 1

in: [[[0.5,0.5],[0.5,0.5]]]

expected: 0

case 2

in: [[[0.9,0.1],[0.2,0.8]]]

expected: 0.08170416594550198

case 3

in: [[[0,1],[1,0]]]

expected: 0

case 4

in: [[[0.8,0.1,0.1],[0.1,0.8,0.1],[0.2,0.2,0.6]]]

expected: 0.06303440583380093

Starter codePython

import math
def kl_stationary_uniform(transitions):
    # Your code here
    pass

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