"""Murphy (2023), Chapter 2: Probability (and Supplementary Chapter 2).

Companion code for Chapter 2 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 5-62 of the book and Supplementary Chapter 2, written from
scratch with numpy, scipy and matplotlib, to be read next to the lecture notes (../ch02-probability.html).

Methods implemented here (everything the chapter computes, not just plotted):
* Section 2.2, distributions: the Student (2.30), Cauchy, Laplace, gamma, beta, Pareto, Dirichlet
  densities written out from their formulas (student_logpdf, laplace_logpdf, gamma_logpdf, ...).
* Section 2.3, Gaussians: moment and information form, marginals and conditionals in both forms
  (mvn_condition, canonical_*), the linear Gaussian system (linear_gaussian_posterior, (2.120)-(2.129)),
  the canonical-potential calculus (potential_*, (2.131)-(2.153)), the product of Gaussians (2.154)-(2.159).
* Section 2.4, exponential family: log partition functions, moment matching, Bregman divergence.
* Section 2.5, transformations: change of variables, Monte Carlo, probability integral transform and
  the Kolmogorov-Smirnov statistic (ks_statistic).
* Section 2.6, Markov chains: stationary distribution by the linear system (2.283) (stationary_dist),
  n-step matrices, maximum likelihood and add-alpha estimation, character n-gram text models (NGram).
* Section 2.7, divergences: f-divergences, the alpha divergence (2.290) and the Gaussian q that
  minimises it (alpha_fit), the MMD with the kernel trick (mmd2, witness), total variation.
* Supplement 2.1: the sensor-fusion posterior with unknown precisions, plug-in and exact
  (sensor_plugin, sensor_exact). Supplement 2.2: PageRank, the power method, damping (pagerank).

Data. Text for Figures 2.5, 2.16 and 2.17: the book uses H. G. Wells, The Time Machine (and the King
James Bible for 2.16). A copy of neither is available offline here, so Lewis Carroll's Alice's
Adventures in Wonderland (public domain, a copy shipped in this course) is the stand-in: the shape of
the curves (a Zipf line, the bigram structure of English) is the same, the numbers differ. All other
figures are simulated with fixed seeds; the 500-site Harvard web graph of Supplementary Figure 2.3 is
not available, so a simulated scale-free web graph stands in.

Figures reproduced: 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.10, 2.12, 2.13, 2.14, 2.16, 2.17, 2.19,
2.20, 2.21, 2.22 and Supplementary 2.1, 2.2, 2.3. Extra figures for gaps filled in the notes: 2.S1
(the Gaussian soap bubble, a computed version of the idea of Figure 2.9), 2.S2 (convergence of the power
method for PageRank).
Skipped, with the reason:
  2.9   cartoon and a figure from another paper (images sampled from a Gaussian); replaced by 2.S1;
  2.11  injective and surjective functions: a schematic diagram, nothing is computed;
  2.15  state transition diagrams of two Markov chains: hand-drawn graphs (the matrices are in the text);
  2.18  the two chains' graphs: hand-drawn; their stationary distributions are computed in the notes;
  2.23  summary diagram of the two families of divergence: a schematic.
Run `python3 ch02_probability.py --list`, `python3 ch02_probability.py` (all figures, a minute or two)
or `python3 ch02_probability.py --fig 2.20`. Files go to ../img/ch02/ and ../data/ch02-*.json.
"""
import json
import os
import re
import sys
import textwrap
from collections import Counter, defaultdict

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

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

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import (BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, CYAN, OUT_DIR, ellipse_xy,  # noqa: E402
                    gauss_logpdf, logsumexp, panel_grid, panel_label, plt, run, savefig)

HERE = os.path.dirname(os.path.abspath(__file__))
DATA_JSON = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 2


# ============================================================================ distributions (Section 2.2)
def student_logpdf(x, nu, mu=0.0, sigma=1.0):
    """log of the Student density (2.30)-(2.31)."""
    z = (np.asarray(x, float) - mu) / sigma
    logZ = 0.5 * np.log(nu * np.pi * sigma ** 2) + special.gammaln(nu / 2) - special.gammaln((nu + 1) / 2)
    return -(nu + 1) / 2 * np.log1p(z ** 2 / nu) - logZ


def laplace_logpdf(x, mu=0.0, b=1.0):
    return -np.log(2 * b) - np.abs(np.asarray(x, float) - mu) / b


def gamma_logpdf(x, a, b):
    """Gamma with shape a and rate b (2.38)."""
    x = np.asarray(x, float)
    return a * np.log(b) - special.gammaln(a) + (a - 1) * np.log(x) - b * x


def beta_logpdf(x, a, b):
    x = np.asarray(x, float)
    return (a - 1) * np.log(x) + (b - 1) * np.log1p(-x) - special.betaln(a, b)


def pareto_logpdf(x, m, kappa):
    x = np.asarray(x, float)
    return np.where(x >= m, np.log(kappa) + kappa * np.log(m) - (kappa + 1) * np.log(np.maximum(x, m)), -np.inf)


def dirichlet_logpdf(x, alpha):
    """log Dir(x | alpha) for rows x on the simplex (2.68)-(2.69)."""
    x = np.atleast_2d(x)
    alpha = np.asarray(alpha, float)
    return ((alpha - 1) * np.log(x)).sum(1) - (special.gammaln(alpha).sum() - special.gammaln(alpha.sum()))


def negbin_pmf(x, r, p):
    """(2.25): C(x+r-1, x) (1-p)^r p^x, x = 0, 1, 2, ... (p = success probability, r failures)."""
    x = np.asarray(x)
    return np.exp(special.gammaln(x + r) - special.gammaln(x + 1) - special.gammaln(r) + r * np.log1p(-p) + x * np.log(p))


def wishart_logpdf(S, Sc, nu):
    """log Wi(S | Sc, nu) with the normaliser |Sc|^{nu/2} 2^{nu D/2} Gamma_D(nu/2) (corrected (2.60))."""
    D = Sc.shape[0]
    logZ = 0.5 * nu * np.linalg.slogdet(Sc)[1] + 0.5 * nu * D * np.log(2) + special.multigammaln(nu / 2, D)
    return (0.5 * (nu - D - 1) * np.linalg.slogdet(S)[1] - 0.5 * np.trace(np.linalg.solve(Sc, S)) - logZ)


def invwishart_logpdf(S, Psi, nu):
    """log IW(S | Psi, nu): |S|^{-(nu+D+1)/2} exp(-tr(Psi S^-1)/2) / Z with Z = |Psi|^{-nu/2} 2^{nu D/2} Gamma_D(nu/2)."""
    D = Psi.shape[0]
    logZ = -0.5 * nu * np.linalg.slogdet(Psi)[1] + 0.5 * nu * D * np.log(2) + special.multigammaln(nu / 2, D)
    return (-0.5 * (nu + D + 1) * np.linalg.slogdet(S)[1] - 0.5 * np.trace(np.linalg.solve(S, Psi).T) - logZ)


# ============================================================================ Gaussians (Section 2.3)
def mvn_condition(mu, Sigma, idx1, idx2, x2):
    """Moment-form conditional p(x1 | x2) of (2.78): mean and covariance."""
    S11 = Sigma[np.ix_(idx1, idx1)]
    S12 = Sigma[np.ix_(idx1, idx2)]
    S22 = Sigma[np.ix_(idx2, idx2)]
    K = np.linalg.solve(S22, S12.T).T
    return mu[idx1] + K @ (x2 - mu[idx2]), S11 - K @ S12.T


def to_canonical(mu, Sigma):
    Lam = np.linalg.inv(Sigma)
    return Lam @ mu, Lam


def canonical_condition(eta, Lam, idx1, idx2, x2):
    """(2.86): eta_{1|2} = eta_1 - Lam_12 x_2, Lam_{1|2} = Lam_11."""
    return eta[idx1] - Lam[np.ix_(idx1, idx2)] @ x2, Lam[np.ix_(idx1, idx1)]


def canonical_marginal(eta, Lam, idx1, idx2):
    """(2.84): marginal of x1: eta_1 - Lam_12 Lam_22^-1 eta_2 and Lam_11 - Lam_12 Lam_22^-1 Lam_21."""
    L12 = Lam[np.ix_(idx1, idx2)]
    L22 = Lam[np.ix_(idx2, idx2)]
    return eta[idx1] - L12 @ np.linalg.solve(L22, eta[idx2]), Lam[np.ix_(idx1, idx1)] - L12 @ np.linalg.solve(L22, L12.T)


def linear_gaussian_posterior(mu0, Sig0, W, b, Om, y, form="kalman"):
    """Posterior p(z|y) of the linear Gaussian system (2.118)-(2.129).
    form 'kalman' uses (2.123)-(2.124); 'info' uses (2.127)-(2.128). Returns mean, covariance, log p(y)."""
    m = W @ mu0 + b
    S = W @ Sig0 @ W.T + Om
    C = Sig0 @ W.T
    if form == "kalman":
        K = C @ np.linalg.inv(S)
        mean = mu0 + K @ (y - m)
        cov = Sig0 - K @ C.T
    else:
        cov = np.linalg.inv(np.linalg.inv(Sig0) + W.T @ np.linalg.solve(Om, W))
        mean = cov @ (W.T @ np.linalg.solve(Om, y - b) + np.linalg.solve(Sig0, mu0))
    return mean, cov, stats.multivariate_normal(m, S).logpdf(y)


# canonical potentials phi(x; g, h, K) = exp(g + h'x - x'Kx/2), (2.132)
def potential_from_moment(mu, Sigma):
    K = np.linalg.inv(Sigma)
    h = K @ mu
    g = -0.5 * len(mu) * np.log(2 * np.pi) - 0.5 * np.linalg.slogdet(Sigma)[1] - 0.5 * mu @ K @ mu
    return g, h, K


def potential_eval(pot, x):
    g, h, K = pot
    x = np.asarray(x, float)
    return np.exp(g + h @ x - 0.5 * x @ K @ x)


def potential_marginalise(pot, n1):
    """Integrate out the first n1 variables, (2.139)-(2.142)."""
    g, h, K = pot
    h1, h2 = h[:n1], h[n1:]
    K11, K12, K21, K22 = K[:n1, :n1], K[:n1, n1:], K[n1:, :n1], K[n1:, n1:]
    ghat = g + 0.5 * (n1 * np.log(2 * np.pi) - np.linalg.slogdet(K11)[1] + h1 @ np.linalg.solve(K11, h1))
    return ghat, h2 - K21 @ np.linalg.solve(K11, h1), K22 - K21 @ np.linalg.solve(K11, K12)


def potential_condition(pot, n1, y):
    """Condition on the last variables y, (2.143)-(2.144): potential over the first n1 variables."""
    g, h, K = pot
    return (g + h[n1:] @ y - 0.5 * y @ K[n1:, n1:] @ y, h[:n1] - K[:n1, n1:] @ y, K[:n1, :n1])


def linear_gaussian_cpd_potential(mu, Sigma, B):
    """(2.148)-(2.150): potential of p(x|u) = N(x | mu + B'u, Sigma) over (x, u); B is (dim u) x (dim x)."""
    Si = np.linalg.inv(Sigma)
    n = len(mu)
    g = -0.5 * mu @ Si @ mu - 0.5 * n * np.log(2 * np.pi) - 0.5 * np.linalg.slogdet(Sigma)[1]
    h = np.concatenate([Si @ mu, -B @ Si @ mu])
    K = np.block([[Si, -Si @ B.T], [-B @ Si, B @ Si @ B.T]])
    return g, h, K


def gauss_product(mu1, S1, mu2, S2):
    """(2.154)-(2.158): the Gaussian proportional to N(mu1,S1) N(mu2,S2), and the constant N(mu1|mu2,S1+S2)."""
    S3 = np.linalg.inv(np.linalg.inv(S1) + np.linalg.inv(S2))
    mu3 = S3 @ (np.linalg.solve(S1, mu1) + np.linalg.solve(S2, mu2))
    return mu3, S3, stats.multivariate_normal(mu2, S1 + S2).pdf(mu1)


def sensor_fusion(x, y, Sx, Sy, mu0=None, S0=None):
    """Posterior of z for x ~ N(z, Sx), y ~ N(z, Sy) with a broad prior N(mu0, S0) (default 1e4 I)."""
    d = len(x)
    mu0 = np.zeros(d) if mu0 is None else mu0
    S0 = 1e4 * np.eye(d) if S0 is None else S0
    W = np.vstack([np.eye(d), np.eye(d)])
    Om = np.block([[Sx, np.zeros((d, d))], [np.zeros((d, d)), Sy]])
    return linear_gaussian_posterior(mu0, S0, W, np.zeros(2 * d), Om, np.concatenate([x, y]), "info")[:2]


# --------------------------------------------------------------------------- Supplement 2.1.2
def sensor_plugin(xbar, sx2, ybar, sy2, Nx=2, Ny=2, iters=200):
    """Fixed-point iteration (2.14)-(2.16) for the MLE of (z, 1/lam_x, 1/lam_y); returns the path of
    (z_hat, var_x, var_y) and the final posterior precision lam_N = Nx lam_x + Ny lam_y (2.8)."""
    vx, vy = sx2, sy2
    path = []
    for _ in range(iters):
        lx, ly = 1.0 / vx, 1.0 / vy
        z = (Nx * lx * xbar + Ny * ly * ybar) / (Nx * lx + Ny * ly)
        path.append((z, vx, vy))
        vx = sx2 + (xbar - z) ** 2
        vy = sy2 + (ybar - z) ** 2
    lx, ly = 1.0 / vx, 1.0 / vy
    z = (Nx * lx * xbar + Ny * ly * ybar) / (Nx * lx + Ny * ly)
    return path, z, vx, vy, 1.0 / (Nx * lx + Ny * ly)


def sensor_exact_unnorm(z, xbar, sx2, ybar, sy2, Nx=2, Ny=2):
    """Exact posterior (up to a constant) under p(z) 1, p(lam) 1/lam: ((xbar-z)^2+sx2)^(-Nx/2) * (...)^(-Ny/2) (2.23)."""
    z = np.asarray(z, float)
    return ((xbar - z) ** 2 + sx2) ** (-Nx / 2) * ((ybar - z) ** 2 + sy2) ** (-Ny / 2)


# ============================================================================ exponential family (Section 2.4)
def logpartition_bernoulli(eta):
    return np.logaddexp(0, eta)


def logpartition_gaussian(eta1, eta2):
    return -eta1 ** 2 / (4 * eta2) - 0.5 * np.log(-2 * eta2)


def bregman(A, gradA, l1, l2):
    return A(l1) - A(l2) - (l1 - l2) @ gradA(l2)


# ============================================================================ Markov chains (Section 2.6)
def stationary_dist(A):
    """Solve pi M = r of (2.283): M = [(I - A) without its last column, 1]."""
    K = A.shape[0]
    M = np.hstack([(np.eye(K) - A)[:, :-1], np.ones((K, 1))])
    r = np.zeros(K)
    r[-1] = 1.0
    return np.linalg.solve(M.T, r)


def stationary_eig(A):
    w, v = np.linalg.eig(A.T)
    k = np.argmin(np.abs(w - 1))
    pi = np.real(v[:, k])
    return pi / pi.sum()


A_FIG218A = np.array([[0, 1.0, 0], [0.5, 0, 0.5], [1.0, 0, 0]])
A_FIG218B = np.array([[0.1, 0.9, 0, 0], [0.9, 0.1, 0, 0], [0, 0.5, 0, 0.5], [0, 0, 0, 1.0]])


def two_state(alpha, beta):
    return np.array([[1 - alpha, alpha], [beta, 1 - beta]])


def markov_mle(seqs, K):
    """(2.278): initial distribution and transition matrix from normalised counts."""
    N1 = np.zeros(K)
    Njk = np.zeros((K, K))
    for s in seqs:
        N1[s[0]] += 1
        for a, b in zip(s[:-1], s[1:]):
            Njk[a, b] += 1
    return N1 / N1.sum(), Njk / np.maximum(Njk.sum(1, keepdims=True), 1), Njk


def add_alpha(Njk, alpha):
    """(2.279): (N_jk + alpha) / (N_j + K alpha): the posterior MEAN under Dir(alpha) (add-one for alpha = 1)."""
    K = Njk.shape[1]
    return (Njk + alpha) / (Njk.sum(1, keepdims=True) + K * alpha)


def map_dirichlet(Njk, alpha):
    """The posterior MODE under Dir(alpha 1): (N_jk + alpha - 1) / (N_j + K (alpha - 1))."""
    K = Njk.shape[1]
    return (Njk + alpha - 1) / (Njk.sum(1, keepdims=True) + K * (alpha - 1))


class NGram:
    """Character n-gram model with backoff: counts of the next character after each context of length 0..n-1."""

    def __init__(self, text, n):
        self.n = n
        self.tab = [defaultdict(Counter) for _ in range(n)]
        for i in range(len(text)):
            for k in range(n):
                if i - k >= 0:
                    self.tab[k][text[i - k:i]][text[i]] += 1

    def sample(self, prefix, length, rng):
        out = prefix
        for _ in range(length):
            for k in range(min(self.n - 1, len(out)), -1, -1):
                ctx = out[len(out) - k:] if k > 0 else ""
                c = self.tab[k].get(ctx)
                if c:
                    chars, cnt = zip(*c.items())
                    cnt = np.array(cnt, float)
                    out += chars[rng.choice(len(chars), p=cnt / cnt.sum())]
                    break
        return out


# --------------------------------------------------------------------------- PageRank (Supplement 2.2)
PAGERANK_EDGES = [(1, 2), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 1), (6, 1)]


def google_matrix(edges, n, p=0.85):
    """(2.29): M_ij = p G_ij / c_j + (1-p)/n if c_j > 0, 1/n otherwise (columns sum to one); G_ij = 1 iff link j -> i."""
    G = np.zeros((n, n))
    for i, j in edges:
        G[j - 1, i - 1] = 1.0
    c = G.sum(0)
    M = np.empty((n, n))
    for j in range(n):
        M[:, j] = 1.0 / n if c[j] == 0 else p * G[:, j] / c[j] + (1 - p) / n
    return M, G, c


def pagerank(edges, n, p=0.85, tol=1e-10, maxit=1000, v0=None):
    """Power method for v = M v using only the sparse part, (2.32)-(2.33): v <- p G D v + 1 z'v.
    Returns v and the L1 error path against the eigenvector solution."""
    G = np.zeros((n, n))
    for i, j in edges:
        G[j - 1, i - 1] = 1.0
    c = G.sum(0)
    d = np.where(c > 0, 1.0 / np.maximum(c, 1), 0.0)
    z = np.where(c > 0, (1 - p) / n, 1.0 / n)
    v = np.full(n, 1.0 / n) if v0 is None else v0.copy()
    hist = []
    for it in range(maxit):
        nv = p * (G @ (d * v)) + z @ v
        hist.append(np.abs(nv - v).sum())
        v = nv
        if hist[-1] < tol:
            break
    return v, hist


def scale_free_web(n, m, rng):
    """A simulated web graph: each new page links to m existing pages chosen by in-degree (preferential
    attachment), and each old page occasionally links back. Returns directed edges (i, j), i links to j."""
    edges = set()
    indeg = np.ones(n)
    for i in range(1, n):
        k = min(i, m)
        pr = indeg[:i] / indeg[:i].sum()
        for j in rng.choice(i, size=k, replace=False, p=pr):
            edges.add((i + 1, int(j) + 1))
            indeg[j] += 1
            if rng.random() < 0.25:
                edges.add((int(j) + 1, i + 1))
                indeg[i] += 1
    return sorted(edges)


# ============================================================================ divergences (Section 2.7)
def alpha_div_grid(logp, logq, dx, alpha):
    """Minka's alpha divergence (2.290) on a grid: (1 - int p^a q^(1-a)) / (a (1-a)); KL limits at a = 0, 1."""
    if abs(alpha - 1) < 1e-12:
        return float(np.sum(np.exp(logp) * (logp - logq)) * dx)      # KL(p||q)
    if abs(alpha) < 1e-12:
        return float(np.sum(np.exp(logq) * (logq - logp)) * dx)      # KL(q||p)
    s = logsumexp(alpha * logp + (1 - alpha) * logq) + np.log(dx)
    return float((1 - np.exp(s)) / (alpha * (1 - alpha)))


P_MIX = dict(w=(0.4, 0.6), mu=(-2.5, 2.0), sd=(0.8, 1.0))
XG = np.linspace(-14, 14, 4001)


def mix_logpdf(x, w, mu, sd):
    return logsumexp(np.stack([np.log(wi) + stats.norm.logpdf(x, m, s) for wi, m, s in zip(w, mu, sd)]), axis=0)


def alpha_fit(alpha, pm=P_MIX, grid=XG, starts=((-2.5, 0.8), (2.0, 1.0), (0.0, 3.0), (0.0, 1.0))):
    """Gaussian q = N(m, s^2) minimising D_alpha(p || q) over (m, log s), best of several starts."""
    dx = grid[1] - grid[0]
    logp = mix_logpdf(grid, **pm)

    def obj(t):
        return alpha_div_grid(logp, stats.norm.logpdf(grid, t[0], np.exp(t[1])), dx, alpha)
    best = None
    for m0, s0 in starts:
        r = optimize.minimize(obj, [m0, np.log(s0)], method="Nelder-Mead", options=dict(xatol=1e-7, fatol=1e-12, maxiter=2000))
        if best is None or r.fun < best.fun:
            best = r
    return float(best.x[0]), float(np.exp(best.x[1])), float(best.fun)


def mmd2(X, Y, sigma, unbiased=False):
    """Squared MMD with the Gaussian kernel via the kernel trick (2.304); unbiased drops the diagonals."""
    def k(a, b):
        return np.exp(-0.5 * (np.asarray(a)[:, None] - np.asarray(b)[None, :]) ** 2 / sigma ** 2)
    Kxx, Kyy, Kxy = k(X, X), k(Y, Y), k(X, Y)
    n, m = len(X), len(Y)
    if unbiased:
        return (Kxx.sum() - np.trace(Kxx)) / (n * (n - 1)) + (Kyy.sum() - np.trace(Kyy)) / (m * (m - 1)) - 2 * Kxy.mean()
    return Kxx.mean() + Kyy.mean() - 2 * Kxy.mean()


def witness(t, X, Y, sigma):
    """Empirical witness (mu_P(t) - mu_Q(t)) = mean_n K(t, x_n) - mean_m K(t, y_m)."""
    t = np.asarray(t)
    k = lambda a, b: np.exp(-0.5 * (a[:, None] - np.asarray(b)[None, :]) ** 2 / sigma ** 2)
    return k(t, X).mean(1) - k(t, Y).mean(1)


def ks_statistic(sample, cdf):
    """(2.263): D_n = max |P_n(x) - P(x)|, evaluated at the jumps of the empirical cdf; also the location."""
    x = np.sort(sample)
    n = len(x)
    F = cdf(x)
    up = np.arange(1, n + 1) / n - F
    dn = F - np.arange(0, n) / n
    i1, i2 = np.argmax(up), np.argmax(dn)
    return (float(up[i1]), x[i1], True) if up[i1] >= dn[i2] else (float(dn[i2]), x[i2], False)


# ============================================================================ text data
def alice_text():
    for p in (os.path.join(common.CACHE, "text", "alice_clean.txt"),
              os.path.join(HERE, "..", "..", "pml", "code", "data", "ch15-alice.txt"),
              os.path.join(HERE, "..", "..", "pml", "code", "data", "ch11_alice.txt")):
        if os.path.exists(p):
            t = open(p, encoding="utf-8", errors="ignore").read().lower()
            t = re.sub(r"[^a-z ]+", " ", t)
            return re.sub(r" +", " ", t).strip()
    raise RuntimeError("no stand-in text found")


def _out(out):
    return out or OUT_DIR


def _sv(fig, name, out):
    savefig(fig, CH, name, out_dir=_out(out))


def _dump(name, obj):
    os.makedirs(DATA_JSON, exist_ok=True)
    with open(os.path.join(DATA_JSON, "ch02-" + name + ".json"), "w") as f:
        json.dump(obj, f, separators=(",", ":"))


# ============================================================================ figures
def fig_2_1(out=None):
    """Student, Gaussian and Laplace densities and log densities."""
    x = np.linspace(-4, 4, 801)
    curves = [("Gaussian", stats.norm.logpdf(x), BLUE), ("Student ($\\nu=1$)", student_logpdf(x, 1), RED),
              ("Student ($\\nu=2$)", student_logpdf(x, 2), GREEN), ("Laplace", laplace_logpdf(x, 0, 1 / np.sqrt(2)), MAGENTA)]
    fig, ax = panel_grid(1, 2, size=(3.6, 2.8))
    for lab, lp, c in curves:
        ax[0, 0].plot(x, np.exp(lp), color=c, label=lab)
        ax[0, 1].plot(x, lp, color=c, label=lab)
    ax[0, 0].set_xlabel("x"); ax[0, 0].set_ylabel("pdf"); ax[0, 1].set_xlabel("x"); ax[0, 1].set_ylabel("log pdf")
    ax[0, 1].set_ylim(-8, 0)
    ax[0, 0].legend(); panel_label(ax[0, 0], "a", "upper right"); panel_label(ax[0, 1], "b", "upper right")
    fig.tight_layout(); _sv(fig, "fig2-1", out)


def fig_2_2(out=None):
    """Gaussian, uniform (sub-Gaussian) and Laplace (super-Gaussian), 1-d densities and 2-d samples."""
    rng = np.random.default_rng(2)
    x = np.linspace(-5, 5, 1001)
    a = np.sqrt(3.0)
    fig, ax = panel_grid(1, 4, size=(2.5, 2.5))
    ax[0, 0].plot(x, stats.norm.pdf(x), color=BLUE, label="Gaussian")
    ax[0, 0].plot(x, stats.uniform.pdf(x, -a, 2 * a), color=GREEN, label="Uniform")
    ax[0, 0].plot(x, np.exp(laplace_logpdf(x, 0, 1 / np.sqrt(2))), color=RED, label="Laplace")
    ax[0, 0].set_xlabel("x"); ax[0, 0].set_ylabel("p(x)"); ax[0, 0].legend(fontsize=7)
    n = 600
    for k, (lab, s, c) in enumerate([("Gaussian", rng.standard_normal((n, 2)), BLUE),
                                     ("Laplace", rng.laplace(0, 1 / np.sqrt(2), (n, 2)), RED),
                                     ("Uniform", rng.uniform(-a, a, (n, 2)), GREEN)], start=1):
        ax[0, k].scatter(s[:, 0], s[:, 1], s=4, color=c, alpha=0.6, linewidths=0)
        ax[0, k].set_xlim(-5, 5); ax[0, k].set_ylim(-5, 5); ax[0, k].set_aspect("equal"); ax[0, k].set_title(lab)
    for k, l in enumerate("abcd"):
        panel_label(ax[0, k], l, "upper right" if k == 0 else "lower right")
    fig.tight_layout(); _sv(fig, "fig2-2", out)


def fig_2_3(out=None):
    """Gamma and beta densities."""
    fig, ax = panel_grid(1, 2, size=(3.7, 2.9))
    x = np.linspace(0.001, 7, 700)
    cols = [BLUE, RED, GREEN, MAGENTA, ORANGE, PURPLE]
    for c, (a, b) in zip(cols, [(1, 1), (1.5, 1), (2, 1), (1, 2), (1.5, 2), (2, 2)]):
        ax[0, 0].plot(x, np.exp(gamma_logpdf(x, a, b)), color=c, label="a=%.1f, b=%.1f" % (a, b))
    ax[0, 0].set_ylim(0, 2); ax[0, 0].set_title("Gamma distributions"); ax[0, 0].legend(fontsize=7); ax[0, 0].set_xlabel("x")
    x = np.linspace(0.002, 0.998, 700)
    for c, (a, b) in zip(cols, [(0.1, 0.1), (0.1, 1), (1, 1), (2, 2), (2, 8)]):
        ax[0, 1].plot(x, np.exp(beta_logpdf(x, a, b)), color=c, label="a=%.1f, b=%.1f" % (a, b))
    ax[0, 1].set_ylim(0, 6); ax[0, 1].set_title("Beta distributions"); ax[0, 1].legend(fontsize=7, loc="upper center"); ax[0, 1].set_xlabel("x")
    panel_label(ax[0, 0], "a", "lower right"); panel_label(ax[0, 1], "b", "lower right")
    fig.tight_layout(); _sv(fig, "fig2-3", out)


def fig_2_4(out=None):
    """Pareto densities, linear and log-log axes."""
    fig, ax = panel_grid(1, 2, size=(3.7, 2.9))
    cols = [BLUE, RED, GREEN, MAGENTA]
    x = np.linspace(0.0, 0.5, 2001)
    xl = np.logspace(-1.2, 0.2, 400)
    for c, (m, k) in zip(cols, [(0.1, 1), (0.1, 2), (0.2, 1), (0.2, 2)]):
        lab = "m=%.1f, $\\kappa$=%d" % (m, k)
        ax[0, 0].plot(x, np.exp(pareto_logpdf(np.maximum(x, 1e-9), m, k)) * (x >= m), color=c, label=lab)
        ax[0, 1].loglog(xl, np.exp(pareto_logpdf(xl, m, k)), color=c, label=lab)
    ax[0, 0].set_xlabel("x"); ax[0, 0].set_ylabel("p(x | m, $\\kappa$)"); ax[0, 0].set_ylim(0, 22); ax[0, 0].legend(fontsize=7)
    ax[0, 1].set_xlabel("x"); ax[0, 1].set_ylabel("p(x | m, $\\kappa$)"); ax[0, 1].set_ylim(1e-1, 1e2)
    panel_label(ax[0, 0], "a", "upper right"); panel_label(ax[0, 1], "b", "lower left")
    fig.tight_layout(); _sv(fig, "fig2-4", out)


def zipf_fit(text, skip=10):
    words = text.split()
    cnt = np.array(sorted(Counter(words).values(), reverse=True), float)
    r = np.arange(1, len(cnt) + 1)
    sl = np.polyfit(np.log(r[skip:]), np.log(cnt[skip:]), 1)
    return r, cnt, sl


def fig_2_5(out=None):
    """Zipf's law: log frequency against log rank (stand-in text)."""
    r, cnt, sl = zipf_fit(alice_text())
    fig, ax = panel_grid(1, 1, size=(4.2, 3.2))
    ax[0, 0].loglog(r, cnt, "o", ms=2.5, color=BLUE, label="word counts")
    ax[0, 0].loglog(r[10:], np.exp(np.polyval(sl, np.log(r[10:]))), color=RED, label="linear fit (slope %.2f)" % sl[0])
    ax[0, 0].set_xlabel("rank"); ax[0, 0].set_ylabel("frequency"); ax[0, 0].legend()
    fig.tight_layout(); _sv(fig, "fig2-5", out)


def simplex_xy(n=160):
    """Grid of barycentric points inside the triangle with corners (0,0), (1,0), (1/2, sqrt(3)/2)."""
    pts, bar = [], []
    for i in range(1, n):
        for j in range(1, n - i):
            a, b = i / n, j / n
            c = 1 - a - b
            bar.append((a, b, c))
    bar = np.array(bar)
    xy = np.stack([bar[:, 1] + 0.5 * bar[:, 2], np.sqrt(3) / 2 * bar[:, 2]], 1)
    return bar, xy


def fig_2_6(out=None):
    """Dirichlet densities on the simplex for K = 3."""
    bar, xy = simplex_xy(150)
    alphas = [(1, 1, 1), (20, 20, 20), (3, 3, 20), (0.1, 0.1, 0.1)]
    fig, ax = panel_grid(1, 4, size=(2.5, 2.4))
    for k, al in enumerate(alphas):
        d = np.exp(dirichlet_logpdf(bar, al))
        vmax = np.quantile(d, 0.995) if al[0] < 1 else d.max()
        ax[0, k].tricontourf(xy[:, 0], xy[:, 1], np.minimum(d, vmax), levels=20, cmap="viridis")
        ax[0, k].plot([0, 1, 0.5, 0], [0, 0, np.sqrt(3) / 2, 0], color="k", lw=0.8)
        ax[0, k].set_aspect("equal"); ax[0, k].axis("off")
        ax[0, k].set_title("$\\alpha$=(%s)" % ",".join("%g" % a for a in al), fontsize=8)
        ax[0, k].text(0.5, -0.02, "(%s)" % "abcd"[k], ha="center", va="top", transform=ax[0, k].transAxes, fontsize=9)
    fig.tight_layout(); _sv(fig, "fig2-6", out)


def fig_2_7(out=None):
    """Samples from a symmetric 5-d Dirichlet."""
    rng = np.random.default_rng(7)
    fig, ax = panel_grid(2, 5, size=(1.6, 1.5))
    for r, a in enumerate([0.1, 1.0]):
        S = rng.dirichlet(a * np.ones(5), 5)
        for k in range(5):
            ax[r, k].bar(np.arange(1, 6), S[k], color=BLUE, width=0.7)
            ax[r, k].set_ylim(0, 1); ax[r, k].set_xticks(range(1, 6))
            if k:
                ax[r, k].set_yticklabels([])
        ax[r, 2].set_title("Samples from Dir($\\alpha$=%.1f)" % a, fontsize=9)
    fig.tight_layout(); _sv(fig, "fig2-7", out)


def fig_2_8(out=None):
    """Level sets of a 2-d Gaussian with full, diagonal and spherical covariance."""
    g = np.linspace(-6, 6, 241)
    X, Y = np.meshgrid(g, g)
    P = np.stack([X.ravel(), Y.ravel()], 1)
    covs = [("Full", np.array([[3.0, 2.2], [2.2, 2.5]])), ("Diagonal", np.diag([3.0, 1.0])), ("Spherical", 2.0 * np.eye(2))]
    fig, ax = panel_grid(1, 3, size=(2.7, 2.7))
    for k, (name, S) in enumerate(covs):
        z = np.exp(gauss_logpdf(P, np.zeros(2), S)).reshape(X.shape)
        ax[0, k].contourf(X, Y, z, levels=14, cmap="viridis")
        ax[0, k].contour(X, Y, z, levels=6, colors="w", linewidths=0.5)
        ax[0, k].set_aspect("equal"); ax[0, k].set_title(name); panel_label(ax[0, k], "abc"[k], "upper right")
    fig.tight_layout(); _sv(fig, "fig2-8", out)


def fig_2_S1(out=None):
    """The Gaussian soap bubble: norm of N(0, I_D) draws concentrates at sqrt(D) with sd about 1/sqrt(2)."""
    rng = np.random.default_rng(3)
    Ds = [1, 2, 10, 100, 1000]
    fig, ax = panel_grid(1, 2, size=(3.9, 2.9))
    cols = [BLUE, RED, GREEN, MAGENTA, ORANGE]
    for D, c in zip(Ds, cols):
        r = np.linalg.norm(rng.standard_normal((4000, D)), axis=1)
        ax[0, 0].hist(r - np.sqrt(D), bins=60, range=(-3, 3), density=True, histtype="step", color=c, label="D=%d" % D)
    t = np.linspace(-3, 3, 300)
    ax[0, 0].plot(t, stats.norm.pdf(t, 0, np.sqrt(0.5)), "k--", lw=1, label="N(0, 1/2)")
    ax[0, 0].set_xlabel("$\\|x\\| - \\sqrt{D}$"); ax[0, 0].set_ylabel("density"); ax[0, 0].legend(fontsize=7)
    Dg = np.unique(np.logspace(0, 3.3, 14).astype(int))
    cv = [np.std((rng.standard_normal((6000, D)) ** 2).sum(1)) / D for D in Dg]
    ax[0, 1].loglog(Dg, cv, "o", color=BLUE, label="simulation")
    ax[0, 1].loglog(Dg, np.sqrt(2 / Dg), color=RED, label="$\\sqrt{2/D}$")
    ax[0, 1].loglog(Dg, np.sqrt(1 / Dg), color=GREY, ls="--", label="$\\sqrt{1/D}$")
    ax[0, 1].set_xlabel("D"); ax[0, 1].set_ylabel("sd($d^2$) / E[$d^2$]"); ax[0, 1].legend(fontsize=7)
    panel_label(ax[0, 0], "a", "upper left"); panel_label(ax[0, 1], "b", "lower left")
    fig.tight_layout(); _sv(fig, "fig2-S1", out)


def _ellipse(ax, mu, S, c, **kw):
    ex, ey = ellipse_xy(mu, S, 1.0)
    ax.plot(ex, ey, color=c, **kw)


def fig_2_10(out=None):
    """Sensor fusion in 2-d: three noise configurations."""
    x = np.array([0.0, -1.0]); y = np.array([1.0, 0.0])
    cfg = [(0.01 * np.eye(2), 0.01 * np.eye(2)), (0.05 * np.eye(2), 0.01 * np.eye(2)),
           (0.01 * np.array([[10, 1], [1, 1]]), 0.01 * np.array([[1, 1], [1, 10]]))]
    fig, ax = panel_grid(1, 3, size=(2.9, 2.8))
    res = []
    for k, (Sx, Sy) in enumerate(cfg):
        m, C = sensor_fusion(x, y, Sx, Sy)
        res.append(m)
        a = ax[0, k]
        _ellipse(a, x, Sx, RED, lw=1.2); _ellipse(a, y, Sy, GREEN, lw=1.2); _ellipse(a, m, C, "k", lw=1.2)
        a.plot(*x, "x", color=RED, ms=9, mew=2, label="x"); a.plot(*y, "x", color=GREEN, ms=9, mew=2, label="y")
        a.plot(*m, "x", color="k", ms=9, mew=2, label="E[z|x,y]")
        a.set_xlim(-0.5, 1.5); a.set_ylim(-1.5, 0.5); a.set_aspect("equal"); a.set_xlabel("first coordinate")
        panel_label(a, "abc"[k], "upper left")
    ax[0, 0].set_ylabel("second coordinate"); ax[0, 0].legend(fontsize=7, loc="lower left")
    fig.tight_layout(); _sv(fig, "fig2-10", out)
    return res


def fig_2_12(out=None):
    """Change of variables: y = sigmoid(x - 5) with x ~ N(6, 1); analytic density against Monte Carlo."""
    rng = np.random.default_rng(12)
    xs = rng.normal(6, 1, 200000)
    ys = common.sigmoid(xs - 5)
    x = np.linspace(0, 12, 600)
    yg = np.linspace(0.002, 0.998, 998)
    pY = stats.norm.pdf(np.log(yg / (1 - yg)) + 5, 6, 1) / (yg * (1 - yg))
    fig, ax = panel_grid(1, 2, size=(3.8, 2.9))
    ax[0, 0].plot(x, stats.norm.pdf(x, 6, 1), color=BLUE, label="$p_X$")
    ax[0, 0].plot(x, common.sigmoid(x - 5), color=RED, label="g")
    ax[0, 0].axvline(6, color=GREY, ls=":", lw=1)
    ax[0, 0].set_xlabel("x"); ax[0, 0].legend(); panel_label(ax[0, 0], "a", "upper left")
    ax[0, 1].hist(ys, bins=70, range=(0, 1), density=True, color="#9bb7e0", label="Monte Carlo")
    ax[0, 1].plot(yg, pY, color=BLUE, label="change of variables")
    ymode = yg[np.argmax(pY)]
    ax[0, 1].axvline(common.sigmoid(1.0), color=RED, ls="--", lw=1, label="g(mode of X) = %.2f" % common.sigmoid(1.0))
    ax[0, 1].axvline(ymode, color="k", ls=":", lw=1.2, label="mode of Y = %.2f" % ymode)
    ax[0, 1].set_xlabel("y"); ax[0, 1].set_ylabel("$p_Y$"); ax[0, 1].legend(fontsize=7, loc="upper center"); panel_label(ax[0, 1], "b", "upper left")
    fig.tight_layout(); _sv(fig, "fig2-12", out)
    return ymode


def fig_2_13(out=None):
    """Probability integral transform for three distributions."""
    rng = np.random.default_rng(13)
    dists = [("Gamma(2, scale 2)", stats.gamma(2, scale=2.0)), ("Beta(2, 5) on [1, 5]", stats.beta(2, 5, loc=1, scale=4)),
             ("N(0,1)/N(2,0.5) mixture", None)]
    mix_cdf = lambda t: 0.6 * stats.norm.cdf(t, 0, 1) + 0.4 * stats.norm.cdf(t, 2.5, 0.5)
    mix_pdf = lambda t: 0.6 * stats.norm.pdf(t, 0, 1) + 0.4 * stats.norm.pdf(t, 2.5, 0.5)
    fig, ax = panel_grid(3, 3, size=(2.5, 1.9))
    n = 400
    for r, (name, d) in enumerate(dists):
        if d is None:
            comp = rng.random(n) < 0.6
            xs = np.where(comp, rng.normal(0, 1, n), rng.normal(2.5, 0.5, n)); cdf, pdf = mix_cdf, mix_pdf
            g = np.linspace(-3.5, 4.5, 500)
        else:
            xs = d.rvs(n, random_state=rng); cdf, pdf = d.cdf, d.pdf
            g = np.linspace(max(d.ppf(0.001), 0), d.ppf(0.999), 500) if r == 0 else np.linspace(1, 5, 500)
        ys = np.sort(cdf(xs))
        ax[r, 0].plot(g, pdf(g), color=BLUE); ax[r, 0].set_ylabel("pdf(X)"); ax[r, 0].set_xlabel("x%d" % (r + 1))
        ax[r, 1].step(ys, np.arange(1, n + 1) / n, color=RED); ax[r, 1].plot([0, 1], [0, 1], color=GREY, lw=0.8)
        ax[r, 1].set_ylabel("cdf(Y)"); ax[r, 1].set_xlabel("y%d" % (r + 1))
        kde = stats.gaussian_kde(ys, bw_method=0.25)
        t = np.linspace(0, 1, 200)
        ax[r, 2].plot(t, kde(t) + kde(-t) + kde(2 - t), color=GREEN); ax[r, 2].set_ylim(0, 1.6); ax[r, 2].set_ylabel("pdf(Y)")
        ax[r, 2].set_xlabel("y%d" % (r + 1))
    fig.tight_layout(); _sv(fig, "fig2-13", out)


def fig_2_14(out=None):
    """The Kolmogorov-Smirnov statistic: empirical cdf of 25 draws against the model cdf."""
    rng = np.random.default_rng(14)
    xs = np.sort(rng.normal(0.25, 1.1, 25))
    d, loc, up = ks_statistic(xs, stats.norm.cdf)
    g = np.linspace(-3.5, 3.5, 600)
    fig, ax = panel_grid(1, 1, size=(4.2, 3.0))
    ax[0, 0].plot(g, stats.norm.cdf(g), color=RED, label="model cdf P")
    ax[0, 0].step(np.r_[-3.5, xs, 3.5], np.r_[0, np.arange(1, 26) / 25, 1], where="post", color=BLUE, label="empirical cdf $P_n$")
    ym = stats.norm.cdf(loc)
    ys = ym + (d if up else -d)
    ax[0, 0].annotate("", xy=(loc, ys), xytext=(loc, ym), arrowprops=dict(arrowstyle="<->", color="k"))
    ax[0, 0].text(loc + 0.25, (ym + ys) / 2 - 0.05, "$D_n$ = %.3f" % d, fontsize=9)
    ax[0, 0].legend(loc="upper left", fontsize=8); ax[0, 0].set_xlabel("x"); ax[0, 0].set_ylabel("cdf")
    fig.tight_layout(); _sv(fig, "fig2-14", out)
    return d


def fig_2_16(out=None):
    """Samples from character n-gram models (stand-in text), given the prefix 'alice was'."""
    text = alice_text()
    fig = plt.figure(figsize=(6.6, 3.1))
    ax = fig.add_axes([0, 0, 1, 1]); ax.axis("off")
    y = 0.96
    samples = {}
    for n in (2, 4, 10):
        rng = np.random.default_rng(16)
        s = NGram(text, n).sample("alice was ", 190, rng)
        samples[n] = s
        ax.text(0.01, y, "%d-gram (context of %d characters):" % (n, n - 1), fontsize=8.5, weight="bold", va="top", transform=ax.transAxes)
        y -= 0.065
        for line in textwrap.wrap(s, 88):
            ax.text(0.02, y, line, fontsize=8.2, family="monospace", va="top", transform=ax.transAxes)
            y -= 0.062
        y -= 0.035
    _sv(fig, "fig2-16", out)
    return samples


def bigram_counts(text, order=None):
    chars = " " + "abcdefghijklmnopqrstuvwxyz"
    uni = Counter(text)
    order = order or [c for c, _ in uni.most_common() if c in chars]
    idx = {c: i for i, c in enumerate(order)}
    N = np.zeros((len(order), len(order)))
    for a, b in zip(text[:-1], text[1:]):
        if a in idx and b in idx:
            N[idx[a], idx[b]] += 1
    return order, N


def fig_2_17(out=None):
    """Hinton diagram of character bigram counts and the row-normalised version (stand-in text)."""
    order, N = bigram_counts(alice_text())
    fig, ax = panel_grid(1, 2, size=(3.9, 3.9))
    for a, M, lab in [(ax[0, 0], N, "a"), (ax[0, 1], N / np.maximum(N.sum(1, keepdims=True), 1), "b")]:
        s = np.sqrt(M / M.max())
        for i in range(M.shape[0]):
            for j in range(M.shape[1]):
                a.add_patch(plt.Rectangle((j - s[i, j] / 2, i - s[i, j] / 2), s[i, j], s[i, j], color="k"))
        a.set_xlim(-0.6, M.shape[1] - 0.4); a.set_ylim(M.shape[0] - 0.4, -0.6); a.set_aspect("equal")
        lbl = ["_" if c == " " else c for c in order]
        a.set_xticks(range(len(order))); a.set_xticklabels(lbl, fontsize=6); a.set_yticks(range(len(order))); a.set_yticklabels(lbl, fontsize=6)
        a.xaxis.tick_top(); panel_label(a, lab, "lower right")
    fig.tight_layout(); _sv(fig, "fig2-17", out)
    return order, N


def _two_samples(seed, kind):
    rng = np.random.default_rng(seed)
    if kind == "different":
        return rng.normal(0, 1, 60), rng.normal(1.6, 1.0, 60)
    return rng.normal(0, 1, 60), rng.normal(0.1, 1.0, 60)


def fig_2_19(out=None):
    """Two samples that come from different (a) or from similar (b) distributions."""
    fig, ax = panel_grid(1, 2, size=(3.8, 2.4))
    for k, kind in enumerate(["different", "similar"]):
        X, Y = _two_samples(19, kind)
        a = ax[0, k]
        a.hist(X, bins=14, range=(-3.5, 5), color=BLUE, alpha=0.55, density=True)
        a.hist(Y, bins=14, range=(-3.5, 5), color=RED, alpha=0.55, density=True)
        a.plot(X, np.full_like(X, -0.02), "|", color=BLUE); a.plot(Y, np.full_like(Y, -0.04), "|", color=RED)
        a.set_xlabel("x"); a.set_title("%s distributions" % kind.capitalize(), fontsize=9)
        a.text(0.97, 0.95, "MMD$^2$=%.3f" % mmd2(X, Y, 1.0), ha="right", va="top", transform=a.transAxes, fontsize=8)
        panel_label(a, "ab"[k], "upper left")
    fig.tight_layout(); _sv(fig, "fig2-19", out)


def fig_2_20(out=None):
    """The Gaussian q that minimises the alpha divergence to a two-component mixture p, for several alpha."""
    alphas = [-4.0, 0.0, 0.5, 1.0, 4.0]
    x = np.linspace(-7, 7, 700)
    fig, ax = panel_grid(1, 5, size=(2.3, 2.3))
    fits = {}
    for k, al in enumerate(alphas):
        m, s, d = alpha_fit(al)
        fits[al] = (m, s, d)
        ax[0, k].plot(x, np.exp(mix_logpdf(x, **P_MIX)), color=RED, label="p")
        ax[0, k].plot(x, stats.norm.pdf(x, m, s), color=BLUE, label="q")
        ax[0, k].set_title("$\\alpha$ = %g" % al, fontsize=9); ax[0, k].set_yticks([]); ax[0, k].set_xticks([-5, 0, 5])
    ax[0, 0].legend(fontsize=7, loc="upper left")
    fig.tight_layout(); _sv(fig, "fig2-20", out)
    return fits


def fig_2_21(out=None):
    """The witness function of the MMD for two samples that differ (a) and that are alike (b)."""
    t = np.linspace(-3.5, 5, 500)
    fig, ax = panel_grid(1, 2, size=(3.8, 2.6))
    for k, kind in enumerate(["different", "similar"]):
        X, Y = _two_samples(19, kind)
        a = ax[0, k]
        a.plot(t, witness(t, X, Y, 1.0), color="k", label="witness")
        a.plot(X, np.full_like(X, -0.42), "|", color=BLUE); a.plot(Y, np.full_like(Y, -0.47), "|", color=RED)
        a.axhline(0, color=GREY, lw=0.6); a.set_ylim(-0.5, 0.5); a.set_xlabel("x"); a.set_title("%s" % kind, fontsize=9)
        panel_label(a, "ab"[k], "upper left")
    ax[0, 0].set_ylabel("$\\mu_P(x) - \\mu_Q(x)$")
    fig.tight_layout(); _sv(fig, "fig2-21", out)


def fig_2_22(out=None):
    """Effect of the kernel bandwidth on the witness function: sigma = 3, 0.7, 0.12."""
    rng = np.random.default_rng(22)
    X = rng.normal(0, 1, 100); Y = rng.laplace(0, 1 / np.sqrt(2), 100)
    t = np.linspace(-4, 4, 800)
    fig, ax = panel_grid(1, 3, size=(2.7, 2.4))
    vals = []
    for k, sg in enumerate([3.0, 0.7, 0.12]):
        ax[0, k].plot(t, witness(t, X, Y, sg), color="k")
        ax[0, k].plot(X, np.full_like(X, -0.0), "|", color=BLUE, alpha=0.4); ax[0, k].axhline(0, color=GREY, lw=0.6)
        m = mmd2(X, Y, sg); vals.append(m)
        ax[0, k].set_title("$\\sigma$=%g, MMD$^2$=%.4f" % (sg, m), fontsize=8)
        ax[0, k].set_xlabel("x"); panel_label(ax[0, k], "abc"[k], "lower right")
    fig.tight_layout(); _sv(fig, "fig2-22", out)
    return vals


def fig_S2_1(out=None):
    """Supplementary Figure 2.1: sensor fusion with unknown precisions, plug-in and exact posterior."""
    xbar, sx2, ybar, sy2 = 1.5, 0.16, 3.5, 0.36
    z = np.linspace(-2, 6, 1200)
    path, zh, vx, vy, vN = sensor_plugin(xbar, sx2, ybar, sy2)
    ex = sensor_exact_unnorm(z, xbar, sx2, ybar, sy2)
    ex /= np.trapz(ex, z)
    fig, ax = panel_grid(1, 2, size=(3.6, 2.7))
    ax[0, 0].plot(z, stats.norm.pdf(z, zh, np.sqrt(vN)), color=BLUE)
    ax[0, 0].set_ylim(0, 1.6)
    ax[0, 1].plot(z, ex, color=BLUE); ax[0, 1].set_ylim(0, 0.8)
    for a, l in zip(ax[0], "ab"):
        a.set_xlabel("z"); a.set_xlim(-2, 6); panel_label(a, l, "upper right")
    ax[0, 0].set_title("Plug-in", fontsize=9); ax[0, 1].set_title("Exact", fontsize=9)
    fig.tight_layout(); _sv(fig, "figS2-1", out)


def fig_S2_2(out=None):
    """Supplementary Figure 2.2: the small web and its stationary distribution (PageRank, p = 0.85)."""
    import networkx as nx
    v, _ = pagerank(PAGERANK_EDGES, 6)
    fig, ax = panel_grid(1, 2, size=(3.3, 3.0))
    Gr = nx.DiGraph(PAGERANK_EDGES)
    pos = {1: (0.5, 1.0), 2: (0.5, 0.65), 3: (0.5, 0.3), 4: (0.1, 0.0), 5: (0.5, 0.0), 6: (0.9, 0.0)}
    nx.draw_networkx_nodes(Gr, pos, ax=ax[0, 0], node_color="#7fd37f", node_size=420, edgecolors="k")
    nx.draw_networkx_labels(Gr, pos, ax=ax[0, 0], labels={i: "$x_%d$" % i for i in Gr.nodes}, font_size=8)
    nx.draw_networkx_edges(Gr, pos, ax=ax[0, 0], arrows=True, arrowsize=10, node_size=420, connectionstyle="arc3,rad=0.12")
    ax[0, 0].axis("off"); panel_label(ax[0, 0], "a", "upper left")
    ax[0, 1].bar(np.arange(1, 7), v, color=BLUE)
    ax[0, 1].set_xticks(range(1, 7)); ax[0, 1].set_xticklabels(["$x_%d$" % i for i in range(1, 7)]); panel_label(ax[0, 1], "b", "upper right")
    fig.tight_layout(); _sv(fig, "figS2-2", out)
    return v


WEB_N, WEB_M = 500, 3


def web_graph():
    return scale_free_web(WEB_N, WEB_M, np.random.default_rng(500))


def fig_S2_3(out=None):
    """Supplementary Figure 2.3: adjacency pattern of a 500-page simulated web and its PageRank vector."""
    E = web_graph()
    v, hist = pagerank(E, WEB_N, 0.85, tol=1e-6)
    fig, ax = panel_grid(1, 2, size=(3.6, 3.0))
    ij = np.array(E) - 1
    ax[0, 0].plot(ij[:, 1], ij[:, 0], ".", ms=1.2, color=BLUE)
    ax[0, 0].set_xlim(0, WEB_N); ax[0, 0].set_ylim(WEB_N, 0); ax[0, 0].set_aspect("equal")
    ax[0, 0].set_xlabel("target page"); ax[0, 0].set_ylabel("source page"); panel_label(ax[0, 0], "a", "lower right")
    ax[0, 1].plot(np.arange(1, WEB_N + 1), v, color=BLUE, lw=0.8)
    ax[0, 1].set_xlabel("page"); ax[0, 1].set_ylabel("PageRank"); panel_label(ax[0, 1], "b", "upper right")
    fig.tight_layout(); _sv(fig, "figS2-3", out)
    return v, len(hist)


def fig_2_S2(out=None):
    """Convergence of the power method for PageRank: error against iteration, and the bound p^t."""
    E = web_graph()
    fig, ax = panel_grid(1, 1, size=(4.4, 3.0))
    for p, c in [(0.5, GREEN), (0.85, BLUE), (0.99, RED)]:
        v, hist = pagerank(E, WEB_N, p, tol=1e-13, maxit=600)
        ax[0, 0].semilogy(np.arange(1, len(hist) + 1), hist, color=c, label="p=%.2f (%d iterations)" % (p, len(hist)))
        t = np.arange(1, len(hist) + 1)
        ax[0, 0].semilogy(t, hist[0] * p ** (t - 1), color=c, ls=":", lw=1)
    ax[0, 0].set_ylim(1e-13, 2); ax[0, 0].set_xlabel("iteration t"); ax[0, 0].set_ylabel("$\\|v_{t+1}-v_t\\|_1$")
    ax[0, 0].legend(fontsize=7)
    fig.tight_layout(); _sv(fig, "fig2-S2", out)


def export_data(out=None):
    """JSON for the browser demonstrations: the sensor data, the alpha-divergence reference fits and
    the PageRank graphs with their stationary vectors."""
    v6, h6 = pagerank(PAGERANK_EDGES, 6)
    E = web_graph()
    v500, h500 = pagerank(E, WEB_N, 0.85, tol=1e-10)
    _dump("pagerank", dict(small=dict(n=6, edges=PAGERANK_EDGES, pi=v6.tolist()),
                           web=dict(n=WEB_N, edges=E, pi=v500.tolist(), note="simulated preferential-attachment web (stand-in)")))
    fits = {}
    for al in [-4, -2, -1, 0, 0.5, 1, 2, 4]:
        m, s, d = alpha_fit(float(al))
        fits[str(al)] = dict(m=m, s=s, D=d)
    _dump("alpha-fits", dict(p=dict(w=list(P_MIX["w"]), mu=list(P_MIX["mu"]), sd=list(P_MIX["sd"])), fits=fits))
    path, zh, vx, vy, vN = sensor_plugin(1.5, 0.16, 3.5, 0.36)
    _dump("sensor", dict(xbar=1.5, sx2=0.16, ybar=3.5, sy2=0.36, plugin=dict(z=zh, varx=vx, vary=vy, post_var=vN)))
    print("wrote data JSON in", DATA_JSON)


FIGURES = {
    "2.1": fig_2_1, "2.2": fig_2_2, "2.3": fig_2_3, "2.4": fig_2_4, "2.5": fig_2_5, "2.6": fig_2_6, "2.7": fig_2_7,
    "2.8": fig_2_8, "2.10": fig_2_10, "2.12": fig_2_12, "2.13": fig_2_13, "2.14": fig_2_14, "2.16": fig_2_16,
    "2.17": fig_2_17, "2.19": fig_2_19, "2.20": fig_2_20, "2.21": fig_2_21, "2.22": fig_2_22,
    "S2.1": fig_S2_1, "S2.2": fig_S2_2, "S2.3": fig_S2_3, "2.S1": fig_2_S1, "2.S2": fig_2_S2, "data": export_data,
}

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