#!/usr/bin/env python3
"""verify.py -- computational checks for
"Entropy, Sources, and Channels in Higher Categories".

Standard library only; fixed random seed.  Run:  python3 verify.py
Prints one line per check and exits with status 0 iff all checks pass.
Version 1.0.

A passing check is evidence about the numerical examples and about the finite
structural claims as stated in the text.  It is not a proof of any theorem.
"""
import heapq
import itertools
import math
import random
import sys
from math import comb, log2

random.seed(20261116)
results = []


def check(name, cond, detail=""):
    results.append((name, bool(cond)))
    print(("PASS  " if cond else "FAIL  ") + name + (("   [" + str(detail) + "]") if detail != "" else ""))


def close(a, b, tol=1e-9):
    return abs(a - b) <= tol


def H(ps):
    return -sum(p * log2(p) for p in ps if p > 0)


def hb(x):
    return 0.0 if x <= 0 or x >= 1 else -x * log2(x) - (1 - x) * log2(1 - x)


def hinv(v):
    lo, hi = 0.0, 0.5
    for _ in range(80):
        m = (lo + hi) / 2
        lo, hi = (m, hi) if hb(m) < v else (lo, m)
    return lo


def KL(p, q):
    s = 0.0
    for a, b in zip(p, q):
        if a > 0:
            if b <= 0:
                return math.inf
            s += a * log2(a / b)
    return s


def rd(n):
    w = [random.random() + 0.05 for _ in range(n)]
    t = sum(w)
    return [x / t for x in w]


def rstoch(m, n):
    return [rd(n) for _ in range(m)]


def push(p, W):
    return [sum(p[x] * W[x][y] for x in range(len(p))) for y in range(len(W[0]))]


def compose(V, W):
    """W: X->Y then V: Y->Z."""
    return [push(W[x], V) for x in range(len(W))]


def tensor(W, V):
    return [[W[x][y] * V[a][b] for y in range(len(W[0])) for b in range(len(V[0]))]
            for x in range(len(W)) for a in range(len(V))]


def MI(p, W):
    q = push(p, W)
    return sum(p[x] * W[x][y] * log2(W[x][y] / q[y])
               for x in range(len(p)) for y in range(len(q)) if p[x] > 0 and W[x][y] > 0)


def capacity(W, iters=2500):
    n = len(W)
    p = [1 / n] * n
    for _ in range(iters):
        q = push(p, W)
        d = [sum(W[x][y] * math.log(W[x][y] / q[y]) for y in range(len(q)) if W[x][y] > 0) for x in range(n)]
        w = [p[x] * math.exp(d[x]) for x in range(n)]
        t = sum(w)
        p = [x / t for x in w]
    return MI(p, W), p


def bsc(d):
    return [[1 - d, d], [d, 1 - d]]


def renyi(p, a):
    if a == 0:
        return log2(sum(1 for x in p if x > 0))
    if a == math.inf:
        return -log2(max(p))
    if abs(a - 1) < 1e-12:
        return H(p)
    return log2(sum(x ** a for x in p if x > 0)) / (1 - a)


# ---------------------------------------------------------------- Chapter 1: finite schemes
def Hmap(p, f, m):
    q = [0.0] * m
    for x, px in enumerate(p):
        q[f[x]] += px
    tot = sum(q[y] * H([p[x] / q[y] for x in range(len(p)) if f[x] == y]) for y in range(m) if q[y] > 0)
    return tot, q


p0 = [0.5, 0.25, 0.125, 0.125]
check("ch1 H(1/2,1/4,1/8,1/8)=1.75; merging the last two loses 0.25, the first two 0.689",
      close(H(p0), 1.75) and close(Hmap(p0, [0, 1, 2, 2], 3)[0], 0.25) and close(Hmap(p0, [0, 0, 1, 2], 3)[0], 0.75 * hb(2 / 3))
      and close(0.75 * hb(2 / 3), 0.6887, 1e-4))
ok = True
for _ in range(200):
    p = rd(8)
    f = [random.randrange(5) for _ in range(8)]
    g = [random.randrange(3) for _ in range(5)]
    hf, q = Hmap(p, f, 5)
    hg, r = Hmap(q, g, 3)
    hgf, _ = Hmap(p, [g[f[x]] for x in range(8)], 3)
    ok &= close(hgf, hf + hg) and close(hf, H(p) - H(q)) and hf >= -1e-12
check("ch1 entropy of a map: H(f)=H(p)-H(q)>=0 and H(gf)=H(f)+H(g) on 200 random composites", ok)


def opcomp(q, ps):
    return [q[i] * x for i in range(len(q)) for x in ps[i]]


ok = True
for _ in range(200):
    q = rd(4)
    ps = [rd(random.randint(1, 4)) for _ in range(4)]
    ok &= close(H(opcomp(q, ps)), H(q) + sum(q[i] * H(ps[i]) for i in range(4)))
check("ch1 operadic chain rule H(q o (p_1..p_m)) = H(q) + sum q_i H(p_i) on 200 random composites", ok)
ok = True
for _ in range(100):
    lam = random.random()
    p, pp = rd(5), rd(4)
    f = [random.randrange(3) for _ in range(5)]
    g = [random.randrange(2) for _ in range(4)]
    mix = [lam * x for x in p] + [(1 - lam) * x for x in pp]
    fm = f + [3 + y for y in g]
    ok &= close(Hmap(mix, fm, 5)[0], lam * Hmap(p, f, 3)[0] + (1 - lam) * Hmap(pp, g, 2)[0])
    ok &= close(H(mix), lam * H(p) + (1 - lam) * H(pp) + hb(lam))
check("ch1 convex-linearity on morphisms; objects pick up the extra term h(lambda)", ok)
ok = True
for _ in range(200):
    nx, ny = random.randint(2, 5), random.randint(2, 5)
    p = rd(nx)
    W = rstoch(nx, ny)
    q = push(p, W)
    joint = [p[x] * W[x][y] for x in range(nx) for y in range(ny)]
    HYX = sum(p[x] * H(W[x]) for x in range(nx))
    HXY = sum(q[y] * H([p[x] * W[x][y] / q[y] for x in range(nx)]) for y in range(ny))
    ok &= close(H(joint), H(p) + HYX) and HYX <= H(q) + 1e-12 and H(p) <= log2(nx) + 1e-12
    ok &= close(HXY, H(p) - H(q) + HYX)
check("ch1 Khinchin's properties (ii)-(iv) and equivocation = H(p)-H(q)+noise on 200 random kernels", ok)
ok = True
for _ in range(100):
    n = 5
    perms = [random.sample(range(n), n) for _ in range(4)]
    lam = rd(4)
    D = [[sum(lam[k] for k in range(4) if perms[k][x] == y) for y in range(n)] for x in range(n)]
    p = rd(n)
    ok &= H(push(p, D)) >= H(p) - 1e-12
Wbad = [[0.9, 0.1, 0.0], [0.9, 0.0, 0.1], [0.8, 0.1, 0.1]]
check("sol 1.4 doubly stochastic maps do not decrease entropy; a non-doubly-stochastic one lowers it at the uniform state",
      ok and H(push([1 / 3] * 3, Wbad)) < log2(3) - 0.1)
check("sol 1.1 H(g)=0.689, H(h)=0.25, H(hg)=1.75-h(1/4)=0.939",
      close(0.75 * hb(2 / 3) + 0.25, 1.75 - hb(0.25)) and close(1.75 - hb(0.25), 0.9387, 1e-4))
ok = True
for _ in range(100):
    p = rd(3)
    W, V = rstoch(3, 3), rstoch(3, 3)
    VW = compose(V, W)

    def equiv(p, K):
        q = push(p, K)
        return sum(q[y] * H([p[x] * K[x][y] / q[y] for x in range(len(p))]) for y in range(len(q)))
    ok &= equiv(p, VW) <= equiv(p, W) + equiv(push(p, W), V) + 1e-12
check("sol 1.5 equivocation is subadditive along a Markov chain X -> Y -> Z (100 random)", ok)

# ---------------------------------------------------------------- Chapter 2: uniqueness
ok = True
for _ in range(100):
    g = [random.randint(1, 9) for _ in range(random.randint(2, 6))]
    G = sum(g)
    p = [x / G for x in g]
    ok &= close(log2(G) - sum(pi * log2(gi) for pi, gi in zip(p, g)), H(p))
check("ch2 Khinchin's second step: log g - sum p_i log g_i = H(p) for 100 random rational p", ok)
check("sol 2.1 p=(1/2,1/3,1/6): both sides equal 1.459",
      close(log2(6) - 0.5 * log2(3) - log2(2) / 3, H([1 / 2, 1 / 3, 1 / 6])) and close(H([1 / 2, 1 / 3, 1 / 6]), 1.4591, 1e-4))
ok = True
for _ in range(100):
    a = random.choice([0.3, 0.5, 2.0, 3.0])
    p, q = rd(4), rd(3)
    ok &= close(renyi([x * y for x in p for y in q], a), renyi(p, a) + renyi(q, a))
    ok &= renyi(p, a) <= 2 + 1e-12 and close(renyi(p + [0.0], a), renyi(p, a))
    ok &= abs(renyi(p, 1 + 1e-6) - H(p)) < 1e-4
check("ch2 Renyi entropies: additive on products, maximal at uniform, expansible, -> H as alpha -> 1", ok)
pr = [0.5, 0.25, 0.25]
check("ch2 Example: H_2(1/2,1/4,1/4)=log(8/3)=1.415 but the chain rule would give 1.5",
      close(renyi(pr, 2), log2(8 / 3)) and close(renyi([.5, .5], 2) + 0.5 * renyi([.5, .5], 2), 1.5) and close(log2(8 / 3), 1.415, 1e-3))
ok = True
bad = False
for _ in range(100):
    p, q = rd(4), rd(3)
    i = random.randrange(4)
    comp = p[:i] + [p[i] * x for x in q] + p[i + 1:]
    ok &= close(H(comp), H(p) + p[i] * H(q))
    bad |= abs(renyi(comp, 2) - renyi(p, 2) - p[i] * renyi(q, 2)) > 1e-3
check("ch2 Leibniz rule H(p o_i q) = H(p) + p_i H(q) holds for H and fails for H_2", ok and bad)
F2 = lambda p, q: renyi(p, 2) - renyi(q, 2)
ok = True
for _ in range(100):
    p = rd(6)
    f = [random.randrange(3) for _ in range(6)]
    ok &= F2(p, Hmap(p, f, 3)[1]) >= -1e-12
check("sol 2.4 F(f)=H_2(p)-H_2(q) is a nonnegative functor that is not convex-linear (0.415 vs 0.5)",
      ok and close(F2([.25, .25, .5], [.5, .5]), log2(8 / 3) - 1) and close(log2(8 / 3) - 1, 0.415, 1e-3))

# ---------------------------------------------------------------- Chapter 3: cocycles


def canon(labels):
    seen = {}
    return tuple(seen.setdefault(l, len(seen)) for l in labels)


def rpart(n, k):
    return canon([random.randrange(k) for _ in range(n)])


def prod(X, Y):
    return canon(list(zip(X, Y)))


def blocks(X):
    b = {}
    for i, l in enumerate(X):
        b.setdefault(l, []).append(i)
    return list(b.values())


def law(X, P):
    return [sum(P[i] for i in B) for B in blocks(X)]


def cond(P, B):
    m = sum(P[i] for i in B)
    return [P[i] / m if i in B else 0.0 for i in range(len(P))]


def act(Y, f, alpha=1.0):
    def g(P):
        tot = 0.0
        for B in blocks(Y):
            m = sum(P[i] for i in B)
            if m > 0:
                tot += m ** alpha * f(cond(P, set(B)))
        return tot
    return g


NOM = 5
ok = True
for _ in range(60):
    Y, Z = rpart(NOM, 3), rpart(NOM, 3)
    P = rd(NOM)
    f = lambda Q: sum(math.sin(3 * Q[i] + i) for i in range(NOM))
    for al in (1.0, 0.5, 2.0):
        ok &= close(act(Y, act(Z, f, al), al)(P), act(prod(Y, Z), f, al)(P))
    ok &= close(act(canon([0] * NOM), f)(P), f(P))
check("ch3 conditioning is a monoid action: Y.(Z.f) = (YZ).f for alpha = 1, 1/2, 2 (60 random)", ok)
Hc = lambda Y: (lambda P: H(law(Y, P)))
ok = True
for _ in range(100):
    Y, Z = rpart(NOM, 3), rpart(NOM, 3)
    P = rd(NOM)
    ok &= close(Hc(prod(Y, Z))(P), Hc(Y)(P) + act(Y, Hc(Z))(P))
check("ch3 entropy is a 1-cocycle: H[YZ] = H[Y] + Y.H[Z] on 100 random pairs of observables", ok)


def cochain(Y):
    c = 1.0 + 0.37 * len(blocks(Y)) + 0.11 * sum(Y)
    return lambda P: sum(c * m * m + math.sin(3 * m) for m in law(Y, P))


def d1(f, al=1.0):
    return lambda Y, Z: (lambda P: act(Y, f(Z), al)(P) - f(prod(Y, Z))(P) + f(Y)(P))


def d2(g, al=1.0):
    return lambda X, Y, Z: (lambda P: act(X, g(Y, Z), al)(P) - g(prod(X, Y), Z)(P) + g(X, prod(Y, Z))(P) - g(X, Y)(P))


ok = True
nonzero = False
for _ in range(40):
    X, Y, Z = rpart(NOM, 2), rpart(NOM, 3), rpart(NOM, 2)
    P = rd(NOM)
    for al in (1.0, 2.0):
        ok &= abs(d2(d1(cochain, al), al)(X, Y, Z)(P)) < 1e-9
    nonzero |= abs(d1(cochain)(Y, Z)(P)) > 1e-3
check("ch3 delta delta = 0 on a generic local 1-cochain (which is not itself a cocycle), alpha = 1 and 2", ok and nonzero)
ok = True
for _ in range(60):
    Y, Z = rpart(NOM, 3), rpart(NOM, 3)
    P = rd(NOM)
    for al in (0.5, 2.0, 3.0):
        S = lambda Y, al=al: (lambda P: (1 - sum(m ** al for m in law(Y, P))) / (al - 1))
        ok &= close(act(Y, lambda Q: 1.0, al)(P) - 1.0, -(al - 1) * S(Y)(P))
        ok &= close(S(prod(Y, Z))(P), S(Y)(P) + act(Y, S(Z), al)(P))
    ok &= close(act(Y, lambda Q: 1.0, 1.0)(P), 1.0)
    al = 1 + 1e-6
    ok &= abs((1 - sum(m ** al for m in law(Y, P))) / (al - 1) - math.log(2) * H(law(Y, P))) < 1e-4
check("ch3 Tsallis entropy is the alpha-coboundary of a constant, an alpha-cocycle, and tends to ln2 * H", ok)
ok = True
for _ in range(60):
    P1, P2 = rd(3), rd(4)
    al = random.choice([0.5, 2.0, 3.0])
    S = lambda p: (1 - sum(x ** al for x in p)) / (al - 1)
    ok &= close(S([a * b for a in P1 for b in P2]), S(P1) + S(P2) - (al - 1) * S(P1) * S(P2))
check("sol 3.2 Tsallis entropy of an independent pair: S+S'-(alpha-1)SS'", ok)


def feith(h, x, y):
    return h(x) + (1 - x) * h(y / (1 - x)) - h(y) - (1 - y) * h(x / (1 - y))


ok = True
bad = False
for _ in range(300):
    x = random.random() * 0.98
    y = random.random() * (1 - x)
    ok &= abs(feith(hb, x, y)) < 1e-9 and abs(feith(lambda t: t, x, y)) < 1e-12
    bad |= abs(feith(lambda t: t * (1 - t), x, y)) > 1e-3
check("ch3 fundamental equation: h_2 and h(x)=x satisfy it, x(1-x) does not", ok and bad)
basis = [hb, lambda t: t * (1 - t), lambda t: (t * (1 - t)) ** 2, lambda t: math.sin(math.pi * t)]
rows = []
for _ in range(40):
    x = random.random() * 0.9 + 0.02
    y = random.random() * (0.98 - x)
    rows.append([feith(b, x, y) for b in basis])


def rank(M, tol=1e-8):
    M = [r[:] for r in M]
    rk = 0
    for c in range(len(M[0])):
        piv = max(range(rk, len(M)), key=lambda r: abs(M[r][c]))
        if abs(M[piv][c]) < tol:
            continue
        M[rk], M[piv] = M[piv], M[rk]
        for r in range(rk + 1, len(M)):
            fct = M[r][c] / M[rk][c]
            M[r] = [a - fct * b for a, b in zip(M[r], M[rk])]
        rk += 1
    return rk


check("ch3 in a 4-dimensional test space of symmetric functions vanishing at 0 and 1, the solutions of the equation are spanned by h_2",
      rank(rows) == 3)
dpart = lambda x: 0.0 if x <= 0 else -x * log2(x)
ok = True
for _ in range(200):
    x, y = random.random(), random.random()
    ok &= close(dpart(x * y), x * dpart(y) + y * dpart(x))
    p = rd(5)
    ok &= close(sum(dpart(t) for t in p), H(p))
check("ch3 d(x) = -x log x is a derivation and H(p) = sum d(p_i) - d(sum p_i)", ok)
PRIMES = [3, 5, 7, 11, 13]


def Hp(pi, p):
    a = [x % p for x in pi]
    assert sum(a) % p == 1
    return ((1 - sum(x ** p for x in a)) // p) % p


def rdist_mod(n, p):
    v = [random.randrange(p) for _ in range(n - 1)]
    return v + [(1 - sum(v)) % p]


ok = True
for p in PRIMES:
    for _ in range(100):
        a, b = random.randrange(1, 200), random.randrange(1, 200)
        fq = lambda z: (z - z ** p) // p
        ok &= (fq(a * b) - a * fq(b) - fq(a) * b) % p == 0
check("ch3 the Fermat quotient satisfies the Leibniz rule mod p (p = 3..13)", ok)
ok = True
for p in PRIMES:
    for _ in range(100):
        n = random.randint(2, 4)
        gam = rdist_mod(n, p)
        pis = [rdist_mod(random.randint(1, 3), p) for _ in range(n)]
        comp = [(gam[i] * x) % p for i in range(n) for x in pis[i]]
        ok &= Hp(comp, p) == (Hp(gam, p) + sum(gam[i] * Hp(pis[i], p) for i in range(n))) % p
        lift = [x + p * random.randrange(-3, 4) for x in gam]
        ok &= ((1 - sum(x ** p for x in lift)) // p) % p == Hp(gam, p)
check("ch3 entropy mod p is well defined and satisfies the chain rule (500 random instances, p = 3..13)", ok)
ok = True
for p in PRIMES:
    hp = lambda x, p=p: sum(pow(x, k, p) * pow(k, -1, p) for k in range(1, p)) % p
    for x in range(p):
        ok &= hp(x) == Hp([x, 1 - x], p)
    for x in range(p):
        for y in range(p):
            if x != 1 and y != 1:
                lhs = hp(x) + (1 - x) * hp(y * pow(1 - x, -1, p) % p)
                rhs = hp(y) + (1 - y) * hp(x * pow(1 - y, -1, p) % p)
                ok &= (lhs - rhs) % p == 0
check("ch3 H_p(x,1-x) is the truncated logarithm sum x^k/k and satisfies the fundamental equation on F_p", ok)
check("sol 3.5 H_5(2,4)=4, H_3(2,2)=1, H_3(1,1,2)=0 and the chain rule 1+2*1+2*0=0 mod 3",
      Hp([2, 4], 5) == 4 and Hp([2, 2], 3) == 1 and Hp([1, 1, 2], 3) == 0 and Hp([1], 3) == 0)

# ---------------------------------------------------------------- Chapter 4: divergence
ok = True
for _ in range(300):
    nx, ny = random.randint(2, 5), random.randint(2, 5)
    p, pp = rd(nx), rd(nx)
    W = rstoch(nx, ny)
    ok &= KL(p, pp) >= -1e-12 and KL(push(p, W), push(pp, W)) <= KL(p, pp) + 1e-12
    W2 = rstoch(nx, ny)
    r = [p[x] * W[x][y] for x in range(nx) for y in range(ny)]
    r2 = [pp[x] * W2[x][y] for x in range(nx) for y in range(ny)]
    ok &= close(KL(r, r2), KL(p, pp) + sum(p[x] * KL(W[x], W2[x]) for x in range(nx)))
check("ch4 Gibbs' inequality, the chain rule for relative entropy and data processing (300 random)", ok)
Dm = lambda f, g: max(KL(a, b) for a, b in zip(f, g))
ok = True
for _ in range(100):
    f, g = rstoch(3, 4), rstoch(3, 4)
    hh, k = rstoch(4, 3), rstoch(2, 3)
    f2, g2 = rstoch(2, 2), rstoch(2, 2)
    ok &= Dm(compose(hh, f), compose(hh, g)) <= Dm(f, g) + 1e-12
    ok &= Dm(compose(f, k), compose(g, k)) <= Dm(f, g) + 1e-12
    ok &= close(Dm(tensor(f, f2), tensor(g, g2)), Dm(f, g) + Dm(f2, g2))
check("ch4 composition is short and tensor is additive for the divergence on hom-sets (100 random)", ok)
ok = True
for _ in range(100):
    n = random.randint(2, 6)
    p = rd(n)
    cp = [p[x] if x == y else 0.0 for x in range(n) for y in range(n)]
    pp = [p[x] * p[y] for x in range(n) for y in range(n)]
    ok &= close(KL(cp, pp), H(p)) and close(0.5 * sum(abs(a - b) for a, b in zip(cp, pp)), 1 - sum(x * x for x in p))
check("ch4 entropy is the divergence of copy.p from p(x)p; with total variation it is the Gini-Simpson index", ok)
check("sol 4.3 for (1/2,1/4,1/4): TV = 5/8 and KL = 1.5", close(1 - (0.25 + 0.0625 + 0.0625), 0.625) and close(H(pr), 1.5))
ok = True
for _ in range(200):
    nx, ny = random.randint(2, 4), random.randint(2, 5)
    p = rd(nx)
    W = rstoch(nx, ny)
    q = push(p, W)
    S = [y for y in range(ny) if random.random() < 0.5]
    lhs = -sum(p[x] * W[x][y] * log2(W[x][y]) for x in range(nx) for y in S)
    ok &= lhs <= -sum(q[y] * log2(q[y]) for y in S) + 1e-12
check("ch4 Khinchin's Lemma 1.1: the partial-sum form of Shannon's inequality (200 random)", ok)


def meet(X, Y):
    n = len(X)
    par = list(range(n))

    def find(i):
        while par[i] != i:
            par[i] = par[par[i]]
            i = par[i]
        return i
    for Z in (X, Y):
        for B in blocks(Z):
            for i in B[1:]:
                par[find(i)] = find(B[0])
    return canon([find(i) for i in range(n)])


ok = True
for _ in range(200):
    n = 6
    X, Y, Z = rpart(n, 3), rpart(n, 3), rpart(n, 2)
    P = rd(n)
    h = lambda V: H(law(V, P))
    ok &= h(prod(prod(X, Y), Z)) + h(Y) <= h(prod(X, Y)) + h(prod(Y, Z)) + 1e-12
    ok &= h(prod(X, Y)) + h(meet(X, Y)) <= h(X) + h(Y) + 1e-12
    ok &= h(prod(X, Y)) >= h(X) - 1e-12
check("ch4 entropy is monotone and submodular on the lattice of partitions (Khinchin's Lemma 1.2), 200 random", ok)
rr = [0.4, 0.1, 0.1, 0.4]
check("sol 4.4 two correlated bits: I = 2 - H(.4,.1,.1,.4) = 0.278 with trivial meet",
      close(2 - H(rr), 0.2781, 1e-4) and len(blocks(meet((0, 0, 1, 1), (0, 1, 0, 1)))) == 1)
ok = True
for _ in range(200):
    nx, ny = random.randint(2, 5), random.randint(2, 5)
    p = rd(nx)
    W = rstoch(nx, ny)
    q = push(p, W)
    r = [[p[x] * W[x][y] for y in range(ny)] for x in range(nx)]
    Pe = 1 - sum(max(r[x][y] for x in range(nx)) for y in range(ny))
    HXY = sum(q[y] * H([r[x][y] / q[y] for x in range(nx)]) for y in range(ny))
    ok &= HXY <= hb(Pe) + Pe * log2(nx - 1) + 1e-9 if nx > 1 else True
    # Feinstein (i): Markov inequality
    Z = set((x, y) for x in range(nx) for y in range(ny) if random.random() < 0.8)
    U0 = set(x for x in range(nx) if random.random() < 0.8)
    al = random.choice([0.2, 0.5])
    d1_, d2_ = 1 - sum(r[x][y] for (x, y) in Z), 1 - sum(p[x] for x in U0)
    U1 = [x for x in U0 if sum(W[x][y] for y in range(ny) if (x, y) not in Z) <= al]
    ok &= sum(p[x] for x in U1) >= 1 - d2_ - d1_ / al - 1e-12
    # Feinstein (ii): MAP beats any decoder
    dec = [random.randrange(nx) for _ in range(ny)]
    ok &= sum(r[dec[y]][y] for y in range(ny)) <= 1 - Pe + 1e-12
check("ch4 Feinstein's three inequalities, including Fano's (200 random joint distributions)", ok)
n_, e_ = 5, 0.3
check("sol 4.5 symmetric noise attains equality in Fano's inequality",
      close(H([1 - e_] + [e_ / (n_ - 1)] * (n_ - 1)), hb(e_) + e_ * log2(n_ - 1)))
check("sol 4.1 D(p||q)=0.2075, D(q||p)=0.1887, after BSC(0.1): 0.1258",
      close(KL([.5, .5], [.25, .75]), 0.2075, 1e-4) and close(KL([.25, .75], [.5, .5]), 0.1887, 1e-4)
      and close(KL(push([.5, .5], bsc(.1)), push([.25, .75], bsc(.1))), 0.1258, 1e-4))
ok = True
for _ in range(100):
    nx, ny, nz = 6, 3, 2
    p = rd(nx)
    f = [x % ny for x in range(nx)]
    g = [y % nz for y in range(ny)]
    q = Hmap(p, f, ny)[1]
    r = Hmap(q, g, nz)[1]
    s = [[(random.random() + 0.1) if f[x] == y else 0.0 for x in range(nx)] for y in range(ny)]
    s = [[v / sum(row) for v in row] for row in s]
    t = [[(random.random() + 0.1) if g[y] == z else 0.0 for y in range(ny)] for z in range(nz)]
    t = [[v / sum(row) for v in row] for row in t]
    ok &= close(KL(p, push(push(r, t), s)), KL(p, push(q, s)) + KL(q, push(r, t)))
check("ch4 relative entropy is functorial on FinStat: RE(gf, st) = RE(f,s) + RE(g,t) (100 random)", ok)

# ---------------------------------------------------------------- Chapter 5: sources
A2 = (0, 1)


def seq_probs(n, sigma, emit):
    out = {}

    def rec(prefix, alpha):
        if len(prefix) == n:
            out[prefix] = sum(alpha.values())
            return
        for a in A2:
            nb = {}
            for s, w in alpha.items():
                for s2, pr_ in emit[s].get(a, ()):
                    nb[s2] = nb.get(s2, 0.0) + w * pr_
            if nb:
                rec(prefix + (a,), nb)
    rec((), dict(sigma))
    return out


qa, qb = 0.1, 0.3
Q = [[1 - qa, qa], [qb, 1 - qb]]
PI = [qb / (qa + qb), qa / (qa + qb)]
markov = {s: {a: [(a, Q[s][a])] for a in A2} for s in A2}
Hn = lambda n, sig, em: H(seq_probs(n, sig, em).values()) if n > 0 else 0.0
MRATE = PI[0] * hb(qa) + PI[1] * hb(qb)
hs = [Hn(n, dict(enumerate(PI)), markov) for n in range(0, 9)]
cs = [hs[n + 1] - hs[n] for n in range(8)]
check("ch5 Markov source: rate 0.572 = H_{n+1}-H_n for n>=1; H_n subadditive; marginal entropy 0.811",
      close(MRATE, 0.5721, 1e-4) and all(close(c, MRATE) for c in cs[1:]) and close(cs[0], hb(0.25)) and close(hb(0.25), 0.8113, 1e-4)
      and all(hs[m + n] <= hs[m] + hs[n] + 1e-12 for m in range(1, 5) for n in range(1, 5)))
ee = 0.2
hmm = {s: {a: [(s2, ((1 - ee) if a == s else ee) * Q[s][s2]) for s2 in A2] for a in A2} for s in A2}
up = lambda n: Hn(n, dict(enumerate(PI)), hmm) - Hn(n - 1, dict(enumerate(PI)), hmm)
lo = lambda n: sum(PI[s] * (Hn(n, {s: 1.0}, hmm) - Hn(n - 1, {s: 1.0}, hmm)) for s in A2)
ups = [up(n) for n in range(1, 11)]
los = [lo(n) for n in range(1, 11)]
check("ch5 hidden Markov source: bounds 0.9033 <= H <= 0.9055 at n=4, meeting at 0.9052; upper decreasing, lower increasing",
      close(los[3], 0.9033, 1e-4) and close(ups[3], 0.9055, 1e-4) and close(ups[7], 0.9052, 1e-4) and close(los[7], 0.9052, 1e-4)
      and all(ups[i + 1] <= ups[i] + 1e-12 and los[i + 1] >= los[i] - 1e-12 and los[i] <= ups[i] + 1e-12 for i in range(9)))
d6, d5 = seq_probs(6, dict(enumerate(PI)), hmm), seq_probs(5, dict(enumerate(PI)), hmm)
marg = {}
for k_, v_ in d6.items():
    marg[k_[1:]] = marg.get(k_[1:], 0.0) + v_
check("ch5 the source emitted from an invariant state distribution is stationary (block laws are shift invariant)",
      all(close(marg[k_], d5[k_]) for k_ in d5))
ok = True
for n in range(1, 7):
    src = seq_probs(n + 1, dict(enumerate(PI)), markov)
    out = {}
    for k_, v_ in src.items():
        y = tuple((k_[i] + k_[i + 1]) % 2 for i in range(n))
        out[y] = out.get(y, 0.0) + v_
    ok &= H(out.values()) <= H(src.values()) + 1e-12
fair = {0: {a: [(0, 0.5)] for a in A2}}
src = seq_probs(7, {0: 1.0}, fair)
out = {}
for k_, v_ in src.items():
    y = tuple((k_[i] + k_[i + 1]) % 2 for i in range(6))
    out[y] = out.get(y, 0.0) + v_
check("ch5 a sliding block code does not raise block entropies; x_n+x_{n+1} maps fair bits to fair bits two-to-one",
      ok and close(H(out.values()), 6.0) and len(out) == 64 and len(src) == 128)
pts = list(itertools.product(A2, repeat=2))
rot = lambda x: (x[1], x[0])
cnt = sum(1 for img in itertools.product(pts, repeat=4) if all(img[pts.index(rot(x))] == rot(img[pts.index(x)]) for x in pts))
check("sol 5.3 cofreeness: there are |B|^(|A|^N) = 16 equivariant maps A^(Z/2) -> B^(Z/2) for binary A, B", cnt == 16)
even = {0: {0: [(0, 0.5)], 1: [(1, 0.5)]}, 1: {1: [(0, 1.0)]}}
sig_even = {0: 2 / 3, 1: 1 / 3}
lo_even = sum(sig_even[s] * (Hn(8, {s: 1.0}, even) - Hn(7, {s: 1.0}, even)) for s in (0, 1))
up_even = Hn(12, sig_even, even) - Hn(11, sig_even, even)
check("ch5 unifilar formula: the even process has entropy sum sigma(s) H(e_s) = 2/3",
      close(lo_even, 2 / 3) and 2 / 3 - 1e-9 <= up_even < 2 / 3 + 0.01, round(up_even, 4))
fm = lambda a, b: (b * hb(a) + a * hb(b)) / (a + b)
grid = [i / 20 for i in range(1, 20)]
check("sol 5.1 two-state Markov entropy is maximal (=1) at a=b=1/2 and equals the marginal entropy iff a+b=1",
      close(max(fm(a, b) for a in grid for b in grid), 1.0) and all(close(fm(a, 1 - a), hb(a)) for a in grid)
      and fm(0.1, 0.3) < hb(0.25) - 0.1)

# ---------------------------------------------------------------- Chapter 6: ergodic sources


def Hmix(n):
    tot = 0.0
    for k in range(n + 1):
        pk = 0.5 * (0.1 ** k * 0.9 ** (n - k)) + 0.5 * 0.5 ** n
        if pk > 0:
            tot += comb(n, k) * (-pk * log2(pk))
    return tot


HMIX = 0.5 * (hb(0.1) + 1)
ok = close(HMIX, 0.7345, 1e-4)
for n, v in ((10, 0.8106), (100, 0.7445), (1000, 0.7355)):
    ok &= close(Hmix(n) / n, v, 1e-4)
    lowb = 0.5 * n * hb(0.1) + 0.5 * n
    ok &= lowb - 1e-9 <= Hmix(n) <= lowb + 1 + 1e-9
check("ch6 mixture of two coins: entropy 0.7345; H_n/n = 0.8106, 0.7445, 0.7355; the excess is at most one bit", ok)
Qk = [[1.0, 0.0], [0.0, 1.0]]
acc = 0.0
NN = 4000
for k in range(NN):
    acc += PI[1] * Qk[1][1]
    Qk = [[sum(Qk[i][m] * Q[m][j] for m in A2) for j in A2] for i in A2]
check("ch6 ergodicity criterion: Cesaro averages of P(x_0=1,x_k=1) tend to pi_1^2 for the Markov chain, not for the mixture",
      abs(acc / NN - PI[1] ** 2) < 1e-3 and abs((0.5 * 0.01 + 0.5 * 0.25) - 0.3 ** 2) > 0.03)
check("sol 6.4 on the fair component the first component has rate 1.737 > 1",
      close(0.5 * log2(10) + 0.5 * log2(10 / 9), 1.737, 1e-3))
Qb = [[0.8, 0.2, 0, 0], [0.4, 0.6, 0, 0], [0, 0, 0.5, 0.5], [0, 0, 0.9, 0.1]]
pi1, pi2 = [2 / 3, 1 / 3, 0, 0], [0, 0, 9 / 14, 5 / 14]
rate = lambda pi: sum(pi[a] * H(Qb[a]) for a in range(4))
lam = 0.3
mixpi = [lam * a + (1 - lam) * b for a, b in zip(pi1, pi2)]
check("sol 6.1 two closed classes: stationary laws form a segment and the entropy is affine on it",
      all(close(sum(pi[a] * Qb[a][b] for a in range(4)), pi[b]) for pi in (pi1, pi2, mixpi) for b in range(4))
      and close(rate(mixpi), lam * rate(pi1) + (1 - lam) * rate(pi2)))

# ---------------------------------------------------------------- Chapter 7: martingales


def condexp(X, n):
    """conditional expectation matrix for the uniform distribution on n points and the partition X"""
    M = [[0.0] * n for _ in range(n)]
    for B in blocks(X):
        for i in B:
            for j in B:
                M[i][j] = 1 / len(B)
    return M


matmul = lambda A_, B_: [[sum(A_[i][k] * B_[k][j] for k in range(len(B_))) for j in range(len(B_[0]))] for i in range(len(A_))]
mclose = lambda A_, B_: all(close(a, b) for ra, rb in zip(A_, B_) for a, b in zip(ra, rb))
E1 = condexp((0, 0, 1, 1, 1, 1), 6)
check("sol 7.1 the conditional expectation matrix is idempotent and symmetric, with block averages 1.5 and 4.5",
      mclose(matmul(E1, E1), E1) and all(close(E1[i][j], E1[j][i]) for i in range(6) for j in range(6))
      and [round(sum(E1[i][j] * (j + 1) for j in range(6)), 6) for i in range(6)] == [1.5, 1.5, 4.5, 4.5, 4.5, 4.5])
ok = True
for _ in range(50):
    n = 8
    fine = rpart(n, 5)
    coarse = canon([fine[i] % 2 for i in range(n)])
    Ef, Ec = condexp(fine, n), condexp(coarse, n)
    ok &= mclose(matmul(Ec, Ef), Ec) and mclose(matmul(Ef, Ec), Ec)
Pa, Pb = condexp((0, 0, 1), 3), condexp((0, 1, 1), 3)
v = [1.0, 0.0, 0.0]
ap = lambda M, v: [sum(M[i][j] * v[j] for j in range(len(v))) for i in range(len(M))]
check("ch7 tower property e_G e_G' = e_G for G in G'; two conditional expectations on three points do not commute",
      ok and all(close(a, b) for a, b in zip(ap(Pb, ap(Pa, v)), [0.5, 0.25, 0.25])) and all(close(a, b) for a, b in zip(ap(Pa, ap(Pb, v)), [0.5, 0.5, 0.0])))
NG = 1024
fgrid = [(i + 0.5) / NG for i in range(NG)]
errs = []
for n in range(0, 7):
    L = NG >> n
    e2 = 0.0
    for b in range(0, NG, L):
        m = sum(fgrid[b:b + L]) / L
        e2 += sum((x - m) ** 2 for x in fgrid[b:b + L])
    errs.append(math.sqrt(e2 / NG))
check("ch7 dyadic martingale of f(x)=x: the L2 error is 2^-n / sqrt(12) and decreases to 0",
      all(abs(errs[n] - 2 ** -n / math.sqrt(12)) < 2e-4 for n in range(7)) and all(errs[n + 1] < errs[n] for n in range(6)))
th = 0.8
rho = 0.5 * (math.sqrt(2 * th) + math.sqrt(2 * (1 - th)))


def lik_stats(n):
    EM = EsM = tail = tv = 0.0
    for k in range(n + 1):
        lw = math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1) - n * math.log(2)
        lM = k * math.log(2 * th) + (n - k) * math.log(2 * (1 - th))
        w = math.exp(lw)
        EM += math.exp(lw + lM)
        EsM += math.exp(lw + lM / 2)
        tail += w if lM > math.log(0.01) else 0.0
        tv += 0.5 * abs(w - math.exp(lw + lM))
    return EM, EsM, tail, tv


EM, EsM, tail, tv = lik_stats(50)
_, _, tail400, tv400 = lik_stats(400)
check("ch7 likelihood-ratio martingale: E M_n = 1, E sqrt(M_n) = rho^n with rho = 0.949, yet M_n -> 0 in probability; the laws become singular",
      close(EM, 1.0, 1e-9) and close(EsM, rho ** 50, 1e-9) and close(rho, 0.9487, 1e-4) and tail400 < 1e-6 and tv400 > 0.999)
sig = [1, 2, 0, 4, 3]
U = [[1.0 if sig[j] == i else 0.0 for j in range(5)] for i in range(5)]
acc = [[0.0] * 5 for _ in range(5)]
Uk = [[1.0 if i == j else 0.0 for j in range(5)] for i in range(5)]
for _ in range(6):
    acc = [[acc[i][j] + Uk[i][j] / 6 for j in range(5)] for i in range(5)]
    Uk = matmul(U, Uk)
check("sol 7.5 mean ergodic theorem for a permutation: the average over a period is the conditional expectation on the cycles",
      mclose(acc, condexp((0, 0, 0, 1, 1), 5)))
ok = True
for _ in range(30):
    n = 12
    f = [random.gauss(0, 1) for _ in range(n)]
    labels = [[0] * n]
    for _ in range(4):
        labels.append([2 * a + random.randrange(2) for a in labels[-1]])
    Ms = [ap(condexp(canon(l), n), f) for l in labels]
    incs = [[b - a for a, b in zip(Ms[k], Ms[k + 1])] for k in range(4)]
    for j in range(4):
        for k in range(j + 1, 4):
            ok &= abs(sum(a * b for a, b in zip(incs[j], incs[k]))) < 1e-9
    ok &= close(sum(sum(a * a for a in inc) for inc in incs), sum((b - a) ** 2 for a, b in zip(Ms[0], Ms[4])))
check("ch7 martingale increments are orthogonal and their squared norms add up (30 random filtrations)", ok)

# ---------------------------------------------------------------- Chapter 8: McMillan's theorem
ok = True
for em in (markov, hmm):
    K = 6
    dk1, dk = seq_probs(K + 1, dict(enumerate(PI)), em), seq_probs(K, dict(enumerate(PI)), em)
    for t in (0.5, 1, 2, 3, 4, 6):
        mass = sum(v_ for k_, v_ in dk1.items() if -log2(v_ / dk[k_[:-1]]) > t)
        ok &= mass <= 2 * 2 ** (-t) + 1e-12
check("ch8 tail estimate: mu{g_k > t} <= |A| 2^-t for the Markov and hidden Markov sources (k = 6)", ok)
PB = 0.2
HB = hb(PB)


def typ(n, eps):
    return sum(math.exp(math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1) + k * math.log(PB) + (n - k) * math.log(1 - PB))
               for k in range(n + 1) if abs(-(k * log2(PB) + (n - k) * log2(1 - PB)) / n - HB) < eps)


def Nrate(n, lam, probf):
    acc = 0.0
    cnt = 0
    for k in range(n + 1):
        pk = probf(n, k)
        m = comb(n, k)
        if acc + m * pk >= lam:
            return log2(cnt + max(1, math.ceil((lam - acc) / pk))) / n
        acc += m * pk
        cnt += m


bern = lambda n, k: PB ** k * (1 - PB) ** (n - k)
mixp = lambda n, k: 0.5 * math.exp(k * math.log(0.1) + (n - k) * math.log(0.9)) + 0.5 * math.exp(-n * math.log(2))
tab = {(n, l): Nrate(n, l, bern) for n in (100, 1000) for l in (0.1, 0.5, 0.9)}
check("ch8 independent bits with P(1)=0.2: H=0.7219; the 0.05-typical set has probability 0.468 (n=100), 0.952 (n=1000)",
      close(HB, 0.7219, 1e-4) and close(typ(100, 0.05), 0.4677, 1e-3) and close(typ(1000, 0.05), 0.9519, 1e-3))
want = {(100, 0.1): 0.571, (100, 0.5): 0.684, (100, 0.9): 0.779, (1000, 0.1): 0.683, (1000, 0.5): 0.717, (1000, 0.9): 0.748}
check("ch8 counting theorem: the rates (1/n) log N_n(lambda) of the table, converging to H for every lambda",
      all(close(tab[k_], want[k_], 6e-4) for k_ in want) and all(abs(tab[(1000, l)] - HB) < abs(tab[(100, l)] - HB) for l in (0.1, 0.5, 0.9)))
check("ch8 non-ergodic mixture: the rate depends on lambda (0.463 at 0.25, 0.999 at 0.75; limits h(0.1)=0.469 and 1)",
      close(Nrate(1000, 0.25, mixp), 0.4634, 1e-3) and close(Nrate(1000, 0.75, mixp), 0.999, 1e-3) and close(hb(0.1), 0.469, 1e-3))
sgm = 0.8
pred = lambda lam_z: HB + sgm * lam_z / math.sqrt(1000)
check("sol 8.1/8.5 variance 0.64; second-order prediction 0.754 and 0.690 against 0.748 and 0.683",
      close(PB * (1 - PB) * log2((1 - PB) / PB) ** 2, 0.64) and close(pred(1.2816), 0.7543, 1e-3) and close(pred(-1.2816), 0.6895, 1e-3)
      and abs(pred(1.2816) - tab[(1000, 0.9)]) < 0.01 and abs(pred(-1.2816) - tab[(1000, 0.1)]) < 0.01)


def markovL1(n):
    tot = 0.0
    for f0 in A2:
        d = {(f0, 0, 0): PI[f0]}
        for _ in range(n - 1):
            nd = {}
            for (s, x01, x11), pr_ in d.items():
                for t in A2:
                    key = (t, x01 + (s == 0 and t == 1), x11 + (s == 1 and t == 1))
                    nd[key] = nd.get(key, 0.0) + pr_ * Q[s][t]
            d = nd
        for (s, x01, x11), pr_ in d.items():
            x10 = x01 - (f0 == 0 and s == 1) + (f0 == 1 and s == 0)
            x00 = (n - 1) - x01 - x10 - x11
            l = -log2(PI[f0]) - x00 * log2(Q[0][0]) - x01 * log2(Q[0][1]) - x10 * log2(Q[1][0]) - x11 * log2(Q[1][1])
            tot += pr_ * abs(l / n - MRATE)
    return tot


l1 = [markovL1(n) for n in (4, 16, 64)]
check("ch8 McMillan in mean for the Markov source: E|i_n/n - H| = 0.447, 0.216, 0.109 at n = 4, 16, 64",
      close(l1[0], 0.4472, 1e-3) and close(l1[1], 0.2159, 1e-3) and close(l1[2], 0.1085, 1e-3), [round(x, 4) for x in l1])
nC = 2000
epsC = 0.05
logp = [k * math.log(PB) + (nC - k) * math.log(1 - PB) for k in range(nC + 1)]
lcomb = [math.lgamma(nC + 1) - math.lgamma(k + 1) - math.lgamma(nC - k + 1) for k in range(nC + 1)]
Sset = [k for k in range(nC + 1) if abs(-logp[k] / math.log(2) / nC - HB) <= epsC]


def lse(xs):
    m = max(xs)
    return m + math.log(sum(math.exp(x - m) for x in xs))


lmass = lse([lcomb[k] + logp[k] for k in Sset])
ren = {0: lse([lcomb[k] for k in Sset]) / math.log(2),
       2: -(lse([lcomb[k] + 2 * (logp[k] - lmass) for k in Sset])) / math.log(2),
       math.inf: -(max(logp[k] for k in Sset) - lmass) / math.log(2),
       1: -sum(math.exp(lcomb[k] + logp[k] - lmass) * (logp[k] - lmass) for k in Sset) / math.log(2)}
check("ch12 collapse: after conditioning on a typical set all Renyi rates are within 4*eps of H; before, H_0 and H_inf rates are 1 and 0.322",
      math.exp(lmass) > 1 - epsC and all(abs(v_ / nC - HB) <= 4 * epsC for v_ in ren.values())
      and close(-log2(1 - PB), 0.3219, 1e-4), {k_: round(v_ / nC, 4) for k_, v_ in ren.items()})

# ---------------------------------------------------------------- Chapter 9: channels
pts3 = list(itertools.product(A2, repeat=3))
rot3 = lambda x: (x[1], x[2], x[0])
ok = True
for _ in range(20):
    w = {x: random.random() for x in pts3}
    mu = {x: (w[x] + w[rot3(x)] + w[rot3(rot3(x))]) for x in pts3}
    tot = sum(mu.values())
    mu = {x: v_ / tot for x, v_ in mu.items()}
    k0 = {x: dict(zip(pts3, rd(8))) for x in pts3}
    nu = {x: {y: (k0[x][y] + k0[rot3(x)][rot3(y)] + k0[rot3(rot3(x))][rot3(rot3(y))]) / 3 for y in pts3} for x in pts3}
    ok &= all(close(nu[rot3(x)][rot3(y)], nu[x][y]) for x in pts3 for y in pts3)
    ok &= all(close(mu[rot3(x)] * nu[rot3(x)][rot3(y)], mu[x] * nu[x][y]) for x in pts3 for y in pts3)
check("ch9 compound source of an invariant state and an equivariant kernel is invariant (cyclic model of length 3, 20 random)", ok)
mu3 = {x: 1 / 8 for x in pts3}
om = {(x, y): mu3[x] * (0.5 if y in ((0, 0, 0), (1, 1, 1)) else 0.0) for x in pts3 for y in pts3}
inv_set = sum(v_ for (x, y), v_ in om.items() if y == (0, 0, 0))
mi_gap = H([1 / 8] * 8) + H([0.5, 0.5]) - H([v_ for v_ in om.values() if v_ > 0])
check("ch9 the constant random channel: an invariant set of probability 1/2 in the compound source, and zero information",
      close(inv_set, 0.5) and close(mi_gap, 0.0))
Zc = [[1.0, 0.0], [0.1, 0.9]]
bec = lambda e: [[1 - e, e, 0.0], [0.0, e, 1 - e]]
cZ, pZ = capacity(Zc)
check("ch9 capacities: BSC(0.1)=0.531, BEC(0.25)=0.75, Z(0.1)=log(1+0.9*0.1^(1/9))=0.763",
      close(capacity(bsc(0.1))[0], 1 - hb(0.1), 1e-6) and close(1 - hb(0.1), 0.531, 1e-3) and close(capacity(bec(0.25))[0], 0.75, 1e-6)
      and close(cZ, log2(1 + 0.9 * 0.1 ** (1 / 9)), 1e-6) and close(cZ, 0.7628, 1e-4))
sZ = 1 / (1 + 2 ** (hb(0.1) / 0.9))
check("sol 9.1 the optimal input of the Z-channel: q(1-delta) = 1/(1+2^(h(delta)/(1-delta)))", close(pZ[1] * 0.9, sZ, 1e-4))
c2 = capacity(compose(bsc(0.1), bsc(0.1)))[0]
check("ch9 composition: BSC(0.1) twice is BSC(0.18) with capacity 0.320 <= 0.531",
      mclose(compose(bsc(0.1), bsc(0.1)), bsc(0.18)) and close(c2, 0.3199, 1e-4))
cb, ce = capacity(bsc(0.1))[0], capacity(bec(0.25))[0]
cprod = capacity(tensor(bsc(0.1), bec(0.25)))[0]
Wsum = [r + [0.0] * 3 for r in bsc(0.1)] + [[0.0] * 2 + r for r in bec(0.25)]
check("ch9 capacity is additive under tensor and satisfies the sum formula log(2^C + 2^C')",
      close(cprod, cb + ce, 1e-5) and close(capacity(Wsum)[0], log2(2 ** cb + 2 ** ce), 1e-5))
ok = True
for _ in range(20):
    U_, V_ = rstoch(4, 2), rstoch(2, 5)
    ok &= capacity(compose(V_, U_), 600)[0] <= 1 + 1e-9
    p = rd(3)
    W, V = rstoch(3, 4), rstoch(4, 3)
    ok &= MI(p, compose(V, W)) <= min(MI(p, W), MI(push(p, W), V)) + 1e-12
    q = push(p, W)
    Wd = [[p[x] * W[x][y] / q[y] for x in range(3)] for y in range(4)]
    ok &= close(MI(p, W), MI(q, Wd))
idk = [[1.0 if i == j else 0.0 for j in range(5)] for i in range(5)]
check("ch9 C(id_5)=log 5, constant channels have C=0, C <= log r through an r-point set, data processing, dagger symmetry",
      ok and close(capacity(idk, 50)[0], log2(5)) and close(capacity([[0.3, 0.7]] * 3, 50)[0], 0.0))
W = rstoch(2, 3)
nat = True
for x in itertools.product(A2, repeat=3):
    full = {y: math.prod(W[x[i]][y[i]] for i in range(3)) for y in itertools.product(range(3), repeat=3)}
    for y2 in itertools.product(range(3), repeat=2):
        nat &= close(sum(full[y2 + (b,)] for b in range(3)), W[x[0]][y2[0]] * W[x[1]][y2[1]])
check("ch9 a memoryless channel is a natural family: marginalizing the last output of W^(x)3 gives W^(x)2 on the first two inputs", nat)

dl = 0.1
Wisi = []
for x in itertools.product(A2, repeat=5):
    clean = [x[i] ^ x[i + 1] for i in range(4)]
    Wisi.append([math.prod((1 - dl) if y[i] == clean[i] else dl for i in range(4)) for y in itertools.product(A2, repeat=4)])
check("ch9 channel with memory y_n = x_n + x_{n-1} + z_n: uniform inputs give 4(1-h(delta)) bits in 4 uses, the capacity of the BSC",
      close(MI([1 / 32] * 32, Wisi), 4 * (1 - hb(dl))) and capacity(Wisi, 60)[0] <= 4 * (1 - hb(dl)) + 1e-9)

# ---------------------------------------------------------------- Chapter 10: Feinstein's lemma


def feinstein(W, P, M, gam):
    nx, ny = len(W), len(W[0])
    Qo = push(P, W)
    thr = log2(M) + gam
    dens = lambda x, y: (log2(W[x][y] / Qo[y]) if W[x][y] > 0 else -math.inf)
    eps = sum(P[x] * W[x][y] for x in range(nx) for y in range(ny) if dens(x, y) <= thr) + 2 ** (-gam)
    E = [set(y for y in range(ny) if dens(x, y) > thr) for x in range(nx)]
    used, code = set(), []
    while eps < 1:
        for x in range(nx):
            Dx = E[x] - used
            if Dx and sum(W[x][y] for y in Dx) >= 1 - eps - 1e-12:
                code.append((x, Dx))
                used |= Dx
                break
        else:
            break
    return eps, code, E, Qo


def noisy_id(n, noise):
    R_ = rstoch(n, n)
    return [[(1 - noise) * (1.0 if i == j else 0.0) + noise * R_[i][j] for j in range(n)] for i in range(n)]


ok = True
used_inst = 0
okQ = True
okconv = True
saved = None
for _ in range(40):
    W0 = noisy_id(3, random.choice([0.05, 0.1, 0.15]))
    W = tensor(tensor(W0, W0), W0)
    P = [a * b * c for a in rd(3) for b in rd(3) for c in rd(3)]
    M, gam = random.choice([(2, 2.0), (3, 1.5), (4, 1.5), (4, 1.0), (6, 1.0)])
    eps, code, E, Qo = feinstein(W, P, M, gam)
    okQ &= all(sum(Qo[y] for y in E[x]) <= 2 ** (-gam) / M + 1e-12 for x in range(27))
    if eps < 1:
        used_inst += 1
        ok &= len(code) >= M
        ok &= all(sum(W[x][y] for y in D) >= 1 - eps - 1e-12 for x, D in code)
        ok &= all(not (code[i][1] & code[j][1]) for i in range(len(code)) for j in range(i))
        okconv &= log2(len(code)) <= (3 * capacity(W0, 400)[0] + 1) / (1 - eps) + 1e-6
        if saved is None and len(code) >= 4 and eps < 0.7:
            saved = (W, code, eps)
check("ch10 Feinstein's lemma: the greedy construction yields at least M codewords with maximal error eps whenever eps < 1",
      ok and used_inst >= 25, "instances with eps<1: %d of 40" % used_inst)
check("ch10 the counting estimate Q(E_x) <= 2^-gamma / M, and the weak converse log M <= (C+1)/(1-eps) for the codes found", okQ and okconv)


def fein_bsc(n, d=0.11, R=0.25):
    C = 1 - hb(d)
    g = n * (C - R) / 2
    thr = n * R + g
    pr_ = sum(math.exp(math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1) + k * math.log(d) + (n - k) * math.log(1 - d))
              for k in range(n + 1) if n + k * log2(d) + (n - k) * log2(1 - d) <= thr)
    return pr_ + 2 ** (-g)


fb = [fein_bsc(n) for n in (200, 1000, 5000)]
check("ch10 Feinstein bound for BSC(0.11) at rate 1/4: 0.032, 3e-5, 2e-19 at n = 200, 1000, 5000",
      close(fb[0], 0.0318, 1e-3) and 2.5e-5 < fb[1] < 3.5e-5 and 1e-19 < fb[2] < 3e-19, ["%.3g" % x for x in fb])
i0 = 7 + 7 * log2(0.99)
i1 = 7 + log2(0.01) + 6 * log2(0.99)
check("sol 10.2 length 7, delta=0.01, M=16: Feinstein guarantees 0.202; the Hamming code achieves 0.0020",
      close(i0, 6.898, 1e-3) and close(i1, 0.269, 1e-3) and close((1 - 0.99 ** 7) + 2 ** (-(i0 - 4)), 0.202, 1e-3)
      and close(1 - 0.99 ** 7 - 7 * 0.01 * 0.99 ** 6, 0.00203, 1e-5))


def Mstar(W, eps):
    nx, ny = len(W), len(W[0])
    best = 1
    for M in range(2, ny + 1):
        found = False
        for lab in itertools.product(range(M + 1), repeat=ny):
            if all(max(sum(W[x][y] for y in range(ny) if lab[y] == j + 1) for x in range(nx)) >= 1 - eps - 1e-12 for j in range(M)):
                found = True
                break
        if not found:
            break
        best = M
    return best


id3 = [[1.0 if i == j else 0.0 for j in range(3)] for i in range(3)]
const4 = [[0.25] * 4] * 2
check("sol 10.3 exact eps-ranks: M*(id_3, eps)=3; for a constant channel with uniform output on 4 points, 1, 2, 4 at eps = 0.4, 0.5, 0.75",
      Mstar(id3, 0.3) == 3 and Mstar(id3, 0.0) == 3 and [Mstar(const4, e) for e in (0.4, 0.5, 0.75)] == [1, 2, 4])
ok = True
for k in range(1, 8):
    for m in range(k, 14):
        fail = 1 - math.prod(1 - 2.0 ** (i - m) for i in range(k))
        ok &= fail <= 2.0 ** (k - m) + 1e-12
check("sol 10.5 a random k x m binary matrix has rank < k with probability at most 2^(k-m)", ok)

# ---------------------------------------------------------------- Chapter 11: Shannon's theorems


def huffman_lengths(ps):
    hp = [(p, i, [i]) for i, p in enumerate(ps)]
    heapq.heapify(hp)
    L = [0] * len(ps)
    c = len(ps)
    while len(hp) > 1:
        a = heapq.heappop(hp)
        b = heapq.heappop(hp)
        for i in a[2] + b[2]:
            L[i] += 1
        heapq.heappush(hp, (a[0] + b[0], c, a[2] + b[2]))
        c += 1
    return L


ok = True
for _ in range(100):
    p = rd(random.randint(2, 9))
    L = huffman_lengths(p)
    EL = sum(a * b for a, b in zip(p, L))
    ok &= close(sum(2.0 ** -l for l in L), 1.0) and H(p) - 1e-12 <= EL < H(p) + 1
    ok &= EL <= sum(a * math.ceil(-log2(a)) for a in p) + 1e-12
check("ch11 Kraft's inequality (with equality for Huffman codes) and H <= L* < H+1 on 100 random distributions", ok)
p3 = [0.7, 0.2, 0.1]
blk = lambda k: sum(a * b for a, b in zip(*(lambda ps: (ps, huffman_lengths(ps)))([math.prod(t) for t in itertools.product(p3, repeat=k)]))) / k
rates = [blk(k) for k in (1, 2, 3, 4, 6)]
check("ch11 Huffman coding of blocks from (0.7,0.2,0.1): 1.3, 1.165, 1.175, 1.164, 1.162 bits per letter; H = 1.157",
      close(H(p3), 1.1568, 1e-4) and all(close(a, b, 6e-4) for a, b in zip(rates, [1.3, 1.165, 1.1753, 1.1639, 1.162])), [round(x, 4) for x in rates])
p4 = [0.4, 0.3, 0.2, 0.1]
check("sol 11.1 optimal code for (0.4,0.3,0.2,0.1) has lengths (1,2,3,3) and expected length 1.9 against H = 1.846",
      sorted(huffman_lengths(p4)) == [1, 2, 3, 3] and close(sum(a * b for a, b in zip(p4, huffman_lengths(p4))), 1.9) and close(H(p4), 1.8464, 1e-4))
assert saved is not None
Wc, codec, epsc = saved
src = [2.0 ** -(i + 1) for i in range(11)] + [2.0 ** -11]
eps1 = 1 - sum(src[:4])
eps2 = max(1 - sum(Wc[codec[j][0]][y] for y in codec[j][1]) for j in range(4))
fail = sum(src[j] * (1 - sum(Wc[codec[j][0]][y] for y in codec[j][1])) for j in range(4)) + sum(src[4:])
check("ch11 retractions compose: a compression with error eps1 followed by a code with maximal error eps2 fails with probability <= eps1+eps2",
      eps2 <= epsc + 1e-12 and eps1 <= fail <= eps1 + eps2 + 1e-12 and eps1 + eps2 < 0.6, (round(eps1, 4), round(eps2, 4), round(fail, 4)))
check("ch11 converse: fair bits through BSC(0.1) at n=100 are lost with probability at least 0.459",
      close((1 - (1 - hb(0.1)) - 1 / 100) / 1, 0.459, 1e-3))


def polar(W):
    ny = len(W[0])
    Wm = [[0.5 * sum(W[u1 ^ u2][y1] * W[u2][y2] for u2 in A2) for y1 in range(ny) for y2 in range(ny)] for u1 in A2]
    Wp = [[0.5 * W[u1 ^ u2][y1] * W[u2][y2] for y1 in range(ny) for y2 in range(ny) for u1 in A2] for u2 in A2]
    return Wm, Wp


IU = lambda W: MI([0.5, 0.5], W)
ok = True
for W in [bsc(0.11), bec(0.3), rstoch(2, 3), rstoch(2, 4), [[1.0, 0.0], [0.2, 0.8]]]:
    Wm, Wp = polar(W)
    a = hinv(1 - IU(W))
    ok &= close(IU(Wm) + IU(Wp), 2 * IU(W)) and IU(Wm) <= IU(W) + 1e-12 <= IU(Wp) + 2e-12
    ok &= IU(Wm) <= 1 - hb(2 * a * (1 - a)) + 1e-9
Wm, Wp = polar(bec(0.3))
check("ch11 polar transform: I(W-)+I(W+)=2I(W), I(W-)<=I(W)<=I(W+), and the Mrs Gerber bound on I(W-); for BEC(e): 1-(2e-e^2), 1-e^2",
      ok and close(IU(Wm), 1 - (0.6 - 0.09)) and close(IU(Wp), 1 - 0.09)
      and close(IU(polar(bsc(0.11))[0]), 1 - hb(2 * 0.11 * 0.89)))
z = [0.5]
sq = []
fr = {}
for n in range(1, 19):
    prev = z
    z = [w for x in z for w in (2 * x - x * x, x * x)]
    sq.append(sum((z[2 * i + j] - prev[i]) ** 2 for i in range(len(prev)) for j in (0, 1)) / len(z))
    if n in (6, 10, 14, 18):
        fr[n] = (sum(1 for x in z if x < 0.01) / len(z), sum(z) / len(z), sum(math.sqrt(x * (1 - x)) for x in z) / len(z))
check("ch11 BEC(1/2) polarization: fraction of good channels 0.234, 0.373, 0.441, 0.473 at n=6,10,14,18; the mean stays 1/2",
      all(close(fr[n][0], v_, 6e-4) for n, v_ in ((6, 0.2344), (10, 0.373), (14, 0.4412), (18, 0.4725))) and all(close(fr[n][1], 0.5) for n in fr))
check("sol 11.5 the mean of sqrt(e(1-e)) contracts by sqrt(3)/2 per step; squared increments of the martingale sum to at most 1",
      all(fr[n][2] <= (math.sqrt(3) / 2) ** n * 0.5 + 1e-12 for n in fr) and sum(sq) <= 1.0
      and close(sum(sq), sum((x - 0.5) ** 2 for x in z) / len(z), 1e-9))
check("sol 11.4 log of the factorization rank bounds capacity (BSC: 1 > 0.531); log min(|X|,|Y|) is not monotone under composition",
      1 > 1 - hb(0.1) and log2(min(3, 3)) > min(log2(min(3, 1)), log2(min(1, 3))))

# ---------------------------------------------------------------- Chapter 12: rates and spectra
adj5 = lambda i, j: (i - j) % 5 in (1, 4)
conf = lambda u, v: u != v and all(a == b or adj5(a, b) for a, b in zip(u, v))
V2 = list(itertools.product(range(5), repeat=2))
adjm = [sum(1 << j for j, v in enumerate(V2) if conf(u, v)) for u in V2]


def alpha_num(adj):
    best = 0

    def rec(cands, size):
        nonlocal best
        if size + bin(cands).count("1") <= best:
            return
        if cands == 0:
            best = size
            return
        v = max((i for i in range(len(adj)) if cands >> i & 1), key=lambda i: bin(adj[i] & cands).count("1"))
        rec(cands & ~adj[v] & ~(1 << v), size + 1)
        rec(cands & ~(1 << v), size)
    rec((1 << len(adj)) - 1, 0)
    return best


a1 = alpha_num([sum(1 << j for j in range(5) if adj5(i, j)) for i in range(5)])
words = [(i, 2 * i % 5) for i in range(5)]
pent = [[0.5 if (y - x) % 5 in (0, 1) else 0.0 for y in range(5)] for x in range(5)]
check("ch12 pentagon: alpha(C5)=2, alpha(C5 x C5)=5 with the words (i,2i); capacity log5-1=1.322 > (1/2)log 5=1.161",
      a1 == 2 and alpha_num(adjm) == 5 and all(not conf(u, v) for u in words for v in words if u != v)
      and close(capacity(pent, 200)[0], log2(5) - 1, 1e-9) and close(0.5 * log2(5), 1.161, 1e-3))
ct2 = 1 / math.sqrt(5)
uv = [(math.sqrt(1 - ct2) * math.cos(2 * math.pi * k / 5), math.sqrt(1 - ct2) * math.sin(2 * math.pi * k / 5), math.sqrt(ct2)) for k in range(5)]
dot = lambda a, b: sum(x * y for x, y in zip(a, b))
check("ch12 Lovasz's umbrella: an orthonormal representation of C5 with 1/(c.u)^2 = sqrt(5)",
      all(abs(dot(uv[i], uv[(i + 2) % 5])) < 1e-12 for i in range(5)) and all(close(dot(u, u), 1.0) for u in uv) and close(1 / uv[0][2] ** 2, math.sqrt(5)))
ok = True
for _ in range(100):
    n = 5
    perms = [random.sample(range(n), n) for _ in range(4)]
    lam = rd(4)
    D = [[sum(lam[k] for k in range(4) if perms[k][x] == y) for y in range(n)] for x in range(n)]
    p = rd(n)
    q = push(p, D)
    ok &= all(renyi(q, a) >= renyi(p, a) - 1e-12 for a in (0, 0.3, 0.7, 1, 2, 5, math.inf))
check("sol 12.2 every Renyi entropy is monotone under doubly stochastic maps (100 random)", ok)
pe, Re = 0.1, 0.7
lo_, hi_ = pe, 0.5
for _ in range(80):
    m_ = (lo_ + hi_) / 2
    lo_, hi_ = (m_, hi_) if hb(m_) < Re else (lo_, m_)
tau = lo_
Dtau = KL([1 - tau, tau], [1 - pe, pe])
best = max(rho_ * (Re - renyi([1 - pe, pe], 1 / (1 + rho_))) for rho_ in [i / 1000 for i in range(1, 5000)])
check("sol 12.3 source-coding exponent at R=0.7 for (0.9,0.1): the Renyi formula and the divergence formula both give 0.0521",
      close(tau, 0.1893, 1e-4) and close(Dtau, 0.0521, 1e-4) and close(best, Dtau, 1e-5))
phi = (1 + math.sqrt(5)) / 2
fib = [2, 3]
while len(fib) < 30:
    fib.append(fib[-1] + fib[-2])
cnt12 = sum(1 for s in itertools.product(A2, repeat=12) if all(not (s[i] and s[i + 1]) for i in range(11)))
ga = max((hb(a) / (1 + a), a) for a in [i / 100000 for i in range(1, 100000)])
check("ch12 golden mean shift: Fibonacci counts, capacity log phi = 0.694, attained by the Markov chain with q_01 = 0.382",
      cnt12 == fib[11] and close(log2(fib[29]) / 30, log2(phi), 0.03) and close(ga[0], log2(phi), 1e-9) and close(ga[1], (3 - math.sqrt(5)) / 2, 1e-4)
      and close(log2(phi), 0.6942, 1e-4))
check("sol 12.5 entropies of the Bernoulli shifts: 1, log 3, and 2 for both of Meshalkin's",
      close(H([.5, .5]), 1) and close(H([1 / 3] * 3), log2(3)) and close(H([.25] * 4), 2) and close(H([.5] + [.125] * 4), 2))

# ---------------------------------------------------------------- summary
n_pass = sum(1 for _, okk in results if okk)
print("\n%d checks, %d passed, %d failed" % (len(results), n_pass, len(results) - n_pass))
sys.exit(0 if n_pass == len(results) else 1)
