"""Wasserman (2004), Chapter 5: Convergence of Random Variables.

Reproduces the computed figure of Chapter 5 of L. Wasserman, All of Statistics: A Concise Course in
Statistical Inference (Springer, 2004), pp. 71-84, and adds supplementary figures for the results the
chapter states without a picture. Everything is written from scratch with numpy, scipy and matplotlib;
the functions are small and meant to be read next to the lecture notes (../ch05-convergence.html):

* Section 5.2, modes of convergence: normal_shrink_cdf (Example 5.3), the counterexamples of
  Theorem 5.4 (spike_moments for X_n = n^a I(U < n^-b), minus_x for X_n = -X), and spike_sim, a
  path simulation of X_n = n^a I(U_n < n^-b) under two couplings (one uniform U for the whole
  sequence, or independent U_n), which separates almost-sure convergence from convergence in
  probability (Appendix 5.7.1).
* Section 5.3, the weak law: coin_interval_prob (exact binomial probabilities for Example 5.7)
  against Chebyshev's bound and the normal approximation.
* Section 5.4, the central limit theorem and the Berry-Esseen bound (5.4): be_family (mean,
  variance, skewness and third absolute central moment of the gamma, Bernoulli and Poisson laws),
  sum_cdf (the exact cdf of the standardised sum), ks_exact (the exact Kolmogorov distance
  sup_z |P(Z_n <= z) - Phi(z)|) and edgeworth (the one-term Edgeworth expansion, with Esseen's
  sawtooth term for lattice laws).
* Section 5.5, the delta method: delta_exact (exact mean, standard deviation and Kolmogorov
  distance of g(Xbar_n) for exponential, Bernoulli and Poisson samples, against the first-order
  normal approximation of Theorem 5.13, or the second-order chi-square limit when g'(mu) = 0),
  and the Monte Carlo checks of Examples 5.14 and 5.16 and Exercises 5.14 and 5.15.
* Appendix 5.7, the strong law: running means of exponential and Cauchy samples.

JSRandom is the seeded generator of the browser demonstrations (mulberry32 with Box-Muller normals),
so that the Python and browser simulations draw the same numbers.

Figures reproduced: 5.1 (the cdfs of Example 5.3), plus six supplementary figures:
5.S1 (the counterexamples of Theorem 5.4 and the warning example), 5.S2 (Example 5.7: Chebyshev,
the normal approximation and the exact probability), 5.S3 (the exact Berry-Esseen error for skewed
laws, with the bound (5.4) and the Edgeworth correction), 5.S4 (the delta method: Example 5.14,
Exercise 5.14 and the second-order case), 5.S5 (the multivariate central limit theorem and the
multivariate delta method of Example 5.16 and Exercise 5.15), 5.S6 (the strong law, and its failure
for the Cauchy law).
Run `python3 ch05_convergence.py --list`, `python3 ch05_convergence.py` (all figures, under a
minute) or `python3 ch05_convergence.py --fig 5.S3`. Files go to ../img/ch05/.

Figures not reproduced, and why:
* Figure 5.2 is a diagram of the implications between the modes of convergence; nothing in it is
  computed. The lecture notes redraw it, extended by the almost-sure and L1 modes of the appendix.

Settings chosen where the book gives none:
* Figure 5.1: X_n ~ N(0, 1/n) for n = 1, 4, 16, 64 and 256 (the book draws one unlabelled curve).
* Figure 5.S1: epsilon = 0.5; Monte Carlo estimates from 20,000 draws (default_rng(51)); the raster
  shows 30 paths up to n = 10,000 drawn with JSRandom(5101).
* Figure 5.S3: gamma laws with shape 1 (the exponential) and 0.25, Bernoulli(0.5) and (0.1), and
  Poisson(1); n = 1, ..., 1000.
* Figure 5.S5: X_i = (E_1, E_1 + E_2) with E_1, E_2 independent Exp(1), so mu = (1, 2) and
  Sigma = [[1, 1], [1, 2]]; 20,000 Monte Carlo replications (default_rng(55)).
"""
import math
import os

import numpy as np
from scipy import special, stats

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

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


# ======== the demos' generator
class JSRandom:
    """mulberry32 uniforms and Box-Muller normals, bit for bit the generator DK.rng(seed) of the
    browser demonstrations (courses/demo-kit.js)."""

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

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

    def pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self.pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


# ======== Section 5.2
def normal_shrink_cdf(t, n):
    """F_n(t) = P(X_n <= t) for X_n ~ N(0, 1/n) (Example 5.3)."""
    return stats.norm.cdf(np.sqrt(n) * np.asarray(t, float))


def spike_moments(n, a, b):
    """For X_n = n^a I(U < n^-b): P(X_n != 0), E|X_n| and E X_n^2 (Theorem 5.4 and its counterexamples:
    a = 1/2, b = 1 is the book's sqrt(n) I(0 < U < 1/n); a = 2, b = 1 is the warning example)."""
    n = np.asarray(n, float)
    p = n ** (-b)
    return p, n ** a * p, n ** (2 * a) * p


def spike_sup_prob(n, b, coupling, N=None):
    """P(X_m != 0 for some m >= n) for the spike sequence, exactly. With one uniform U for the whole
    sequence the events are nested and the answer is n^-b. With independent U_m it is
    1 - prod_{m >= n} (1 - m^-b): equal to 1 when b <= 1 (second Borel-Cantelli lemma); for b > 1 the
    infinite product is computed to m = 10^6 plus an integral tail. With N given, only m <= N count."""
    if coupling == "common":
        return float(n) ** (-b)
    if N is not None:
        m = np.arange(n, N + 1, dtype=float)
        return float(-np.expm1(np.sum(np.log1p(-m ** (-b)))) if n > 1 else 1.0)
    if b <= 1:
        return 1.0
    if n == 1:
        return 1.0
    M = 10 ** 6
    m = np.arange(n, M + 1, dtype=float)
    s = np.sum(np.log1p(-m ** (-b))) - M ** (1 - b) / (b - 1)   # tail: log(1 - x) ~ -x
    return float(-np.expm1(s))


def spike_sim(a, b, coupling, N, R, eps, seed, kind="spike", keep=25):
    """Simulate R paths n = 1..N of |X_n - X| with JSRandom(seed), exactly as the modes-of-convergence
    demonstration does. kind: 'spike' (X_n = n^a I(U_n < n^-b), limit 0), 'normal' (X_n = Z_n / sqrt(n),
    limit 0) or 'minus' (X_n = -X, limit X). coupling: 'common' (one U or Z per path) or 'indep'.
    Returns last[r] (the last n <= N with |X_n - X| > eps, 0 if none) and, for the first `keep`
    paths, the list of exceedance times."""
    rng = JSRandom(seed)
    last = np.zeros(R, dtype=int)
    raster = []
    for r in range(R):
        ex = []
        if kind == "minus":
            x = rng.norm()
            if 2 * abs(x) > eps:
                ex = list(range(1, N + 1))
        elif coupling == "common":
            v = rng.u() if kind == "spike" else rng.norm()
            for n in range(1, N + 1):
                if kind == "spike":
                    hit = v < n ** (-b) and n ** a > eps
                    if not v < n ** (-b):
                        break
                else:
                    hit = abs(v) / math.sqrt(n) > eps
                    if not hit:
                        break
                if hit:
                    ex.append(n)
        else:
            for n in range(1, N + 1):
                if kind == "spike":
                    if rng.u() < n ** (-b) and n ** a > eps:
                        ex.append(n)
                else:
                    if abs(rng.norm()) / math.sqrt(n) > eps:
                        ex.append(n)
        last[r] = ex[-1] if ex else 0
        if r < keep:
            raster.append(ex)
    return last, raster


def sup_prob_mc(last, n):
    """Monte Carlo P(|X_m - X| > eps for some n <= m <= N) from the last exceedance times."""
    return float(np.mean(np.asarray(last) >= n))


# ======== Section 5.3
def coin_interval_prob(n, p=0.5, lo=0.4, hi=0.6):
    """Exact P(lo <= Xbar_n <= hi) for n tosses of a coin with P(heads) = p (Example 5.7)."""
    n = np.atleast_1d(n)
    k_hi = np.floor(hi * n + 1e-9)
    k_lo = np.ceil(lo * n - 1e-9)
    return stats.binom.cdf(k_hi, n, p) - stats.binom.cdf(k_lo - 1, n, p)


# ======== Section 5.4
def gamma_rho(k):
    """E|X - k|^3 for X ~ Gamma(k, 1), in closed form: E(X-k)^3 = 2k, and the part below k is a
    combination of incomplete gamma functions, E[X^j; X < k] = Gamma(k+j)/Gamma(k) P(k+j, k)."""
    mom = [special.gammainc(k + j, k) * math.exp(special.gammaln(k + j) - special.gammaln(k)) for j in range(4)]
    low = k ** 3 * mom[0] - 3 * k ** 2 * mom[1] + 3 * k * mom[2] - mom[3]   # E[(k - X)^3; X < k]
    return 2 * k + 2 * low


def pois_rho(lam):
    """E|X - lam|^3 for X ~ Poisson(lam), by summation."""
    K = int(lam + 40 * math.sqrt(lam) + 60)
    k = np.arange(K + 1)
    return float(np.sum(np.abs(k - lam) ** 3 * stats.poisson.pmf(k, lam)))


def be_family(dist, par):
    """mean, sd, skewness, third absolute central moment rho and lattice flag of one observation."""
    if dist == "gamma":
        return dict(mu=par, sd=math.sqrt(par), skew=2 / math.sqrt(par), rho=gamma_rho(par), lattice=False)
    if dist == "bern":
        q = 1 - par
        return dict(mu=par, sd=math.sqrt(par * q), skew=(1 - 2 * par) / math.sqrt(par * q),
                    rho=par * q * (par ** 2 + q ** 2), lattice=True)
    if dist == "pois":
        return dict(mu=par, sd=math.sqrt(par), skew=1 / math.sqrt(par), rho=pois_rho(par), lattice=True)
    raise ValueError(dist)


def sum_cdf(dist, par, n, s):
    """Exact cdf of S_n = X_1 + ... + X_n at s."""
    if dist == "gamma":
        return stats.gamma.cdf(s, n * par)
    if dist == "bern":
        return stats.binom.cdf(np.floor(s), n, par)
    return stats.poisson.cdf(np.floor(s), n * par)


def golden_max(f, a, b, iters=60):
    """Maximise a unimodal f on [a, b] by golden-section search (as the demonstrations do)."""
    g = (math.sqrt(5) - 1) / 2
    c, d = b - g * (b - a), a + g * (b - a)
    fc, fd = f(c), f(d)
    for _ in range(iters):
        if fc > fd:
            b, d, fd = d, c, fc
            c = b - g * (b - a)
            fc = f(c)
        else:
            a, c, fc = c, d, fd
            d = a + g * (b - a)
            fd = f(d)
    x = (a + b) / 2
    return x, f(x)


def ks_exact(dist, par, n, grid=1601):
    """Exact Kolmogorov distance sup_z |P(Z_n <= z) - Phi(z)|, Z_n = (S_n - n mu) / (sigma sqrt(n)).

    Lattice laws: the supremum is attained at an atom, from the left or the right, so it is a maximum
    over the atoms. Continuous laws: a grid on [max(-8, z_min), 8] and golden-section refinement in the
    two grid cells around the best grid point. Returns (distance, location z*)."""
    f = be_family(dist, par)
    mu, sd = f["mu"], f["sd"]
    rn = math.sqrt(n)
    if f["lattice"]:
        mean = n * mu
        K = n if dist == "bern" else int(mean + 12 * math.sqrt(mean) + 25)
        k = np.arange(K + 1)
        pmf = stats.binom.pmf(k, n, par) if dist == "bern" else stats.poisson.pmf(k, mean)
        F = np.cumsum(pmf)
        Fm = F - pmf
        z = (k - mean) / (sd * rn)
        P = stats.norm.cdf(z)
        d = np.maximum(np.abs(F - P), np.abs(Fm - P))
        i = int(np.argmax(d))
        return float(d[i]), float(z[i])
    zmin = -n * mu / (sd * rn)
    lo = max(-8.0, zmin)
    zs = np.linspace(lo, 8.0, grid)

    def err(z):
        return abs(float(sum_cdf(dist, par, n, n * mu + z * sd * rn)) - float(stats.norm.cdf(z)))

    e = np.abs(sum_cdf(dist, par, n, n * mu + zs * sd * rn) - stats.norm.cdf(zs))
    i = int(np.argmax(e))
    a, b = zs[max(i - 1, 0)], zs[min(i + 1, grid - 1)]
    zb, eb = golden_max(err, a, b)
    if e[i] >= eb:
        return float(e[i]), float(zs[i])
    return eb, zb


def be_bound(dist, par, n, C=33 / 4):
    """The Berry-Esseen bound C rho / (sigma^3 sqrt(n)) of (5.4); C = 33/4 in the book."""
    f = be_family(dist, par)
    return C * f["rho"] / (f["sd"] ** 3 * math.sqrt(n))


def edgeworth(dist, par, n, z):
    """One-term Edgeworth approximation of P(Z_n <= z): Phi(z) + phi(z)[gamma (1 - z^2)/6 + lattice term]/sqrt(n).
    For a lattice law on the integers the term (1/sigma) S(n mu + z sigma sqrt(n)) is added, with the
    sawtooth S(y) = floor(y) - y + 1/2 (Esseen 1945)."""
    f = be_family(dist, par)
    z = np.asarray(z, float)
    rn = math.sqrt(n)
    term = f["skew"] * (1 - z ** 2) / 6
    if f["lattice"]:
        y = n * f["mu"] + z * f["sd"] * rn
        term = term + (np.floor(y) - y + 0.5) / f["sd"]
    return stats.norm.cdf(z) + stats.norm.pdf(z) * term / rn


# ======== Section 5.5
def trigamma(x):
    """psi'(x) by recurrence and the asymptotic series (as the delta-method demonstration computes it)."""
    s = 0.0
    while x < 10:
        s += 1 / (x * x)
        x += 1
    ix2 = 1 / (x * x)
    return s + 1 / x + ix2 / 2 + (1 / x) * ix2 * (1 / 6 - ix2 * (1 / 30 - ix2 * (1 / 42 - ix2 / 30)))


TRANSFORMS = {
    # name: (g, g', g'', monotone direction on (0, inf): +1, -1 or 0)
    "exp": (np.exp, np.exp, np.exp, 1),
    "log": (np.log, lambda x: 1 / x, lambda x: -1 / x ** 2, 1),
    "sqrt": (np.sqrt, lambda x: 0.5 / np.sqrt(x), lambda x: -0.25 * x ** -1.5, 1),
    "square": (lambda x: x * x, lambda x: 2 * x, lambda x: 2 + 0 * x, 1),
    "recip": (lambda x: 1 / x, lambda x: -1 / x ** 2, lambda x: 2 / x ** 3, -1),
    "binvar": (lambda x: x * (1 - x), lambda x: 1 - 2 * x, lambda x: -2 + 0 * x, 0),
    "arcsin": (lambda x: np.arcsin(np.sqrt(x)), lambda x: 0.5 / np.sqrt(x * (1 - x)),
               lambda x: (2 * x - 1) / (4 * (x * (1 - x)) ** 1.5), 0),
}


def pop_moments(pop, par):
    """mean and variance of one observation: Exponential (mean par), Bernoulli(par), Poisson(par)."""
    if pop == "exp":
        return par, par ** 2
    if pop == "bern":
        return par, par * (1 - par)
    return par, par


def delta_allowed(pop, par, g):
    """Whether g(Xbar) is defined with probability one (discrete laws put mass on Xbar = 0)."""
    if pop == "exp":
        return g not in ("binvar", "arcsin")
    if pop == "pois":
        return g in ("exp", "sqrt", "square")
    return g in ("exp", "sqrt", "square", "binvar", "arcsin")


def delta_approx(pop, par, g, n):
    """The approximation of Theorem 5.13: g(Xbar) ~ N(g(mu), g'(mu)^2 sigma^2 / n), or, when
    g'(mu) = 0, g(Xbar) ~ g(mu) + g''(mu) sigma^2 chi^2_1 / (2n). Returns a dict with the cdf."""
    mu, v = pop_moments(pop, par)
    G, G1, G2, _ = TRANSFORMS[g]
    gm, d1, d2 = float(G(mu)), float(G1(mu)), float(G2(mu))
    if abs(d1) > 1e-12:
        s = abs(d1) * math.sqrt(v / n)
        return dict(order=1, center=gm, sd=s, cdf=lambda y: stats.norm.cdf((np.asarray(y) - gm) / s))
    c = d2 * v / (2 * n)            # g(Xbar) - g(mu) ~ c chi^2_1

    def cdf(y):
        w = (np.asarray(y, float) - gm) / c
        pc = stats.chi2.cdf(np.maximum(w, 0), 1)
        return pc if c > 0 else 1 - pc
    return dict(order=2, center=gm, sd=abs(c) * math.sqrt(2), cdf=cdf, scale=c)


def delta_exact(pop, par, g, n, grid=3001):
    """Exact mean, sd of g(Xbar_n) and Kolmogorov distance between its cdf and the delta-method
    approximation. Exponential samples: Xbar ~ Gamma(n, scale par/n), moments in closed form, the cdf
    through the monotone map g; discrete samples: enumeration of the atoms k/n."""
    mu, v = pop_moments(pop, par)
    G = TRANSFORMS[g][0]
    A = delta_approx(pop, par, g, n)
    if pop == "exp":
        th = par / n
        lg = special.gammaln(n)
        if g in ("sqrt", "square", "recip"):
            r = {"sqrt": 0.5, "square": 2.0, "recip": -1.0}[g]
            m1 = th ** r * math.exp(special.gammaln(n + r) - lg) if n + r > 0 else math.inf
            m2 = th ** (2 * r) * math.exp(special.gammaln(n + 2 * r) - lg) if n + 2 * r > 0 else math.inf
        elif g == "exp":
            m1 = (1 - th) ** (-n) if th < 1 else math.inf
            m2 = (1 - 2 * th) ** (-n) if 2 * th < 1 else math.inf
        else:   # log
            m1 = special.digamma(n) + math.log(th)
            m2 = trigamma(n) + m1 ** 2
        mean = m1
        sd = math.sqrt(max(m2 - m1 ** 2, 0)) if math.isfinite(m2) else math.inf
        xlo = stats.gamma.ppf(1e-12, n, scale=th)
        xhi = stats.gamma.ppf(1 - 1e-12, n, scale=th)
        xs = np.linspace(xlo, xhi, grid)
        dirn = TRANSFORMS[g][3]

        def err(x):
            Fx = float(stats.gamma.cdf(x, n, scale=th))
            ex = Fx if dirn > 0 else 1 - Fx
            return abs(ex - float(A["cdf"](G(x))))
        Fx = stats.gamma.cdf(xs, n, scale=th)
        e = np.abs((Fx if dirn > 0 else 1 - Fx) - A["cdf"](G(xs)))
        i = int(np.argmax(e))
        xb, eb = golden_max(err, xs[max(i - 1, 0)], xs[min(i + 1, grid - 1)])
        ks = max(float(e[i]), eb)
        return dict(mean=mean, sd=sd, ks=ks, approx=A)
    # discrete
    if pop == "bern":
        k = np.arange(n + 1)
        pmf = stats.binom.pmf(k, n, par)
    else:
        K = int(n * par + 12 * math.sqrt(n * par) + 25)
        k = np.arange(K + 1)
        pmf = stats.poisson.pmf(k, n * par)
    y = G(k / n)
    mean = float(np.sum(pmf * y))
    sd = float(math.sqrt(max(np.sum(pmf * y * y) - mean ** 2, 0)))
    order = np.argsort(y, kind="stable")
    ys, ps = y[order], pmf[order]
    # merge equal values (x(1 - x) takes the same value at k and n - k)
    vals, probs = [], []
    for yy, pp in zip(ys, ps):
        if vals and abs(yy - vals[-1]) <= 1e-12 * max(1.0, abs(yy)):
            probs[-1] += pp
        else:
            vals.append(yy)
            probs.append(pp)
    vals, probs = np.array(vals), np.array(probs)
    H = np.cumsum(probs)
    Hm = H - probs
    P = A["cdf"](vals)
    ks = float(np.max(np.maximum(np.abs(H - P), np.abs(Hm - P))))
    return dict(mean=mean, sd=sd, ks=ks, approx=A)


# ======== figures
def fig_5_1(out_dir=None):
    """Figure 5.1: the cdfs F_n of N(0, 1/n) and the cdf F of the point mass at 0 (Example 5.3)."""
    fig, ax = panel_grid(1, 2, size=(3.6, 2.7))
    t = np.linspace(-2, 2, 801)
    cols = [GREY, PURPLE, BLUE, GREEN, RED]
    for n, c in zip([1, 4, 16, 64, 256], cols):
        ax[0, 0].plot(t, normal_shrink_cdf(t, n), color=c, label="n = %d" % n)
    ax[0, 0].plot([0], [0.5], "o", color="k", ms=4)
    ax[0, 0].annotate(r"$F_n(0)=1/2$", (0, 0.5), (0.25, 0.32), fontsize=9, arrowprops=dict(arrowstyle="-", lw=0.6))
    ax[0, 0].set_title(r"$F_n(t)=P(X_n\leq t)$, $X_n\sim N(0,1/n)$")
    ax[0, 0].legend(loc="upper left", frameon=False, fontsize=8)
    ax[0, 1].plot([-2, 0], [0, 0], color="k")
    ax[0, 1].plot([0, 2], [1, 1], color="k")
    ax[0, 1].plot([0], [1], "o", color="k", ms=4)
    ax[0, 1].plot([0], [0], "o", mfc="white", color="k", ms=4)
    ax[0, 1].set_title(r"$F(t)$: point mass at 0")
    for a in ax[0]:
        a.set_xlabel("t")
        a.set_ylim(-0.05, 1.08)
    panel_label(ax[0, 0], "a", "lower right")
    panel_label(ax[0, 1], "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-1", out_dir)


def fig_5_s1(out_dir=None):
    """Figure 5.S1: the counterexamples of Theorem 5.4 and the warning example, with Monte Carlo."""
    rng = np.random.default_rng(51)
    eps, M = 0.5, 20000
    ns = np.unique(np.round(np.logspace(0, 4, 25)).astype(int))
    fig, ax = panel_grid(2, 2, size=(3.5, 2.8))
    # (a) sqrt(n) I(U < 1/n)
    p, m1, m2 = spike_moments(ns, 0.5, 1)
    U = rng.random(M)
    mc_p = [np.mean(U < 1 / n) for n in ns]
    mc_2 = [np.mean(n * (U < 1 / n)) for n in ns]
    a = ax[0, 0]
    a.loglog(ns, p, color=BLUE, label=r"$P(|X_n|>\epsilon)=1/n$")
    a.loglog(ns, m2, color=RED, label=r"$E X_n^2=1$")
    a.loglog(ns, m1, color=GREEN, label=r"$E|X_n|=n^{-1/2}$")
    a.loglog(ns, np.maximum(mc_p, 1e-5), "o", ms=3, color=BLUE)
    a.loglog(ns, mc_2, "o", ms=3, color=RED)
    a.set_title(r"$X_n=\sqrt{n}\,I(U<1/n)$: in probability, not in $L^2$", fontsize=9)
    a.set_xlabel("n")
    a.set_ylim(1e-4, 5)
    a.legend(frameon=False, fontsize=7.5, loc="lower left")
    # (b) X_n = -X
    a = ax[0, 1]
    x = np.linspace(-3, 3, 400)
    a.plot(x, stats.norm.cdf(x), color=BLUE, lw=3, alpha=0.5, label=r"cdf of $X$")
    a.plot(x, stats.norm.cdf(x), color=RED, ls="--", label=r"cdf of $X_n=-X$")
    X = rng.standard_normal(M)
    a.axhline(np.mean(np.abs(2 * X) > eps), color=GREEN, lw=1.2)
    a.text(-2.9, np.mean(np.abs(2 * X) > eps) + 0.06, r"$P(|X_n-X|>0.5)=P(|X|>0.25)=%.3f$" % (2 * stats.norm.sf(0.25)),
           fontsize=7.5, color=GREEN)
    a.set_title(r"$X_n=-X$: in distribution, not in probability", fontsize=9)
    a.legend(frameon=False, fontsize=7.5, loc="center right")
    # (c) warning example: n^2 with probability 1/n
    a = ax[1, 0]
    p, m1, _ = spike_moments(ns, 2, 1)
    mc_m = [np.mean(n * n * (U < 1 / n)) for n in ns]
    a.loglog(ns, p, color=BLUE, label=r"$P(X_n\neq0)=1/n$")
    a.loglog(ns, m1, color=RED, label=r"$E X_n=n$")
    a.loglog(ns, np.maximum(mc_m, 1e-5), "o", ms=3, color=RED)
    a.set_title(r"$P(X_n=n^2)=1/n$: $X_n\to0$ in probability, $E X_n\to\infty$", fontsize=9)
    a.set_xlabel("n")
    a.legend(frameon=False, fontsize=7.5, loc="upper left")
    # (d) raster: common U against independent U_n, b = 1
    a = ax[1, 1]
    N = 10000
    _, rc = spike_sim(0, 1, "common", N, 15, eps, 5101, keep=15)
    _, ri = spike_sim(0, 1, "indep", N, 15, eps, 5102, keep=15)
    for j, ex in enumerate(rc):
        a.plot(ex, np.full(len(ex), j), "|", color=BLUE, ms=4)
    for j, ex in enumerate(ri):
        a.plot(ex, np.full(len(ex), 16 + j), "|", color=RED, ms=4)
    a.set_xscale("log")
    a.set_xlim(0.8, N)
    a.set_yticks([7, 23])
    a.set_yticklabels(["one $U$", "independent $U_n$"], fontsize=8)
    a.set_xlabel(r"n (a tick where $X_n=1$)")
    a.set_title(r"$I(U_n<1/n)$: same marginals, a.s. only with one $U$", fontsize=9)
    for k, (i, j) in enumerate([(0, 0), (0, 1), (1, 0), (1, 1)]):
        panel_label(ax[i, j], "abcd"[k], "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S1", out_dir)


def fig_5_s2(out_dir=None):
    """Figure 5.S2: Example 5.7, P(0.4 <= Xbar_n <= 0.6) for a fair coin: exact, Chebyshev, normal."""
    n = np.arange(1, 121)
    ex = coin_interval_prob(n)
    cheb = np.maximum(1 - 25 / n, 0)
    clt = 2 * stats.norm.cdf(0.1 * 2 * np.sqrt(n)) - 1
    fig, ax = panel_grid(1, 1, size=(5.6, 3.1))
    a = ax[0, 0]
    a.step(n, ex, where="mid", color=BLUE, label=r"exact (binomial)")
    a.plot(n, clt, color=GREEN, label=r"normal approximation $2\Phi(0.2\sqrt{n})-1$")
    a.plot(n, cheb, color=RED, label=r"Chebyshev bound $1-25/n$")
    a.axhline(0.7, color=GREY, ls=":", lw=1)
    a.axvline(84, color=RED, ls=":", lw=1)
    n0 = n0_all(ex, n, 0.7)
    a.axvline(n0, color=BLUE, ls=":", lw=1)
    a.text(86, 0.45, "Chebyshev: n = 84", color=RED, fontsize=8)
    a.text(n0 + 1, 0.45, "exact: n >= %d" % n0, color=BLUE, fontsize=8)
    a.set_xlabel("n (tosses)")
    a.set_ylabel(r"$P(0.4\leq\bar X_n\leq0.6)$")
    a.set_ylim(0, 1.02)
    a.legend(frameon=False, fontsize=8, loc="lower right", bbox_to_anchor=(1.0, 0.02))
    fig.tight_layout()
    savefig(fig, CH, "fig5-S2", out_dir)


def n0_all(prob, n, level):
    """smallest n0 such that prob >= level for every n >= n0 in the range."""
    bad = np.where(prob < level)[0]
    return int(n[bad[-1] + 1]) if len(bad) else int(n[0])


BE_CASES = [("gamma", 1.0, "Exponential", BLUE), ("gamma", 0.25, "Gamma(0.25)", PURPLE),
            ("bern", 0.5, "Bernoulli(0.5)", GREEN), ("bern", 0.1, "Bernoulli(0.1)", ORANGE), ("pois", 0.2, "Poisson(0.2)", RED)]


def fig_5_s3(out_dir=None):
    """Figure 5.S3: the exact Berry-Esseen error sup_z |P(Z_n <= z) - Phi(z)| for skewed laws, the bound
    (5.4), and the Edgeworth correction for the exponential at n = 10."""
    ns = np.unique(np.round(np.logspace(0, 3, 22)).astype(int))
    fig, ax = panel_grid(1, 2, size=(3.9, 3.1))
    a = ax[0, 0]
    for dist, par, lab, c in BE_CASES:
        d = [ks_exact(dist, par, n)[0] for n in ns]
        a.loglog(ns, d, "o-", ms=2.5, color=c, label=lab, lw=1.2)
    a.loglog(ns, [be_bound("gamma", 1.0, n) for n in ns], color=BLUE, ls="--", lw=1)
    a.loglog(ns, [be_bound("gamma", 1.0, n, 0.4748) for n in ns], color=BLUE, ls=":", lw=1)
    a.text(25, 5.5, "(5.4), C = 33/4,\nexponential", fontsize=7, color=BLUE)
    a.text(40, 0.3, "C = 0.4748", fontsize=7, color=BLUE)
    a.set_xlabel("n")
    a.set_ylabel(r"$\sup_z|P(Z_n\leq z)-\Phi(z)|$")
    a.set_ylim(3e-3, 30)
    a.legend(frameon=False, fontsize=7, loc="lower left")
    a = ax[0, 1]
    n = 10
    z = np.linspace(-3.5, 4.5, 800)
    exact = sum_cdf("gamma", 1.0, n, n + z * math.sqrt(n)) - stats.norm.cdf(z)
    a.plot(z, exact, color=BLUE, label="exact, n = 10")
    a.plot(z, edgeworth("gamma", 1.0, n, z) - stats.norm.cdf(z), color=RED, ls="--", label="Edgeworth")
    a.axhline(0, color=GREY, lw=0.6)
    a.set_xlabel("z")
    a.set_ylabel(r"$P(Z_n\leq z)-\Phi(z)$")
    a.legend(frameon=False, fontsize=7.5, loc="upper right")
    panel_label(ax[0, 0], "a", "upper right")
    panel_label(ax[0, 1], "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S3", out_dir)


def gamma_mean_density(x, n, mu=1.0):
    """density of Xbar_n for an Exponential(mean mu) sample: Gamma(n, scale mu/n)."""
    return stats.gamma.pdf(x, n, scale=mu / n)


def fig_5_s4(out_dir=None):
    """Figure 5.S4: the delta method. (a) Example 5.14 with exponential data: exact density of
    exp(Xbar_n) against N(e^mu, e^{2mu} sigma^2 / n); (b) Exercise 5.14: sqrt(n)(Xbar^2 - 1/4) for
    uniform data against N(0, 1/12); (c) g'(mu) = 0: n(Xbar(1 - Xbar) - 1/4) for a fair coin against
    -chi^2_1 / 4."""
    rng = np.random.default_rng(54)
    fig, ax = panel_grid(1, 3, size=(3.2, 2.8))
    a = ax[0, 0]
    for n, c in [(10, BLUE), (50, RED)]:
        y = np.linspace(0.8, 6.5, 600)
        dens = gamma_mean_density(np.log(y), n) / y          # change of variables, x = log y
        a.plot(y, dens, color=c, label="exact, n = %d" % n)
        a.plot(y, stats.norm.pdf(y, math.e, math.e / math.sqrt(n)), color=c, ls="--", lw=1,
               label="delta method" if n == 50 else None)
    a.set_title(r"$e^{\bar X_n}$, Exp(1) data", fontsize=9.5)
    a.set_xlabel("y")
    a.legend(frameon=False, fontsize=7.5)
    a = ax[0, 1]
    zz = np.linspace(-1.2, 1.2, 400)
    for n, c in [(2, BLUE), (50, RED)]:
        Xb = rng.random((40000, n)).mean(1)
        T = math.sqrt(n) * (Xb ** 2 - 0.25)
        a.hist(T, bins=80, range=(-1.2, 1.2), density=True, histtype="step", color=c, label="n = %d" % n)
    a.plot(zz, stats.norm.pdf(zz, 0, math.sqrt(1 / 12)), color="k", lw=1.2, label=r"$N(0,1/12)$")
    a.set_title(r"$\sqrt{n}(\bar X_n^2-1/4)$, Uniform(0,1)", fontsize=9.5)
    a.legend(frameon=False, fontsize=7.5)
    a = ax[0, 2]
    n = 200
    k = np.arange(n + 1)
    pmf = stats.binom.pmf(k, n, 0.5)
    W = n * (k / n * (1 - k / n) - 0.25)
    o = np.argsort(W)
    a.step(W[o], np.cumsum(pmf[o]), where="post", color=BLUE, label="exact, n = 200")
    w = np.linspace(-2, 0, 400)
    a.plot(w, stats.chi2.sf(-4 * w, 1), color=RED, ls="--", label=r"$-\chi^2_1/4$")
    a.set_xlim(-2, 0.15)
    a.set_title(r"$n(\bar X_n(1-\bar X_n)-1/4)$, $p=1/2$", fontsize=9.5)
    a.set_xlabel("w")
    a.set_ylabel("cdf")
    a.legend(frameon=False, fontsize=7.5, loc="upper left")
    for k, aa in enumerate(ax[0]):
        panel_label(aa, "abc"[k], "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S4", out_dir)


MV_MU = np.array([1.0, 2.0])
MV_SIGMA = np.array([[1.0, 1.0], [1.0, 2.0]])


def mv_sample(rng, M, n):
    """M samples of size n of X = (E1, E1 + E2): returns the two sample means, shape (M, 2)."""
    E = rng.exponential(size=(M, n, 2))
    X = np.stack([E[..., 0], E[..., 0] + E[..., 1]], axis=-1)
    return X.mean(1)


def delta_var_product(mu, S):
    """Example 5.16: the asymptotic variance of sqrt(n)(Xbar1 Xbar2 - mu1 mu2)."""
    g = np.array([mu[1], mu[0]])
    return float(g @ S @ g)


def delta_var_ratio(mu, S):
    """Exercise 5.15: the asymptotic variance of sqrt(n)(Xbar1 / Xbar2 - mu1 / mu2)."""
    g = np.array([1 / mu[1], -mu[0] / mu[1] ** 2])
    return float(g @ S @ g)


def fig_5_s5(out_dir=None):
    """Figure 5.S5: (a) the multivariate CLT, sqrt(n)(Xbar - mu) for n = 30 against the 50% and 95%
    ellipses of N(0, Sigma); (b) sd of sqrt(n)(g(Xbar) - g(mu)) by Monte Carlo against the multivariate
    delta method for the product (Example 5.16) and the ratio (Exercise 5.15)."""
    rng = np.random.default_rng(55)
    fig, ax = panel_grid(1, 2, size=(3.6, 3.1))
    a = ax[0, 0]
    n = 30
    Xb = mv_sample(rng, 4000, n)
    Zs = math.sqrt(n) * (Xb - MV_MU)
    a.plot(Zs[:1500, 0], Zs[:1500, 1], ".", ms=1.5, color=GREY, alpha=0.6)
    for q, ls in [(0.5, "--"), (0.95, "-")]:
        ex, ey = common.ellipse_xy([0, 0], MV_SIGMA, math.sqrt(stats.chi2.ppf(q, 2)))
        a.plot(ex, ey, color=RED, ls=ls, lw=1.2)
        inside = np.mean(np.einsum("ij,jk,ik->i", Zs, np.linalg.inv(MV_SIGMA), Zs) <= stats.chi2.ppf(q, 2))
        a.text(0.03, 0.97 - 0.07 * (q > 0.6), "%.0f%% ellipse holds %.1f%%" % (100 * q, 100 * inside),
               transform=a.transAxes, fontsize=7.5, va="top")
    a.set_xlabel(r"$\sqrt{n}(\bar X_1-\mu_1)$")
    a.set_ylabel(r"$\sqrt{n}(\bar X_2-\mu_2)$")
    a.set_title(r"$X=(E_1,E_1+E_2)$, $n=30$", fontsize=9.5)
    a = ax[0, 1]
    ns = [5, 10, 20, 50, 100, 200, 500]
    sp, sr = [], []
    for n in ns:
        Xb = mv_sample(rng, 20000, n)
        sp.append(math.sqrt(n) * np.std(Xb[:, 0] * Xb[:, 1]))
        sr.append(math.sqrt(n) * np.std(Xb[:, 0] / Xb[:, 1]))
    a.semilogx(ns, sp, "o", color=BLUE, ms=4, label=r"product $\bar X_1\bar X_2$ (MC)")
    a.axhline(math.sqrt(delta_var_product(MV_MU, MV_SIGMA)), color=BLUE, ls="--", lw=1)
    a.semilogx(ns, np.array(sr) * 10, "s", color=RED, ms=4, label=r"ratio $\bar X_1/\bar X_2$ (MC), x10")
    a.axhline(10 * math.sqrt(delta_var_ratio(MV_MU, MV_SIGMA)), color=RED, ls="--", lw=1)
    a.set_xlabel("n")
    a.set_ylabel(r"sd of $\sqrt{n}(g(\bar X)-g(\mu))$")
    a.set_title("Monte Carlo (points), delta method (dashed)", fontsize=9.5)
    a.legend(frameon=False, fontsize=7.5, loc="center right")
    panel_label(ax[0, 0], "a", "lower right")
    panel_label(ax[0, 1], "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S5", out_dir)


def fig_5_s6(out_dir=None):
    """Figure 5.S6: the strong law. Running means of 20 paths of Exp(1) data, which settle at 1, and of
    Cauchy data (no mean), which never settle."""
    rng = np.random.default_rng(56)
    N = 100000
    n = np.arange(1, N + 1)
    idx = np.unique(np.round(np.logspace(0, 5, 400)).astype(int)) - 1
    fig, ax = panel_grid(1, 2, size=(3.6, 2.9))
    for j in range(20):
        e = np.cumsum(rng.exponential(size=N)) / n
        c = np.cumsum(rng.standard_cauchy(size=N)) / n
        ax[0, 0].semilogx(n[idx], e[idx], color=BLUE, lw=0.7, alpha=0.7)
        ax[0, 1].semilogx(n[idx], c[idx], color=RED, lw=0.7, alpha=0.7)
    ax[0, 0].axhline(1, color="k", lw=0.8)
    ax[0, 0].set_ylim(0, 2.5)
    ax[0, 0].set_title(r"$\bar X_n$, Exp(1): converges almost surely", fontsize=9.5)
    ax[0, 1].set_ylim(-8, 8)
    ax[0, 1].set_title(r"$\bar X_n$, Cauchy: no limit", fontsize=9.5)
    for a in ax[0]:
        a.set_xlabel("n")
    panel_label(ax[0, 0], "a", "upper right")
    panel_label(ax[0, 1], "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S6", out_dir)


FIGURES = {"5.1": fig_5_1, "5.S1": fig_5_s1, "5.S2": fig_5_s2, "5.S3": fig_5_s3, "5.S4": fig_5_s4,
           "5.S5": fig_5_s5, "5.S6": fig_5_s6}

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