@EricHolloway/

ASC GI Probability Violations

Python 2.7

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

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