Fano's Inequality Lower Bound

Problem

Return the weak Fano lower bound on the error probability for estimating X from Y:

P_e >= (H(X|Y) - 1) / log2(|X|)

Clamp the result at 0 and assume the alphabet size is at least 2.

Hint

Subtracting 1 bit accounts for the binary uncertainty of whether an error occurred.

case 1

in: [1,2]

expected: 0

case 2

in: [2,4]

expected: 0.5

case 3

in: [1.5,2]

expected: 0.5

case 4

in: [3,8]

expected: 0.6666666666666666

Starter codePython

import math
def fano_lower_bound(h_given, n_classes):
    # Your code here
    pass

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