@EricHolloway/

# ASC GI Probability Violations

## Check if the ASC based GI violates the inequality P(GI >= b) <= 2^-b.

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
52
53
54
55
```
```import sys
import math

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

def log2(n): return math.log(n,2)

def calc_err_penalty(errs, num_bits):
if errs == 0:
return 0
penalty = math.ceil(log2(errs)+1)*2
penalty += errs*num_bits
return penalty

if __name__ == "__main__":
bits = 8
if len(sys.argv) > 1:
bits = int(sys.argv[1])

model_size = (bits+1)*4+1

bs_len = 2**bits
n = bs_len

probits = {}

err_penalty = bits
for k in range(n):
gi_prob = nCk(n,k)/float(2**n)
gi_probits = nCk(n,k)

err = min(k, n-k)
asc_info = n - calc_err_penalty(err, bits)
gen_info = asc_info - model_size

if gen_info > 0:
probits[gen_info] = probits.get(gen_info, 0) + gi_probits

cum_probits = {}
for k0,v in probits.items():
for k1 in probits.keys():
if k1 <= k0:
cum_probits[k1] = cum_probits.get(k1,0) + v

failures = 0
for k,v in sorted(cum_probits.items()):
if k > n-log2(v):
failures += 1

print "Number of bits in bitstring: " + str(2**bits)
print "Violations of GI improbability: " + str(failures)

```