"""Chapter 3, section 3.7 and exercise 3.2: what zero failures can and cannot show. n bug-containing cases are drawn independently from a specified error distribution, and the checker detects every one. If each case is missed independently with probability q, the chance that all n are detected is (1 - q)^n. The one-sided upper confidence bound at level 1 - alpha is the q at which that chance equals alpha: q_upper = 1 - alpha^(1/n). Standard library only. """ import math def upper(n, alpha=0.05): """One-sided upper confidence bound on the miss rate after n of n detections.""" if n == 0: return 1.0 # no bug-containing case: the data say nothing about the miss rate return 1 - alpha ** (1 / n) print("chance that a checker with miss rate q detects all 100 cases, (1-q)^100:") for q in (0.01, 0.02, upper(100), 0.03, 0.05): print(f" q = {q:.4%}: {(1 - q) ** 100:.4f}") print(f"\n0.05^(1/100) = {0.05 ** (1 / 100):.6f}; upper bound n=100: {upper(100):.4%}") print(f"ln(0.99) = {math.log(0.99):.5f} (close to -0.01)") print(f"ln(0.05) = {math.log(0.05):.4f}; e^-3 = {math.exp(-3):.4f}") print("\nexact bound vs 3/n:") for n in (0, 1, 5, 10, 30, 100, 300, 1000, 3000): approx = "n/a" if n == 0 else f"{3 / n:.4%}" print(f" n = {n:4d}: exact {upper(n):.4%}, 3/n {approx}") print(f"\n100 samples, 5 contain bugs, all 5 detected: bound = {upper(5):.4%}") print(f"100 samples, none contains a bug: bound = {upper(0):.0%} (no evidence)") print(f"\n99% one-sided bound, n = 100: {upper(100, 0.01):.4%} (ln(100) = {math.log(100):.3f}, so about 4.6/n)") for target in (0.01, 0.001, 0.0001): n_needed = math.ceil(math.log(0.05) / math.log(1 - target)) print(f"all-detected cases needed for a 95% bound <= {target:.2%}: n = {n_needed} (3/target = {3 / target:.0f})") # standard-error formula at zero failures p_hat, n = 0.0, 100 print(f"\nsqrt(p(1-p)/n) at p = 0: {math.sqrt(p_hat * (1 - p_hat) / n)}")