Entropy Rate of a Markov Chain

Problem

Compute the entropy rate in bits of a Markov chain given its row-stochastic transition matrix and stationary distribution:

R = sum_i pi_i * H(row_i)

where H(row_i) is the Shannon entropy of row i in bits. Rows with pi_i = 0 contribute nothing.

Hint

Weight each row's entropy by how often the chain visits that state.

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 0.5533064273553082

case 4

in: [[[0.8,0.1,0.1],[0.1,0.8,0.1],[0.1,0.1,0.8]],[0.3333333333333333,0.3333333333333333,0.3333333333333333]]

expected: 0.9219280948873623

Starter codePython

import math
def entropy_rate(transitions, stationary):
    # Your code here
    pass

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