Rate of a Markov Source

Problem

Compute the entropy rate in bits of a Markov source with row-stochastic transition matrix transitions. Find the stationary distribution with 1000 steps of lazy power iteration (mixing in 0.5 of the identity each step to handle periodic chains), then return

R = sum(pi_i * H(row_i))

where H is the entropy in bits of row i.

Hint

Lazy mixing keeps the stationary distribution unchanged while removing periodic oscillation.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0.5533064273553054

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.1,0.1,0.8]]]

expected: 0.9219280948873623

Starter codePython

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

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