"""Wasserman (2004), Chapter 1: Probability.

Code for Chapter 1 of L. Wasserman, All of Statistics: A Concise Course in Statistical Inference
(Springer, 2004), pp. 3-17, written from scratch with numpy and matplotlib, to be read next to the
lecture notes (../ch01-probability.html). The chapter is about exact reasoning with events, so most
of the functions compute probabilities exactly, with Python's Fraction type, by listing a finite
sample space; simulations then show the same numbers as long-run frequencies.

* Finite sample spaces (Sections 1.2-1.4): FiniteSpace (outcomes with exact probabilities, events as
  sets), prob(), inclusion_exclusion() (the general form of Lemma 1.6), matching_probability() (the
  matching problem, a classical use of inclusion-exclusion), committee counts.
* Independence (Section 1.5): independence_table() lists P(intersection) against the product of the
  probabilities for every sub-collection of a family of events, and classify_independence() says
  whether a family is mutually independent, pairwise independent only, or neither.
  bernstein_events() is the standard example of events that are pairwise but not mutually
  independent; triple_product_events() satisfies P(ABC) = P(A)P(B)P(C) without pairwise independence.
* Conditional probability and Bayes' theorem (Sections 1.6-1.7): bayes() (Theorem 1.17 for any
  finite partition), positive_predictive_value() (Example 1.13 as a function of the base rate),
  basketball() (Example 1.11, by the series and by first-step analysis).
* The Monty Hall problem (Exercise 1.10): monty_exact() enumerates the sample space of the book,
  pairs (prize door, opened door), for the standard host, a host who prefers one door, and a host who
  opens a door at random.
* The exercises: ex_1_5, ex_1_13, ex_1_15, ex_1_19, ex_1_20 (exact answers) and the computer
  experiments of Exercises 1.21-1.23.
* The browser demonstrations draw their random numbers with the seeded generator of
  courses/demo-kit.js (mulberry32); JSRandom and js_uniforms reproduce it exactly, and
  bayes_demo_sim, indep_demo_sim, freq_demo and monty_demo_sim are the simulations of the four demos.

Figures. Chapter 1 of the book has no figures, so nothing is skipped. The supplementary figures
below are computed for the examples and computer experiments of the chapter:
* 1.S1: Exercise 1.21, the proportion of heads against the number of tosses, p = 0.3 and p = 0.03.
* 1.S2: Exercise 1.22, the average of repeated binomial counts against np, n = 10, 100, 1000.
* 1.S3: Exercise 1.23, simulated P(A), P(B), P(AB) and P(A)P(B) for an independent and a dependent
  pair of events on a die.
* 1.S4: the continuity of probability (Theorem 1.8): an increasing and a decreasing sequence of
  events, exact probabilities against simulated frequencies.
* 1.S5: Example 1.13, the probability of disease given a positive test against the base rate.
* 1.S6: the Monty Hall problem (Exercise 1.10), running win frequencies of staying and switching
  for three hosts (the second
  host opens door 2 with probability 0.8 when he has a choice; games where he opens door 2).
* 1.S7: pairwise against mutual independence: simulated and exact probabilities of the
  intersections for Bernstein's example.
* 1.S8: Exercise 1.20, posterior probabilities of the five coins after one head, after two heads,
  and after a first head on the fourth toss.
Run `python3 ch01_probability.py --list`, `python3 ch01_probability.py` (all figures, a few seconds)
or `python3 ch01_probability.py --fig 1.S4`. Files go to ../img/ch01/.
"""
import itertools
import math
import os
from fractions import Fraction

import numpy as np

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig

CH = 1
HERE = os.path.dirname(os.path.abspath(__file__))
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    """32-bit multiplication with wrap-around (JavaScript's Math.imul, unsigned result)."""
    return (a * b) & M32


class JSRandom:
    """DK.rng(seed) of courses/demo-kit.js, one draw at a time: u() is the mulberry32 generator, a
    uniform number in [0, 1) with 32 random bits."""

    def __init__(self, seed):
        self.a = int(seed) & M32

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0


def js_uniforms(seed, n, start=0):
    """Draws number start+1, ..., start+n of DK.rng(seed).u(), vectorised. mulberry32 adds a constant
    to its state at every call, so draw j is a fixed hash of seed + j * 0x6D2B79F5 (mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


# =========================================================================== finite sample spaces
class FiniteSpace:
    """A finite sample space with exact probabilities (Section 1.4).

    outcomes: a list of hashable outcomes; weights: their probabilities (Fractions or integers,
    normalised here), or None for the uniform distribution P(A) = |A| / |Omega|."""

    def __init__(self, outcomes, weights=None):
        self.outcomes = list(outcomes)
        if weights is None:
            weights = [1] * len(self.outcomes)
        w = [Fraction(x) for x in weights]
        tot = sum(w)
        self.p = {o: x / tot for o, x in zip(self.outcomes, w)}

    def event(self, pred):
        """The event {omega : pred(omega)} as a frozenset."""
        return frozenset(o for o in self.outcomes if pred(o))

    def prob(self, A):
        return sum((self.p[o] for o in A), Fraction(0))

    def cond(self, A, B):
        """P(A | B) = P(AB) / P(B), Definition 1.12 (requires P(B) > 0)."""
        pb = self.prob(B)
        if pb == 0:
            raise ZeroDivisionError("P(B) = 0: P(A|B) is not defined")
        return self.prob(frozenset(A) & frozenset(B)) / pb

    @property
    def omega(self):
        return frozenset(self.outcomes)


def two_dice():
    return FiniteSpace([(i, j) for i in range(1, 7) for j in range(1, 7)])


def coin_space(n, p=Fraction(1, 2)):
    """n independent tosses of a coin with P(H) = p: outcomes are strings such as 'HTH'."""
    outs = ["".join(s) for s in itertools.product("HT", repeat=n)]
    w = [p ** s.count("H") * (1 - p) ** s.count("T") for s in outs]
    return FiniteSpace(outs, w)


def inclusion_exclusion(space, events):
    """P(A_1 u ... u A_n) by inclusion-exclusion, sum over nonempty J of (-1)^(|J|+1) P(cap_J A_j)."""
    n = len(events)
    tot = Fraction(0)
    for r in range(1, n + 1):
        for J in itertools.combinations(range(n), r):
            inter = frozenset.intersection(*[frozenset(events[j]) for j in J])
            tot += (-1) ** (r + 1) * space.prob(inter)
    return tot


def bonferroni_partial(space, events, r_max):
    """The partial sums S_1 - S_2 + ... +- S_r of inclusion-exclusion, r = 1..r_max (Bonferroni bounds)."""
    n = len(events)
    out, tot = [], Fraction(0)
    for r in range(1, r_max + 1):
        s = Fraction(0)
        for J in itertools.combinations(range(n), r):
            s += space.prob(frozenset.intersection(*[frozenset(events[j]) for j in J]))
        tot += (-1) ** (r + 1) * s
        out.append(tot)
    return out


def matching_probability(n):
    """P(a random permutation of n letters has at least one fixed point) = sum_{k=1}^n (-1)^(k+1)/k!,
    the inclusion-exclusion answer to the matching problem; tends to 1 - 1/e."""
    return sum(Fraction((-1) ** (k + 1), math.factorial(k)) for k in range(1, n + 1))


def matching_bruteforce(n):
    perms = list(itertools.permutations(range(n)))
    hit = sum(any(p[i] == i for i in range(n)) for p in perms)
    return Fraction(hit, len(perms))


# =========================================================================== independence
def independence_table(space, events, names=None):
    """For every sub-collection J (|J| >= 2) of the events: (names, P(cap_J), prod_J P)."""
    names = names or [chr(65 + i) for i in range(len(events))]
    rows = []
    for r in range(2, len(events) + 1):
        for J in itertools.combinations(range(len(events)), r):
            inter = frozenset.intersection(*[frozenset(events[j]) for j in J])
            prod = Fraction(1)
            for j in J:
                prod *= space.prob(events[j])
            rows.append(("".join(names[j] for j in J), space.prob(inter), prod))
    return rows


def classify_independence(space, events):
    """'mutual' if P(cap_J) = prod_J P for every J (Definition 1.9), 'pairwise' if only every pair
    satisfies it, otherwise 'dependent'."""
    rows = independence_table(space, events)
    pair_ok = all(a == b for nm, a, b in rows if len(nm) == 2)
    all_ok = all(a == b for nm, a, b in rows)
    return "mutual" if all_ok else ("pairwise" if pair_ok else "dependent")


def bernstein_events():
    """Two fair coins: A = heads on toss 1, B = heads on toss 2, C = the two tosses agree.
    Every pair is independent, but P(ABC) = 1/4 is not P(A)P(B)P(C) = 1/8."""
    S = coin_space(2)
    A = S.event(lambda w: w[0] == "H")
    B = S.event(lambda w: w[1] == "H")
    C = S.event(lambda w: w[0] == w[1])
    return S, [A, B, C]


def triple_product_events():
    """Omega = {1,...,8} uniform; A = {1,2,3,4}, B = {1,2,5,6}, C = {1,3,7,8}:
    P(ABC) = 1/8 = P(A)P(B)P(C), yet P(BC) = 1/8 differs from P(B)P(C) = 1/4."""
    S = FiniteSpace(range(1, 9))
    return S, [frozenset({1, 2, 3, 4}), frozenset({1, 2, 5, 6}), frozenset({1, 3, 7, 8})]


# =========================================================================== Bayes' theorem
def bayes(prior, lik):
    """Theorem 1.17 for a finite partition A_1..A_k: returns (posterior P(A_i|B), P(B)).
    prior[i] = P(A_i) (summing to 1) and lik[i] = P(B|A_i). Works with floats or Fractions."""
    joint = [a * b for a, b in zip(prior, lik)]
    pb = sum(joint)
    return [j / pb for j in joint], pb


def positive_predictive_value(prev, sens, spec, k=1):
    """P(D | k positive tests), the tests conditionally independent given the disease status:
    prev s^k / (prev s^k + (1 - prev)(1 - c)^k), with s = P(+|D) and c = P(-|D^c)."""
    a = prev * sens ** k
    b = (1 - prev) * (1 - spec) ** k
    return a / (a + b)


def example_1_13():
    """The table of Example 1.13 and the three conditional probabilities computed from it."""
    t = {("+", "D"): Fraction(9, 1000), ("+", "Dc"): Fraction(99, 1000),
         ("-", "D"): Fraction(1, 1000), ("-", "Dc"): Fraction(891, 1000)}
    pD = t["+", "D"] + t["-", "D"]
    pDc = t["+", "Dc"] + t["-", "Dc"]
    sens = t["+", "D"] / pD
    spec = t["-", "Dc"] / pDc
    ppv = t["+", "D"] / (t["+", "D"] + t["+", "Dc"])
    return dict(table=t, prev=pD, sens=sens, spec=spec, ppv=ppv)


def example_1_19():
    """Example 1.19 (spam), with the corrected likelihood P(B|A3) = .01 (the book prints P(B|A1))."""
    prior = [Fraction(7, 10), Fraction(2, 10), Fraction(1, 10)]
    lik = [Fraction(9, 10), Fraction(1, 100), Fraction(1, 100)]
    return bayes(prior, lik)


def basketball(p1=Fraction(1, 3), p2=Fraction(1, 4)):
    """Example 1.11: P(person 1 succeeds first) = p1 / (1 - (1-p1)(1-p2)), by summing the geometric
    series of the book and, equivalently, by first-step analysis x = p1 + (1-p1)(1-p2) x."""
    r = (1 - p1) * (1 - p2)
    series = p1 / (1 - r)
    # first-step analysis: solve x = p1 + r x
    first_step = p1 / (1 - r)
    return series, first_step


def basketball_sim(n, rng, p1=1 / 3, p2=1 / 4):
    """Monte Carlo for Example 1.11: the proportion of n games won by person 1."""
    wins = 0
    for _ in range(n):
        while True:
            if rng.random() < p1:
                wins += 1
                break
            if rng.random() < p2:
                break
    return wins / n


# =========================================================================== Monty Hall
def monty_exact(rule="standard", q=Fraction(1, 2), d=3):
    """Exact Monty Hall probabilities when the player always picks door 1 (Exercise 1.10).

    The sample space is that of the book, pairs (prize door, door left closed by the host) with
    their probabilities (for d = 3 the door left closed determines the door opened).
    rule = 'standard': the host knows where the prize is, opens all other doors but one without the
    prize, choosing at random when the prize is behind door 1;
    'biased' (d = 3 only): as 'standard' but, when the prize is behind door 1, he opens door 2 with
    probability q and door 3 with probability 1 - q;
    'ignorant': he leaves one of doors 2..d closed at random and opens the others; games in which he
    reveals the prize are discarded (we condition on the opened doors being empty).
    Returns dict with P(win | stay), P(win | switch) and, for d = 3, the same given each opened door."""
    q = Fraction(q)
    pts = {}   # (prize, closed) -> probability
    for prize in range(1, d + 1):
        for c in range(2, d + 1):
            if rule == "standard":
                pr = Fraction(1, d - 1) if prize == 1 else Fraction(int(c == prize))
            elif rule == "biased":
                assert d == 3
                if prize == 1:
                    pr = q if c == 3 else 1 - q          # leaving 3 closed means opening door 2
                else:
                    pr = Fraction(int(c == prize))
            elif rule == "ignorant":
                pr = Fraction(1, d - 1)
            else:
                raise ValueError(rule)
            if pr:
                pts[prize, c] = Fraction(1, d) * pr
    if rule == "ignorant":   # condition on: no opened door shows the prize
        pts = {k: v for k, v in pts.items() if k[0] == 1 or k[0] == k[1]}
    tot = sum(pts.values())
    stay = sum(v for (prize, c), v in pts.items() if prize == 1) / tot
    switch = sum(v for (prize, c), v in pts.items() if prize == c) / tot
    out = dict(stay=stay, switch=switch, space=pts)
    if d == 3:
        for opened in (2, 3):
            c = 5 - opened
            sub = {k: v for k, v in pts.items() if k[1] == c}
            s = sum(sub.values())
            if s:
                out["switch_given_open%d" % opened] = sum(v for (pz, cc), v in sub.items() if pz == cc) / s
    return out


def monty_demo_sim(n, seed, rule="standard", d=3, q=0.5):
    """The Monty Hall demo: n games with DK.rng(seed), two draws per game (prize door, host's
    choice). Returns per-game arrays valid (game counted), stay_win, switch_win and opened (d = 3:
    the door the host opened)."""
    u = js_uniforms(seed, 2 * n)
    u1, u2 = u[0::2], u[1::2]
    prize = 1 + np.floor(u1 * d).astype(int)
    if rule == "biased":
        # prize behind 1: open door 2 with probability q (leave 3 closed), else open 3 (leave 2 closed)
        closed = np.where(prize == 1, np.where(u2 < q, 3, 2), prize)
        valid = np.ones(n, bool)
    else:
        rand_closed = 2 + np.floor(u2 * (d - 1)).astype(int)
        if rule == "standard":
            closed = np.where(prize == 1, rand_closed, prize)
            valid = np.ones(n, bool)
        else:   # ignorant
            closed = rand_closed
            valid = (prize == 1) | (prize == closed)
    opened = np.where(closed == 2, 3, 2) if d == 3 else np.zeros(n, int)
    return dict(valid=valid, stay=(prize == 1), switch=(prize == closed), opened=opened)


def monty_demo_summary(n, seed, rule="standard", d=3, q=0.5):
    s = monty_demo_sim(n, seed, rule, d, q)
    v = s["valid"]
    out = dict(games=int(v.sum()), stay=int((s["stay"] & v).sum()), switch=int((s["switch"] & v).sum()))
    if d == 3:
        for o in (2, 3):
            m = v & (s["opened"] == o)
            out["open%d" % o] = int(m.sum())
            out["switch_open%d" % o] = int((s["switch"] & m).sum())
    return out


# =========================================================================== demo simulations
def bayes_demo_sim(prior, lik, n, seed):
    """The Bayes demo: n individuals drawn with DK.rng(seed); for each, a first draw picks the class
    (the first i with u < P(A_1) + ... + P(A_i)) and a second draw decides B (v < P(B|A_i)).
    Returns the classes and the indicator of B."""
    u = js_uniforms(seed, 2 * n)
    u1, u2 = u[0::2], u[1::2]
    cum = np.cumsum(np.asarray(prior, float))   # sequential sums, as in JavaScript
    k = len(prior)
    h = np.minimum(np.searchsorted(cum, u1, side="right"), k - 1)
    b = u2 < np.asarray(lik, float)[h]
    return h, b


def bayes_demo_summary(prior, lik, n, seed):
    h, b = bayes_demo_sim(prior, lik, n, seed)
    k = len(prior)
    return dict(nB=int(b.sum()), counts=[int(((h == i) & b).sum()) for i in range(k)],
                classes=[int((h == i).sum()) for i in range(k)])


def indep_demo_sim(m, events, n, seed):
    """The independence demo: n outcomes drawn uniformly from {0, ..., m-1} with DK.rng(seed),
    outcome = floor(m u). events: list of sets of outcome indices. Returns the indicators (n x k)."""
    w = np.floor(js_uniforms(seed, n) * m).astype(int)
    return np.stack([np.isin(w, sorted(E)) for E in events], 1)


def indep_demo_summary(m, events, n, seed):
    """Relative frequencies of each event and of each intersection of two or more events."""
    I = indep_demo_sim(m, events, n, seed)
    k = I.shape[1]
    out = {"n": n, "single": [float(I[:, j].mean()) for j in range(k)], "inter": {}}
    for r in range(2, k + 1):
        for J in itertools.combinations(range(k), r):
            out["inter"]["".join("ABC"[j] for j in J)] = float(np.all(I[:, J], 1).mean())
    return out


def freq_demo(p, K, N, seed, eps, ns=None):
    """The frequency demo: K independent coin paths of N tosses, path j drawn with DK.rng(seed + j)
    (heads when u < p). Returns the running proportions (K x N) and, at the tosses ns, the fraction of
    paths with |phat_n - p| > eps and the fraction with |phat_k - p| > eps for some k in n..N."""
    U = np.stack([js_uniforms(seed + j, N) for j in range(K)])
    H = (U < p).astype(float)
    P = np.cumsum(H, 1) / np.arange(1, N + 1)
    out = np.abs(P - p) > eps
    later = np.flip(np.cumsum(np.flip(out, 1), 1), 1) > 0      # some k >= n (up to N) outside
    if ns is None:
        ns = np.arange(1, N + 1)
    ns = np.asarray(ns)
    return dict(P=P, now=out[:, ns - 1].mean(0), ever=later[:, ns - 1].mean(0), ns=ns)


def binom_tail_outside(n, p, eps):
    """Exact P(|S_n / n - p| > eps) for S_n ~ Binomial(n, p) (log-space pmf, float)."""
    k = np.arange(n + 1)
    lp = (math.lgamma(n + 1) - np.array([math.lgamma(i + 1) + math.lgamma(n - i + 1) for i in k])
          + (k * math.log(p) if p > 0 else 0) + ((n - k) * math.log(1 - p) if p < 1 else 0))
    pmf = np.exp(lp)
    return float(pmf[np.abs(k / n - p) > eps].sum())


def chebyshev_bound(n, p, eps):
    """p(1-p) / (n eps^2), the Chebyshev bound for P(|S_n/n - p| >= eps), capped at 1."""
    return min(1.0, p * (1 - p) / (n * eps ** 2))


# =========================================================================== the exercises
def ex_1_5(k):
    """Toss a fair coin until the second head: P(exactly k tosses) = (k - 1) / 2^k, k >= 2."""
    return Fraction(k - 1, 2 ** k) if k >= 2 else Fraction(0)


def ex_1_13():
    """Toss until both faces have appeared: P(exactly three tosses) = P(HHT) + P(TTH) = 1/4."""
    return Fraction(1, 8) + Fraction(1, 8)


def ex_1_15():
    """Three children, each blue-eyed with probability 1/4 independently: (a) P(at least two | at
    least one), (b) P(at least two | the youngest)."""
    S = coin_space(3, Fraction(1, 4))   # 'H' = blue eyes; position 0 = youngest
    blue = lambda w: w.count("H")
    a = S.cond(S.event(lambda w: blue(w) >= 2), S.event(lambda w: blue(w) >= 1))
    b = S.cond(S.event(lambda w: blue(w) >= 2), S.event(lambda w: w[0] == "H"))
    return a, b


def ex_1_19():
    """P(Windows | virus) with priors .3, .5, .2 and infection rates .65, .82, .5."""
    post, pb = bayes([Fraction(3, 10), Fraction(5, 10), Fraction(2, 10)],
                     [Fraction(65, 100), Fraction(82, 100), Fraction(50, 100)])
    return post[1], pb


COINS = [Fraction(0), Fraction(1, 4), Fraction(1, 2), Fraction(3, 4), Fraction(1)]


def ex_1_20():
    """The five coins: (a) P(C_i | H), (b) P(H_2 | H_1), (c) P(C_i | first head on toss 4)."""
    prior = [Fraction(1, 5)] * 5
    a, pH = bayes(prior, COINS)
    pHH = sum(Fraction(1, 5) * p * p for p in COINS)
    b = pHH / pH
    c, _ = bayes(prior, [(1 - p) ** 3 * p for p in COINS])
    return a, b, c


def ex_1_21(p, n, rng):
    """Running proportion of heads in n tosses with P(H) = p."""
    x = rng.random(n) < p
    return np.cumsum(x) / np.arange(1, n + 1)


def ex_1_22(p, n, reps, rng):
    """reps binomial(n, p) counts (each the number of heads in n simulated tosses) and their average."""
    X = (rng.random((reps, n)) < p).sum(1)
    return X, X.mean()


def ex_1_23(n, rng, A=(2, 4, 6), B=(1, 2, 3, 4)):
    """Simulated P(A), P(B), P(AB) for n rolls of a fair die."""
    w = rng.integers(1, 7, size=n)
    a, b = np.isin(w, A), np.isin(w, B)
    return a.mean(), b.mean(), (a & b).mean()


# =========================================================================== figures
def _plt():
    import matplotlib.pyplot as plt
    return plt


def fig_1_s1(out_dir=None):
    """Supplementary (Exercise 1.21): running proportion of heads for p = 0.3 and p = 0.03."""
    plt = _plt()
    rng = np.random.default_rng(121)
    n = 1000
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    for ax, p in zip(axes, (0.3, 0.03)):
        k = np.arange(1, n + 1)
        band = 2 * np.sqrt(p * (1 - p) / k)
        ax.fill_between(k, np.maximum(p - band, 0), np.minimum(p + band, 1), color=GREY, alpha=0.18, lw=0,
                        label=r"$p\pm2\sqrt{p(1-p)/n}$")
        for j, col in enumerate((BLUE, ORANGE, GREEN)):
            ax.plot(k, ex_1_21(p, n, rng), color=col, lw=1.1, label="path %d" % (j + 1))
        ax.axhline(p, color=RED, lw=1.2, ls="--")
        ax.set_xscale("log")
        ax.set_xlim(1, n)
        ax.set_ylim(0, min(1, 4 * p + 0.15))
        ax.set_xlabel("number of tosses $n$")
        ax.set_ylabel("proportion of heads")
        ax.set_title("$p = %g$" % p)
    axes[0].legend(frameon=False, fontsize=8, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S1", out_dir)


def fig_1_s2(out_dir=None):
    """Supplementary (Exercise 1.22): the average of repeated binomial counts is close to np."""
    plt = _plt()
    rng = np.random.default_rng(122)
    p, reps = 0.3, 2000
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 2.9))
    for ax, n in zip(axes, (10, 100, 1000)):
        X, m = ex_1_22(p, n, reps, rng)
        cnt = np.bincount(X)
        v = np.nonzero(cnt)[0]
        ax.bar(v, cnt[v], width=1.0 if n < 1000 else 1.6, color=BLUE, alpha=0.75)
        ax.set_ylim(0, 1.3 * cnt.max())
        ax.axvline(n * p, color=RED, lw=1.6, label="$np = %g$" % (n * p))
        ax.axvline(m, color=ORANGE, lw=1.4, ls="--", label=r"average $%.2f$" % m)
        ax.set_title("$n = %d$" % n)
        ax.set_xlabel("number of heads $X$")
        ax.legend(frameon=False, fontsize=7.5, loc="upper left")
    axes[0].set_ylabel("count (2000 repetitions)")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S2", out_dir)


def fig_1_s3(out_dir=None):
    """Supplementary (Exercise 1.23): simulated probabilities on a die, independent and dependent pairs."""
    plt = _plt()
    rng = np.random.default_rng(123)
    N = 20000
    w = rng.integers(1, 7, size=N)
    k = np.arange(1, N + 1)
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.3))
    for ax, (A, B, ttl) in zip(axes, (((2, 4, 6), (1, 2, 3, 4), r"$A=\{2,4,6\},\ B=\{1,2,3,4\}$: independent"),
                                     ((2, 4, 6), (1, 2, 3), r"$A=\{2,4,6\},\ B=\{1,2,3\}$: dependent"))):
        a, b = np.isin(w, A), np.isin(w, B)
        pa, pb, pab = np.cumsum(a) / k, np.cumsum(b) / k, np.cumsum(a & b) / k
        ax.plot(k, pab, color=BLUE, lw=1.3, label=r"$\hat P(AB)$")
        ax.plot(k, pa * pb, color=ORANGE, lw=1.3, label=r"$\hat P(A)\hat P(B)$")
        ax.axhline(len(set(A) & set(B)) / 6, color=BLUE, ls=":", lw=1)
        ax.axhline(len(A) * len(B) / 36, color=ORANGE, ls=":", lw=1)
        ax.set_xscale("log")
        ax.set_xlim(10, N)
        ax.set_ylim(0, 0.6)
        ax.set_xlabel("number of rolls")
        ax.set_title(ttl, fontsize=9.5)
    axes[0].set_ylabel("relative frequency")
    axes[0].legend(frameon=False, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig1-S3", out_dir)


def fig_1_s4(out_dir=None):
    """Supplementary (Theorem 1.8): continuity of probability for an increasing and a decreasing sequence."""
    plt = _plt()
    rng = np.random.default_rng(124)
    R, nmax = 4000, 40
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.3))
    # increasing: A_n = {a six in the first n rolls}, A = {a six eventually}, P(A) = 1
    rolls = rng.integers(1, 7, size=(R, nmax))
    first6 = np.where((rolls == 6).any(1), (rolls == 6).argmax(1) + 1, nmax + 1)
    n = np.arange(1, nmax + 1)
    ax = axes[0]
    ax.plot(n, 1 - (5 / 6) ** n, color=RED, lw=1.6, label=r"$P(A_n)=1-(5/6)^n$")
    ax.plot(n, [(first6 <= m).mean() for m in n], "o", color=BLUE, ms=3, label="simulated (4000 sequences)")
    ax.axhline(1, color=GREY, ls="--", lw=1)
    ax.set_title(r"increasing: $A_n$ = a six in the first $n$ rolls", fontsize=9.5)
    ax.set_xlabel("$n$")
    ax.set_ylabel("probability")
    ax.legend(frameon=False, fontsize=8.5, loc="lower right")
    # decreasing: B_n = {first n tosses all agree with toss 1}, B = cap B_n = {all equal}, P(B) = 0;
    # with Omega = [0, 1) the same limit for B_n = [0, 1/n)
    tosses = rng.random((R, nmax)) < 0.5
    run = np.cumprod(tosses == tosses[:, :1], 1)     # 1 while every toss so far equals the first
    ax = axes[1]
    ax.plot(n, 0.5 ** (n - 1), color=RED, lw=1.6, label=r"$P(B_n)=2^{-(n-1)}$")
    ax.plot(n, run.mean(0), "o", color=BLUE, ms=3, label="simulated")
    ax.plot(n, 1 / n, color=GREEN, lw=1.3, ls="--", label=r"$P([0,1/n))=1/n$, uniform on $[0,1)$")
    ax.axhline(0, color=GREY, ls="--", lw=1)
    ax.set_title(r"decreasing: $B_n$ = the first $n$ tosses agree", fontsize=9.5)
    ax.set_xlabel("$n$")
    ax.legend(frameon=False, fontsize=8.5, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S4", out_dir)


def fig_1_s5(out_dir=None):
    """Supplementary (Example 1.13): P(D | +) against the base rate P(D)."""
    plt = _plt()
    prev = np.logspace(-4, 0, 400)[:-1]
    fig, ax = plt.subplots(figsize=(5.8, 3.6))
    for (s, c, col, lab) in ((0.9, 0.9, BLUE, "sensitivity .9, specificity .9 (Example 1.13)"),
                             (0.99, 0.99, GREEN, "sensitivity .99, specificity .99"),
                             (0.9, 0.999, ORANGE, "sensitivity .9, specificity .999")):
        ax.plot(prev, positive_predictive_value(prev, s, c), color=col, lw=1.6, label=lab)
    ax.plot(prev, positive_predictive_value(prev, 0.9, 0.9, k=2), color=BLUE, lw=1.2, ls="--",
            label="Example 1.13 test, two positives")
    ax.plot(prev, prev, color=GREY, lw=1, ls=":", label="no information: $P(D|+)=P(D)$")
    ax.plot([0.01], [1 / 12], "o", color=RED, ms=6)
    ax.annotate("book: $P(D)=.01$, $P(D|+)=.083$", (0.01, 1 / 12), xytext=(0.0125, 0.012), fontsize=8.5,
                bbox=dict(boxstyle="round,pad=0.15", fc="white", ec="none", alpha=0.9),
                arrowprops=dict(arrowstyle="->", color=RED, lw=0.8))
    ax.set_xscale("log")
    ax.set_xlim(1e-4, 1)
    ax.set_ylim(0, 1.01)
    ax.set_xlabel("base rate $P(D)$")
    ax.set_ylabel("$P(D\\,|\\,+)$")
    ax.legend(frameon=False, fontsize=7.8, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S5", out_dir)


def fig_1_s6(out_dir=None):
    """Supplementary (Exercise 1.10): Monty Hall, running win frequency of staying and switching."""
    plt = _plt()
    n = 3000
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.1), sharey=True)
    for ax, (rule, q, ttl) in zip(axes, (("standard", 0.5, "host knows, picks at random"),
                                         ("biased", 0.8, "host knows, opens door 2 w.p. 0.8 if he can"),
                                         ("ignorant", 0.5, "host opens a door at random"))):
        s = monty_demo_sim(n, 2024, rule=rule, q=q)
        v = s["valid"]
        if rule == "biased":   # condition on the host opening door 2
            v = v & (s["opened"] == 2)
        g = np.cumsum(v)
        ok = g > 0
        k = np.arange(1, n + 1)[ok]
        ax.plot(k, (np.cumsum(s["stay"] & v)[ok] / g[ok]), color=BLUE, lw=1.3, label="stay")
        ax.plot(k, (np.cumsum(s["switch"] & v)[ok] / g[ok]), color=ORANGE, lw=1.3, label="switch")
        ex = monty_exact(rule, Fraction(q).limit_denominator(1000))
        sw = ex["switch_given_open2"] if rule == "biased" else ex["switch"]
        ax.axhline(float(sw), color=ORANGE, ls=":", lw=1)
        ax.axhline(float(1 - sw), color=BLUE, ls=":", lw=1)
        ax.set_xscale("log")
        ax.set_xlim(5, n)
        ax.set_ylim(0, 1.05)
        ax.set_title(ttl + ("\n(games where door 2 is opened)" if rule == "biased" else
                            "\n(games where he reveals the prize dropped)" if rule == "ignorant" else "\n"), fontsize=9)
        ax.set_xlabel("games played")
    axes[0].set_ylabel("proportion of games won")
    axes[0].legend(frameon=False, fontsize=8.5, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S6", out_dir)


def fig_1_s7(out_dir=None):
    """Supplementary: pairwise but not mutual independence (Bernstein's example), simulated and exact."""
    plt = _plt()
    rng = np.random.default_rng(127)
    S, (A, B, C) = bernstein_events()
    n = 5000
    t = rng.random((n, 2)) < 0.5
    a, b = t[:, 0], t[:, 1]
    c = a == b
    labs = ["AB", "AC", "BC", "ABC"]
    sim_int = [np.mean(a & b), np.mean(a & c), np.mean(b & c), np.mean(a & b & c)]
    sim_prod = [a.mean() * b.mean(), a.mean() * c.mean(), b.mean() * c.mean(), a.mean() * b.mean() * c.mean()]
    rows = {nm: (x, y) for nm, x, y in independence_table(S, [A, B, C])}
    fig, ax = plt.subplots(figsize=(5.8, 3.3))
    x = np.arange(4)
    ax.bar(x - 0.2, sim_int, 0.36, color=BLUE, alpha=0.8, label="simulated $P$(intersection)")
    ax.bar(x + 0.2, sim_prod, 0.36, color=ORANGE, alpha=0.8, label="simulated product of the $P$'s")
    for i, nm in enumerate(labs):
        ex_i, ex_p = rows[nm]
        ax.plot([i - 0.38, i - 0.02], [float(ex_i)] * 2, color="k", lw=1.6)
        ax.plot([i + 0.02, i + 0.38], [float(ex_p)] * 2, color="k", lw=1.6)
    ax.set_xticks(x, labs)
    ax.set_ylim(0, 0.36)
    ax.set_ylabel("probability")
    ax.set_title("two fair coins: A = H on toss 1, B = H on toss 2, C = tosses agree", fontsize=9)
    ax.legend(frameon=False, fontsize=8, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig1-S7", out_dir)


def fig_1_s8(out_dir=None):
    """Supplementary (Exercise 1.20): posterior probabilities of the five coins."""
    plt = _plt()
    a, b, c = ex_1_20()
    post2, _ = bayes([Fraction(1, 5)] * 5, [p * p for p in COINS])
    fig, ax = plt.subplots(figsize=(6.0, 3.2))
    x = np.arange(5)
    w = 0.2
    ax.bar(x - 1.5 * w, [0.2] * 5, w, color=GREY, alpha=0.7, label="prior")
    ax.bar(x - 0.5 * w, [float(v) for v in a], w, color=BLUE, label="after one head (a)")
    ax.bar(x + 0.5 * w, [float(v) for v in post2], w, color=GREEN, label="after two heads")
    ax.bar(x + 1.5 * w, [float(v) for v in c], w, color=ORANGE, label="first head on toss 4 (c)")
    ax.set_xticks(x, ["$p=%s$" % str(p) for p in COINS])
    ax.set_ylabel("probability of coin $i$")
    ax.set_ylim(0, 0.8)
    ax.legend(frameon=False, fontsize=8, loc="upper left", ncol=2)
    fig.tight_layout()
    savefig(fig, CH, "fig1-S8", out_dir)


FIGURES = {"1.S1": fig_1_s1, "1.S2": fig_1_s2, "1.S3": fig_1_s3, "1.S4": fig_1_s4,
           "1.S5": fig_1_s5, "1.S6": fig_1_s6, "1.S7": fig_1_s7, "1.S8": fig_1_s8}

if __name__ == "__main__":
    common.run(FIGURES, CH)
