@EricHolloway/

# Entropy Lower Bound Violations

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

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))
```