@EricHolloway/

Entropy Lower Bound Violations

Python

Test if the accuracy lower bound calculated from entropy is violated by the numerical simulation.

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import math
from math import ceil

f = math.factorial
def nCk(n,k):
    return f(n) / f(k) / f(n-k)

def binom(n,k,p):
    return nCk(n,k)*(1-p)**k*p**(n-k)

def cum_binom(n,k,p):
    tail_prob = 0
    for c in range(0, k+1):
        tail_prob += binom(n, c, p)
    return tail_prob
        
def lg2(n):
    if n == 0:
        return 0
    return math.log(n, 2)

def H(p):
    if p == 0 or p == 1:
        return 0
    q = 1-p
    return -p*lg2(p)-q*lg2(q)

def err_penalty(errs, n):
    p = errs/float(n)
    return n*H(p)

if __name__ == "__main__":
    violations = 0
    for bs_len in range(1, 2**7+1):
        print("Testing bitstring length: " + str(bs_len))
        discount = ceil(lg2(bs_len))
        
        for zeros in range(0, int(bs_len/2)):
            penalty = err_penalty(zeros, bs_len) + discount + 1 # Extra one is for rounding error.
            lower_bound = 2**(-penalty/float(bs_len))

            n = bs_len
            k = zeros
            p = lower_bound
            tail_prob = cum_binom(n, k, p)

            if -lg2(tail_prob) < discount and bs_len - penalty >= 0:
                violations += 1
        
    print("Violations: " + str(violations))