# Independent check: exact null rejection probabilities by forward recursion over head counts,
# with the one-sided exact binomial p-value and the LR boundary computed separately.
from fractions import Fraction as F
from math import comb
def pval(n, k): return F(sum(comb(n, j) for j in range(k, n + 1)), 2 ** n)
def run(rule, H, p=F(1, 2)):
    dist = {0: F(1)}; rej = F(0); stop = F(0)
    for n in range(1, H + 1):
        new = {}
        for k, w in dist.items():
            new[k] = new.get(k, 0) + w * (1 - p); new[k + 1] = new.get(k + 1, 0) + w * p
        dist = {}
        for k, w in new.items():
            if rule == "lr": hit = F(3) ** k / F(2) ** n >= 20
            elif rule == "peek": hit = pval(n, k) <= F(1, 20)
            else: hit = n == H and pval(n, k) <= F(1, 20)
            if hit: rej += w; stop += n * w
            else: dist[k] = w
    return rej, stop + H * sum(dist.values())
for H in (100, 200):
    for rule in ("fixed", "peek", "lr"):
        r, e = run(rule, H)
        print(H, rule, float(r), float(e))
print("Ville bound for the LR rule: P(sup ratio >= 20) <= 1/20 = 0.05 for every horizon")