Periodic Source Entropy Rate

Problem

A source picks one of several equal-length deterministic periodic patterns with the given probabilities and repeats it forever. Return the entropy rate in bits per symbol:

R = entropy_bits(probs) / len(patterns[0])

The entropy of the pattern choice is spread over the period length.

Hint

One deterministic pattern carries no information, so its rate is zero.

Test cases

case 1

in: [["ab","cd"],[0.5,0.5]]

expected: 0.5

case 2

in: [["abc"],[1]]

expected: 0

case 3

in: [["01","10","00"],[0.3333333333333333,0.3333333333333333,0.3333333333333333]]

expected: 0.792481250360578

case 4

in: [["abcd","bcda","cdab","dabc"],[0.25,0.25,0.25,0.25]]

expected: 0.5

Starter codePython

import math
def periodic_source_rate(patterns, probs):
    # Your code here
    pass

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