"""Wasserman (2004), Chapter 9: Parametric Inference.

Companion code for Chapter 9 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 119-148, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch09-parametric-inference.html):

* Section 9.2, the method of moments: gamma_mom (Example 9.2 and Exercise 9.1), the asymptotic
  covariance of a moment estimator, mom_avar (Theorem 9.6, with the covariance matrix of
  (X, X^2) in the sandwich), and gamma_moments.
* Section 9.3, maximum likelihood: the Bernoulli likelihood (Figure 9.1) and the Uniform(0, theta)
  likelihood (Figure 9.2); gamma_mle, Newton-Raphson on the profile likelihood of the Gamma shape,
  checked against scipy.stats.gamma.fit.
* Section 9.5, consistency: cauchy_Mn and cauchy_kl (M_n(theta) and its limit -D(theta*, theta),
  Theorem 9.13), cauchy_mle (global maximiser by a grid and Newton steps).
* Sections 9.7-9.10, asymptotic normality, the Wald interval, optimality, the delta method:
  fisher_info, wald_interval and wald_coverage (exact coverage of the Wald interval on the
  parameter scale and on the log or logit scale for the Bernoulli, Poisson, Exponential and
  Normal-sigma models), median_nvar (Section 9.8), hodges_nmse (the superefficient estimator),
  ex929_se (Example 9.29).
* Section 9.11, the parametric bootstrap: boot_se, Exercises 9.3, 9.7, 9.9 and 9.10.
* Section 9.13.2, sufficiency: poisson_zero_estimators (Rao-Blackwell for P(X = 0)).
* Section 9.13.4, computing the MLE: Newton-Raphson and the EM algorithm for the two-Normal
  mixture of Example 9.50 (mix2_*), for right-censored Normal data (cens_*), and EM for the
  five-parameter mixture of Example 9.49 (em_mixture5), run on the Old Faithful data.
* JSRandom: the seeded generator of the browser demonstrations (DK.rng in courses/demo-kit.js), and
  the samplers and estimators the three demonstrations use (demo_sample, demo_estimators,
  demo_newton_em), so that the simulations of the pages can be rerun here.

Figures. The book has two figures in Chapter 9, both reproduced:
  9.1 the Bernoulli likelihood for n = 20 and 12 successes;
  9.2 the Uniform(0, theta) density for three values of theta, and the likelihood.
Nothing is skipped. Eight supplementary figures of our own illustrate the gaps filled in the notes:
  9.S1 the method of moments against maximum likelihood for the Gamma shape (Theorem 9.6);
  9.S2 consistency through the Kullback-Leibler divergence, Cauchy location (Theorem 9.13);
  9.S3 asymptotic normality and the exact coverage of Wald intervals (Theorems 9.18, 9.19);
  9.S4 efficiency: mean against median, and Hodges' superefficient estimator (Section 9.8);
  9.S5 the delta method against the parametric and nonparametric bootstrap (Sections 9.9-9.11);
  9.S6 the bootstrap for the Uniform maximum (Exercise 9.10);
  9.S7 Rao-Blackwell and the Cramer-Rao bound for P(X = 0) in a Poisson model (Section 9.13.2);
  9.S8 Newton-Raphson and EM (Section 9.13.4, Examples 9.49 and 9.50).
Run `python3 ch09_parametric_inference.py --list`, `python3 ch09_parametric_inference.py` (all
figures, about a minute on one CPU thread) or `python3 ch09_parametric_inference.py --fig 9.S3`.
Files go to ../img/ch09/; the demonstrations read ../data/ch09-faithful.json (written by
export_json()).
"""
import json
import math
import os

import numpy as np
from scipy import optimize, special, stats

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

CH = 9
M32 = 0xFFFFFFFF
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
Z95 = 1.959963984540054


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


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32, norm() the Box-Muller transform that returns r cos(t) and keeps r sin(t) for the
    next call, exp(mean) an exponential variable, exactly as in JavaScript."""

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

    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 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)

    def exp(self, mean):
        return -mean * math.log(self.pos())


def js_pnorm(z):
    """DK.pnorm of the demo kit: the standard Normal cdf through a rational approximation of erfc
    (relative error below 1.2e-7). Used where a demo needs Phi, so the numbers agree with the page."""
    x = abs(z) / math.sqrt(2.0)
    t = 1.0 / (1.0 + 0.5 * x)
    r = t * math.exp(-x * x - 1.26551223 + t * (1.00002368 + t * (0.37409196 + t * (0.09678418 + t * (
        -0.18628806 + t * (0.27886807 + t * (-1.13520398 + t * (1.48851587 + t * (-0.82215223 + t * 0.17087277)))))))))
    return 1.0 - 0.5 * r if z >= 0 else 0.5 * r


def js_upper(t):
    """1 - Phi(t) with the same approximation, computed without cancellation for t >= 0."""
    x = abs(t) / math.sqrt(2.0)
    s = 1.0 / (1.0 + 0.5 * x)
    r = s * math.exp(-x * x - 1.26551223 + s * (1.00002368 + s * (0.37409196 + s * (0.09678418 + s * (
        -0.18628806 + s * (0.27886807 + s * (-1.13520398 + s * (1.48851587 + s * (-0.82215223 + s * 0.17087277)))))))))
    return 0.5 * r if t >= 0 else 1.0 - 0.5 * r


def phi(x):
    return math.exp(-0.5 * x * x) / math.sqrt(2.0 * math.pi)


def digamma_series(x):
    """psi(x) by recurrence and the asymptotic series (as the demos compute it)."""
    s = 0.0
    while x < 10:
        s -= 1.0 / x
        x += 1.0
    i2 = 1.0 / (x * x)
    return s + math.log(x) - 0.5 / x - i2 * (1 / 12 - i2 * (1 / 120 - i2 * (1 / 252 - i2 * (1 / 240 - i2 / 132))))


def trigamma_series(x):
    s = 0.0
    while x < 10:
        s += 1.0 / (x * x)
        x += 1.0
    i2 = 1.0 / (x * x)
    return s + 1.0 / x + i2 / 2 + (1.0 / x) * i2 * (1 / 6 - i2 * (1 / 30 - i2 * (1 / 42 - i2 / 30)))


# =========================================================================== 9.2 method of moments
def gamma_moments(alpha, beta, k):
    """E X^k for X ~ Gamma(alpha, scale beta): beta^k Gamma(alpha + k) / Gamma(alpha)."""
    return beta ** k * math.exp(special.gammaln(alpha + k) - special.gammaln(alpha))


def gamma_mom(x):
    """Method of moments for Gamma(alpha, scale beta) (Exercise 9.1): equate E X = alpha beta and
    V X = alpha beta^2 to the sample mean and the (divisor n) sample variance."""
    x = np.asarray(x, float)
    m = x.mean(-1)
    v = x.var(-1)
    return m * m / v, v / m


def mom_avar(alpha, beta, book=False):
    """Asymptotic covariance of the Gamma method-of-moments estimator (alpha, beta) (Theorem 9.6):
    Sigma = G V(Y) G^T with Y = (X, X^2) and G the Jacobian of the map (a1, a2) -> (alpha, beta)
    that inverts the moment equations. With book=True the second-moment matrix E(Y Y^T) is used in
    place of V(Y), as printed in the book; the two differ (see the notes)."""
    m = [gamma_moments(alpha, beta, k) for k in range(5)]
    EY = np.array([m[1], m[2]])
    EYY = np.array([[m[2], m[3]], [m[3], m[4]]])
    VY = EYY - np.outer(EY, EY)
    a1, a2 = m[1], m[2]
    s2 = a2 - a1 * a1                       # the variance
    # alpha = a1^2 / (a2 - a1^2), beta = (a2 - a1^2) / a1
    G = np.array([[2 * a1 / s2 + 2 * a1 ** 3 / s2 ** 2, -a1 ** 2 / s2 ** 2],
                  [-a2 / a1 ** 2 - 1.0, 1.0 / a1]])
    return G @ (EYY if book else VY) @ G.T


def gamma_fisher(alpha, beta):
    """Fisher information matrix of one Gamma(alpha, scale beta) observation."""
    return np.array([[special.polygamma(1, alpha), 1.0 / beta], [1.0 / beta, alpha / beta ** 2]])


def gamma_mle(x, tol=1e-12, maxit=100):
    """MLE of Gamma(alpha, scale beta) by Newton-Raphson (Section 9.13.4) on the profile equation
    log(alpha) - psi(alpha) = log(mean x) - mean(log x), with beta = mean(x) / alpha. Works on the last
    axis, so many samples are fitted at once. Returns alpha, beta and the number of iterations."""
    x = np.asarray(x, float)
    s = np.log(x.mean(-1)) - np.log(x).mean(-1)
    a = (3 - s + np.sqrt((s - 3) ** 2 + 24 * s)) / (12 * s)   # a close starting value
    it = 0
    for it in range(1, maxit + 1):
        f = np.log(a) - special.digamma(a) - s
        fp = 1.0 / a - special.polygamma(1, a)
        step = f / fp
        anew = a - step
        anew = np.where(anew <= 0, a / 2, anew)
        done = np.all(np.abs(anew - a) <= tol * anew)
        a = anew
        if done:
            break
    return a, x.mean(-1) / a, it


# =========================================================================== 9.3 likelihood examples
def bernoulli_lik(p, S, n):
    """L_n(p) = p^S (1 - p)^(n - S) (Example 9.10)."""
    p = np.asarray(p, float)
    with np.errstate(divide="ignore"):
        return np.exp(S * np.log(p) + (n - S) * np.log1p(-p))


def uniform_lik(theta, x):
    """L_n(theta) for Uniform(0, theta): theta^(-n) if theta >= max(x), else 0 (Example 9.12)."""
    theta = np.asarray(theta, float)
    return np.where(theta >= np.max(x), theta ** (-len(x)), 0.0)


# =========================================================================== 9.5 consistency
def cauchy_loglik(theta, x):
    """Log-likelihood of the Cauchy location model (scale 1), up to the constant -n log(pi);
    theta may be an array (evaluated on a grid)."""
    theta = np.asarray(theta, float)
    return -np.log1p((np.asarray(x)[..., None, :] - theta[..., :, None]) ** 2).sum(-1)


def cauchy_kl(theta0, theta):
    """D(Cauchy(theta0), Cauchy(theta)) = log(1 + (theta - theta0)^2 / 4)."""
    return np.log1p((np.asarray(theta, float) - theta0) ** 2 / 4.0)


def cauchy_Mn(theta, x, theta0=0.0):
    """M_n(theta) = n^-1 sum log f(X_i; theta) / f(X_i; theta0) on a grid of theta (Theorem 9.13)."""
    x = np.asarray(x, float)
    return (cauchy_loglik(theta, x) - cauchy_loglik(np.array([theta0]), x)[0]) / len(x)


def cauchy_mle(X, grid_half=12.0, ngrid=481, newton=30):
    """Global maximiser of the Cauchy location likelihood for each row of X: the best point of a grid
    around the median, then Newton steps (the log-likelihood is smooth and the grid spacing is far
    below the width of any local peak)."""
    X = np.atleast_2d(np.asarray(X, float))
    med = np.median(X, 1)
    g = np.linspace(-grid_half, grid_half, ngrid)
    out = np.empty(len(X))
    for i0 in range(0, len(X), 200):
        Xi = X[i0:i0 + 200]
        T = med[i0:i0 + 200, None] + g[None, :]
        ll = -np.log1p((Xi[:, None, :] - T[:, :, None]) ** 2).sum(-1)
        th = T[np.arange(len(Xi)), ll.argmax(1)]
        for _ in range(newton):
            u = Xi - th[:, None]
            s = (2 * u / (1 + u * u)).sum(1)
            h = (2 * (u * u - 1) / (1 + u * u) ** 2).sum(1)
            step = np.where(h < 0, -s / np.where(h < 0, h, -1), 0.0)
            step = np.clip(step, -0.05, 0.05)
            th = th + step
        out[i0:i0 + 200] = th
    return out


# =========================================================================== 9.7 Fisher information, Wald
WALD_MODELS = ("bern", "pois", "expo", "normsd")


def fisher_info(model, th):
    """Fisher information I(theta) of one observation:
    bern p: 1/(p(1-p)); pois lambda: 1/lambda; expo (rate lambda): 1/lambda^2; normsd (sigma, mean known): 2/sigma^2."""
    th = np.asarray(th, float)
    return {"bern": 1 / (th * (1 - th)), "pois": 1 / th, "expo": 1 / th ** 2, "normsd": 2 / th ** 2}[model]


def loglik(model, th, suff, n):
    """Log-likelihood from the sufficient statistic (constants dropped): bern/pois suff = sum x;
    expo suff = sum x; normsd suff = sum x^2 (mean 0 known)."""
    th = np.asarray(th, float)
    with np.errstate(divide="ignore", invalid="ignore"):
        if model == "bern":
            return suff * np.log(th) + (n - suff) * np.log1p(-th)
        if model == "pois":
            return suff * np.log(th) - n * th
        if model == "expo":
            return n * np.log(th) - th * suff
        return -n * np.log(th) - suff / (2 * th ** 2)


def mle_from_suff(model, suff, n):
    return {"bern": suff / n, "pois": suff / n, "expo": n / suff if suff > 0 else np.inf,
            "normsd": math.sqrt(suff / n)}[model]


def g_scale(model):
    """The transformation used for the second Wald interval: logit for p, log otherwise; with its inverse
    and derivative."""
    if model == "bern":
        return (lambda p: math.log(p / (1 - p)), lambda y: 1 / (1 + math.exp(-y)), lambda p: 1 / (p * (1 - p)))
    return (math.log, math.exp, lambda t: 1 / t)


def wald_interval(model, thhat, n, scale="theta", z=Z95):
    """Wald interval thhat +- z se, se = 1/sqrt(n I(thhat)) (Theorem 9.19), on the parameter scale; with
    scale='g' the interval g(thhat) +- z |g'(thhat)| se mapped back (delta method, Theorem 9.24).
    Returns None when the interval is undefined (estimate on the boundary)."""
    if model in ("bern", "pois") and thhat == 0 or model == "bern" and thhat == 1:
        return (thhat, thhat) if scale == "theta" else None
    se = 1.0 / math.sqrt(n * float(fisher_info(model, thhat)))
    if scale == "theta":
        return thhat - z * se, thhat + z * se
    g, ginv, dg = g_scale(model)
    c, h = g(thhat), z * abs(dg(thhat)) * se
    return ginv(c - h), ginv(c + h)


def wald_coverage(model, th, n, scale="theta", z=Z95):
    """Exact coverage P_theta(theta in C_n) of the 95% Wald interval. Discrete models: a finite sum over
    the sufficient statistic (degenerate intervals count as misses). Continuous models: the interval is
    built from a pivot, so the coverage is a Gamma or chi-square probability that does not depend on theta."""
    if model == "bern":
        k = np.arange(n + 1)
        pk = stats.binom.pmf(k, n, th)
        cov = 0.0
        for kk, pp in zip(k, pk):
            iv = wald_interval(model, kk / n, n, scale, z)
            if iv is not None and iv[0] <= th <= iv[1]:
                cov += pp
        return cov
    if model == "pois":
        kmax = int(n * th + 12 * math.sqrt(n * th) + 30)
        cov = 0.0
        for kk in range(kmax + 1):
            iv = wald_interval(model, kk / n, n, scale, z)
            if iv is not None and iv[0] <= th <= iv[1]:
                cov += stats.poisson.pmf(kk, n * th)
        return cov
    rn = math.sqrt(n)
    if model == "expo":           # T = n Xbar lambda ~ Gamma(n, 1), and lambdahat / lambda = n / T
        if scale == "theta":
            lo, hi = n - z * rn, n + z * rn
        else:
            lo, hi = n * math.exp(-z / rn), n * math.exp(z / rn)
        return special.gammainc(n, hi) - special.gammainc(n, max(lo, 0.0))
    c = z / math.sqrt(2 * n)      # normsd: W = n sigmahat^2 / sigma^2 ~ chi-square(n)
    if scale == "theta":
        lo = n / (1 + c) ** 2
        hi = n / (1 - c) ** 2 if c < 1 else np.inf
    else:
        lo, hi = n * math.exp(-2 * c), n * math.exp(2 * c)
    return stats.chi2.cdf(hi, n) - stats.chi2.cdf(lo, n)


def lr_interval(model, suff, n, cut=Z95 ** 2 / 2):
    """Likelihood-ratio interval {theta: l(thhat) - l(theta) <= z^2/2}, by root finding (for the figures)."""
    th = mle_from_suff(model, suff, n)
    l0 = float(loglik(model, th, suff, n)) if np.isfinite(th) else None
    f = lambda t: float(loglik(model, t, suff, n)) - l0 + cut
    lo_b = {"bern": 1e-12, "pois": 1e-12, "expo": 1e-12, "normsd": 1e-12}[model]
    hi_b = {"bern": 1 - 1e-12}.get(model, None)
    lo = optimize.brentq(f, lo_b, th) if th > lo_b and f(lo_b) < 0 else lo_b
    if hi_b is None:
        hi_b = th * 2 + 1
        while f(hi_b) > 0:
            hi_b *= 2
    hi = optimize.brentq(f, th, hi_b) if th < hi_b else hi_b
    return lo, hi


# =========================================================================== 9.8 optimality
def median_nvar(n, R=20000, seed=0, dist="normal"):
    """Monte Carlo n * Var(sample median) for N(0,1) or Cauchy(0,1) samples of size n."""
    rng = np.random.default_rng(seed)
    out = []
    for i in range(0, R, 2000):
        m = min(2000, R - i)
        X = rng.standard_normal((m, n)) if dist == "normal" else rng.standard_cauchy((m, n))
        out.append(np.median(X, 1))
    med = np.concatenate(out)
    return n * np.mean(med ** 2)


def hodges_nmse(theta, n, sigma=1.0):
    """Exact n * MSE of Hodges' estimator T = Xbar 1{|Xbar| > n^(-1/4)} for N(theta, sigma^2) data.
    With Xbar ~ N(theta, s^2), s = sigma/sqrt(n), and a = n^(-1/4):
    MSE = E(Xbar - theta)^2 - E[((Xbar - theta)^2 - theta^2) 1{|Xbar| <= a}]."""
    theta = np.asarray(theta, float)
    s = sigma / math.sqrt(n)
    a = n ** -0.25
    lo, hi = (-a - theta) / s, (a - theta) / s      # standardised limits of Xbar - theta
    # E[Z^2 1{lo <= Z <= hi}] = [Phi(hi) - Phi(lo)] - [hi phi(hi) - lo phi(lo)]
    p = stats.norm.cdf(hi) - stats.norm.cdf(lo)
    ez2 = p - (hi * stats.norm.pdf(hi) - lo * stats.norm.pdf(lo))
    mse = s ** 2 - (s ** 2 * ez2 - theta ** 2 * p)
    return n * mse


# =========================================================================== 9.10 delta method, multiparameter
def ex929_se(mu, sigma, n, book=False):
    """Delta-method standard error of tau = sigma/mu for N(mu, sigma^2) (Example 9.29):
    sqrt(grad^T J_n grad) with J_n = diag(sigma^2, sigma^2/2)/n and grad = (-sigma/mu^2, 1/mu), giving
    n^(-1/2) sqrt(sigma^4/mu^4 + sigma^2/(2 mu^2)). book=True gives the printed 1/mu^4 version."""
    a = (1.0 if book else sigma ** 4) / mu ** 4
    return math.sqrt((a + sigma ** 2 / (2 * mu ** 2)) / n)


def boot_se(reps, center=None):
    """Bootstrap standard error: sqrt(mean((tau*_b - c)^2)); c is the mean of the replications (usual)
    or, with center given, the original estimate (as printed in Example 9.30)."""
    reps = np.asarray(reps, float)
    c = reps.mean() if center is None else center
    return math.sqrt(np.mean((reps - c) ** 2))


EX93_DATA = np.array([3.23, -2.50, 1.88, -0.68, 4.43, 0.17, 1.03, -0.07, -0.01, 0.76, 1.76, 3.18,
                      0.33, -0.31, 0.30, -0.61, 1.52, 5.43, 1.54, 2.28, 0.42, 2.33, -1.03, 4.00, 0.39])


def ex93(B=10000, seed=93):
    """Exercise 9.3: the 0.95 quantile tau = mu + z_.05 sigma of a Normal model. MLE, delta-method se
    sqrt((sigma^2 + z^2 sigma^2 / 2)/n) and parametric-bootstrap se."""
    x = EX93_DATA
    n = len(x)
    mu, sig = x.mean(), x.std()
    z = stats.norm.ppf(0.95)
    tau = mu + z * sig
    se_delta = sig * math.sqrt((1 + z * z / 2) / n)
    rng = np.random.default_rng(seed)
    Xs = rng.normal(mu, sig, (B, n))
    taus = Xs.mean(1) + z * Xs.std(1)
    return dict(n=n, mu=mu, sigma=sig, tau=tau, se_delta=se_delta, se_boot=boot_se(taus), reps=taus)


def ex97(B=10000, seed=97, conf=0.90):
    """Exercise 9.7: psi = p1 - p2 with n1 = n2 = 200, X1 = 160, X2 = 148."""
    n1 = n2 = 200
    x1, x2 = 160, 148
    p1, p2 = x1 / n1, x2 / n2
    psi = p1 - p2
    se = math.sqrt(p1 * (1 - p1) / n1 + p2 * (1 - p2) / n2)
    z = stats.norm.ppf(0.5 + conf / 2)
    rng = np.random.default_rng(seed)
    reps = rng.binomial(n1, p1, B) / n1 - rng.binomial(n2, p2, B) / n2
    seb = boot_se(reps)
    return dict(psi=psi, se=se, ci_delta=(psi - z * se, psi + z * se), se_boot=seb,
                ci_boot=(psi - z * seb, psi + z * seb), ci_pct=tuple(np.quantile(reps, [0.05, 0.95])))


def ex99(mu=5.0, n=100, B=10000, seed=99):
    """Exercise 9.9: theta = e^mu with N(mu, 1) data, n = 100. Delta method, parametric and nonparametric
    bootstrap, and the true sampling distribution of exp(Xbar) (lognormal, known exactly)."""
    rng = np.random.default_rng(seed)
    x = rng.normal(mu, 1.0, n)
    xb = x.mean()
    th = math.exp(xb)
    se_delta = th / math.sqrt(n)
    par = np.exp(rng.normal(xb, 1.0, (B, n)).mean(1))
    nonpar = np.exp(x[rng.integers(0, n, (B, n))].mean(1))
    true = np.exp(rng.normal(mu, 1.0 / math.sqrt(n), 200000))
    z = Z95
    return dict(x=x, theta=th, se_delta=se_delta, ci_delta=(th - z * se_delta, th + z * se_delta),
                se_par=boot_se(par), se_nonpar=boot_se(nonpar), par=par, nonpar=nonpar, true=true,
                ci_par=tuple(np.quantile(par, [0.025, 0.975])), ci_nonpar=tuple(np.quantile(nonpar, [0.025, 0.975])),
                se_true=math.exp(mu) * math.sqrt((math.exp(1 / n) - 1) * math.exp(1 / n)))


def ex910(n=50, B=20000, seed=910):
    """Exercise 9.10: Uniform(0, 1), n = 50, thetahat = max. Parametric and nonparametric bootstrap."""
    rng = np.random.default_rng(seed)
    x = rng.uniform(0, 1, n)
    th = x.max()
    par = th * rng.uniform(0, 1, (B, n)).max(1)
    nonpar = x[rng.integers(0, n, (B, n))].max(1)
    return dict(x=x, theta=th, par=par, nonpar=nonpar, p_atom=np.mean(nonpar == th),
                p_atom_exact=1 - (1 - 1 / n) ** n)


# =========================================================================== 9.13.2 sufficiency, Rao-Blackwell
def poisson_zero_estimators(lam, n):
    """Estimators of psi = P(X = 0) = e^(-lambda) from n Poisson(lambda) observations, S = sum X:
    naive 1{X_1 = 0} (unbiased), its Rao-Blackwellisation E(1{X_1 = 0} | S) = (1 - 1/n)^S (unbiased),
    and the MLE exp(-S/n). Returns exact variances / MSEs and the Cramer-Rao bound lambda e^(-2 lambda)/n."""
    lam = np.asarray(lam, float)
    psi = np.exp(-lam)
    var_naive = psi * (1 - psi)
    var_rb = np.exp(-2 * lam) * (np.exp(lam / n) - 1)
    # MLE: E exp(-t S) = exp(n lam (e^-t - 1)) with t = 1/n
    m1 = np.exp(n * lam * (np.exp(-1 / n) - 1))
    m2 = np.exp(n * lam * (np.exp(-2 / n) - 1))
    mse_mle = m2 - 2 * psi * m1 + psi ** 2
    cr = lam * np.exp(-2 * lam) / n
    return dict(naive=var_naive, rb=var_rb, mle=mse_mle, cr=cr)


# =========================================================================== 9.13.4 Newton-Raphson and EM
def mix2_tau(y, m0, m1, s=1.0, p=0.5):
    """Posterior probability that y came from component 1 in p N(m1, s^2) + (1-p) N(m0, s^2)."""
    a = p * np.exp(-0.5 * ((y - m1) / s) ** 2)
    b = (1 - p) * np.exp(-0.5 * ((y - m0) / s) ** 2)
    return a / (a + b)


def mix2_loglik(y, m0, m1, s=1.0, p=0.5):
    """Log-likelihood of Example 9.50 (constants included); m0, m1 may be arrays of the same shape."""
    y = np.asarray(y, float)
    m0, m1 = np.broadcast_arrays(np.asarray(m0, float), np.asarray(m1, float))
    a = np.log(p) - 0.5 * ((y[..., :] - m1[..., None]) / s) ** 2
    b = np.log(1 - p) - 0.5 * ((y[..., :] - m0[..., None]) / s) ** 2
    mx = np.maximum(a, b)
    return (mx + np.log(np.exp(a - mx) + np.exp(b - mx))).sum(-1) - len(y) * (np.log(s) + 0.5 * np.log(2 * np.pi))


def mix2_grad_hess(y, m0, m1, s=1.0, p=0.5):
    t = mix2_tau(y, m0, m1, s, p)
    r0, r1 = y - m0, y - m1
    g = np.array([np.sum((1 - t) * r0), np.sum(t * r1)]) / s ** 2
    w = t * (1 - t)
    H = np.array([[np.sum(-(1 - t) / s ** 2 + w * r0 ** 2 / s ** 4), -np.sum(w * r0 * r1) / s ** 4],
                  [-np.sum(w * r0 * r1) / s ** 4, np.sum(-t / s ** 2 + w * r1 ** 2 / s ** 4)]])
    return g, H


def mix2_em_step(y, m0, m1, s=1.0, p=0.5):
    """One EM step for Example 9.50 (weights p fixed, common known s): responsibility-weighted means."""
    t = mix2_tau(y, m0, m1, s, p)
    return np.sum((1 - t) * y) / np.sum(1 - t), np.sum(t * y) / np.sum(t)


def mix2_newton_step(y, m0, m1, s=1.0, p=0.5):
    g, H = mix2_grad_hess(y, m0, m1, s, p)
    d = np.linalg.solve(H, g)
    return m0 - d[0], m1 - d[1]


def run_iter(step, th0, maxit=200, tol=1e-12, blow=1e6):
    """Iterate a map until the step is below tol, or it blows up; returns the path (a list of tuples)."""
    path = [tuple(np.atleast_1d(np.asarray(th0, float)))]
    th = th0
    for _ in range(maxit):
        try:
            new = step(*np.atleast_1d(th)) if np.ndim(th) else step(th)
        except np.linalg.LinAlgError:
            break
        new_t = tuple(np.atleast_1d(np.asarray(new, float)))
        if not np.all(np.isfinite(new_t)) or max(abs(v) for v in new_t) > blow:
            path.append(new_t)
            break
        path.append(new_t)
        if max(abs(a - b) for a, b in zip(new_t, path[-2])) < tol:
            break
        th = new
    return path


def mix2_em_rate(y, m0, m1, s=1.0, p=0.5):
    """Rate of EM at a fixed point: the spectral radius of I - I_com^-1 I_obs (Dempster, Laird and
    Rubin 1977), with I_com = diag(sum(1 - tau), sum(tau))/s^2 and I_obs = -Hessian."""
    t = mix2_tau(y, m0, m1, s, p)
    _, H = mix2_grad_hess(y, m0, m1, s, p)
    Icom = np.diag([np.sum(1 - t), np.sum(t)]) / s ** 2
    Mjac = np.eye(2) - np.linalg.solve(Icom, -H)
    return float(np.max(np.abs(np.linalg.eigvals(Mjac))))


# right-censored Normal(mu, 1) data, censored at c: observed y_i = min(x_i, c), m = number censored
def mills(t):
    """Inverse Mills ratio phi(t) / (1 - Phi(t)), with the demo kit's Phi."""
    return phi(t) / js_upper(t)


def cens_loglik(mu, yobs, m, c):
    mu = np.asarray(mu, float)
    ll = -0.5 * ((np.asarray(yobs)[None, :] - np.atleast_1d(mu)[:, None]) ** 2).sum(1)
    up = np.array([js_upper(c - v) for v in np.atleast_1d(mu)])
    return ll + m * np.log(up) - len(yobs) * 0.5 * math.log(2 * math.pi)


def cens_score_info(mu, yobs, m, c):
    t = c - mu
    lam = mills(t)
    sc = float(np.sum(np.asarray(yobs) - mu)) + m * lam
    info = len(yobs) + m * lam * (lam - t)        # observed information -l''(mu)
    return sc, info


def cens_newton_step(mu, yobs, m, c):
    sc, info = cens_score_info(mu, yobs, m, c)
    return mu + sc / info


def cens_em_step(mu, yobs, m, c):
    """E-step: E(X | X > c; mu) = mu + mills(c - mu); M-step: the average of the completed data."""
    n = len(yobs) + m
    return (float(np.sum(yobs)) + m * (mu + mills(c - mu))) / n


def cens_em_rate(mu, yobs, m, c):
    """EM rate = fraction of missing information 1 - I_obs / I_com, with I_com = n."""
    _, info = cens_score_info(mu, yobs, m, c)
    return 1.0 - info / (len(yobs) + m)


def em_mixture5(y, th0, iters=200):
    """EM for the five-parameter mixture of Example 9.49, f = (1-p) N(mu0, s0^2) + p N(mu1, s1^2).
    Returns the path of parameters and of log-likelihoods."""
    y = np.asarray(y, float)
    mu0, s0, mu1, s1, p = th0
    path, lls = [], []
    for _ in range(iters + 1):
        a = p * stats.norm.pdf(y, mu1, s1)
        b = (1 - p) * stats.norm.pdf(y, mu0, s0)
        lls.append(float(np.sum(np.log(a + b))))
        path.append((mu0, s0, mu1, s1, p))
        t = a / (a + b)
        p = t.mean()
        mu1 = np.sum(t * y) / t.sum()
        mu0 = np.sum((1 - t) * y) / (1 - t).sum()
        s1 = math.sqrt(np.sum(t * (y - mu1) ** 2) / t.sum())
        s0 = math.sqrt(np.sum((1 - t) * (y - mu0) ** 2) / (1 - t).sum())
    return np.array(path), np.array(lls)


def faithful():
    """Old Faithful eruptions (minutes) and waiting times (minutes), the book's faithful.dat."""
    lines = open(common.aos_file("faithful.dat")).read().splitlines()
    i = next(k for k, l in enumerate(lines) if l.split() == ["eruptions", "waiting"])
    rows = [l.split() for l in lines[i + 1:] if l.strip()]
    A = np.array([[float(r[1]), float(r[2])] for r in rows])
    return A[:, 0], A[:, 1]


# =========================================================================== the demonstrations
def demo_sample(rng, model, th, n):
    """One sample drawn exactly as the demos draw it (mle-efficiency-demo, wald-interval-demo)."""
    if model == "bern":
        return [1.0 if rng.u() < th else 0.0 for _ in range(n)]
    if model == "pois":
        out = []
        for _ in range(n):
            u, k, pk = rng.u(), 0, math.exp(-th)
            F = pk
            while u > F and k < 1000:
                k += 1
                pk *= th / k
                F += pk
            out.append(float(k))
        return out
    if model == "expo":
        return [rng.exp(1.0 / th) for _ in range(n)]
    if model in ("normsd",):
        return [th * rng.norm() for _ in range(n)]
    if model in ("normal", "probit"):
        return [th + rng.norm() for _ in range(n)]
    if model == "cauchy":
        return [th + math.tan(math.pi * (rng.u() - 0.5)) for _ in range(n)]
    if model == "gamma":           # shape 2 (integer), scale 1: a sum of two exponentials
        return [-math.log(rng.pos()) - math.log(rng.pos()) for _ in range(n)]
    if model == "uniform":
        return [th * rng.u() for _ in range(n)]
    raise ValueError(model)


def _median(x):
    s = sorted(x)
    n = len(s)
    return s[n // 2] if n % 2 else 0.5 * (s[n // 2 - 1] + s[n // 2])


def cauchy_mle_demo(x):
    """The demo's Cauchy MLE: Newton from the median; when the curvature is not negative or the
    log-likelihood would drop, a weighted-mean (EM) step, which never decreases it."""
    th = _median(x)

    def ll(t):
        return -sum(math.log1p((v - t) ** 2) for v in x)

    for _ in range(60):
        s = h = sw = swx = 0.0
        for v in x:
            u = v - th
            d = 1 + u * u
            s += 2 * u / d
            h += 2 * (u * u - 1) / (d * d)
            sw += 1 / d
            swx += v / d
        em = swx / sw
        new = th - s / h if h < 0 else em
        if ll(new) < ll(th):
            new = em
        if abs(new - th) < 1e-10:
            th = new
            break
        th = new
    return th


def gamma_mle_demo(x):
    """The demo's Gamma-shape MLE: Newton on log a - psi(a) = log mean - mean log (series psi, psi')."""
    n = len(x)
    m = sum(x) / n
    s = math.log(m) - sum(math.log(v) for v in x) / n
    a = (3 - s + math.sqrt((s - 3) ** 2 + 24 * s)) / (12 * s)
    for _ in range(50):
        f = math.log(a) - digamma_series(a) - s
        fp = 1 / a - trigamma_series(a)
        new = a - f / fp
        if new <= 0:
            new = a / 2
        if abs(new - a) < 1e-10 * new:
            a = new
            break
        a = new
    return a


EFF_MODELS = {
    # model: (true theta, target, 1/I or None, competitor's asymptotic variance)
    "normal": (0.0, 0.0, 1.0, math.pi / 2),
    "cauchy": (0.0, 0.0, 2.0, math.pi ** 2 / 4),
    "gamma": (2.0, 2.0, 2.0 / (2.0 * (math.pi ** 2 / 6 - 1) - 1), 2 * 2.0 * 3.0),
    "probit": (0.5, None, None, None),
    "uniform": (1.0, 1.0, None, 1.0 / 3.0),
}


def demo_estimators(model, x):
    """(MLE, competitor) as computed by the efficiency demo."""
    n = len(x)
    if model == "normal":
        return sum(x) / n, _median(x)
    if model == "cauchy":
        return cauchy_mle_demo(x), _median(x)
    if model == "gamma":
        m = sum(x) / n
        v = sum((t - m) ** 2 for t in x) / n
        return gamma_mle_demo(x), m * m / v
    if model == "probit":
        return js_pnorm(sum(x) / n), sum(1.0 for t in x if t > 0) / n
    if model == "uniform":
        return max(x), 2 * sum(x) / n
    raise ValueError(model)


def eff_target(model):
    th = EFF_MODELS[model][0]
    return js_pnorm(th) if model == "probit" else th


def eff_limits(model):
    """(asymptotic variance of the MLE = 1/I, of the competitor); None when there is none."""
    if model == "probit":
        th = EFF_MODELS[model][0]
        P = js_pnorm(th)
        return phi(th) ** 2, P * (1 - P)
    return EFF_MODELS[model][2], EFF_MODELS[model][3]


def demo_eff_run(model, n, R, seed):
    """The efficiency demo at sample size n: R samples from DK.rng(seed * 7919 + n); returns the arrays of
    sqrt(n)(estimate - target) for the MLE and for the competitor."""
    rng = JSRandom(seed * 7919 + n)
    th0 = EFF_MODELS[model][0]
    tgt = eff_target(model)
    a, b = [], []
    for _ in range(R):
        x = demo_sample(rng, model, th0, n)
        e1, e2 = demo_estimators(model, x)
        a.append(math.sqrt(n) * (e1 - tgt))
        b.append(math.sqrt(n) * (e2 - tgt))
    return np.array(a), np.array(b)


def demo_wald_sample(model, th, n, seed):
    """The Wald demo's sample: DK.rng(seed); returns the sufficient statistic (sum x, or sum x^2)."""
    rng = JSRandom(seed)
    x = demo_sample(rng, model, th, n)
    return float(sum(v * v for v in x)) if model == "normsd" else float(sum(x))


def demo_newton_em_data(kind, n, par, seed):
    """Data of the Newton/EM demo. kind 'cens': N(1, 1) draws censored at c = par (returns observed
    values and the number censored); kind 'mix': half N(0, 1), half N(par, 1), the label drawn by u < 1/2."""
    rng = JSRandom(seed)
    if kind == "cens":
        x = [1.0 + rng.norm() for _ in range(n)]
        yobs = [v for v in x if v <= par]
        return np.array(yobs), n - len(yobs)
    y = []
    for _ in range(n):
        z = rng.u() < 0.5
        y.append((par if z else 0.0) + rng.norm())
    return np.array(y), None


FAITHFUL_S = 0.4        # the known component sd used for the Old Faithful eruptions in the Newton/EM demo


def demo_newton_em(kind, start, n=100, par=1.5, seed=1):
    """The Newton/EM demo: data (kind 'cens', 'mix' or 'faithful'), the EM and Newton paths from start,
    the reference MLE (EM from a default start, polished by Newton steps), the iterations each method
    needs to come within 1e-8 of it, the EM rate predicted by the missing information, and the status of
    Newton's method. Mirrors the JavaScript of newton-em-demo.html."""
    if kind == "cens":
        yobs, m = demo_newton_em_data("cens", n, par, seed)
        c = par
        em_step = lambda mu: cens_em_step(mu, yobs, m, c)
        nt_step = lambda mu: cens_newton_step(mu, yobs, m, c)
        ref0 = float(np.mean(yobs))
    else:
        if kind == "mix":
            y, _ = demo_newton_em_data("mix", n, par, seed)
            sd = 1.0
        else:
            y = faithful()[0]
            sd = FAITHFUL_S
        em_step = lambda a, b: mix2_em_step(y, a, b, sd)
        nt_step = lambda a, b: mix2_newton_step(y, a, b, sd)
        ys = np.sort(y)
        ref0 = (ys[int(0.25 * (len(y) - 1))], ys[int(0.75 * (len(y) - 1))])
    ref = run_iter(em_step, ref0, maxit=5000, tol=1e-14)[-1]
    for _ in range(3):
        ref = tuple(np.atleast_1d(nt_step(*ref)))
    ref = np.array(ref)
    em = np.array(run_iter(em_step, start, maxit=500, tol=1e-12))
    nt = np.array(run_iter(nt_step, start, maxit=100, tol=1e-12))

    def dist(P):
        d = np.max(np.abs(P - ref), 1)
        if kind != "cens":
            d = np.minimum(d, np.max(np.abs(P - ref[::-1]), 1))
        return d

    de, dn = dist(em), dist(nt)
    first = lambda d: int(np.argmax(d < 1e-8)) if np.any(d < 1e-8) else None
    rate = cens_em_rate(ref[0], yobs, m, c) if kind == "cens" else mix2_em_rate(y, ref[0], ref[1], sd)
    return dict(ref=ref, em=em, nt=nt, de=de, dn=dn, it_em=first(de), it_nt=first(dn), rate=rate)


# =========================================================================== exports
def export_json():
    """Old Faithful data for the Newton/EM demo (eruption durations and waiting times)."""
    e, w = faithful()
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch09-faithful.json")
    with open(path, "w") as f:
        json.dump({"source": "Old Faithful geyser, faithful.dat from the book's website (Wasserman 2004)",
                   "eruptions": [round(float(v), 3) for v in e], "waiting": [int(v) for v in w]},
                  f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    return path


# ==== FIGURES
def _uniform_data(n=10):
    """Ten Uniform(0, 1) observations whose maximum is near 0.95, as in the book's figure: the first seed
    of numpy's default generator (counting from 0) that gives 0.93 < max < 0.97."""
    for seed in range(1000):
        x = np.random.default_rng(seed).uniform(0, 1, n)
        if 0.93 < x.max() < 0.97:
            return np.sort(x), seed
    raise RuntimeError


def fig_9_1(out_dir=None):
    """Figure 9.1: the Bernoulli likelihood for n = 20 and 12 successes."""
    n, S = 20, 12
    p = np.linspace(0, 1, 801)
    L = bernoulli_lik(p, S, n)
    fig, ax = common.plt.subplots(figsize=(5.2, 2.9))
    ax.plot(p, L / L.max(), color="k", lw=1.8)
    ax.annotate(r"$\widehat p_n=0.6$", xy=(0.6, 0.02), xytext=(0.6, 0.45), ha="center",
                arrowprops=dict(arrowstyle="->", lw=1.2))
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1.05)
    ax.set_xlabel("$p$")
    ax.set_ylabel(r"$\mathcal{L}_n(p)/\mathcal{L}_n(\widehat p_n)$")
    ax.set_title(r"Bernoulli likelihood, $n=20$, $\sum_i X_i=12$")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-1", out_dir)


def fig_9_2(out_dir=None):
    """Figure 9.2: the Uniform(0, theta) density for theta = 0.75, 1, 1.25, and the likelihood."""
    x, _ = _uniform_data()
    n = len(x)
    fig, axes = common.panel_grid(2, 2, size=(2.9, 2.35))
    t = np.linspace(0, 2, 801)
    for ax, th in zip(axes.flat[:3], (0.75, 1.0, 1.25)):
        ax.plot(t, np.where(t <= th, 1 / th, 0.0), color="k", lw=1.6)
        bad = x > th
        ax.vlines(x[~bad], 0, 0.5, color=BLUE, lw=0.9, linestyles="dashed")
        ax.vlines(x[bad], 0, 0.5, color=RED, lw=1.3)
        ax.plot(x, np.full(n, 0.5), "o", ms=3.5, mfc="white", mec="k", mew=0.8)
        ax.set_ylim(0, 1.5)
        ax.set_xlabel("$x$")
        ax.set_ylabel(r"$f(x;\theta)$")
        ax.set_title(r"$\theta=%g$" % th + ("" if not bad.any() else r": $f(X_{(n)};\theta)=0$"))
    ax = axes[1, 1]
    th = np.linspace(0.6, 1.5, 901)
    ax.plot(th, uniform_lik(th, x), color="k", lw=1.6)
    ax.axvline(x.max(), color=GREY, lw=0.8, ls=":")
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"$\mathcal{L}_n(\theta)$")
    ax.set_title(r"likelihood, max at $X_{(n)}=%.3f$" % x.max())
    fig.tight_layout()
    return savefig(fig, CH, "fig9-2", out_dir)


def fig_9_s1(out_dir=None):
    """Figure 9.S1: method of moments against maximum likelihood for the Gamma shape (Theorem 9.6)."""
    alpha, beta = 2.0, 1.0
    rng = np.random.default_rng(91)
    am_lim = mom_avar(alpha, beta)[0, 0]
    am_book = mom_avar(alpha, beta, book=True)[0, 0]
    al_lim = np.linalg.inv(gamma_fisher(alpha, beta))[0, 0]
    fig, axes = common.panel_grid(1, 2, size=(3.6, 2.8))
    ax = axes[0, 0]
    n, R = 100, 4000
    X = rng.gamma(alpha, beta, (R, n))
    a_mom, _ = gamma_mom(X)
    a_mle, _, _ = gamma_mle(X)
    bins = np.linspace(-12, 14, 66)
    ax.hist(np.sqrt(n) * (a_mom - alpha), bins=bins, density=True, color=ORANGE, alpha=0.45, label="moments")
    ax.hist(np.sqrt(n) * (a_mle - alpha), bins=bins, density=True, color=BLUE, alpha=0.45, label="MLE")
    u = np.linspace(-12, 14, 400)
    ax.plot(u, stats.norm.pdf(u, 0, math.sqrt(am_lim)), color=ORANGE, lw=1.3)
    ax.plot(u, stats.norm.pdf(u, 0, math.sqrt(al_lim)), color=BLUE, lw=1.3)
    ax.set_xlabel(r"$\sqrt{n}(\widehat\alpha-\alpha)$, $n=100$")
    ax.set_ylabel("density")
    ax.set_title(r"Gamma($\alpha=2$, $\beta=1$): shape estimates")
    ax.legend(fontsize=7.5, frameon=False, loc="upper right")
    common.panel_label(ax, "a")
    ax = axes[0, 1]
    ns = np.array([10, 20, 50, 100, 200, 500, 1000])
    vm, vl = [], []
    for m in ns:
        Xm = rng.gamma(alpha, beta, (4000, m))
        vm.append(m * np.mean((gamma_mom(Xm)[0] - alpha) ** 2))
        vl.append(m * np.mean((gamma_mle(Xm)[0] - alpha) ** 2))
    ax.semilogx(ns, vm, "o-", color=ORANGE, ms=4, label="moments (simulated)")
    ax.semilogx(ns, vl, "s-", color=BLUE, ms=4, label="MLE (simulated)")
    ax.axhline(am_lim, color=ORANGE, ls="--", lw=1, label=r"$\Sigma_{11}=2\alpha(\alpha+1)=%g$" % am_lim)
    ax.axhline(al_lim, color=BLUE, ls="--", lw=1, label=r"$(I^{-1})_{11}=%.2f$" % al_lim)
    ax.axhline(am_book, color=GREY, ls=":", lw=1.2, label=r"with $\mathbb{E}(YY^T)$: %g" % am_book)
    ax.set_ylim(0, 52)
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$n\,\mathbb{E}(\widehat\alpha-\alpha)^2$")
    ax.set_title("scaled mean squared error")
    ax.legend(fontsize=6.8, frameon=False, loc="center right")
    common.panel_label(ax, "b")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S1", out_dir)


def fig_9_s2(out_dir=None):
    """Figure 9.S2: consistency of the MLE for the Cauchy location (Theorem 9.13)."""
    rng = np.random.default_rng(92)
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.7))
    ax = axes[0, 0]
    th = np.linspace(-8, 8, 641)
    x = rng.standard_cauchy(500)
    for m, col in ((5, ORANGE), (50, GREEN), (500, BLUE)):
        ax.plot(th, cauchy_Mn(th, x[:m]), color=col, lw=1.2, label="$n=%d$" % m)
    ax.plot(th, -cauchy_kl(0.0, th), color="k", lw=1.8, label=r"$-D(\theta_\star,\theta)$")
    ax.set_ylim(-3.6, 0.8)
    ax.set_xlabel(r"$\theta$ ($\theta_\star=0$)")
    ax.set_ylabel(r"$M_n(\theta)$")
    ax.set_title(r"$M_n$ and its limit")
    ax.legend(fontsize=7, frameon=False, loc="lower center", ncol=2)
    common.panel_label(ax, "a")
    ax = axes[0, 1]
    ns = np.array([5, 10, 20, 50, 100, 200, 500, 1000, 2000])
    g = np.linspace(-8, 8, 161)
    M = -cauchy_kl(0.0, g)
    qs = []
    for m in ns:
        X = rng.standard_cauchy((100, m))
        sups = [np.max(np.abs(cauchy_Mn(g, X[r]) - M)) for r in range(100)]
        qs.append(np.quantile(sups, [0.1, 0.5, 0.9]))
    qs = np.array(qs)
    ax.fill_between(ns, qs[:, 0], qs[:, 2], color=BLUE, alpha=0.2, lw=0)
    ax.loglog(ns, qs[:, 1], "o-", color=BLUE, ms=3.5, label="median of 100 samples")
    ax.loglog(ns, qs[0, 1] * np.sqrt(ns[0] / ns), "--", color=GREY, lw=1, label=r"slope $-1/2$")
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$\sup_{|\theta|\leq 8}|M_n(\theta)-M(\theta)|$")
    ax.set_title("uniform convergence (9.7)")
    ax.legend(fontsize=7, frameon=False, loc="lower left")
    common.panel_label(ax, "b", loc="upper right")
    ax = axes[0, 2]
    bins = np.linspace(-3, 3, 61)
    u = np.linspace(-3, 3, 400)
    for m, col in ((10, ORANGE), (40, GREEN), (160, BLUE)):
        est = cauchy_mle(rng.standard_cauchy((3000, m)))
        ax.hist(est, bins=bins, density=True, histtype="step", color=col, lw=1.2, label="$n=%d$" % m)
        ax.plot(u, stats.norm.pdf(u, 0, math.sqrt(2 / m)), color=col, lw=0.8, ls="--")
    ax.set_xlabel(r"$\widehat\theta_n$")
    ax.set_ylabel("density")
    ax.set_title("the MLE concentrates")
    ax.legend(fontsize=7, frameon=False, loc="upper left")
    common.panel_label(ax, "c", loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S2", out_dir)


def fig_9_s3(out_dir=None):
    """Figure 9.S3: asymptotic normality of the MLE and the exact coverage of Wald intervals."""
    rng = np.random.default_rng(93)
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.7))
    ax = axes[0, 0]
    bins = np.linspace(-5, 4, 73)
    u = np.linspace(-5, 4, 400)
    for m, col in ((10, ORANGE), (100, BLUE)):
        lam = 1.0 / rng.exponential(1.0, (40000, m)).mean(1)
        ax.hist(np.sqrt(m) * (lam - 1) / lam, bins=bins, density=True, histtype="step", color=col, lw=1.3,
                label="$n=%d$" % m)
    ax.plot(u, stats.norm.pdf(u), color="k", lw=1.2, ls="--", label="$N(0,1)$")
    ax.set_xlabel(r"$(\widehat\lambda_n-\lambda)/\widehat{\mathsf{se}}$")
    ax.set_ylabel("density")
    ax.set_title(r"Exponential rate: (9.13)")
    ax.legend(fontsize=7, frameon=False, loc="upper left")
    common.panel_label(ax, "a", loc="upper right")
    ax = axes[0, 1]
    ns = np.unique(np.round(np.logspace(np.log10(5), 3, 40)).astype(int))
    for model, col, lab in (("expo", BLUE, r"rate $\lambda$"), ("normsd", GREEN, r"$\sigma$, Ex. 9.26")):
        ax.semilogx(ns, [wald_coverage(model, 1.0, m, "theta") for m in ns], color=col, lw=1.4, label=lab)
        ax.semilogx(ns, [wald_coverage(model, 1.0, m, "g") for m in ns], color=col, lw=1.4, ls="--",
                    label=lab.split(",")[0] + ", log scale")
    ax.axhline(0.95, color="k", lw=0.7, ls=":")
    ax.set_ylim(0.82, 0.975)
    ax.set_xlabel("$n$")
    ax.set_ylabel("exact coverage")
    ax.set_title("95% Wald intervals")
    ax.legend(fontsize=6.6, frameon=False, loc="lower right")
    common.panel_label(ax, "b", loc="lower left")
    ax = axes[0, 2]
    ps = np.linspace(0.005, 0.995, 397)
    ax.plot(ps, [wald_coverage("bern", p, 50, "theta") for p in ps], color=RED, lw=1.0, label="$p$ scale")
    ax.plot(ps, [wald_coverage("bern", p, 50, "g") for p in ps], color=BLUE, lw=1.0, label="logit scale")
    ax.axhline(0.95, color="k", lw=0.7, ls=":")
    ax.set_ylim(0.5, 1.0)
    ax.set_xlabel("$p$")
    ax.set_ylabel("exact coverage")
    ax.set_title(r"Bernoulli, $n=50$")
    ax.legend(fontsize=7, frameon=False, loc="lower center")
    common.panel_label(ax, "c", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S3", out_dir)


def fig_9_s4(out_dir=None):
    """Figure 9.S4: efficiency (mean against median) and Hodges' superefficient estimator (Section 9.8)."""
    rng = np.random.default_rng(94)
    fig, axes = common.panel_grid(1, 2, size=(3.7, 2.8))
    ax = axes[0, 0]
    ns = np.array([5, 11, 21, 51, 101, 201])
    med_n = [median_nvar(m, 20000, seed=int(m), dist="normal") for m in ns]
    med_c = [median_nvar(m, 20000, seed=1000 + int(m), dist="cauchy") for m in ns]
    mle_c = [m * np.mean(cauchy_mle(rng.standard_cauchy((3000, m))) ** 2) for m in ns]
    ax.semilogx(ns, np.ones(len(ns)), "o-", color=BLUE, ms=3.5, label="Normal: mean (MLE)")
    ax.semilogx(ns, med_n, "s-", color=ORANGE, ms=3.5, label="Normal: median")
    ax.semilogx(ns, mle_c, "o-", color=GREEN, ms=3.5, label="Cauchy: MLE")
    ax.semilogx(ns, med_c, "s-", color=MAGENTA, ms=3.5, label="Cauchy: median")
    for v, col in ((1.0, BLUE), (math.pi / 2, ORANGE), (2.0, GREEN), (math.pi ** 2 / 4, MAGENTA)):
        ax.axhline(v, color=col, lw=0.8, ls="--")
    ax.set_ylim(0.6, 4.2)
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$n\,\mathbb{E}(\widehat\theta_n-\theta)^2$")
    ax.set_title(r"limits $1,\ \pi/2,\ 2,\ \pi^2/4$")
    ax.legend(fontsize=6.6, frameon=False, loc="upper right")
    common.panel_label(ax, "a", loc="upper left")
    ax = axes[0, 1]
    th = np.linspace(-1, 1, 801)
    for m, col in ((10, ORANGE), (100, GREEN), (1000, BLUE), (10000, PURPLE)):
        ax.plot(th, hodges_nmse(th, m), color=col, lw=1.2, label="$n=%d$" % m)
    ax.axhline(1.0, color="k", lw=0.8, ls="--", label=r"$\overline{X}_n$")
    ax.set_ylim(0, 6)
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"$n\,\mathrm{MSE}$")
    ax.set_title("Hodges' estimator")
    ax.legend(fontsize=6.8, frameon=False, loc="upper right")
    common.panel_label(ax, "b", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S4", out_dir)


def fig_9_s5(out_dir=None):
    """Figure 9.S5: delta method, parametric and nonparametric bootstrap (Sections 9.9-9.11, Exercises 9.3, 9.9)."""
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.75))
    r = ex99()
    ax = axes[0, 0]
    lo, hi = np.quantile(r["true"], [0.0005, 0.9995])
    bins = np.linspace(lo, hi, 60)
    wts = np.full(len(r["par"]), 1000.0 / (len(r["par"]) * (bins[1] - bins[0])))
    ax.hist(r["par"], bins=bins, weights=wts, color=BLUE, alpha=0.4, label="parametric")
    ax.hist(r["nonpar"], bins=bins, weights=wts, histtype="step", color=RED, lw=1.2, label="nonparametric")
    u = np.linspace(lo, hi, 400)
    ax.plot(u, 1000 * stats.lognorm.pdf(u, 0.1, scale=math.exp(5.0)), color="k", lw=1.4, label="true")
    ax.plot(u, 1000 * stats.norm.pdf(u, r["theta"], r["se_delta"]), color=GREEN, lw=1.2, ls="--", label="delta")
    ax.set_xlabel(r"$\widehat\theta=e^{\overline{X}}$")
    ax.set_ylabel(r"density $\times 10^3$")
    ax.set_ylim(0, 39)
    ax.set_title(r"Exercise 9.9: $\mu=5$, $n=100$")
    ax.legend(fontsize=6.5, frameon=False, loc="upper right")
    common.panel_label(ax, "a", loc="upper left")
    ax = axes[0, 1]
    rng = np.random.default_rng(95)
    mu, sig = 5.0, 2.0
    ns = np.array([10, 20, 50, 100, 200, 500])
    true_sd, boot = [], []
    for m in ns:
        X = rng.normal(mu, sig, (20000, m))
        true_sd.append(np.sqrt(m) * np.std(X.std(1) / X.mean(1)))
        bs = []
        for d in range(100):
            x = rng.normal(mu, sig, m)
            Xs = rng.normal(x.mean(), x.std(), (1000, m))
            bs.append(boot_se(Xs.std(1) / Xs.mean(1)))
        boot.append(np.sqrt(m) * np.mean(bs))
    ax.semilogx(ns, true_sd, "o-", color="k", ms=3.5, label="true sd")
    ax.semilogx(ns, boot, "s-", color=BLUE, ms=3.5, label="parametric bootstrap")
    ax.axhline(math.sqrt(sig ** 4 / mu ** 4 + sig ** 2 / (2 * mu ** 2)), color=GREEN, ls="--", lw=1.1, label="delta method")
    ax.axhline(math.sqrt(1 / mu ** 4 + sig ** 2 / (2 * mu ** 2)), color=GREY, ls=":", lw=1.3, label=r"with $1/\mu^4$")
    ax.set_ylim(0.2, 0.36)
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$\sqrt{n}\,\mathsf{se}(\widehat\sigma/\widehat\mu)$")
    ax.set_title(r"Example 9.29: $\mu=5$, $\sigma=2$")
    ax.legend(fontsize=6.5, frameon=False, loc="lower right")
    common.panel_label(ax, "b", loc="upper left")
    ax = axes[0, 2]
    e = ex93()
    bins = np.linspace(e["reps"].min(), e["reps"].max(), 55)
    ax.hist(e["reps"], bins=bins, density=True, color=BLUE, alpha=0.45, label="parametric bootstrap")
    u = np.linspace(bins[0], bins[-1], 300)
    ax.plot(u, stats.norm.pdf(u, e["tau"], e["se_delta"]), color=GREEN, lw=1.3, ls="--", label="delta: $N(\\widehat\\tau,\\widehat{\\mathsf{se}}^2)$")
    ax.axvline(e["tau"], color="k", lw=0.8)
    ax.set_xlabel(r"$\widehat\tau^*=\widehat\mu^*+1.645\,\widehat\sigma^*$")
    ax.set_ylabel("density")
    ax.set_title("Exercise 9.3: 95th percentile")
    ax.legend(fontsize=6.5, frameon=False, loc="upper left")
    common.panel_label(ax, "c", loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S5", out_dir)


def fig_9_s6(out_dir=None):
    """Figure 9.S6: the bootstrap for the Uniform maximum (Exercise 9.10)."""
    r = ex910()
    n = 50
    fig, axes = common.panel_grid(1, 2, size=(3.7, 2.8))
    ax = axes[0, 0]
    bins = np.linspace(0.86, 1.0, 57)
    ax.hist(r["par"], bins=bins, density=True, color=BLUE, alpha=0.4, label="parametric")
    w = bins[1] - bins[0]
    ax.hist(r["nonpar"], bins=bins, density=True, histtype="step", color=RED, lw=1.2, label="nonparametric")
    t = np.linspace(0.86, 1.0, 400)
    ax.plot(t, n * t ** (n - 1), color="k", lw=1.4, label=r"true: $n t^{n-1}$")
    ax.axvline(r["theta"], color=GREY, lw=0.8, ls=":")
    ax.set_xlabel(r"$\widehat\theta=X_{(n)}$, $n=50$")
    ax.set_ylabel("density")
    ax.set_title(r"atom: $P(\widehat\theta^*=\widehat\theta)=%.3f$" % r["p_atom"])
    ax.legend(fontsize=6.8, frameon=False, loc="upper left")
    common.panel_label(ax, "a", loc="lower left")
    ax = axes[0, 1]
    ns = np.arange(1, 201)
    ax.semilogx(ns, 1 - (1 - 1 / ns) ** ns, color=RED, lw=1.4, label=r"$1-(1-1/n)^n$")
    ax.axhline(1 - math.exp(-1), color="k", ls="--", lw=0.9, label=r"$1-e^{-1}=0.632$")
    rng = np.random.default_rng(96)
    for m in (2, 5, 10, 20, 50, 100, 200):
        x = rng.uniform(0, 1, m)
        b = x[rng.integers(0, m, (20000, m))].max(1)
        ax.plot(m, np.mean(b == x.max()), "o", color=RED, ms=4, mfc="white")
    ax.set_ylim(0.6, 0.78)
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$P(\widehat\theta^*=\widehat\theta)$")
    ax.set_title("nonparametric bootstrap")
    ax.legend(fontsize=7, frameon=False, loc="upper right")
    common.panel_label(ax, "b", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S6", out_dir)


def fig_9_s7(out_dir=None):
    """Figure 9.S7: Rao-Blackwell and the Cramer-Rao bound, P(X = 0) for Poisson data."""
    fig, axes = common.panel_grid(1, 2, size=(3.7, 2.8))
    ax = axes[0, 0]
    n = 10
    lam = np.linspace(0.05, 5, 300)
    r = poisson_zero_estimators(lam, n)
    ax.semilogy(lam, r["naive"], color=ORANGE, lw=1.4, label=r"$1\{X_1=0\}$")
    ax.semilogy(lam, r["rb"], color=BLUE, lw=1.4, label=r"$(1-1/n)^{S}$ (Rao-Blackwell)")
    ax.semilogy(lam, r["mle"], color=GREEN, lw=1.2, ls="-.", label=r"$e^{-\overline{X}}$ (MLE, MSE)")
    ax.semilogy(lam, r["cr"], color="k", lw=1.0, ls="--", label="Cramér-Rao bound")
    rng = np.random.default_rng(97)
    for l0 in (0.5, 1.0, 2.0, 4.0):
        X = rng.poisson(l0, (200000, n))
        ax.plot(l0, np.var(X[:, 0] == 0), "o", color=ORANGE, ms=4, mfc="white")
        ax.plot(l0, np.var((1 - 1 / n) ** X.sum(1)), "o", color=BLUE, ms=4, mfc="white")
    ax.set_ylim(1e-5, 0.4)
    ax.set_xlabel(r"$\lambda$")
    ax.set_ylabel("variance / MSE")
    ax.set_title(r"estimating $e^{-\lambda}$, $n=10$")
    ax.legend(fontsize=6.5, frameon=False, loc="lower left")
    common.panel_label(ax, "a", loc="upper right")
    ax = axes[0, 1]
    ns = np.unique(np.round(np.logspace(0, 3, 60)).astype(int))
    for l0, col in ((0.5, ORANGE), (2.0, GREEN), (5.0, BLUE)):
        rr = [poisson_zero_estimators(l0, m) for m in ns]
        ax.semilogx(ns, [q["cr"] / q["rb"] for q in rr], color=col, lw=1.4, label=r"$\lambda=%g$" % l0)
    ax.axhline(1.0, color="k", lw=0.7, ls=":")
    ax.set_ylim(0, 1.05)
    ax.set_xlabel("$n$")
    ax.set_ylabel("bound / variance")
    ax.set_title("efficiency of the Rao-Blackwell estimator")
    ax.legend(fontsize=7, frameon=False, loc="lower right")
    common.panel_label(ax, "b", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S7", out_dir)


NE_FIG = dict(n=100, delta=1.5, seed=4, start=(-1.0, 2.0), good=(-0.5, 1.5))


def fig_9_s8(out_dir=None):
    """Figure 9.S8: Newton-Raphson and EM (Section 9.13.4, Examples 9.49 and 9.50)."""
    fig, axes = common.panel_grid(2, 2, size=(3.7, 2.9))
    y, _ = demo_newton_em_data("mix", NE_FIG["n"], NE_FIG["delta"], NE_FIG["seed"])
    st = NE_FIG["start"]
    em = np.array(run_iter(lambda a, b: mix2_em_step(y, a, b), st, maxit=2000))
    nt_bad = np.array(run_iter(lambda a, b: mix2_newton_step(y, a, b), st, maxit=100))
    nt = np.array(run_iter(lambda a, b: mix2_newton_step(y, a, b), NE_FIG["good"], maxit=100))
    mle = em[-1]
    for _ in range(3):                      # polish the reference value with Newton steps
        mle = np.array(mix2_newton_step(y, *mle))
    ax = axes[0, 0]
    g0 = np.linspace(-1.5, 2.5, 161)
    g1 = np.linspace(-1.5, 2.5, 161)
    A, B = np.meshgrid(g0, g1)
    L = mix2_loglik(y, A, B)
    lv = L.max() - np.array([60, 40, 25, 15, 8, 4, 2, 1, 0.3])
    ax.contour(A, B, L, levels=lv, colors=GREY, linewidths=0.6)
    ax.plot(em[:, 0], em[:, 1], "o-", color=ORANGE, ms=2.5, lw=1.0, label="EM (%d steps)" % (len(em) - 1))
    ax.plot(nt[:, 0], nt[:, 1], "s-", color=BLUE, ms=3, lw=1.0, label="Newton (%d steps)" % (len(nt) - 1))
    ax.plot(nt_bad[:, 0], nt_bad[:, 1], "s--", color=PURPLE, ms=3, lw=1.0, label="Newton: a saddle point")
    ax.plot(mle[0], mle[1], "*", color=RED, ms=9)
    ax.plot(mle[1], mle[0], "*", color=RED, ms=9, mfc="white")
    ax.set_xlabel(r"$\mu_0$")
    ax.set_ylabel(r"$\mu_1$")
    ax.set_title(r"Example 9.50: $\ell(\mu_0,\mu_1)$, $n=%d$" % NE_FIG["n"])
    ax.legend(fontsize=6.5, frameon=False, loc="lower left")
    common.panel_label(ax, "a", loc="upper right")
    ax = axes[0, 1]
    de = np.max(np.abs(em - mle), 1)
    dn = np.max(np.abs(nt - mle), 1)
    ax.semilogy(np.arange(len(de)), np.maximum(de, 1e-16), "o-", color=ORANGE, ms=2.5, lw=1, label="EM")
    ax.semilogy(np.arange(len(dn)), np.maximum(dn, 1e-16), "s-", color=BLUE, ms=3, lw=1, label="Newton")
    rate = mix2_em_rate(y, *mle)
    j = np.arange(len(de))
    ax.semilogy(j, de[3] * rate ** (j - 3), "--", color="k", lw=0.8, label=r"rate %.2f" % rate)
    ax.set_ylim(1e-14, 10)
    ax.set_xlabel("iteration $j$")
    ax.set_ylabel(r"$\max|\theta^j-\widehat\theta|$")
    ax.set_title("linear against quadratic convergence")
    ax.legend(fontsize=7, frameon=False, loc="upper right")
    common.panel_label(ax, "b", loc="lower left")
    _, w = faithful()
    path, lls = em_mixture5(w, (55.0, 5.0, 80.0, 5.0, 0.5), 300)
    ax = axes[1, 0]
    ax.hist(w, bins=np.arange(40, 100, 2.5), density=True, color=GREY, alpha=0.45)
    t = np.linspace(40, 100, 400)
    mu0, s0, mu1, s1, p = path[-1]
    ax.plot(t, (1 - p) * stats.norm.pdf(t, mu0, s0) + p * stats.norm.pdf(t, mu1, s1), color=RED, lw=1.5)
    ax.plot(t, (1 - p) * stats.norm.pdf(t, mu0, s0), color=BLUE, lw=0.9, ls="--")
    ax.plot(t, p * stats.norm.pdf(t, mu1, s1), color=BLUE, lw=0.9, ls="--")
    ax.set_xlabel("waiting time (minutes)")
    ax.set_ylabel("density")
    ax.set_title("Old Faithful: Example 9.49 by EM")
    common.panel_label(ax, "c", loc="upper left")
    ax = axes[1, 1]
    gap = lls[-1] - lls[:35]
    ax.semilogy(np.arange(35), gap, "o-", color=RED, ms=2.5, lw=1)
    ax.set_xlabel("iteration $j$")
    ax.set_ylabel(r"$\ell(\widehat\theta)-\ell(\theta^j)$")
    ax.set_title("EM never decreases the likelihood")
    common.panel_label(ax, "d", loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-S8", out_dir)


def fig_all_json(out_dir=None):
    """Data file for the Newton/EM demonstration (Old Faithful)."""
    return export_json()


FIGURES = {"9.1": fig_9_1, "9.2": fig_9_2, "9.S1": fig_9_s1, "9.S2": fig_9_s2, "9.S3": fig_9_s3,
           "9.S4": fig_9_s4, "9.S5": fig_9_s5, "9.S6": fig_9_s6, "9.S7": fig_9_s7, "9.S8": fig_9_s8,
           "json": fig_all_json}

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