Entropy Lower Bound Check

Problem

Check Shannon's source-coding bound for a set of symbol probabilities and proposed code lengths. Normalize the probabilities and return True when the expected length L is at least the entropy H, allowing a tolerance of 1e-9. Return True for an empty or all-zero distribution.

Hint

Expected length can never beat the entropy, so violations mean the lengths are impossible.

Test cases

case 1

in: [[0.5,0.5],[1,2]]

expected: true

case 2

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

expected: false

case 3

in: [[1],[0]]

expected: true

case 4

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

expected: false

case 5

in: [[0.75,0.25],[1,2]]

expected: true

Starter codePython

import math
def entropy_bound_holds(probs, lengths):
    # Your code here
    pass

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