Last active
May 8, 2016 18:17
-
-
Save Juddling/1a34fd02a1291ac28225a92348ca1159 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from math import log, pow, factorial | |
| def nCr(n,r): | |
| f = factorial | |
| return f(n) / f(r) / f(n-r) | |
| def H(x): | |
| # Shannon entropy / information content | |
| sum = 0.0 | |
| for p in x: | |
| sum += float(p) * log(1/p, 2) | |
| return sum | |
| def relative_entropy(p, q): | |
| # Relative entropy | |
| sum = 0.0 | |
| assert len(p) == len(q) | |
| for i in range(len(p)): | |
| sum += p[i] * log(p[i]/q[i], 2) | |
| return sum | |
| def flip_probability(p, n, k): | |
| # k flips in an n-bit repetition code, with p being the probability of a flip | |
| prob = nCr(n, k) * pow(p, k) * pow(1-p, n-k) | |
| print("P(%d flips) = %f" % (k, prob)) | |
| return prob | |
| def incorrigible_error(p, n): | |
| correctible_flips = (n - 1) / 2 | |
| error_prob = 1.0 | |
| flips = 0 | |
| while flips <= correctible_flips: | |
| error_prob -= flip_probability(p, n, flips) | |
| flips += 1 | |
| return error_prob | |
| assert nCr(5, 3) == 10 | |
| assert nCr(4, 1) == 4 | |
| # p = [0.5,0.2,0.17,0.13] | |
| # q = [0.5,0.3,0.1,0.1] | |
| # info_content = H(p) | |
| # print("H(X) = %f" % info_content) | |
| # print("D(p||q) = %f" % relative_entropy(p, q)) | |
| # print("P(0 flips) = %f" % flip_probability(0.25, 5, 5)) | |
| print("P_err = %f where n = 5 and p = 0.25" % incorrigible_error(0.25, 3)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment