"""Murphy (2023), Chapter 12: Markov chain Monte Carlo.

Companion code for Chapter 12 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press,
2023; December 2025 draft), pp. 499-542, written from scratch with numpy, scipy and matplotlib, to be read
next to the lecture notes (../ch12-mcmc.html). Supplementary Chapter 12 has a title page only in this
draft, so there is no supplement material to reproduce.

Methods implemented (the notes use these functions by name)
* Metropolis-Hastings (Section 12.2): random walk Metropolis (rwm), the 1-d two-component mixture target of
  Figure 12.1 (gmm1d_logpdf), optimal scaling in D dimensions (rwm_gauss_scaling, limit curve
  rwm_limit_acceptance).
* Gibbs sampling (Section 12.3): the Ising posterior for image denoising with checkerboard updates
  (ising_denoise_gibbs, (12.24)-(12.29)), Gibbs for a mixture with known parameters (gibbs_gmm1d, (12.35))
  and its exact two-state switching rate (gmm1d_switch_prob), Gibbs for a mixture with unknown parameters
  (gibbs_gmm_unknown, (12.39)-(12.48)), the collapsed sampler of Algorithm 12.2 (collapsed_gibbs_gmm1d,
  (12.51)-(12.57)), Gibbs on a correlated Gaussian (gibbs_gauss2d, Figure 12.5).
* Auxiliary variables (Section 12.4): slice sampling with stepping out and shrinkage (slice_sample,
  (12.58)-(12.60)), single-site Gibbs and Swendsen-Wang for the Ising model (ising_gibbs, swendsen_wang,
  (12.61)).
* Hamiltonian Monte Carlo (Section 12.5): the leapfrog, Euler and modified Euler integrators
  ((12.67)-(12.74)), HMC with a diagonal mass matrix and divergence detection (hmc, Algorithm 12.3), MALA
  and the unadjusted Langevin algorithm (mala, ula, Algorithm 12.4 and (12.81)-(12.83)), the minibatch
  gradient noise of SGD (minibatch_grad_moments, (12.85)-(12.91)).
* Convergence (Section 12.6): the random walk on {0, ..., 20} (Figure 12.11) with its spectrum, total
  variation distance and conductance (rw_integers_*), R-hat and split R-hat ((12.97)-(12.100)), the
  autocorrelation function and effective sample size ((12.107)-(12.110)), trace rank plots, the two-point
  Gaussian model with a diffuse and a sensible prior (unigauss_*), Neal's funnel in the centred and
  non-centred parameterisations ((12.111)-(12.115)).
* Stochastic gradient MCMC (Section 12.7): SGLD (12.123), SGLD-CV (12.124) and SVRG-LD (Algorithm 12.5)
  on a Bayesian linear regression whose posterior is known exactly (sgld_family).
* Reversible jump MCMC (Section 12.8): an RBF regression model with the linear coefficients and the noise
  variance integrated out (rbf_log_marglik), birth, death, split and merge moves on the centres
  (rjmcmc_rbf, Algorithm 12.6) and the exact posterior over the number of centres for small models by
  quadrature (rbf_exact_k_posterior).
* Annealing (Section 12.9): the peaks target (12.145), its tempered versions (12.144) and simulated
  annealing with an exponential cooling schedule (simulated_annealing, (12.146)).
* The browser demonstrations: a port of the demo kit's seeded generator (DKRng, mulberry32 with
  Box-Muller) and the exact algorithms the pages run (demo_mh_run, demo_hmc_run, demo_ising_run).

Data. Everything is simulated except Figure 12.8, which uses the twelve car-weight classes of the book's
binomial regression example (number of cars tested and number with poor fuel economy at each weight).
The image of Figure 12.3 is a synthetic binary shape (the book's image is not available). Seeds are fixed.

Figures. Reproduced here: 12.1, 12.3, 12.4, 12.5, 12.7, 12.8, 12.11, 12.13, 12.14, 12.15, 12.16, 12.17,
12.18, 12.20, 12.21, 12.22, 12.23. Skipped, with the reason:
  12.2   the checkerboard colouring of a grid (a diagram; the colouring is used in ising_denoise_gibbs);
  12.6, 12.10  graphical-model diagrams of a mixture before and after collapsing (nothing computed);
  12.9   a hand-drawn illustration of one Swendsen-Wang step (the algorithm itself is run in 12.S2);
  12.12  a hand-drawn chain with a bottleneck (conductance is computed for Figure 12.11 in 12.S5);
  12.19  a sketch of dimension matching (the moves are implemented in rjmcmc_rbf).
Figure 12.7(a) is redrawn from a computed slice of the target of panel (b) instead of the book's sketch.
Supplementary figures for the gaps filled in the notes:
  12.S1  random walk Metropolis in D = 20: expected squared jump distance against the scale, with the
         limit curve that gives 2.38 / sqrt(D) and the acceptance rate 0.234;
  12.S2  single-site Gibbs against Swendsen-Wang on a 32 x 32 Ising torus at three couplings;
  12.S3  Euler, modified Euler and leapfrog on a harmonic oscillator, and the leapfrog energy error;
  12.S4  stationary spread of ULA, SGLD, SGLD-CV and SVRG-LD against the step size, with the exact posterior;
  12.S5  total variation distance of the random walk of Figure 12.11 against the spectral bound.
Run `python3 ch12_mcmc.py --list`, `python3 ch12_mcmc.py` (all figures, about five minutes) or
`python3 ch12_mcmc.py --fig 12.1`. Files go to ../img/ch12/; the data used by the browser demonstrations go
to ../data/ch12-*.json.
"""
import json
import os
import sys

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

import numpy as np
from scipy import special, stats
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components

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, plt, savefig, panel_label  # noqa: E402

CH = 12
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache", "ch12-work")


# =========================================================================== diagnostics (Section 12.6)
def acf(x, maxlag=None):
    """Sample autocorrelation rho(l), l = 0..maxlag, of one chain (divisor N, the usual biased estimator)."""
    x = np.asarray(x, float)
    n = x.size
    maxlag = n - 1 if maxlag is None else min(maxlag, n - 1)
    d = x - x.mean()
    f = np.fft.rfft(d, 2 * n)
    r = np.fft.irfft(f * np.conj(f))[:n] / n
    if r[0] <= 0:
        return np.r_[1.0, np.zeros(maxlag)]
    return r[:maxlag + 1] / r[0]


def acf_direct(x, maxlag):
    """The same estimator by direct sums (what the browser demonstration computes)."""
    x = np.asarray(x, float)
    n = x.size
    d = x - x.mean()
    c0 = np.dot(d, d) / n
    if c0 <= 0:
        return np.r_[1.0, np.zeros(maxlag)]
    return np.array([np.dot(d[:n - l], d[l:]) / n / c0 for l in range(maxlag + 1)])


def ess(chains, maxlag=None):
    """Effective sample size (12.110): N M / (1 + 2 sum_{l=1}^{L} rho(l)), with rho the chain-averaged ACF and
    the sum stopped before the first lag at which the estimated autocorrelation is not positive."""
    C = np.atleast_2d(np.asarray(chains, float))
    M, N = C.shape
    maxlag = N - 1 if maxlag is None else maxlag
    rho = np.mean([acf(c, maxlag) for c in C], axis=0)
    s = 0.0
    for l in range(1, rho.size):
        if rho[l] <= 0:
            break
        s += rho[l]
    return N * M / (1 + 2 * s)


def rhat(chains):
    """Potential scale reduction (12.97)-(12.100) for an M x N array of chains."""
    C = np.atleast_2d(np.asarray(chains, float))
    M, N = C.shape
    means = C.mean(1)
    B = N / (M - 1) * np.sum((means - means.mean()) ** 2)
    W = np.mean(C.var(1, ddof=1))
    Vplus = (N - 1) / N * W + B / N
    return float(np.sqrt(Vplus / W))


def split_rhat(chains):
    C = np.atleast_2d(np.asarray(chains, float))
    h = C.shape[1] // 2
    return rhat(np.vstack([C[:, :h], C[:, h:2 * h]]))


def ranks_all(chains):
    """Ranks (1..NM) of every draw among all draws of all chains, for the trace rank plot."""
    C = np.atleast_2d(np.asarray(chains, float))
    return stats.rankdata(C.ravel()).reshape(C.shape)


# =========================================================================== the 1-d mixture (Figures 12.1, 12.4, 12.17)
GMM_PI = np.array([0.3, 0.7])
GMM_MU = np.array([-20.0, 20.0])
GMM_SD = np.array([10.0, 10.0])


def gmm1d_logpdf(x):
    x = np.asarray(x, float)[..., None]
    return special.logsumexp(np.log(GMM_PI) + stats.norm.logpdf(x, GMM_MU, GMM_SD), axis=-1)


def rwm(logp, x0, tau, n, rng):
    """Random walk Metropolis (12.15) with proposal N(x, tau^2 I); returns the n states (x0 first) and the
    acceptance rate."""
    x = np.array(x0, float).reshape(-1)
    lp = logp(x)
    out = np.empty((n, x.size))
    out[0] = x
    acc = 0
    for s in range(1, n):
        xp = x + tau * rng.standard_normal(x.size)
        lpp = logp(xp)
        if np.log(rng.uniform()) < lpp - lp:
            x, lp = xp, lpp
            acc += 1
        out[s] = x
    return out.squeeze(), acc / (n - 1)


def gibbs_gmm1d(x0, n, rng):
    """Gibbs sampling of (z, x) for the mixture with known parameters: z | x by (12.35), x | z = N(mu_z, sd_z^2)."""
    xs, zs = np.empty(n), np.empty(n, int)
    x = float(x0)
    for s in range(n):
        lw = np.log(GMM_PI) + stats.norm.logpdf(x, GMM_MU, GMM_SD)
        p1 = 1.0 / (1.0 + np.exp(lw[0] - lw[1]))
        z = int(rng.uniform() < p1)
        x = GMM_MU[z] + GMM_SD[z] * rng.standard_normal()
        xs[s], zs[s] = x, z
    return xs, zs


def gmm1d_switch_prob():
    """The z-chain of gibbs_gmm1d is a two-state Markov chain; P(z' = k | z = j) = int N(x|mu_j, sd_j) p(z = k | x) dx.
    Returns the 2 x 2 transition matrix by quadrature."""
    from scipy import integrate
    P = np.zeros((2, 2))
    for j in range(2):
        def f(x):
            lw = np.log(GMM_PI) + stats.norm.logpdf(x, GMM_MU, GMM_SD)
            return stats.norm.pdf(x, GMM_MU[j], GMM_SD[j]) / (1 + np.exp(lw[0] - lw[1]))
        P[j, 1] = integrate.quad(f, -200, 200, limit=200, points=[-20, 0, 20])[0]
        P[j, 0] = 1 - P[j, 1]
    return P


# =========================================================================== Gibbs for GMMs with unknown parameters (12.36)-(12.48)
def gibbs_gmm_unknown(X, K, n_iter, rng, alpha=1.0, m0=None, V0=None, S0=None, nu0=None):
    """Gibbs sampler for a Bayesian GMM with the conditionally conjugate prior (12.34). Returns the draws of
    the means (n_iter x K x D) and the weights."""
    from scipy.stats import invwishart
    N, D = X.shape
    m0 = X.mean(0) if m0 is None else m0
    V0 = np.eye(D) * 10.0 if V0 is None else V0
    nu0 = D + 2 if nu0 is None else nu0
    S0 = np.eye(D) * 0.5 if S0 is None else S0
    mu = X[rng.choice(N, K, replace=False)].copy()
    Sig = np.array([np.cov(X.T) for _ in range(K)])
    pi = np.ones(K) / K
    V0i = np.linalg.inv(V0)
    out_mu, out_pi = np.empty((n_iter, K, D)), np.empty((n_iter, K))
    for it in range(n_iter):
        lw = np.log(pi) + np.stack([common.gauss_logpdf(X, mu[k], Sig[k]) for k in range(K)], 1)   # (12.39)
        lw -= lw.max(1, keepdims=True)
        p = np.exp(lw)
        p /= p.sum(1, keepdims=True)
        z = (rng.uniform(size=(N, 1)) > np.cumsum(p, 1)).sum(1)
        Nk = np.bincount(z, minlength=K)
        pi = rng.dirichlet(alpha + Nk)                                                          # (12.40)
        for k in range(K):
            Xk = X[z == k]
            Si = np.linalg.inv(Sig[k])
            Vk = np.linalg.inv(V0i + Nk[k] * Si)                                                # (12.42)
            xbar = Xk.mean(0) if Nk[k] else np.zeros(D)
            mk = Vk @ (Si @ (Nk[k] * xbar) + V0i @ m0)                                          # (12.43)
            mu[k] = rng.multivariate_normal(mk, Vk)                                             # (12.41)
            R = Xk - mu[k]
            Sig[k] = invwishart.rvs(df=nu0 + Nk[k], scale=S0 + R.T @ R, random_state=rng)      # (12.46)-(12.48)
        out_mu[it], out_pi[it] = mu, pi
    return out_mu, out_pi


# =========================================================================== collapsed Gibbs (Algorithm 12.2), 1-d Gaussian clusters
def nig_logpred(x, n, s1, s2, m0, k0, a0, b0):
    """log posterior predictive of x under a normal-inverse-gamma prior (m0, k0, a0, b0) after n points with
    sum s1 and sum of squares s2: a Student t."""
    kn = k0 + n
    mn = (k0 * m0 + s1) / kn
    an = a0 + n / 2
    xbar = s1 / n if n > 0 else 0.0
    ss = s2 - n * xbar ** 2 if n > 0 else 0.0
    bn = b0 + 0.5 * ss + k0 * n * (xbar - m0) ** 2 / (2 * kn) if n > 0 else b0
    scale = np.sqrt(bn * (kn + 1) / (an * kn))
    return stats.t.logpdf(x, 2 * an, mn, scale)


def collapsed_gibbs_gmm1d(x, K, n_sweeps, rng, alpha=1.0, prior=(0.0, 0.01, 1.0, 1.0)):
    """Algorithm 12.2 for a 1-d mixture with a symmetric Dirichlet(alpha/K) prior on the weights and a
    normal-inverse-gamma prior on each component; the weights and parameters are integrated out."""
    N = x.size
    z = rng.integers(0, K, N)
    n = np.bincount(z, minlength=K).astype(float)
    s1 = np.bincount(z, x, minlength=K)
    s2 = np.bincount(z, x * x, minlength=K)
    Z = np.empty((n_sweeps, N), int)
    for t in range(n_sweeps):
        for i in rng.permutation(N):
            k = z[i]
            n[k] -= 1; s1[k] -= x[i]; s2[k] -= x[i] ** 2                      # remove x_i's statistics
            lp = np.log(n + alpha / K) + np.array([nig_logpred(x[i], n[j], s1[j], s2[j], *prior) for j in range(K)])
            p = np.exp(lp - lp.max()); p /= p.sum()
            k = int((rng.uniform() > np.cumsum(p)).sum())
            z[i] = k
            n[k] += 1; s1[k] += x[i]; s2[k] += x[i] ** 2                      # add them to the new cluster
        Z[t] = z
    return Z


def dirmult_log_prob(z, K, alpha):
    """log p(z_1..z_N | alpha) for the symmetric Dirichlet(alpha/K) prior, (12.54)."""
    N = len(z)
    Nk = np.bincount(z, minlength=K)
    return special.gammaln(alpha) - special.gammaln(N + alpha) + np.sum(special.gammaln(Nk + alpha / K) - special.gammaln(alpha / K))


# =========================================================================== Gibbs on a correlated Gaussian (Figure 12.5)
def gibbs_gauss2d(rho, n, x0, rng):
    """Systematic-scan Gibbs for N(0, [[1, rho], [rho, 1]]); returns the 2n+1 corner points of the path and the
    n sweep states."""
    x = np.array(x0, float)
    path, states = [x.copy()], []
    s = np.sqrt(1 - rho ** 2)
    for _ in range(n):
        x[0] = rho * x[1] + s * rng.standard_normal(); path.append(x.copy())
        x[1] = rho * x[0] + s * rng.standard_normal(); path.append(x.copy())
        states.append(x.copy())
    return np.array(path), np.array(states)


# =========================================================================== Ising models (Sections 12.3.3, 12.4.2)
def _nbr_sum(x, periodic):
    if periodic:
        return np.roll(x, 1, 0) + np.roll(x, -1, 0) + np.roll(x, 1, 1) + np.roll(x, -1, 1)
    p = np.pad(x, 1)
    return p[:-2, 1:-1] + p[2:, 1:-1] + p[1:-1, :-2] + p[1:-1, 2:]


def checkerboard(shape):
    i, j = np.indices(shape)
    return [(i + j) % 2 == c for c in (0, 1)]


def ising_denoise_problem(seed=0, size=64, sigma=2.0):
    """A synthetic binary image (a ring with a bar and a square) and its noisy version y = x + N(0, sigma^2)."""
    rng = np.random.default_rng(seed)
    i, j = np.indices((size, size))
    c = (size - 1) / 2
    r = np.hypot(i - c, j - c)
    img = ((r > size * 0.22) & (r < size * 0.36)) | ((np.abs(i - c) < size * 0.06) & (np.abs(j - c) < size * 0.3))
    img |= (np.abs(i - size * 0.8) < size * 0.08) & (np.abs(j - size * 0.8) < size * 0.08)
    x = np.where(img, 1.0, -1.0)
    y = x + sigma * rng.standard_normal(x.shape)
    return x, y


def ising_denoise_gibbs(y, J, sigma, sweeps, rng, x0=None):
    """Checkerboard Gibbs sampling of p(x | y) with an Ising prior and Gaussian local evidence, (12.29):
    p(x_i = +1 | rest) = sigmoid(2 J eta_i + log psi_i(+1)/psi_i(-1)), the log ratio being 2 y_i / sigma^2.
    Returns the state after each sweep."""
    x = np.where(y > 0, 1.0, -1.0) if x0 is None else x0.copy()
    loc = 2 * y / sigma ** 2
    masks = checkerboard(y.shape)
    out = []
    for _ in range(sweeps):
        for m in masks:
            eta = _nbr_sum(x, False)
            p = common.sigmoid(2 * J * eta + loc)
            u = rng.uniform(size=y.shape)
            x = np.where(m, np.where(u < p, 1.0, -1.0), x)
        out.append(x.copy())
    return np.array(out)


def ising_gibbs(L, J, sweeps, rng, x0=None):
    """Checkerboard Gibbs on an L x L torus, (12.27); returns the magnetisation after each sweep and the state."""
    x = np.ones((L, L)) if x0 is None else x0.copy()
    masks = checkerboard((L, L))
    mags = np.empty(sweeps)
    for t in range(sweeps):
        for m in masks:
            p = common.sigmoid(2 * J * _nbr_sum(x, True))
            x = np.where(m, np.where(rng.uniform(size=x.shape) < p, 1.0, -1.0), x)
        mags[t] = x.mean()
    return mags, x


def _torus_edges(L):
    idx = np.arange(L * L).reshape(L, L)
    a = np.r_[idx.ravel(), idx.ravel()]
    b = np.r_[np.roll(idx, -1, 1).ravel(), np.roll(idx, -1, 0).ravel()]
    return a, b


def swendsen_wang(L, J, sweeps, rng, x0=None):
    """Swendsen-Wang on an L x L torus: bonds v_e ~ Ber(1 - exp(-2J)) on agreeing edges (p(v | x)), then every
    connected component gets an independent uniform spin (an exact draw from p(x | v)). Returns magnetisations."""
    x = np.ones(L * L) if x0 is None else x0.ravel().copy()
    a, b = _torus_edges(L)
    pb = 1 - np.exp(-2 * J)
    mags = np.empty(sweeps)
    for t in range(sweeps):
        on = (x[a] == x[b]) & (rng.uniform(size=a.size) < pb)
        G = coo_matrix((np.ones(on.sum()), (a[on], b[on])), shape=(L * L, L * L))
        nc, lab = connected_components(G, directed=False)
        x = np.where(rng.uniform(size=nc) < 0.5, 1.0, -1.0)[lab]
        mags[t] = x.mean()
    return mags, x.reshape(L, L)


def ising_exact_torus(L, J):
    """Exact E[|m|], E[m^2] by enumeration on a small torus (L <= 4)."""
    n = L * L
    a, b = _torus_edges(L)
    st = 1 - 2 * ((np.arange(2 ** n)[:, None] >> np.arange(n)) & 1)
    e = (st[:, a] * st[:, b]).sum(1)
    w = np.exp(J * (e - e.max()))
    w /= w.sum()
    m = st.mean(1)
    return float(w @ np.abs(m)), float(w @ m ** 2)


# =========================================================================== slice sampling (Section 12.4.1)
def slice_1d(logf, x, w, rng, m=50):
    """One slice-sampling update of a scalar x (Neal 2003): stepping out with width w (at most m steps)
    and shrinkage. Returns the new x and the number of evaluations of logf."""
    logu = logf(x) + np.log(rng.uniform())      # the auxiliary height, on the log scale (12.60)
    L = x - w * rng.uniform()
    R = L + w
    j = int(np.floor(m * rng.uniform()))
    k = m - 1 - j
    ne = 1
    while j > 0 and logf(L) > logu:
        L -= w; j -= 1; ne += 1
    while k > 0 and logf(R) > logu:
        R += w; k -= 1; ne += 1
    while True:
        x1 = L + (R - L) * rng.uniform()
        ne += 1
        if logf(x1) > logu:
            return x1, ne
        if x1 < x:
            L = x1
        else:
            R = x1


def slice_sample(logp, x0, widths, n, rng, burnin=0):
    """Coordinate-wise slice sampling (one auxiliary height per coordinate, as in the text)."""
    x = np.array(x0, float).reshape(-1)
    widths = np.broadcast_to(np.asarray(widths, float), x.shape)
    out = []
    for s in range(n + burnin):
        for d in range(x.size):
            def f(t, d=d):
                y = x.copy(); y[d] = t
                return logp(y)
            x[d], _ = slice_1d(f, x[d], widths[d], rng)
        if s >= burnin:
            out.append(x.copy())
    return np.array(out).squeeze()


def slice_target_1d(x):
    """The unnormalised 1-d target of Figure 12.7(b)."""
    x = np.asarray(x, float)
    return np.exp(-x ** 2 / 2) * (1 + np.sin(3 * x) ** 2) * (1 + np.cos(5 * x) ** 2)


# the car-weight data of Figure 12.8: weight classes (lb), cars tested, cars with poor fuel economy
CAR_WEIGHT = np.array([2100, 2300, 2500, 2700, 2900, 3100, 3300, 3500, 3700, 3900, 4100, 4300], float)
CAR_TOTAL = np.array([48, 42, 31, 34, 31, 21, 23, 23, 21, 16, 17, 21], float)
CAR_POOR = np.array([1, 2, 0, 3, 8, 8, 14, 17, 19, 15, 17, 21], float)
CAR_X = (CAR_WEIGHT - 2800) / 1000
CAR_PRIOR_SD = 20.0


def car_logpost(b):
    """log posterior (up to a constant) of the binomial logistic regression y_i ~ Bin(n_i, sigmoid(b1 + b2 x_i))
    with independent N(0, 20^2) priors."""
    b = np.asarray(b, float)
    eta = b[..., :1] + b[..., 1:2] * CAR_X
    ll = np.sum(CAR_POOR * eta - CAR_TOTAL * np.logaddexp(0, eta), axis=-1)
    return ll - 0.5 * np.sum(b ** 2, axis=-1) / CAR_PRIOR_SD ** 2


def car_grad(b):
    b = np.asarray(b, float)
    p = common.sigmoid(b[0] + b[1] * CAR_X)
    r = CAR_POOR - CAR_TOTAL * p
    return np.array([r.sum(), (r * CAR_X).sum()]) - b / CAR_PRIOR_SD ** 2


def car_grid(n=241, lim=((-2.6, -0.9), (2.8, 5.8))):
    b1 = np.linspace(*lim[0], n)
    b2 = np.linspace(*lim[1], n)
    B1, B2 = np.meshgrid(b1, b2, indexing="ij")
    lp = car_logpost(np.stack([B1, B2], -1))
    p = np.exp(lp - lp.max())
    p /= p.sum() * (b1[1] - b1[0]) * (b2[1] - b2[0])
    return b1, b2, p


# =========================================================================== Hamiltonian Monte Carlo (Section 12.5)
def leapfrog(grad_logp, theta, v, eps, L, inv_mass):
    """L leapfrog steps (12.72)-(12.74) for H = E(theta) + v^T M^{-1} v / 2, E = -log p. Returns the path."""
    th, v = theta.copy(), v.copy()
    path = [th.copy()]
    v = v + 0.5 * eps * grad_logp(th)
    for l in range(L):
        th = th + eps * inv_mass * v
        path.append(th.copy())
        g = grad_logp(th)
        v = v + (eps if l < L - 1 else 0.5 * eps) * g
    return th, v, np.array(path)


def hmc(logp, grad_logp, theta0, eps, L, n, rng, inv_mass=None, jitter=False, max_dH=1000.0):
    """Algorithm 12.3 with a diagonal inverse mass matrix (the momentum is v ~ N(0, M), M = diag(1/inv_mass)).
    A trajectory whose energy error exceeds max_dH (or is not finite) is a divergence and is rejected.
    If jitter, the number of steps is uniform on {1, ..., L}. Returns draws, acceptance rate, divergence flags."""
    th = np.array(theta0, float)
    D = th.size
    im = np.ones(D) if inv_mass is None else np.asarray(inv_mass, float)
    out, div = np.empty((n, D)), np.zeros(n, bool)
    lp, acc = logp(th), 0
    for s in range(n):
        v = rng.standard_normal(D) / np.sqrt(im)
        Ls = int(rng.integers(1, L + 1)) if jitter else L
        with np.errstate(all="ignore"):
            th1, v1, _ = leapfrog(grad_logp, th, v, eps, Ls, im)
            lp1 = logp(th1)
            H0 = -lp + 0.5 * np.sum(im * v * v)
            H1 = -lp1 + 0.5 * np.sum(im * v1 * v1)
        dH = H1 - H0
        if not np.isfinite(dH) or dH > max_dH:
            div[s] = True
        elif np.log(rng.uniform()) < -dH:
            th, lp = th1, lp1
            acc += 1
        out[s] = th
    return out, acc / n, div


def hmc_warmup(logp, grad_logp, theta0, eps0, L, n_warm, rng, target=0.8, max_dH=1000.0):
    """Warm-up: HMC steps whose log step size is moved by a Robbins-Monro rule towards an average acceptance
    probability `target`. Returns the final state and step size (the warm-up draws are discarded)."""
    th = np.array(theta0, float)
    leps = np.log(eps0)
    lp = logp(th)
    for t in range(n_warm):
        v = rng.standard_normal(th.size)
        with np.errstate(all="ignore"):
            th1, v1, _ = leapfrog(grad_logp, th, v, np.exp(leps), L, np.ones(th.size))
            lp1 = logp(th1)
            dH = (-lp1 + 0.5 * v1 @ v1) - (-lp + 0.5 * v @ v)
        a = 0.0 if (not np.isfinite(dH) or dH > max_dH) else min(1.0, np.exp(-dH))
        if a > 0 and rng.uniform() < a:
            th, lp = th1, lp1
        leps += (a - target) / np.sqrt(t + 1.0)
    return th, float(np.exp(leps))


def mala(logp, grad_logp, theta0, eps, n, rng):
    """MALA = HMC with one leapfrog step and unit mass (Algorithm 12.4)."""
    out, a, _ = hmc(logp, grad_logp, theta0, eps, 1, n, rng)
    return out, a


def mala_by_proposal(logp, grad_logp, theta, eps, rng):
    """One MALA step written as Metropolis-Hastings with the Langevin proposal
    N(theta + (eps^2/2) grad log p(theta), eps^2 I), for comparing with the HMC form."""
    h = eps ** 2 / 2
    mean = lambda t: t + h * grad_logp(t)
    prop = mean(theta) + eps * rng.standard_normal(theta.size)
    lq = lambda a, b: -np.sum((a - mean(b)) ** 2) / (2 * eps ** 2)   # log q(a | b)
    la = logp(prop) - logp(theta) + lq(theta, prop) - lq(prop, theta)
    return prop, la


def ula(grad_logp, theta0, h, n, rng):
    """Unadjusted Langevin: theta' = theta + h grad log p(theta) + sqrt(2h) N(0, I) (Euler-Maruyama for (12.83))."""
    th = np.array(theta0, float)
    out = np.empty((n, th.size))
    for s in range(n):
        th = th + h * grad_logp(th) + np.sqrt(2 * h) * rng.standard_normal(th.size)
        out[s] = th
    return out


def integrate_oscillator(method, q0, p0, eps, n):
    """Euler (12.67)-(12.68), modified Euler (12.70)-(12.71) or leapfrog for H = q^2/2 + p^2/2."""
    q, p = float(q0), float(p0)
    out = [(q, p)]
    for _ in range(n):
        if method == "euler":
            q, p = q + eps * p, p - eps * q
        elif method == "modified":
            p = p - eps * q; q = q + eps * p
        else:
            p = p - 0.5 * eps * q; q = q + eps * p; p = p - 0.5 * eps * q
        out.append((q, p))
    return np.array(out)


# ==== the two-point Gaussian model of Section 12.6.2.1, sampled on (alpha, log sigma)
UNI_Y = np.array([-1.0, 1.0])
PRIORS = {"diffuse": dict(m=0.0, s=1000.0, rate=1e-4), "sensible": dict(m=1.0, s=10.0, rate=1.0)}


def unigauss_logp(th, prior):
    a, s = th[0], th[1]
    P = PRIORS[prior]
    sig = np.exp(s)
    return (-0.5 * (a - P["m"]) ** 2 / P["s"] ** 2 + np.log(P["rate"]) - P["rate"] * sig + s
            - UNI_Y.size * s - 0.5 * sum((yy - a) ** 2 for yy in UNI_Y) / sig ** 2)


def unigauss_grad(th, prior):
    a, s = th[0], th[1]
    P = PRIORS[prior]
    sig2 = np.exp(2 * s)
    return np.array([-(a - P["m"]) / P["s"] ** 2 + np.sum(UNI_Y - a) / sig2,
                     -P["rate"] * np.exp(s) + 1 - UNI_Y.size + np.sum((UNI_Y - a) ** 2) / sig2])


def unigauss_chains(prior, n_chains=3, n=500, eps=0.3, L=10, n_warm=300, seed=0):
    """Three HMC chains started from draws of the prior, each with a step-size warm-up of n_warm iterations,
    then n kept draws, as in Figures 12.13-12.16. Returns alpha, sigma, divergence flags, acceptance, step sizes."""
    rng = np.random.default_rng(seed)
    P = PRIORS[prior]
    lp = lambda t: unigauss_logp(t, prior)
    gr = lambda t: unigauss_grad(t, prior)
    res = []
    for c in range(n_chains):
        a0 = rng.normal(P["m"], P["s"])
        s0 = np.log(rng.exponential(1 / P["rate"]))
        th, e = hmc_warmup(lp, gr, [a0, s0], eps, L, n_warm, rng, target=0.9)
        dr, acc, div = hmc(lp, gr, th, e, L, n, rng)
        res.append((dr, acc, div, e))
    alpha = np.array([r[0][:, 0] for r in res])
    sigma = np.exp(np.array([r[0][:, 1] for r in res]))
    return alpha, sigma, np.array([r[2] for r in res]), [r[1] for r in res], [r[3] for r in res]


def unigauss_exact(prior, n=4001):
    """Exact posterior marginals of alpha and sigma on a grid (for checking the sensible-prior chains)."""
    a = np.linspace(-15, 15, n)
    s = np.linspace(-4, 6, n)
    A, S = np.meshgrid(a, s, indexing="ij")
    lp = unigauss_logp(np.stack([A, S]), prior)
    p = np.exp(lp - lp.max())
    p /= p.sum()
    return dict(mean_alpha=float((p * A).sum()), mean_sigma=float((p * np.exp(S)).sum()),
                sd_alpha=float(np.sqrt((p * A ** 2).sum() - (p * A).sum() ** 2)))


# ==== Neal's funnel (12.111)-(12.115): v ~ N(0, 3^2), x | v ~ N(0, e^v) (standard deviation e^{v/2})
def funnel_logp(th):
    x, v = th[0], th[1]
    return -v ** 2 / 18 - v / 2 - 0.5 * x ** 2 * np.exp(-v)


def funnel_grad(th):
    x, v = th[0], th[1]
    return np.array([-x * np.exp(-v), -v / 9 - 0.5 + 0.5 * x ** 2 * np.exp(-v)])


def funnel_nc_logp(th):
    return -th[1] ** 2 / 18 - th[0] ** 2 / 2


def funnel_nc_grad(th):
    return np.array([-th[0], -th[1] / 9])


def funnel_runs(n=1000, eps=0.2, L=25, seed=1):
    rng = np.random.default_rng(seed)
    c, ac, dc = hmc(funnel_logp, funnel_grad, [1.0, 0.0], eps, L, n, rng, jitter=True)
    z, an, dn = hmc(funnel_nc_logp, funnel_nc_grad, [1.0, 0.0], eps, L, n, rng, jitter=True)
    nc = np.c_[z[:, 0] * np.exp(z[:, 1] / 2), z[:, 1]]
    return dict(centred=c, noncentred=nc, div_c=dc, div_n=dn, acc_c=ac, acc_n=an)


# ==== SGD as Langevin: moments of the minibatch gradient (12.85)-(12.91), with L the average loss
def minibatch_grad_moments(G, B):
    """G: N x D per-example gradients of L_n. For the average loss L = (1/N) sum L_n and a minibatch of size B drawn
    with replacement, the minibatch gradient has mean grad L and covariance D(theta)/B with
    D = (1/N) sum g_n g_n^T - grad L grad L^T."""
    g = G.mean(0)
    Dm = G.T @ G / G.shape[0] - np.outer(g, g)
    return g, Dm / B


# =========================================================================== stochastic gradient MCMC (Section 12.7)
def blr_problem(N=1000, seed=3, prior_sd=10.0):
    """1-d Bayesian linear regression y_n = theta x_n + N(0, 1) with theta ~ N(0, prior_sd^2): Gaussian posterior."""
    rng = np.random.default_rng(seed)
    x = rng.standard_normal(N) * np.sqrt(1 + 0.8 * rng.uniform(size=N))
    y = 0.7 * x + rng.standard_normal(N)
    prec = np.sum(x * x) + 1 / prior_sd ** 2
    return dict(x=x, y=y, N=N, prior_sd=prior_sd, mean=np.sum(x * y) / prec, sd=1 / np.sqrt(prec), prec=prec)


def blr_grad_En(P, th, idx):
    """gradient of E_n(theta) = (y_n - theta x_n)^2 / 2 + theta^2 / (2 N prior_sd^2), (12.119), for n in idx."""
    x, y = P["x"][idx], P["y"][idx]
    return x * (th * x - y) + th / (P["N"] * P["prior_sd"] ** 2)


def sgld_family(P, h, n, B, rng, method="sgld", tau=50, theta0=None):
    """SGLD (12.123), SGLD-CV (12.124) or SVRG-LD (Algorithm 12.5, gradient added; snapshot every tau steps)."""
    N = P["N"]
    th = P["mean"] if theta0 is None else theta0
    full = lambda t: np.sum(blr_grad_En(P, t, np.arange(N)))
    ref = P["mean"]
    gref = full(ref)
    out = np.empty(n)
    for t in range(n):
        if method == "svrg" and t % tau == 0:
            ref, gref = th, full(th)
        idx = rng.integers(0, N, B)
        if method == "sgld":
            g = N / B * np.sum(blr_grad_En(P, th, idx))
        elif method == "ula":
            g = full(th)
        else:
            g = gref + N / B * np.sum(blr_grad_En(P, th, idx) - blr_grad_En(P, ref, idx))
        th = th - h * g + np.sqrt(2 * h) * rng.standard_normal()
        out[t] = th
    return out


def ula_gauss_var(s2, h):
    """Stationary variance of ULA on N(m, s2) with step h: s2 / (1 - h / (2 s2)), valid for h < 2 s2."""
    return s2 / (1 - h / (2 * s2))


# =========================================================================== random walk on {0..20} (Figure 12.11)
def rw_integers_T(n=21):
    """Propose +-1 with probability 1/2 each; moves off the ends are rejected (the walker stays)."""
    T = np.zeros((n, n))
    for i in range(n):
        T[i, max(i - 1, 0)] += 0.5
        T[i, min(i + 1, n - 1)] += 0.5
    return T


def rw_integers_dists(x0, ts, n=21):
    T = rw_integers_T(n)
    p0 = np.zeros(n); p0[x0] = 1
    return {t: p0 @ np.linalg.matrix_power(T, t) for t in ts}


def tv_to_uniform(T, x0, tmax):
    n = T.shape[0]
    p = np.zeros(n); p[x0] = 1
    out = []
    for _ in range(tmax + 1):
        out.append(0.5 * np.abs(p - 1 / n).sum())
        p = p @ T
    return np.array(out)


def conductance(T, pi):
    """Exact conductance (12.96) with the stationary weights, min over subsets with pi(S) <= 1/2 (small chains:
    contiguous intervals suffice for a path graph; here all 2^n subsets are not needed, see the notes)."""
    n = T.shape[0]
    best = np.inf
    for a in range(n):
        for b in range(a, n):
            S = np.zeros(n, bool); S[a:b + 1] = True
            if pi[S].sum() > 0.5 + 1e-12:
                continue
            flow = (pi[S][:, None] * T[np.ix_(S, ~S)]).sum()
            best = min(best, flow / pi[S].sum())
    return best


# =========================================================================== reversible jump MCMC for RBF regression (Section 12.8)
RBF_WIDTH = 0.06
RJ = dict(delta2=20.0, nu0=1.0, gamma0=0.1, lam=1.0, kmax=6, beta=0.1)


def rbf_problem(seed=4, n_train=100, n_test=100):
    rng = np.random.default_rng(seed)
    f = lambda x: 3.0 * np.exp(-0.5 * ((x - 0.3) / 0.06) ** 2) - 2.5 * np.exp(-0.5 * ((x - 0.72) / 0.07) ** 2) + 1.0 * x
    xtr = np.sort(rng.uniform(0, 1, n_train))
    xte = np.sort(rng.uniform(0, 1, n_test))
    s = 0.5
    return dict(xtr=xtr, ytr=f(xtr) + s * rng.standard_normal(n_train), xte=xte, yte=f(xte) + s * rng.standard_normal(n_test),
                f=f, omega=(-0.1, 1.1))


def rbf_design(x, mu):
    mu = np.atleast_1d(mu)
    Phi = np.exp(-0.5 * ((x[:, None] - mu[None, :]) / RBF_WIDTH) ** 2)
    return np.c_[Phi, np.ones_like(x), x]


def rbf_log_marglik(x, y, mu, delta2=None, nu0=None, gamma0=None):
    """log p(y | k, mu) with coefficients ~ N(0, sigma^2 delta2 (D^T D)^{-1}) and sigma^2 ~ IG(nu0/2, gamma0/2)
    integrated out: const - (m/2) log(1 + delta2) - ((nu0 + N)/2) log(gamma0 + y^T P y), m = k + 2 columns,
    P = I - delta2/(1 + delta2) H, H the hat matrix of the design D."""
    delta2 = RJ["delta2"] if delta2 is None else delta2
    nu0 = RJ["nu0"] if nu0 is None else nu0
    gamma0 = RJ["gamma0"] if gamma0 is None else gamma0
    D = rbf_design(x, mu)
    N, m = D.shape
    Q, Rr = np.linalg.qr(D)
    if np.min(np.abs(np.diag(Rr))) < 1e-8 * np.max(np.abs(np.diag(Rr))):
        return -np.inf
    Hy = Q @ (Q.T @ y)
    q = y @ y - delta2 / (1 + delta2) * (y @ Hy)
    c = special.gammaln((nu0 + N) / 2) - special.gammaln(nu0 / 2) - N / 2 * np.log(np.pi) + nu0 / 2 * np.log(gamma0)
    return c - m / 2 * np.log1p(delta2) - (nu0 + N) / 2 * np.log(gamma0 + q)


def rbf_log_prior_k(k, lam=None, kmax=None):
    lam = RJ["lam"] if lam is None else lam
    kmax = RJ["kmax"] if kmax is None else kmax
    if k < 0 or k > kmax:
        return -np.inf
    ks = np.arange(kmax + 1)
    return stats.poisson.logpmf(k, lam) - special.logsumexp(stats.poisson.logpmf(ks, lam))


def rbf_move_probs(k, kmax):
    """b_k, d_k, s_k, m_k (birth, death, split, merge); the rest is a parameter update."""
    b = 0.2 if k < kmax else 0.0
    d = 0.2 if k > 0 else 0.0
    s = 0.2 if 0 < k < kmax else 0.0
    m = 0.2 if k > 1 else 0.0
    return b, d, s, m


def rjmcmc_rbf(x, y, n_iter, rng, omega=(-0.1, 1.1), kmax=None, rw_sd=0.02, return_mu=False):
    """Algorithm 12.6 for the RBF model with the coefficients and noise integrated out. The state is the sorted
    vector of centres (an unordered set; its density is k! / |Omega|^k under the uniform prior). Acceptance
    ratios (derived in the notes):
      birth/death: lik ratio * p(k+1)/p(k) * d_{k+1}/b_k
      split/merge: lik ratio * p(k+1)/p(k) * (k+1)/|Omega| * m_{k+1}/s_k * 2 beta   (u ~ U(0, 1))."""
    kmax = RJ["kmax"] if kmax is None else kmax
    beta = RJ["beta"]
    lo, hi = omega
    W = hi - lo
    mu = np.array([])
    ll = rbf_log_marglik(x, y, mu)
    ks, mus = np.empty(n_iter, int), []
    nacc = dict(birth=0, death=0, split=0, merge=0, update=0)
    for it in range(n_iter):
        k = mu.size
        b, d, s, m = rbf_move_probs(k, kmax)
        u = rng.uniform()
        if u < b:                                     # birth
            new = np.sort(np.r_[mu, lo + W * rng.uniform()])
            ll1 = rbf_log_marglik(x, y, new)
            la = ll1 - ll + rbf_log_prior_k(k + 1, kmax=kmax) - rbf_log_prior_k(k, kmax=kmax) + np.log(rbf_move_probs(k + 1, kmax)[1] / b)
            if np.log(rng.uniform()) < la:
                mu, ll = new, ll1; nacc["birth"] += 1
        elif u < b + d:                               # death
            j = rng.integers(k)
            new = np.delete(mu, j)
            ll1 = rbf_log_marglik(x, y, new)
            la = ll1 - ll + rbf_log_prior_k(k - 1, kmax=kmax) - rbf_log_prior_k(k, kmax=kmax) + np.log(rbf_move_probs(k - 1, kmax)[0] / d)
            if np.log(rng.uniform()) < la:
                mu, ll = new, ll1; nacc["death"] += 1
        elif u < b + d + s:                           # split
            j = rng.integers(k)
            uu = rng.uniform()
            m1, m2 = mu[j] - uu * beta, mu[j] + uu * beta
            rest = np.delete(mu, j)
            ok = lo <= m1 and m2 <= hi and not np.any((rest > m1) & (rest < m2))
            if ok:
                new = np.sort(np.r_[rest, m1, m2])
                ll1 = rbf_log_marglik(x, y, new)
                la = (ll1 - ll + rbf_log_prior_k(k + 1, kmax=kmax) - rbf_log_prior_k(k, kmax=kmax)
                      + np.log((k + 1) / W) + np.log(rbf_move_probs(k + 1, kmax)[3] / s) + np.log(2 * beta))
                if np.log(rng.uniform()) < la:
                    mu, ll = new, ll1; nacc["split"] += 1
        elif u < b + d + s + m:                       # merge an adjacent pair
            j = rng.integers(k - 1)
            m1, m2 = mu[j], mu[j + 1]
            if m2 - m1 < 2 * beta:
                new = np.sort(np.r_[np.delete(mu, [j, j + 1]), 0.5 * (m1 + m2)])
                ll1 = rbf_log_marglik(x, y, new)
                la = (ll1 - ll + rbf_log_prior_k(k - 1, kmax=kmax) - rbf_log_prior_k(k, kmax=kmax)
                      - np.log(k / W) + np.log(rbf_move_probs(k - 1, kmax)[2] / m) - np.log(2 * beta))
                if np.log(rng.uniform()) < la:
                    mu, ll = new, ll1; nacc["merge"] += 1
        elif k > 0:                                   # random-walk update of one centre
            j = rng.integers(k)
            new = mu.copy(); new[j] += rw_sd * rng.standard_normal()
            if lo <= new[j] <= hi:
                new = np.sort(new)
                ll1 = rbf_log_marglik(x, y, new)
                if np.log(rng.uniform()) < ll1 - ll:
                    mu, ll = new, ll1; nacc["update"] += 1
        ks[it] = mu.size
        if return_mu:
            mus.append(mu.copy())
    return (ks, mus, nacc) if return_mu else (ks, nacc)


def rbf_predict(x, y, mu, xnew, delta2=None):
    """Posterior mean of f(xnew) given the centres: the coefficients' posterior mean is delta2/(1+delta2) times
    the least-squares fit."""
    delta2 = RJ["delta2"] if delta2 is None else delta2
    D = rbf_design(x, mu)
    coef = np.linalg.lstsq(D, y, rcond=None)[0] * delta2 / (1 + delta2)
    return rbf_design(xnew, mu) @ coef


def rbf_exact_k_posterior(x, y, kmax=2, omega=(-0.1, 1.1), ngrid=241):
    """p(k | y) for k = 0..kmax (kmax <= 2) by quadrature over the centres: Z_k = |Omega|^{-k} int_{Omega^k} p(y|mu) dmu."""
    lo, hi = omega
    g = np.linspace(lo, hi, ngrid)
    dg = g[1] - g[0]
    wts = np.full(ngrid, dg); wts[[0, -1]] = dg / 2
    logZ = [rbf_log_marglik(x, y, np.array([]))]
    if kmax >= 1:
        l1 = np.array([rbf_log_marglik(x, y, np.array([a])) for a in g])
        logZ.append(special.logsumexp(l1, b=wts) - np.log(hi - lo))
    if kmax >= 2:
        l2 = np.full((ngrid, ngrid), -np.inf)
        for i in range(ngrid):
            for j in range(i + 1, ngrid):
                l2[i, j] = rbf_log_marglik(x, y, np.array([g[i], g[j]]))
        l2 = np.maximum(l2, l2.T)       # symmetric; the diagonal (singular design) has measure zero
        logZ.append(special.logsumexp(l2, b=np.outer(wts, wts)) - 2 * np.log(hi - lo))
    lp = np.array([logZ[k] + rbf_log_prior_k(k, kmax=kmax) for k in range(kmax + 1)])
    return np.exp(lp - special.logsumexp(lp))


# =========================================================================== annealing (Section 12.9)
def peaks(x, y):
    return (3 * (1 - x) ** 2 * np.exp(-x ** 2 - (y + 1) ** 2) - 10 * (x / 5 - x ** 3 - y ** 5) * np.exp(-x ** 2 - y ** 2)
            - np.exp(-(x + 1) ** 2 - y ** 2) / 3)


def peaks_p(x, y):
    """The unnormalised target (12.145), |peaks|, on [-3, 3]^2."""
    return np.abs(peaks(x, y))


PEAKS_MAX = None


def peaks_grid(n=101):
    g = np.linspace(-3, 3, n)
    X, Y = np.meshgrid(g, g, indexing="xy")
    return g, X, Y, peaks_p(X, Y)


def simulated_annealing(n, rng, x0=(0.0, 0.0), sd=0.6, T0=1.0, gamma=0.9):
    """Metropolis with acceptance exp(-(E(x') - E(x))/T_t), E = -log p, T_{t+1} = gamma T_t, (12.146).
    Proposals outside [-3, 3]^2 are rejected (zero probability)."""
    x = np.array(x0, float)
    E = lambda z: -np.log(peaks_p(z[0], z[1]) + 1e-300)
    e = E(x)
    T = T0
    xs, Ts, ps = [x.copy()], [T], [np.exp(-e)]
    for _ in range(n):
        xp = x + sd * rng.standard_normal(2)
        if np.all(np.abs(xp) <= 3):
            ep = E(xp)
            if np.log(rng.uniform()) < -(ep - e) / T:
                x, e = xp, ep
        T *= gamma
        xs.append(x.copy()); Ts.append(T); ps.append(np.exp(-e))
    return np.array(xs), np.array(Ts), np.array(ps)


def tempering_swap_logratio(beta_i, beta_j, E_i, E_j):
    """log acceptance of swapping the states of two tempered chains targeting exp(-beta E)."""
    return (beta_i - beta_j) * (E_i - E_j)


# =========================================================================== optimal scaling of RWM (gap 12.2)
def rwm_gauss_scaling(D, ells, n, rng):
    """RWM on N(0, I_D) with tau = ell / sqrt(D): acceptance rate and expected squared jump distance."""
    acc, esjd = [], []
    for ell in ells:
        tau = ell / np.sqrt(D)
        x = rng.standard_normal(D)
        lp = -0.5 * x @ x
        a, sj = 0, 0.0
        for _ in range(n):
            xp = x + tau * rng.standard_normal(D)
            lpp = -0.5 * xp @ xp
            if np.log(rng.uniform()) < lpp - lp:
                sj += np.sum((xp - x) ** 2)
                x, lp = xp, lpp
                a += 1
        acc.append(a / n); esjd.append(sj / n)
    return np.array(acc), np.array(esjd)


def rwm_limit_acceptance(ell):
    """Limit acceptance rate 2 Phi(-ell/2) of RWM with tau = ell/sqrt(D) on a product Gaussian (D -> infinity)."""
    return 2 * stats.norm.cdf(-np.asarray(ell) / 2)


# =========================================================================== browser-demo ports
class DKRng:
    """Exact port of DK.rng in ../../demo-kit.js (mulberry32 uniforms; Box-Muller normals with a spare)."""

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

    @staticmethod
    def _imul(x, y):
        return (x * y) & 0xFFFFFFFF

    def u(self):
        M = 0xFFFFFFFF
        self.a = (self.a + 0x6D2B79F5) & M
        a = self.a
        t = self._imul(a ^ (a >> 15), 1 | a)
        t = ((t + self._imul(t ^ (t >> 7), 61 | t)) & M) ^ t
        return ((t ^ (t >> 14)) & M) / 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 = np.sqrt(-2 * np.log(self.pos()))
        th = 2 * np.pi * self.u()
        self.spare = r * np.sin(th)
        return r * np.cos(th)


def _gmm_logp_scalar(x):
    a = np.log(0.3) - 0.5 * ((x + 20) / 10) ** 2
    b = np.log(0.7) - 0.5 * ((x - 20) / 10) ** 2
    m = max(a, b)
    return m + np.log(np.exp(a - m) + np.exp(b - m))     # up to the constant -log(10 sqrt(2 pi))


DEMO_MH_STARTS = [20.0, -40.0, 5.0, 60.0]


def demo_mh_run(sampler, tau, n, seed, chains=4, maxlag=1000):
    """What mh-proposal-demo.html computes: `chains` chains from DEMO_MH_STARTS, generator seed + 1000 c for chain c."""
    out, accs = [], []
    for c in range(chains):
        r = DKRng(seed + 1000 * c)
        x = DEMO_MH_STARTS[c]
        lp = _gmm_logp_scalar(x)
        xs = np.empty(n)
        acc = 0
        for s in range(n):
            if sampler == "gibbs":
                a = np.log(0.3) - 0.5 * ((x + 20) / 10) ** 2
                b = np.log(0.7) - 0.5 * ((x - 20) / 10) ** 2
                p1 = 1 / (1 + np.exp(a - b))
                z = 1 if r.u() < p1 else 0
                x = (20.0 if z else -20.0) + 10.0 * r.norm()
                acc += 1
            else:
                xp = x + tau * r.norm()
                lpp = _gmm_logp_scalar(xp)
                if np.log(r.u()) < lpp - lp:
                    x, lp = xp, lpp
                    acc += 1
            xs[s] = x
        out.append(xs); accs.append(acc / n)
    C = np.array(out)
    rho = np.mean([acf_direct(c, min(maxlag, n - 1)) for c in C], axis=0)
    s_ = 0.0
    for l in range(1, rho.size):
        if rho[l] <= 0:
            break
        s_ += rho[l]
    return dict(chains=C, acc=float(np.mean(accs)), acc_chain=accs, rhat=rhat(C), ess=n * chains / (1 + 2 * s_),
                mean=float(C.mean()), frac_neg=float((C < 0).mean()), rho=rho)


# ==== HMC demo targets: correlated Gaussian, funnel (both parameterisations), car posterior
GAUSS_RHO = 0.95
GAUSS_SD = np.array([1.0, 1.0])


def demo_target(name):
    if name == "gauss":
        S = np.array([[1, GAUSS_RHO], [GAUSS_RHO, 1]]) * np.outer(GAUSS_SD, GAUSS_SD)
        Pm = np.linalg.inv(S)
        return (lambda t: -0.5 * t @ Pm @ t), (lambda t: -Pm @ t)
    if name == "funnel":
        return funnel_logp, funnel_grad
    if name == "funnelnc":
        return funnel_nc_logp, funnel_nc_grad
    if name == "cars":
        return car_logpost, car_grad
    raise KeyError(name)


DEMO_HMC_START = {"gauss": [-2.0, 2.0], "funnel": [1.0, 0.0], "funnelnc": [1.0, 0.0], "cars": [-1.0, 3.5]}


def demo_hmc_run(target, eps, L, n, seed, method="hmc", tau=0.5, max_dH=1000.0):
    """What hmc-leapfrog-demo.html computes (unit mass). method 'hmc' or 'rwm' (proposal N(x, tau^2 I))."""
    logp, grad = demo_target(target)
    r = DKRng(seed)
    th = np.array(DEMO_HMC_START[target], float)
    lp = logp(th)
    out, acc, ndiv, dHs = np.empty((n, 2)), 0, 0, []
    for s in range(n):
        if method == "rwm":
            prop = th + tau * np.array([r.norm(), r.norm()])
            lpp = logp(prop)
            if np.log(r.u()) < lpp - lp:
                th, lp = prop, lpp
                acc += 1
        else:
            v = np.array([r.norm(), r.norm()])
            H0 = -lp + 0.5 * v @ v
            t1, v1 = th.copy(), v + 0.5 * eps * grad(th)
            bad = False
            with np.errstate(all="ignore"):
                for l in range(L):
                    t1 = t1 + eps * v1
                    g = grad(t1)
                    v1 = v1 + (eps if l < L - 1 else 0.5 * eps) * g
                    if not np.all(np.isfinite(t1)):
                        bad = True
                        break
                lp1 = logp(t1) if not bad else -np.inf
                dH = (-lp1 + 0.5 * v1 @ v1) - H0
            u = r.u()
            if bad or not np.isfinite(dH) or dH > max_dH:
                ndiv += 1
            else:
                dHs.append(dH)
                if np.log(u) < -dH:
                    th, lp = t1, lp1
                    acc += 1
        out[s] = th
    return dict(draws=out, acc=acc / n, div=ndiv, mean=out.mean(0), sd=out.std(0), ess=[ess(out[:, 0]), ess(out[:, 1])],
                vmin=float(out[:, 1].min()))


def demo_ising_run(L, J, sweeps, seed, method="gibbs", start="plus"):
    """What swendsen-wang-demo.html computes, site by site in raster order (open loops; slow but exact)."""
    r = DKRng(seed)
    n = L * L
    if start == "plus":
        x = np.ones(n, int)
    else:
        x = np.array([1 if r.u() < 0.5 else -1 for _ in range(n)])
    pb = 1 - np.exp(-2 * J)
    mags, ncl = [], []
    for _ in range(sweeps):
        if method == "gibbs":
            for c in (0, 1):
                for i in range(L):
                    for j in range(L):
                        if (i + j) % 2 != c:
                            continue
                        eta = x[((i - 1) % L) * L + j] + x[((i + 1) % L) * L + j] + x[i * L + (j - 1) % L] + x[i * L + (j + 1) % L]
                        p = 1 / (1 + np.exp(-2 * J * eta))
                        x[i * L + j] = 1 if r.u() < p else -1
        else:
            parent = list(range(n))

            def find(a):
                while parent[a] != a:
                    parent[a] = parent[parent[a]]
                    a = parent[a]
                return a
            for i in range(L):
                for j in range(L):
                    s_ = i * L + j
                    for t_ in (i * L + (j + 1) % L, ((i + 1) % L) * L + j):
                        if x[s_] == x[t_] and r.u() < pb:
                            ra, rb = find(s_), find(t_)
                            if ra != rb:
                                parent[max(ra, rb)] = min(ra, rb)
            spin, k = {}, 0
            for s_ in range(n):
                rt = find(s_)
                if rt not in spin:
                    spin[rt] = 1 if r.u() < 0.5 else -1
                    k += 1
                x[s_] = spin[rt]
            ncl.append(k)
        mags.append(x.mean())
    return dict(mags=np.array(mags), ncl=ncl, x=x.reshape(L, L))


# =========================================================================== figures
def _hist_vs_density(ax, xs, grid, dens, bins=60, rng_=(-100, 100), colour=BLUE):
    ax.hist(xs, bins=bins, range=rng_, density=True, color=colour, alpha=0.45, edgecolor="none")
    ax.plot(grid, dens, color=RED, lw=1.5)


def fig_12_1(out=None):
    """Random walk Metropolis on a two-component mixture with tau = 1, 500, 8."""
    grid = np.linspace(-100, 100, 801)
    dens = np.exp(gmm1d_logpdf(grid))
    fig, axes = plt.subplots(2, 3, figsize=(10.5, 4.8), gridspec_kw=dict(height_ratios=[1.3, 1]))
    for c, (tau, lab) in enumerate([(1, "a"), (500, "b"), (8, "c")]):
        xs, a = rwm(gmm1d_logpdf, 20.0, tau, 1000, np.random.default_rng(10 + c))
        ax = axes[0, c]
        ax.plot(xs, color=BLUE, lw=0.8)
        ax.set_ylim(-80, 80); ax.set_xlabel("iteration"); ax.set_title(r"MH with $\mathcal{N}(0,%d^2)$ proposal" % tau)
        ax.text(0.97, 0.05, "acceptance %.2f" % a, transform=ax.transAxes, ha="right", fontsize=8.5)
        panel_label(ax, lab)
        ax = axes[1, c]
        _hist_vs_density(ax, xs, grid, dens)
        ax.set_xlabel("x"); ax.set_ylim(0, 0.08)
    axes[0, 0].set_ylabel("sample"); axes[1, 0].set_ylabel("density")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-1", out)


def fig_12_3(out=None):
    """Ising-prior image denoising by Gibbs sampling (J = 1, sigma = 2)."""
    x, y = ising_denoise_problem()
    S = ising_denoise_gibbs(y, 1.0, 2.0, 15, np.random.default_rng(5))
    fig, axes = plt.subplots(1, 5, figsize=(12, 2.8))
    ims = [(x, "true image"), (y, r"noisy, $\sigma=2$"), (S[0], "sample 1, Gibbs"), (S[4], "sample 5, Gibbs"),
           (S.mean(0), "mean after 15 sweeps")]
    for ax, (im, t) in zip(axes, ims):
        h = ax.imshow(im, cmap="gray", vmin=-1, vmax=1)
        ax.set_title(t); ax.set_xticks([]); ax.set_yticks([])
    fig.colorbar(h, ax=axes, fraction=0.012, pad=0.01)
    return savefig(fig, CH, "fig12-3", out)


def fig_12_4(out=None):
    """Gibbs sampling of the mixture with known parameters."""
    xs, zs = gibbs_gmm1d(20.0, 1000, np.random.default_rng(7))
    grid = np.linspace(-100, 100, 801)
    fig, axes = plt.subplots(1, 2, figsize=(9.5, 3.2), gridspec_kw=dict(width_ratios=[1.6, 1]))
    ax = axes[0]
    for k, col in ((0, RED), (1, BLUE)):
        ax.scatter(np.where(zs == k)[0], xs[zs == k], s=3, color=col, label="z = %d" % (k + 1))
    ax.set_xlabel("sample number"); ax.set_ylabel("value of x"); ax.legend(loc="lower right", fontsize=8, markerscale=3)
    panel_label(ax, "a")
    ax = axes[1]
    _hist_vs_density(ax, xs, grid, np.exp(gmm1d_logpdf(grid)))
    ax.set_xlabel("x"); ax.set_ylabel("density"); panel_label(ax, "b")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-4", out)


def fig_12_5(out=None):
    """Gibbs sampling on a strongly correlated Gaussian (rho = 0.99)."""
    rho = 0.99
    path, _ = gibbs_gauss2d(rho, 25, [-1.4, -1.0], np.random.default_rng(2))
    fig, ax = plt.subplots(figsize=(4.2, 4.2))
    ex, ey = common.ellipse_xy(np.zeros(2), np.array([[1, rho], [rho, 1]]), 2.0)
    ax.plot(ex, ey, color=RED, lw=1.4)
    ax.plot(path[:, 0], path[:, 1], color=BLUE, lw=1.0, marker="o", ms=2)
    ax.plot(*path[0], "s", color=BLUE, ms=5)
    c = 0.7
    sd = np.sqrt(1 - rho ** 2)
    t = np.linspace(-3, 3, 400)
    ax.plot(t, stats.norm.pdf(t, rho * c, sd) * 0.12 - 3, color=GREEN, lw=1.2)
    ax.plot([rho * c - sd, rho * c + sd], [-2.45, -2.45], color=GREEN, lw=1.5, marker="|", ms=8)
    ax.text(rho * c + sd + 0.1, -2.5, r"$\ell$", color=GREEN)
    ax.annotate("", xy=(-2, 2.4), xytext=(2, 2.4), arrowprops=dict(arrowstyle="<->"))
    ax.text(0, 2.55, r"$L$", ha="center")
    ax.set_xlim(-3, 3); ax.set_ylim(-3, 3); ax.set_aspect("equal")
    ax.set_xlabel(r"$x_1$"); ax.set_ylabel(r"$x_2$")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-5", out)


def fig_12_7(out=None):
    """Slice sampling: one step drawn on the target, and 4000 draws."""
    rng = np.random.default_rng(123)
    logf = lambda t: np.log(slice_target_1d(t))
    g = np.linspace(-5, 4, 2000)
    f = slice_target_1d(g)
    from scipy import integrate
    Z = integrate.quad(slice_target_1d, -12, 12, limit=400)[0]
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.4))
    ax = axes[0]
    x0 = 0.55
    u = 0.62 * slice_target_1d(x0)
    ax.plot(g, f, color="k", lw=1.3)
    ax.plot([x0, x0], [0, slice_target_1d(x0)], color=BLUE, lw=1.2)
    inside = f >= u
    ax.fill_between(g, 0, u, where=inside, color=ORANGE, alpha=0.35, step="mid")
    ax.axhline(u, color=ORANGE, lw=1, ls="--")
    r2 = np.random.default_rng(4)
    while True:
        x1 = r2.uniform(-5, 4)
        if slice_target_1d(x1) >= u:
            break
    ax.plot([x0], [u], "o", color=BLUE); ax.plot([x1], [u], "o", color=RED)
    ax.text(x0 + 0.08, 0.05, r"$x^{(i)}$", color=BLUE); ax.text(x1 + 0.08, u + 0.15, r"$x^{(i+1)}$", color=RED)
    ax.text(-4.8, u + 0.08, r"$v^{(i+1)}$", color=ORANGE)
    ax.set_xlim(-5, 4); ax.set_xlabel("x"); ax.set_ylabel(r"$\tilde p(x)$"); panel_label(ax, "a", "upper right")
    xs = slice_sample(logf, [1.0], 5.0, 4000, rng, burnin=1000)
    ax = axes[1]
    cnt, edges, _ = ax.hist(xs, bins=75, range=(-5, 4), color=BLUE, alpha=0.5, edgecolor="k", lw=0.3)
    bw = edges[1] - edges[0]
    ax.plot(g, xs.size * bw * f / Z, color=RED)
    ax.set_xlim(-5, 4); ax.set_xlabel("x"); ax.set_ylabel("count"); panel_label(ax, "b")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-7", out)


def car_slice_draws(n=1000, burnin=300, seed=123):
    return slice_sample(car_logpost, [1.0, 1.0], [5.0, 5.0], n, np.random.default_rng(seed), burnin=burnin)


def fig_12_8(out=None):
    """Posterior of the binomial logistic regression: slice sampling against a grid."""
    S = car_slice_draws()
    b1, b2, p = car_grid()
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.9))
    ax = axes[0]
    H, e1, e2 = np.histogram2d(S[:, 0], S[:, 1], bins=24, range=[[-2.6, -0.9], [2.8, 5.8]], density=True)
    ax.pcolormesh(e2, e1, H, cmap="viridis", shading="flat", rasterized=True)
    ax.set_title("slice sampling (1000 draws)")
    ax = axes[1]
    ax.pcolormesh(b2, b1, p, cmap="viridis", shading="auto", rasterized=True)
    ax.set_title("grid approximation")
    for a, l in zip(axes, "ab"):
        a.set_xlabel(r"slope $\beta_2$"); a.set_ylabel(r"intercept $\beta_1$"); a.contour(b2, b1, p, levels=4, colors="w", linewidths=0.6)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-8", out)


def fig_12_11(out=None):
    """Convergence of the random walk on {0, ..., 20} from x0 = 10 and x0 = 17."""
    ts = [0, 1, 2, 3, 10, 100, 200, 400]
    fig, axes = plt.subplots(len(ts), 2, figsize=(8, 7.5), sharex=True)
    for c, x0 in enumerate((10, 17)):
        P = rw_integers_dists(x0, ts)
        for r, t in enumerate(ts):
            ax = axes[r, c]
            ax.vlines(np.arange(21), 0, P[t], color=BLUE, lw=1.2)
            ax.plot(np.arange(21), P[t], "o", color=RED, ms=2.5)
            ax.set_yticks([]); ax.set_ylim(0, P[t].max() * 1.18)
            ax.set_ylabel(r"$p_{%d}(x)$" % t, rotation=0, labelpad=16, fontsize=9)
        axes[0, c].set_title(r"initial condition $x_0 = %d$" % x0)
        axes[-1, c].set_xlabel("x"); axes[-1, c].set_xticks(range(0, 21, 5))
    fig.tight_layout()
    return savefig(fig, CH, "fig12-11", out)


def _unigauss_figs(prior, name_trace, name_rank, out=None):
    alpha, sigma, div, acc, _ = unigauss_chains(prior)
    cols = [BLUE, ORANGE, GREEN]
    fig, axes = plt.subplots(2, 2, figsize=(10, 4.8), gridspec_kw=dict(width_ratios=[1, 1.6]))
    for r, (v, nm) in enumerate(((alpha, r"$\alpha$"), (sigma, r"$\sigma$"))):
        lo, hi = np.percentile(v, [0.5, 99.5])
        for c in range(3):
            kde = stats.gaussian_kde(v[c])
            g = np.linspace(lo, hi, 300)
            axes[r, 0].plot(g, kde(g), color=cols[c], lw=1.3)
            axes[r, 1].plot(v[c], color=cols[c], lw=0.8, label="chain %d" % (c + 1))
        axes[r, 0].set_xlabel(nm); axes[r, 0].set_yticks([])
        axes[r, 1].set_ylabel(nm)
        d = np.where(div.any(0))[0]
        if d.size:
            yl = axes[r, 1].get_ylim()
            axes[r, 1].plot(d, np.full(d.size, yl[0]), "|", color="k", ms=10, mew=1.2)
            axes[r, 1].set_ylim(yl)
    axes[0, 1].legend(fontsize=8, loc="upper right", ncol=3)
    axes[1, 1].set_xlabel("iteration")
    fig.tight_layout()
    p1 = savefig(fig, CH, name_trace, out)
    fig, axes = plt.subplots(1, 2, figsize=(10, 2.8))
    for ax, v, nm in zip(axes, (alpha, sigma), (r"$\alpha$", r"$\sigma$")):
        R = ranks_all(v)
        edges = np.linspace(0, v.size, 21)
        for c in range(3):
            h, _ = np.histogram(R[c], bins=edges)
            ax.step(edges, np.r_[h, h[-1]] / h.mean() * 0.4 + c, where="post", color=cols[c])
            ax.axhline(c + 0.4, color=GREY, lw=0.5, ls=":")
        ax.set_yticks([0, 1, 2]); ax.set_ylabel("chain"); ax.set_xlabel("rank (all chains)"); ax.set_title(nm)
    fig.tight_layout()
    savefig(fig, CH, name_rank, out)
    return p1


def fig_12_13(out=None):
    """Marginals and trace plots for the two-point Gaussian model under the diffuse prior (also Figure 12.15)."""
    return _unigauss_figs("diffuse", "fig12-13", "fig12-15", out)


def fig_12_14(out=None):
    """Marginals and trace plots under the sensible prior (also Figure 12.16)."""
    return _unigauss_figs("sensible", "fig12-14", "fig12-16", out)


def fig_12_15(out=None):
    """Trace rank plot under the diffuse prior (made with Figure 12.13)."""
    return fig_12_13(out)


def fig_12_16(out=None):
    """Trace rank plot under the sensible prior (made with Figure 12.14)."""
    return fig_12_14(out)


def fig_12_17(out=None):
    """Autocorrelation functions of the three MH samplers and the Gibbs sampler."""
    runs = [rwm(gmm1d_logpdf, 20.0, tau, 1000, np.random.default_rng(10 + c))[0] for c, tau in enumerate((1, 500, 8))]
    runs.append(gibbs_gmm1d(20.0, 1000, np.random.default_rng(7))[0])
    titles = [r"MH with $\mathcal{N}(0,1^2)$ proposal", r"MH with $\mathcal{N}(0,500^2)$ proposal",
              r"MH with $\mathcal{N}(0,8^2)$ proposal", "Gibbs sampling"]
    fig, axes = plt.subplots(2, 2, figsize=(8, 4.8), sharey=True)
    for ax, x, t, l in zip(axes.ravel(), runs, titles, "abcd"):
        r = acf(x, 40)
        ax.vlines(np.arange(41), 0, r, color=BLUE)
        ax.plot(np.arange(41), r, "o", color=BLUE, ms=2.5)
        ax.axhline(0, color="k", lw=0.6); ax.set_title(t); ax.set_ylim(-0.1, 1.05); panel_label(ax, l, "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-17", out)


def fig_12_18(out=None):
    """Neal's funnel: joint density, HMC on the centred and on the non-centred parameterisation."""
    R = funnel_runs()
    fig, axes = plt.subplots(1, 3, figsize=(12, 3.6))
    g = np.linspace(-5, 5, 400)
    X, V = np.meshgrid(g, g)
    lj = stats.norm.logpdf(V, 0, 3) + stats.norm.logpdf(X, 0, np.exp(V / 2))
    lj = np.where(lj < np.percentile(lj, 42), np.nan, lj)
    cf = axes[0].contourf(g, g, lj, levels=8, cmap="viridis_r")
    fig.colorbar(cf, ax=axes[0], fraction=0.046)
    axes[0].set_title("Neal's funnel (log density)")
    for ax, k, d, t in ((axes[1], "centred", "div_c", "centred parameterisation"), (axes[2], "noncentred", "div_n", "non-centred parameterisation")):
        S = R[k]
        ax.scatter(S[:, 0], S[:, 1], s=3, color=BLUE, alpha=0.6)
        dv = R[d]
        if dv.any():
            ax.scatter(S[dv, 0], S[dv, 1], s=10, color=RED, label="divergent")
            ax.legend(fontsize=8, loc="upper right")
        ax.set_xlim(-20, 20); ax.set_ylim(-10, 10); ax.set_title(t)
    for ax, l in zip(axes, "abc"):
        ax.set_xlabel("x"); ax.set_ylabel(r"$\nu$"); panel_label(ax, l)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-18", out)


def rbf_run(n_iter=2000, seed=11):
    P = rbf_problem()
    ks, mus, nacc = rjmcmc_rbf(P["xtr"], P["ytr"], n_iter, np.random.default_rng(seed), omega=P["omega"], return_mu=True)
    return P, ks, mus, nacc


def fig_12_20(out=None):
    """RJMCMC for an RBF network: predictions, p(k | D) against iteration, final p(k | D)."""
    P, ks, mus, _ = rbf_run()
    burn = 500
    pred_tr = np.mean([rbf_predict(P["xtr"], P["ytr"], m, P["xtr"]) for m in mus[burn::5]], 0)
    pred_te = np.mean([rbf_predict(P["xtr"], P["ytr"], m, P["xte"]) for m in mus[burn::5]], 0)
    fig, axes = plt.subplots(1, 4, figsize=(13, 3.1))
    ax = axes[0]
    ax.plot(P["xtr"], P["ytr"], "o", ms=3, color=GREY); ax.plot(P["xtr"], pred_tr, color=BLUE)
    ax.set_xlabel("train input"); ax.set_ylabel("train output")
    ax = axes[1]
    g = np.linspace(0, 1, 300)
    ax.plot(g, P["f"](g), color="k", lw=1, label="true function")
    ax.plot(P["xte"], P["yte"], "o", ms=3, color=GREY, label="test data")
    ax.plot(P["xte"], pred_te, color=RED, label="prediction")
    ax.legend(fontsize=7.5, loc="lower left"); ax.set_xlabel("test input"); ax.set_ylabel("test output")
    ax = axes[2]
    it = np.arange(1, ks.size + 1)
    for k, col in zip(range(1, 5), (BLUE, RED, GREEN, ORANGE)):
        ax.plot(it, np.cumsum(ks == k) / it, color=col, label=str(k))
    ax.legend(fontsize=8, title="k", title_fontsize=8); ax.set_xlabel("chain length"); ax.set_ylabel(r"$p(k\,|\,\mathcal{D})$"); ax.set_ylim(0, 1)
    ax = axes[3]
    kk = np.arange(0, RJ["kmax"] + 1)
    ax.bar(kk, [(ks[burn:] == k).mean() for k in kk], color=BLUE)
    ax.set_xlabel("k"); ax.set_ylabel(r"$p(k\,|\,\mathcal{D})$")
    for a, l in zip(axes, "abcd"):
        panel_label(a, l, "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-20", out)


def fig_12_21(out=None):
    """The peaks target and its energy."""
    g, X, Y, P = peaks_grid()
    Pn = P / P.max()
    E = -np.log(Pn + 1e-12)
    fig = plt.figure(figsize=(9, 3.8))
    for i, (Z, t) in enumerate(((Pn, r"$p(x,y)$ (scaled to max 1)"), (np.minimum(E, 8) / 8, r"energy $-\log p$ (clipped at 8, divided by 8)"))):
        ax = fig.add_subplot(1, 2, i + 1, projection="3d")
        ax.plot_surface(X, Y, Z, cmap="viridis", linewidth=0, antialiased=True, rcount=60, ccount=60, rasterized=True)
        ax.set_title(t, fontsize=9); ax.set_xlabel("x"); ax.set_ylabel("y"); ax.view_init(30, -60)
        ax.text2D(0.02, 0.92, "(%s)" % "ab"[i], transform=ax.transAxes)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-21", out)


def fig_12_22(out=None):
    """Tempered versions p^(1/T) of the peaks target."""
    g, X, Y, P = peaks_grid()
    Pn = P / P.max()
    fig = plt.figure(figsize=(12, 3.3))
    for i, T in enumerate((10.0, 2.0, 0.4, 0.08)):
        ax = fig.add_subplot(1, 4, i + 1, projection="3d")
        ax.plot_surface(X, Y, Pn ** (1 / T), cmap="viridis", linewidth=0, rcount=60, ccount=60, rasterized=True)
        ax.set_title("T = %.2f" % T); ax.view_init(30, -60); ax.set_zlim(0, 1)
        ax.text2D(0.02, 0.92, "(%s)" % "abcd"[i], transform=ax.transAxes)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-22", out)


def fig_12_23(out=None):
    """Simulated annealing on the peaks target (gamma = 0.9, proposal sd 0.6 = 10 grid units)."""
    xs, Ts, ps = simulated_annealing(300, np.random.default_rng(0))
    g, X, Y, P = peaks_grid()
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.7))
    ax = axes[0]
    ax.plot(Ts, color=BLUE, label="temperature")
    ax.plot(ps / P.max(), color=RED, label="probability (scaled)")
    ax.set_xlabel("iteration"); ax.legend(fontsize=8); panel_label(ax, "a", "upper right")
    ax = axes[1]
    cf = ax.contourf(g, g, P / P.max(), levels=12, cmap="viridis")
    fig.colorbar(cf, ax=ax, fraction=0.046)
    ax.plot(xs[:, 0], xs[:, 1], ".", color="w", ms=3)
    b = np.argmax(ps)
    ax.plot(xs[b, 0], xs[b, 1], "o", color=RED, ms=9)
    ax.set_xlabel("x"); ax.set_ylabel("y"); panel_label(ax, "b")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-23", out)


# ==== supplementary figures
def fig_12_S1(out=None):
    """RWM scaling in D = 20: ESJD and acceptance against ell = tau sqrt(D), with the limit curves."""
    D = 20
    ells = np.linspace(0.3, 5.0, 24)
    acc, esjd = rwm_gauss_scaling(D, ells, 6000, np.random.default_rng(8))
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.4))
    lg = np.linspace(0.05, 5.2, 300)
    ax = axes[0]
    ax.plot(ells, esjd, "o", color=BLUE, ms=4, label="simulation, D = 20")
    ax.plot(lg, lg ** 2 * rwm_limit_acceptance(lg), color=RED, label=r"limit $\ell^2\, 2\Phi(-\ell/2)$")
    ax.axvline(2.38, color=GREY, ls="--", lw=0.8)
    ax.set_xlabel(r"$\ell=\tau\sqrt{D}$"); ax.set_ylabel("expected squared jump"); ax.legend(fontsize=8)
    panel_label(ax, "a", "upper right")
    ax = axes[1]
    ax.plot(acc, esjd, "o", color=BLUE, ms=4)
    ax.plot(rwm_limit_acceptance(lg), lg ** 2 * rwm_limit_acceptance(lg), color=RED)
    ax.axvline(0.234, color=GREY, ls="--", lw=0.8)
    ax.set_xlabel("acceptance rate"); ax.set_ylabel("expected squared jump"); panel_label(ax, "b", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-S1", out)


def fig_12_S2(out=None):
    """Single-site Gibbs against Swendsen-Wang on a 32 x 32 Ising torus."""
    L, sweeps = 32, 600
    fig, axes = plt.subplots(2, 3, figsize=(11, 4.4), sharey=True, sharex=True)
    for c, J in enumerate((0.3, 0.4407, 0.6)):
        mg, _ = ising_gibbs(L, J, sweeps, np.random.default_rng(20 + c))
        ms, _ = swendsen_wang(L, J, sweeps, np.random.default_rng(30 + c))
        axes[0, c].plot(mg, color=BLUE, lw=0.8); axes[1, c].plot(ms, color=RED, lw=0.8)
        axes[0, c].set_title("J = %.4g" % J)
    axes[0, 0].set_ylabel("Gibbs: magnetisation"); axes[1, 0].set_ylabel("Swendsen-Wang")
    for a in axes[1]:
        a.set_xlabel("sweep")
    fig.tight_layout()
    return savefig(fig, CH, "fig12-S2", out)


def fig_12_S3(out=None):
    """Euler, modified Euler and leapfrog on H = q^2/2 + p^2/2 (eps = 0.3, 20 steps), and the leapfrog energy error."""
    fig, axes = plt.subplots(1, 4, figsize=(13, 3.2))
    t = np.linspace(0, 2 * np.pi, 200)
    for ax, (mth, nm) in zip(axes[:3], (("euler", "Euler"), ("modified", "modified Euler"), ("leapfrog", "leapfrog"))):
        Z = integrate_oscillator(mth, 0.0, 1.0, 0.3, 20)
        ax.plot(np.cos(t), np.sin(t), color=GREY, lw=0.8)
        ax.plot(Z[:, 0], Z[:, 1], "o-", color=BLUE, ms=3, lw=0.8)
        ax.set_aspect("equal"); ax.set_xlim(-2, 2); ax.set_ylim(-2, 2); ax.set_title(nm + r", $\eta=0.3$")
        ax.set_xlabel(r"position $\theta$"); ax.set_ylabel(r"momentum $v$")
    ax = axes[3]
    etas = np.logspace(-2, np.log10(1.9), 40)
    err = []
    for e in etas:
        n = int(np.ceil(2 * np.pi / e))
        Z = integrate_oscillator("leapfrog", 1.0, 0.0, e, n)
        H = 0.5 * (Z ** 2).sum(1)
        err.append(np.max(np.abs(H - 0.5)))
    ax.loglog(etas, err, color=BLUE, label="leapfrog, one period")
    ax.loglog(etas, etas ** 2 / 8, color=RED, ls="--", label=r"$\eta^2/8$")
    ax.set_xlabel(r"step size $\eta$"); ax.set_ylabel(r"max $|H-H_0|$"); ax.legend(fontsize=8)
    for a, l in zip(axes, "abcd"):
        panel_label(a, l)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-S3", out)


def sgld_spreads(hs, n=20000, B=10, seed=6):
    P = blr_problem()
    res = {m: [] for m in ("ula", "sgld", "cv", "svrg")}
    for i, h in enumerate(hs):
        for m in res:
            d = sgld_family(P, h, n, B, np.random.default_rng(seed + 17 * i), method=m)
            res[m].append(d[1000:].std())
    return P, {m: np.array(v) for m, v in res.items()}


def fig_12_S4(out=None):
    """Stationary spread of ULA, SGLD, SGLD-CV, SVRG-LD on a Gaussian posterior, against the step size."""
    P = blr_problem()
    s2 = P["sd"] ** 2
    hs = s2 * np.array([0.02, 0.05, 0.1, 0.2, 0.4, 0.8])
    P, R = sgld_spreads(hs)
    fig, ax = plt.subplots(figsize=(5.6, 3.6))
    hg = np.linspace(hs[0], hs[-1], 200)
    ax.axhline(1.0, color="k", lw=1, label="exact posterior")
    ax.plot(hg / s2, np.sqrt(ula_gauss_var(s2, hg) / s2), color=GREY, ls="--", label="ULA, closed form")
    for m, col, nm in (("ula", GREY, "ULA"), ("sgld", RED, "SGLD"), ("cv", BLUE, "SGLD-CV"), ("svrg", GREEN, "SVRG-LD")):
        ax.plot(hs / s2, R[m] / P["sd"], "o-", color=col, ms=4, label=nm)
    ax.set_xscale("log"); ax.set_yscale("log")
    ax.set_xlabel(r"step size $\eta/s^2$ ($s$ = posterior sd)"); ax.set_ylabel("stationary sd / posterior sd")
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-S4", out)


def fig_12_S5(out=None):
    """Total variation distance to uniform for the walk of Figure 12.11, with the spectral bound."""
    T = rw_integers_T()
    lam = np.sort(np.linalg.eigvalsh(T))[::-1]
    lstar = max(abs(lam[1]), abs(lam[-1]))
    t = np.arange(0, 601)
    fig, ax = plt.subplots(figsize=(5.6, 3.5))
    for x0, col in ((10, BLUE), (17, RED), (0, GREEN)):
        ax.semilogy(t, tv_to_uniform(T, x0, 600), color=col, label=r"$x_0=%d$" % x0)
    pi = 1 / 21
    ax.semilogy(t, 0.5 * np.sqrt((1 - pi) / pi) * lstar ** t, color="k", ls="--", label=r"bound $\frac{1}{2}\sqrt{(1-\pi)/\pi}\,\lambda_*^t$")
    ax.set_ylim(1e-4, 1.5); ax.set_xlabel("t"); ax.set_ylabel("total variation distance"); ax.legend(fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig12-S5", out)


FIGURES = {"12.1": fig_12_1, "12.3": fig_12_3, "12.4": fig_12_4, "12.5": fig_12_5, "12.7": fig_12_7, "12.8": fig_12_8,
           "12.11": fig_12_11, "12.13": fig_12_13, "12.14": fig_12_14, "12.17": fig_12_17, "12.18": fig_12_18,
           "12.20": fig_12_20, "12.21": fig_12_21, "12.22": fig_12_22, "12.23": fig_12_23,
           "12.S1": fig_12_S1, "12.S2": fig_12_S2, "12.S3": fig_12_S3, "12.S4": fig_12_S4, "12.S5": fig_12_S5}


def export_json():
    """Data for hmc-leapfrog-demo.html: the car-weight data of Figure 12.8 and the grid posterior summary."""
    os.makedirs(DATA_OUT, exist_ok=True)
    b1, b2, p = car_grid()
    dA = (b1[1] - b1[0]) * (b2[1] - b2[0])
    B1, B2 = np.meshgrid(b1, b2, indexing="ij")
    m1, m2 = (p * B1).sum() * dA, (p * B2).sum() * dA
    d = dict(weight=CAR_WEIGHT.tolist(), total=CAR_TOTAL.tolist(), poor=CAR_POOR.tolist(), x=np.round(CAR_X, 6).tolist(),
             prior_sd=CAR_PRIOR_SD, posterior_mean=[round(float(m1), 4), round(float(m2), 4)],
             posterior_sd=[round(float(np.sqrt((p * B1 ** 2).sum() * dA - m1 ** 2)), 4), round(float(np.sqrt((p * B2 ** 2).sum() * dA - m2 ** 2)), 4)])
    with open(os.path.join(DATA_OUT, "ch12-cars.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ../data/ch12-cars.json")


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
