"""Bishop and Bishop (2024), Chapter 14: Sampling.

Reproduces the figures of Chapter 14 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 429-458, written from scratch with numpy, scipy (special functions
and quadrature only) and matplotlib, and supplies the reference numbers of the three browser
demonstrations. Every algorithm is a short function meant to be read next to the lecture notes
(ch14-sampling.html):

* Section 14.1.1, Monte Carlo estimates: the plain estimator (14.2), its error for independent and
  for correlated (AR(1)) samples, the integrated autocorrelation time and effective sample size
  (iat, ar1_iat).
* Section 14.1.2, standard distributions: inverse-CDF sampling of the exponential and Cauchy
  distributions, the polar Box-Muller method (14.10)-(14.12) and the Cholesky construction.
* Sections 14.1.3-14.1.4, rejection sampling: the gamma density with a Cauchy comparison function
  (14.15)-(14.16) (gamma_cauchy_envelope, rejection_gamma) and adaptive rejection sampling with
  tangent envelopes of a log-concave density (ars_envelope, ars_sample, ars_run).
* Sections 14.1.5-14.1.6, importance sampling and sampling-importance-resampling (14.19)-(14.26).
* Section 14.2, Markov chain Monte Carlo: random-walk Metropolis (Algorithm 14.1), the random walk on
  the integers (14.28)-(14.30), Metropolis-Hastings and Gibbs transition matrices on a finite state
  space (detailed balance and its failure for a systematic scan), Gibbs sampling of a bivariate
  Gaussian with optional over-relaxation (14.46), and ancestral, logic and likelihood-weighted
  sampling (14.47)-(14.48) on a four-node Bayesian network.
* Section 14.3, Langevin sampling: a one-dimensional energy-based model with a radial-basis energy
  (EBM1D) trained by maximum likelihood (14.57) with the negative phase computed exactly on a grid,
  by Langevin chains from noise, by contrastive divergence or by persistent chains (ebm_train); the
  unadjusted Langevin algorithm (14.61) and its Metropolis-adjusted version on three
  two-dimensional targets (langevin_run); the exact stationary variance of Langevin sampling of a
  Gaussian (ula_gauss_var).
* Supplement, gradients of expectations: score-function (REINFORCE) and reparameterisation
  estimators of d/dtheta E_{N(mu, sigma^2)}[f(z)] (grad_estimates) and their exact variances.
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). langevin_run, ebm_train and grad_estimates use only that generator and plain
  floating-point arithmetic, so langevin-sampling-demo.html, ebm-training-demo.html and
  gradient-estimators-demo.html reproduce them number for number.

Figures reproduced: 14.1, 14.2, 14.3, 14.4, 14.5, 14.6, 14.7, 14.8, 14.9, 14.10, 14.11, 14.13 and
14.14. Most are schematic in the book; here each is computed from an explicit density, function or
simulation (14.1, 14.8: explicit densities and functions; 14.2: the gamma CDF and inverse-CDF
samples; 14.3: simulated uniform points in the disc; 14.4, 14.5, 14.7: actual comparison functions
with the smallest valid k; 14.6: tangent lines of a log-concave density; 14.9: a Metropolis run;
14.10, 14.11: real Gaussians with Metropolis and Gibbs paths; 14.13: a one-dimensional energy-based
model whose model samples are drawn by Langevin sampling; 14.14: two uniform discs and a Gibbs path).
Skipped: Figure 14.12 (a hand-drawn graphical model showing a Markov blanket; it has no data).

Supplementary figures (our own, numbered 14.S1-14.S6 in the order they appear in the notes; they
illustrate the gaps filled there):
14.S1 Monte Carlo error: independent of dimension, inflated by correlation, and the random walk;
14.S2 score-function versus reparameterisation gradient estimators;
14.S3 Langevin sampling and its Metropolis-adjusted version on two-dimensional energy landscapes;
14.S4 the discretisation bias of Langevin sampling against the step size, and its mixing time;
14.S5 training an energy-based model: exact gradient, Langevin chains, contrastive divergence and
persistent chains; 14.S6 contrastive divergence with one Langevin step is score matching.

Run `python3 ch14_sampling.py --list`, `python3 ch14_sampling.py` (all figures, about a minute on
one CPU thread) or `python3 ch14_sampling.py --fig 14.9 14.S4`. Files go to ../img/ch14/.
"""
import json
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from matplotlib.patches import Circle  # noqa: E402
from scipy import special, stats  # noqa: E402

import common  # noqa: E402
from common import savefig, run  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
WEB_DATA = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 14
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

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

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

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

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


# =========================================================================== 14.1.1 Monte Carlo error
def iat(x, c=5.0):
    """Integrated autocorrelation time tau = 1 + 2 sum_k rho_k of a scalar chain, with Sokal's
    automatic window (the smallest M with M >= c tau(M)). The effective sample size is len(x)/tau."""
    x = np.asarray(x, float) - np.mean(x)
    n = len(x)
    f = np.fft.rfft(x, 2 * n)
    acf = np.fft.irfft(f * np.conj(f))[:n]
    acf = acf / acf[0]
    tau = 1.0
    for M in range(1, n):
        tau = 1.0 + 2.0 * acf[1:M + 1].sum()
        if M >= c * tau:
            break
    return float(tau)


def ar1_iat(rho):
    """Integrated autocorrelation time of a stationary AR(1) chain with lag-one correlation rho:
    1 + 2 sum_k rho^k = (1 + rho)/(1 - rho)."""
    return (1.0 + rho) / (1.0 - rho)


def ar1_chain(rho, n, rng, x0=None):
    """A stationary AR(1) chain x_{t+1} = rho x_t + sqrt(1 - rho^2) e_t with N(0, 1) marginals."""
    x = np.empty(n)
    x[0] = rng.standard_normal() if x0 is None else x0
    e = rng.standard_normal(n) * math.sqrt(1 - rho * rho)
    for t in range(1, n):
        x[t] = rho * x[t - 1] + e[t]
    return x


def random_walk(T, n, rng):
    """n independent copies of the random walk (14.28)-(14.30) on the integers, T steps from 0."""
    steps = rng.choice(np.array([0, 1, -1]), p=[0.5, 0.25, 0.25], size=(n, T))
    return np.concatenate([np.zeros((n, 1), int), np.cumsum(steps, axis=1)], axis=1)


# =========================================================================== 14.1.2 standard distributions
def exponential_from_uniform(u, lam=1.0):
    """y = h^{-1}(u) for the exponential distribution (14.7): h(y) = 1 - exp(-lam y)."""
    return -np.log1p(-np.asarray(u, float)) / lam


def cauchy_from_uniform(u):
    """y = h^{-1}(u) for the Cauchy distribution (14.8): h(y) = 1/2 + arctan(y)/pi (Exercise 14.4)."""
    return np.tan(math.pi * (np.asarray(u, float) - 0.5))


def box_muller_polar(n_pairs, rng):
    """The polar Box-Muller method (14.10)-(14.11). Returns (y, z, accepted): y holds the Gaussian
    pairs, z all the proposed points in the square (-1, 1)^2 and accepted their inside-disc flags."""
    out, Z, A = [], [], []
    while len(out) < n_pairs:
        z = 2 * rng.random(2) - 1
        r2 = z @ z
        ok = 0 < r2 <= 1
        Z.append(z)
        A.append(ok)
        if ok:
            out.append(z * math.sqrt(-2 * math.log(r2) / r2))
    return np.array(out), np.array(Z), np.array(A)


def mvn_cholesky(mu, Sigma, z):
    """Rows of mu + L z with Sigma = L L^T (Exercise 14.6)."""
    L = np.linalg.cholesky(Sigma)
    return np.asarray(mu) + np.asarray(z) @ L.T


# =========================================================================== 14.1.3-14.1.4 rejection
def gamma_pdf(z, a, b=1.0):
    """Gam(z | a, b) of (14.15) (zero for z <= 0)."""
    z = np.asarray(z, float)
    out = np.zeros_like(z)
    pos = z > 0
    out[pos] = np.exp(a * math.log(b) + (a - 1) * np.log(z[pos]) - b * z[pos] - special.gammaln(a))
    return out


def gamma_cauchy_envelope(a, c=None, s=None):
    """The Cauchy comparison function k / (1 + (z - c)^2 / s^2) of (14.16) for Gam(z | a, 1).

    Defaults are the book's c = a - 1, s^2 = 2a - 1. Returns (c, s, k) with k the smallest constant
    for which the comparison function lies above the gamma density (found on a fine grid and
    refined), and the acceptance probability 1/(k pi s) (the area under the comparison function is
    k pi s, and the gamma density has area 1)."""
    c = a - 1.0 if c is None else c
    s = math.sqrt(2 * a - 1.0) if s is None else s
    z = np.linspace(1e-6, a + 60 * math.sqrt(a) + 60, 400001)
    ratio = gamma_pdf(z, a) * (1 + (z - c) ** 2 / s ** 2)
    i = int(np.argmax(ratio))
    zz = np.linspace(z[max(i - 2, 0)], z[min(i + 2, len(z) - 1)], 20001)
    k = float(np.max(gamma_pdf(zz, a) * (1 + (zz - c) ** 2 / s ** 2)))
    return c, s, k, 1.0 / (k * math.pi * s)


def rejection_gamma(a, n, rng, c=None, s=None):
    """Rejection sampling of Gam(z | a, 1) with the Cauchy comparison function (Section 14.1.3).
    Returns (accepted samples, number of proposals)."""
    c, s, k, _ = gamma_cauchy_envelope(a, c, s)
    out, tried = [], 0
    while len(out) < n:
        z0 = s * math.tan(math.pi * (rng.random() - 0.5)) + c     # Cauchy proposal (Exercise 14.8, corrected)
        u0 = rng.random() * k / (1 + (z0 - c) ** 2 / s ** 2)       # uniform on [0, k q(z0)]
        tried += 1
        if z0 > 0 and u0 <= gamma_pdf(np.array([z0]), a)[0]:
            out.append(z0)                                         # keep z0 (the book's 'u0 is retained' means z0)
    return np.array(out), tried


def ars_envelope(zs, logp, dlogp, lo=-np.inf, hi=np.inf):
    """Tangent-line envelope of a log-concave density (Section 14.1.4, Figure 14.6).

    zs: sorted abscissae where ln p and its derivative are evaluated. Returns a dict with the
    breakpoints e_0 < e_1 < ... < e_n (e_0 = lo, e_n = hi; interior breakpoints are the
    intersections of successive tangents), and for each piece i the tangent point z_i, value
    h_i = ln p(z_i) and slope g_i, so that ln q(z) = h_i + g_i (z - z_i) on (e_i, e_{i+1}].
    'mass' holds the integrals of exp(ln q) over the pieces, i.e. the piecewise-exponential form
    (14.17) with k_i lambda_i fixed by continuity and normalisation (Exercise 14.9)."""
    zs = np.asarray(zs, float)
    h = np.array([logp(z) for z in zs])
    g = np.array([dlogp(z) for z in zs])
    n = len(zs)
    e = [lo]
    for i in range(n - 1):
        # intersection of h_i + g_i (z - z_i) and h_{i+1} + g_{i+1} (z - z_{i+1})
        if abs(g[i] - g[i + 1]) < 1e-12:
            e.append(0.5 * (zs[i] + zs[i + 1]))
        else:
            e.append((h[i + 1] - h[i] - zs[i + 1] * g[i + 1] + zs[i] * g[i]) / (g[i] - g[i + 1]))
    e.append(hi)
    e = np.array(e)
    mass = np.empty(n)
    for i in range(n):
        a_, b_ = e[i], e[i + 1]
        if abs(g[i]) < 1e-12:
            mass[i] = math.exp(h[i]) * (b_ - a_)
        else:
            ea = 0.0 if (a_ == -np.inf and g[i] > 0) else math.exp(h[i] + g[i] * (a_ - zs[i]))
            eb = 0.0 if (b_ == np.inf and g[i] < 0) else math.exp(h[i] + g[i] * (b_ - zs[i]))
            mass[i] = (eb - ea) / g[i]
    return {"z": zs, "h": h, "g": g, "e": e, "mass": mass}


def ars_logq(env, z):
    """ln of the (unnormalised) envelope at the points z."""
    z = np.atleast_1d(np.asarray(z, float))
    i = np.clip(np.searchsorted(env["e"], z) - 1, 0, len(env["z"]) - 1)
    return env["h"][i] + env["g"][i] * (z - env["z"][i])


def ars_sample(env, u1, u2):
    """One draw from the normalised piecewise-exponential envelope (Exercise 14.10): choose piece i
    with probability mass_i / sum(mass) using u1, then invert the truncated-exponential CDF on that
    piece using u2."""
    m = env["mass"]
    cum = np.cumsum(m) / m.sum()
    i = int(min(np.searchsorted(cum, u1), len(m) - 1))
    a_, b_, g_ = env["e"][i], env["e"][i + 1], env["g"][i]
    if abs(g_) < 1e-12:
        return a_ + u2 * (b_ - a_)
    # q on the piece is proportional to exp(g z); its CDF from a_ is (exp(g z) - exp(g a))/(exp(g b) - exp(g a))
    if g_ > 0:          # increasing piece, a_ finite; write relative to b_ for stability
        return b_ + math.log(u2 + (1 - u2) * math.exp(g_ * (a_ - b_))) / g_ if np.isfinite(a_) else b_ + math.log(u2) / g_
    return a_ + math.log(1 - u2 + u2 * math.exp(g_ * (b_ - a_))) / g_ if np.isfinite(b_) else a_ + math.log(1 - u2) / g_


def ars_run(n, logp, dlogp, z_init, rng, lo=-np.inf, hi=np.inf, max_points=50):
    """Adaptive rejection sampling (Gilks and Wild, 1992): sample from the envelope, accept with
    probability p(z)/q(z) and add every rejected point to the abscissae. Returns (samples, number of
    proposals, final abscissae, accept flag of every proposal)."""
    zs = sorted(z_init)
    env = ars_envelope(zs, logp, dlogp, lo, hi)
    out, tried, flags = [], 0, []
    while len(out) < n:
        z = ars_sample(env, rng.random(), rng.random())
        tried += 1
        ok = math.log(rng.random()) <= logp(z) - ars_logq(env, z)[0]
        flags.append(ok)
        if ok:
            out.append(z)
        elif len(zs) < max_points:
            zs = sorted(zs + [z])
            env = ars_envelope(zs, logp, dlogp, lo, hi)
    return np.array(out), tried, np.array(zs), np.array(flags)


# =========================================================================== 14.1.5-14.1.6 importance sampling
def importance_estimate(f, logp_tilde, q_sample, q_logpdf, L, rng):
    """Self-normalised importance sampling (14.22)-(14.23). Returns (estimate, weights w_l, samples,
    estimate of Z_p / Z_q (14.21), effective sample size 1/sum w_l^2)."""
    z = q_sample(L, rng)
    lr = logp_tilde(z) - q_logpdf(z)
    m = lr.max()
    r = np.exp(lr - m)
    w = r / r.sum()
    return float(w @ f(z)), w, z, float(np.exp(m) * r.mean()), float(1.0 / np.sum(w ** 2))


def sir(logp_tilde, q_sample, q_logpdf, L, rng, L_out=None):
    """Sampling-importance-resampling (Section 14.1.6): L draws from q, weights (14.23), then
    L_out draws (default L) from the discrete distribution on the draws with those weights."""
    z = q_sample(L, rng)
    lr = logp_tilde(z) - q_logpdf(z)
    w = np.exp(lr - lr.max())
    w /= w.sum()
    idx = rng.choice(L, size=L if L_out is None else L_out, p=w)
    return z[idx], z, w


# =========================================================================== 14.2 Markov chain Monte Carlo
def metropolis(logp, z0, step, n, rng):
    """Random-walk Metropolis (Algorithm 14.1) with an isotropic Gaussian proposal of standard
    deviation 'step'. Returns (states z^(0..n), proposals, accepted flags)."""
    z = np.array(z0, float)
    lp = logp(z)
    states, props, acc = [z.copy()], [], []
    for _ in range(n):
        zs = z + step * rng.standard_normal(z.shape)
        lps = logp(zs)
        ok = math.log(rng.random()) < lps - lp
        props.append(zs)
        acc.append(ok)
        if ok:
            z, lp = zs, lps
        states.append(z.copy())
    return np.array(states), np.array(props), np.array(acc)


def mh_matrix(p, Q):
    """Transition matrix of Metropolis-Hastings (14.40) on a finite space: target p (vector), proposal
    matrix Q[i, j] = q(j | i). Rejected mass stays on the diagonal."""
    n = len(p)
    T = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j and Q[i, j] > 0:
                T[i, j] = Q[i, j] * min(1.0, p[j] * Q[j, i] / (p[i] * Q[i, j]))
        T[i, i] = 1.0 - T[i].sum()
    return T


def gibbs_site_matrix(P, site):
    """Transition matrix on the 4 states (z1, z2) in {0,1}^2 (state index 2 z1 + z2) of the Gibbs
    update that redraws z_site from its conditional under the 2x2 joint table P[z1, z2]."""
    T = np.zeros((4, 4))
    for z1 in range(2):
        for z2 in range(2):
            i = 2 * z1 + z2
            for v in range(2):
                if site == 0:
                    T[i, 2 * v + z2] += P[v, z2] / P[:, z2].sum()
                else:
                    T[i, 2 * z1 + v] += P[z1, v] / P[z1, :].sum()
    return T


def gibbs_gauss2(rho, z0, n_sweeps, rng, alpha=0.0, sd=(1.0, 1.0), mu=(0.0, 0.0)):
    """Systematic-scan Gibbs sampling of a bivariate Gaussian with correlation rho (Section 14.2.4),
    with Adler's over-relaxation (14.46) when alpha != 0. Returns all intermediate points (two per
    sweep), so the staircase path of Figure 14.11 can be drawn."""
    s1, s2 = sd
    m1, m2 = mu
    z = np.array(z0, float)
    path = [z.copy()]
    c = math.sqrt(1 - rho * rho)
    for _ in range(n_sweeps):
        for i in (0, 1):
            j = 1 - i
            si, sj, mi, mj = (s1, s2, m1, m2) if i == 0 else (s2, s1, m2, m1)
            m = mi + rho * si / sj * (z[j] - mj)
            s = si * c
            z[i] = m + alpha * (z[i] - m) + s * math.sqrt(1 - alpha * alpha) * rng.standard_normal()
            path.append(z.copy())
    return np.array(path)


# a four-node Bayesian network (cloudy -> sprinkler, cloudy -> rain, sprinkler & rain -> wet grass)
BN_P_C = 0.5
BN_P_S = {1: 0.1, 0: 0.5}                     # p(S = 1 | C)
BN_P_R = {1: 0.8, 0: 0.2}                     # p(R = 1 | C)
BN_P_W = {(1, 1): 0.99, (1, 0): 0.9, (0, 1): 0.9, (0, 0): 0.0}   # p(W = 1 | S, R)


def _bern(p, x):
    return p if x == 1 else 1 - p


def bn_joint(c, s, r, w):
    """The joint distribution (14.47) of the four-node network as a product of conditionals."""
    return _bern(BN_P_C, c) * _bern(BN_P_S[c], s) * _bern(BN_P_R[c], r) * _bern(BN_P_W[(s, r)], w)


def bn_exact_posterior_rain(w=1):
    """p(R = 1 | W = w) by enumeration."""
    num = sum(bn_joint(c, s, 1, w) for c in (0, 1) for s in (0, 1))
    den = sum(bn_joint(c, s, r, w) for c in (0, 1) for s in (0, 1) for r in (0, 1))
    return num / den


def bn_ancestral(n, rng):
    """Ancestral sampling (Section 14.2.5): draw C, then S and R given C, then W given S and R."""
    out = np.zeros((n, 4), int)
    for t in range(n):
        c = int(rng.random() < BN_P_C)
        s = int(rng.random() < BN_P_S[c])
        r = int(rng.random() < BN_P_R[c])
        w = int(rng.random() < BN_P_W[(s, r)])
        out[t] = (c, s, r, w)
    return out


def bn_likelihood_weighting(n, rng, w_obs=1):
    """Likelihood-weighted sampling with evidence W = w_obs: sample the unobserved nodes ancestrally,
    fix W, and weight each sample by p(W = w_obs | S, R) (14.48)."""
    R = np.zeros(n)
    wts = np.zeros(n)
    for t in range(n):
        c = int(rng.random() < BN_P_C)
        s = int(rng.random() < BN_P_S[c])
        r = int(rng.random() < BN_P_R[c])
        R[t] = r
        wts[t] = _bern(BN_P_W[(s, r)], w_obs)
    return R, wts


# =========================================================================== 14.3 energy-based model in one dimension
class EBM1D:
    """A one-dimensional energy-based model (14.50) with

        E(x, w) = x^2 / (2 s0^2) + sum_k w_k phi_k(x),   phi_k(x) = exp(-(x - c_k)^2 / (2 h^2)),

    i.e. a confining quadratic plus radial basis functions with learnable weights w. The energy is
    linear in w, so grad_w E = phi(x) (the feature vector) and the model is an exponential family;
    the partition function (14.51) is computed by quadrature on a grid, which is possible only
    because x is one-dimensional and lets us measure exactly what the sampling methods achieve."""

    def __init__(self, centres=None, h=0.6, s0=3.0, lo=-7.0, hi=7.0, n_grid=1401):
        self.c = np.arange(-6.0, 6.01, 0.75) if centres is None else np.asarray(centres, float)
        self.h, self.s0 = float(h), float(s0)
        self.x = np.linspace(lo, hi, n_grid)
        self.dx = self.x[1] - self.x[0]
        self.Phi = self.phi(self.x)

    def phi(self, x):
        x = np.atleast_1d(np.asarray(x, float))
        return np.exp(-(x[:, None] - self.c[None, :]) ** 2 / (2 * self.h ** 2))

    def energy(self, x, w):
        x = np.atleast_1d(np.asarray(x, float))
        return x ** 2 / (2 * self.s0 ** 2) + self.phi(x) @ w

    def score(self, x, w):
        """s(x, w) = -dE/dx (14.60): the partition function has dropped out."""
        x = np.atleast_1d(np.asarray(x, float))
        P = self.phi(x)
        return -(x / self.s0 ** 2 + (P * (-(x[:, None] - self.c[None, :]) / self.h ** 2)) @ w)

    def log_Z(self, w):
        e = -(self.x ** 2 / (2 * self.s0 ** 2) + self.Phi @ w)
        m = e.max()
        return float(m + math.log(np.exp(e - m).sum() * self.dx))

    def density(self, w):
        """p(x | w) on the grid (14.50)."""
        return np.exp(-(self.x ** 2 / (2 * self.s0 ** 2) + self.Phi @ w) - self.log_Z(w))

    def model_mean_phi(self, w):
        """E_{x ~ p_M}[grad_w E(x, w)] = E_M[phi(x)] by quadrature: the exact negative phase."""
        p = self.density(w)
        return (p * self.dx) @ self.Phi

    def loglik(self, X, w):
        """Average log likelihood (14.52)/N of the data X."""
        return float(-np.mean(self.energy(X, w)) - self.log_Z(w))


# The data and starting point of the demo ebm-training-demo.html (exported to ../data/ch14-ebm.json).
EBM_SEED = 14
EBM_N = 200
EBM_MIX = ((0.5, -2.0, 0.55), (0.5, 0.5, 0.55))        # weights, means, standard deviations of p_D


def ebm_data(n=EBM_N, seed=EBM_SEED):
    """n draws from the data distribution p_D (a two-component Gaussian mixture) with JSRandom."""
    rng = JSRandom(seed)
    out = []
    for _ in range(n):
        u = rng.u()
        k = 0 if u < EBM_MIX[0][0] else 1
        out.append(EBM_MIX[k][1] + EBM_MIX[k][2] * rng.norm())
    return np.array(out)


def ebm_pdata(x):
    return sum(pi * np.exp(-(x - m) ** 2 / (2 * s * s)) / (s * math.sqrt(2 * math.pi)) for pi, m, s in EBM_MIX)


def ebm_w0(model):
    """Initial weights: a deep well at x = 3.5, where there are no data (the situation of Figure 14.13)."""
    return -4.0 * np.exp(-(model.c - 3.5) ** 2 / (2 * 0.5 ** 2))


def langevin_1d(model, w, x, steps, eta, rng):
    """Langevin sampling (14.61) of the chains x (a list of floats, updated in place) using the
    JSRandom rng: at every step, chain m gets x_m <- x_m + eta s(x_m, w) + sqrt(2 eta) eps_m, with
    the normals eps_m drawn in the order m = 1, ..., M (as in the demo)."""
    c, h2, s02 = model.c, model.h ** 2, model.s0 ** 2
    sq = math.sqrt(2 * eta)
    xa = np.array(x, float)
    for _ in range(steps):
        eps = np.array([rng.norm() for _ in range(len(xa))])
        d = xa[:, None] - c[None, :]
        g = xa / s02 - (w[None, :] * d / h2 * np.exp(-d * d / (2 * h2))).sum(1)    # dE/dx
        xa = xa - eta * g + sq * eps
    x[:] = xa.tolist()
    return x


def ebm_train(method="exact", iters=200, lr=1.0, M=100, k=1, eta=0.05, T=200, seed=1, model=None,
              X=None, w0=None, record=False):
    """Maximum-likelihood training of EBM1D by gradient ascent on (14.57),

        w <- w + lr ( -mean_n phi(x_n) + mean_m phi(x_m^-) ),

    with the negative-phase samples x^- drawn by
      'exact':  no samples; E_M[phi] by quadrature;
      'noise':  M fresh chains from N(0, 3^2), T Langevin steps each (14.61)-(14.62);
      'cd':     contrastive divergence (Hinton, 2002): M chains started at data points chosen at
                random, k Langevin steps;
      'pcd':    persistent chains: M chains started at data points once, then continued for k steps
                at every iteration.
    The random numbers come from JSRandom(seed) in a fixed order, as in ebm-training-demo.html.
    Returns (w, history) where history holds the exact average log likelihood after each iteration
    (and, if record, the negative samples of each iteration)."""
    model = EBM1D() if model is None else model
    X = ebm_data() if X is None else X
    w = ebm_w0(model).copy() if w0 is None else np.array(w0, float)
    rng = JSRandom(seed)
    pos = model.phi(X).mean(0)
    N = len(X)
    chains = None
    hist = {"ll": [model.loglik(X, w)], "neg": []}
    for _ in range(iters):
        if method == "exact":
            neg = model.model_mean_phi(w)
            xs = None
        else:
            if method == "noise":
                xs = [3.0 * rng.norm() for _ in range(M)]
                langevin_1d(model, w, xs, T, eta, rng)
            elif method == "cd":
                xs = [float(X[int(rng.u() * N)]) for _ in range(M)]
                langevin_1d(model, w, xs, k, eta, rng)
            elif method == "pcd":
                if chains is None:
                    chains = [float(X[int(rng.u() * N)]) for _ in range(M)]
                langevin_1d(model, w, chains, k, eta, rng)
                xs = list(chains)
            else:
                raise ValueError(method)
            neg = model.phi(np.array(xs)).mean(0)
        w = w + lr * (neg - pos)
        hist["ll"].append(model.loglik(X, w))
        if record:
            hist["neg"].append(None if xs is None else np.array(xs))
    return w, hist


def score_matching_grad(model, X, w):
    """Gradient in w of Hyvarinen's score-matching objective J(w) = mean_n [ s(x_n)^2 / 2 + s'(x_n) ]
    for EBM1D, with s = -dE/dx: dJ/dw_k = -mean_n [ s(x_n) phi_k'(x_n) + phi_k''(x_n) ]."""
    X = np.asarray(X, float)
    P = model.phi(X)
    d = X[:, None] - model.c[None, :]
    h2 = model.h ** 2
    dphi = -d / h2 * P
    d2phi = (d * d / h2 ** 2 - 1 / h2) * P
    s = model.score(X, w)
    return -(s[:, None] * dphi + d2phi).mean(0)


# =========================================================================== 14.3.3 Langevin sampling in two dimensions
def _rot(deg):
    t = math.radians(deg)
    return np.array([[math.cos(t), -math.sin(t)], [math.sin(t), math.cos(t)]])


GAUSS_SD = (1.5, 0.4)
GAUSS_ANGLE = 45.0
_RG = _rot(GAUSS_ANGLE)
GAUSS_COV = _RG @ np.diag(np.array(GAUSS_SD) ** 2) @ _RG.T
GAUSS_PREC = np.linalg.inv(GAUSS_COV)
WELLS = ((0.7, (-2.5, 0.0)), (0.3, (2.5, 0.0)))
WELL_SD = 0.55


def target_logp_grad(name, x, y):
    """Unnormalised ln p and its gradient (the score (14.59)) for the three targets of the Langevin
    demo, written with scalar arithmetic in the same order as the JavaScript.
      'gauss':  N(0, Sigma), standard deviations 1.5 and 0.4 along axes rotated by 45 degrees;
      'banana': x ~ N(0, 2^2), y | x ~ N(x^2/4 - 1, 1/2) (standard deviation 0.707);
      'wells':  0.7 N((-2.5, 0), 0.55^2 I) + 0.3 N((2.5, 0), 0.55^2 I)."""
    if name == "gauss":
        P = GAUSS_PREC
        a = P[0, 0] * x + P[0, 1] * y
        b = P[1, 0] * x + P[1, 1] * y
        return -0.5 * (x * a + y * b), -a, -b
    if name == "banana":
        r = y - 0.25 * x * x + 1.0
        return -x * x / 8.0 - r * r, -x / 4.0 + r * x, -2.0 * r     # d/dx: -x/4 - 2 r (-x/2)
    if name == "wells":
        s2 = WELL_SD * WELL_SD
        l0 = math.log(WELLS[0][0]) - ((x - WELLS[0][1][0]) ** 2 + (y - WELLS[0][1][1]) ** 2) / (2 * s2)
        l1 = math.log(WELLS[1][0]) - ((x - WELLS[1][1][0]) ** 2 + (y - WELLS[1][1][1]) ** 2) / (2 * s2)
        m = max(l0, l1)
        e0, e1 = math.exp(l0 - m), math.exp(l1 - m)
        lp = m + math.log(e0 + e1)
        r0, r1 = e0 / (e0 + e1), e1 / (e0 + e1)
        gx = -(r0 * (x - WELLS[0][1][0]) + r1 * (x - WELLS[1][1][0])) / s2
        gy = -(r0 * (y - WELLS[0][1][1]) + r1 * (y - WELLS[1][1][1])) / s2
        return lp, gx, gy
    raise ValueError(name)


def langevin_run(target="gauss", method="ula", eta=0.05, steps=200, n=300, noise=1.0, seed=1,
                 init=(0.0, 0.0, 2.0), keep_path=0):
    """n independent Langevin chains (14.61) on a two-dimensional target, all advanced together.

    method 'ula' is (14.61) with the noise multiplied by 'noise' (noise = 0: gradient ascent; noise
    = 1: the book's update); 'mala' uses the same move as a Metropolis-Hastings proposal
    q(x'|x) = N(x + eta grad ln p(x), 2 eta I) and accepts it with probability (14.40).
    Chains start at init[:2] + init[2] * N(0, I). Random numbers (JSRandom): the starting points
    chain by chain (x then y), then for each step and each chain two normals and, for MALA, one
    uniform. Returns (X (n, 2), acceptance rate, path of chain 0 if keep_path)."""
    rng = JSRandom(seed)
    m0x, m0y, s0 = init
    X = [[m0x + s0 * rng.norm(), m0y + s0 * rng.norm()] for _ in range(n)]
    st = [target_logp_grad(target, p[0], p[1]) for p in X]
    sq = math.sqrt(2 * eta)
    acc = 0
    path = [tuple(X[0])] if keep_path else None
    for t in range(steps):
        for i in range(n):
            x, y = X[i]
            lp, gx, gy = st[i]
            e1 = rng.norm()
            e2 = rng.norm()
            if method == "ula":
                X[i] = [x + eta * gx + noise * sq * e1, y + eta * gy + noise * sq * e2]
                st[i] = target_logp_grad(target, X[i][0], X[i][1])
            else:
                xn, yn = x + eta * gx + sq * e1, y + eta * gy + sq * e2
                lpn, gxn, gyn = target_logp_grad(target, xn, yn)
                # log q(x | x') - log q(x' | x), q(a | b) = N(a | b + eta g(b), 2 eta I)
                dx_b, dy_b = x - xn - eta * gxn, y - yn - eta * gyn
                dx_f, dy_f = xn - x - eta * gx, yn - y - eta * gy
                la = lpn - lp - (dx_b * dx_b + dy_b * dy_b - dx_f * dx_f - dy_f * dy_f) / (4 * eta)
                u = rng.u()
                if la >= 0 or u < math.exp(la):
                    X[i] = [xn, yn]
                    st[i] = (lpn, gxn, gyn)
                    acc += 1
            if keep_path and i == 0 and t < keep_path:
                path.append(tuple(X[0]))
    rate = acc / float(n * steps) if method == "mala" and steps > 0 else float("nan")
    return np.array(X), rate, (np.array(path) if keep_path else None)


def target_moments(name):
    """Exact mean and covariance of the three Langevin targets."""
    if name == "gauss":
        return np.zeros(2), GAUSS_COV.copy()
    if name == "banana":
        return np.zeros(2), np.diag([4.0, 2.5])     # var y = var(x^2/4) + 1/2 = 32/16 + 1/2
    if name == "wells":
        mus = np.array([m for _, m in WELLS])
        pis = np.array([p for p, _ in WELLS])
        mean = pis @ mus
        cov = WELL_SD ** 2 * np.eye(2) + sum(p * np.outer(m - mean, m - mean) for p, m in zip(pis, mus))
        return mean, cov
    raise ValueError(name)


def ula_gauss_var(sigma2, eta):
    """Stationary variance of Langevin sampling (14.61) of N(0, sigma2) with step eta:
    x' = (1 - eta/sigma2) x + sqrt(2 eta) eps has stationary variance 2 eta / (1 - (1 - eta/sigma2)^2)
    = sigma2 / (1 - eta / (2 sigma2)), finite iff 0 < eta < 2 sigma2."""
    return sigma2 / (1.0 - eta / (2.0 * sigma2))


# =========================================================================== supplement: gradients of expectations
def gfun(name, z, a):
    """Test functions f, their derivatives, for the gradient-estimator demo."""
    if name == "quad":
        return (z - a) ** 2, 2 * (z - a)
    if name == "sin":
        return np.sin(a * z), a * np.cos(a * z)
    if name == "step":
        return (z > a).astype(float) if isinstance(z, np.ndarray) else float(z > a), 0.0 * z
    raise ValueError(name)


def grad_true(name, mu, sigma, a):
    """Exact E[f] and its derivatives with respect to mu and sigma under z ~ N(mu, sigma^2)."""
    if name == "quad":
        return (mu - a) ** 2 + sigma ** 2, 2 * (mu - a), 2 * sigma
    if name == "sin":
        d = math.exp(-a * a * sigma * sigma / 2)
        return math.sin(a * mu) * d, a * math.cos(a * mu) * d, -a * a * sigma * math.sin(a * mu) * d
    if name == "step":
        t = (mu - a) / sigma
        ph = math.exp(-t * t / 2) / math.sqrt(2 * math.pi)
        return 0.5 * (1 + math.erf(t / math.sqrt(2))), ph / sigma, -ph * t / sigma
    raise ValueError(name)


def grad_single(name, mu, sigma, a, eps, wrt="mu", baseline=False):
    """Single-sample score-function and reparameterisation estimates for the noise values eps
    (z = mu + sigma eps). Score function: f(z) d/dtheta ln N(z | mu, sigma^2), i.e. f(z) eps / sigma
    for mu and f(z) (eps^2 - 1)/sigma for sigma, with f replaced by f - E[f] if baseline.
    Reparameterisation: f'(z) dz/dtheta, i.e. f'(z) for mu and f'(z) eps for sigma."""
    eps = np.asarray(eps, float)
    z = mu + sigma * eps
    f, df = gfun(name, z, a)
    if baseline:
        f = f - grad_true(name, mu, sigma, a)[0]
    if wrt == "mu":
        return f * eps / sigma, df
    return f * (eps * eps - 1) / sigma, df * eps


def grad_moments(name, mu, sigma, a, wrt="mu", baseline=False, n=20001, lim=10.0):
    """Exact mean and variance of both single-sample estimators by quadrature over eps ~ N(0, 1)
    (trapezoid rule on [-lim, lim]; the step function is integrated exactly at its jump)."""
    e = np.linspace(-lim, lim, n)
    wq = np.exp(-e * e / 2) / math.sqrt(2 * math.pi) * (e[1] - e[0])
    wq[0] *= 0.5
    wq[-1] *= 0.5
    sf, rp = grad_single(name, mu, sigma, a, e, wrt, baseline)
    out = []
    for g in (sf, rp):
        m1 = float(wq @ g)
        out.append((m1, float(wq @ (g * g)) - m1 * m1))
    return out


def grad_estimates(name="quad", mu=1.0, sigma=1.0, a=0.0, wrt="mu", L=1, R=2000, baseline=False, seed=1):
    """R independent L-sample estimates of d/dtheta E[f(z)] by both estimators, using the same noise
    (common random numbers): eps_{r,l} = JSRandom(seed).norm() in the order r then l."""
    rng = JSRandom(seed)
    E = np.array([[rng.norm() for _ in range(L)] for _ in range(R)])
    sf, rp = grad_single(name, mu, sigma, a, E, wrt, baseline)
    return sf.mean(1), rp.mean(1)


def quad_score_var_mu(mu, sigma, a=0.0):
    """Exact variance of the single-sample score-function estimator of d/dmu E[(z - a)^2]:
    E[(m + s e)^4 e^2]/s^2 - 4 m^2 with m = mu - a, s = sigma, i.e. (m^4 + 18 m^2 s^2 + 15 s^4)/s^2 - 4 m^2."""
    m, s = mu - a, sigma
    return (m ** 4 + 18 * m * m * s * s + 15 * s ** 4) / (s * s) - 4 * m * m


# =========================================================================== web data for the demos
def export_ebm_json(path=None):
    """Write ../data/ch14-ebm.json: the data, basis and starting weights of ebm-training-demo.html."""
    model = EBM1D()
    X = ebm_data()
    d = {"note": "Data and settings of ebm-training-demo.html, written by ch14_sampling.py (Bishop and Bishop 2024, Section 14.3).",
         "seed": EBM_SEED, "mix": [list(t) for t in EBM_MIX], "x": [round(float(v), 15) for v in X],
         "centres": model.c.tolist(), "h": model.h, "s0": model.s0, "grid": [float(model.x[0]), float(model.x[-1]), len(model.x)],
         "w0": ebm_w0(model).tolist()}
    path = path or os.path.join(WEB_DATA, "ch14-ebm.json")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    return path


# =========================================================================== figures: Section 14.1
def _gauss(z, m, s):
    return np.exp(-(z - m) ** 2 / (2 * s * s)) / (s * math.sqrt(2 * math.pi))


def fig_14_1(out_dir=None):
    """Figure 14.1: a function f(z) whose expectation under p(z) is to be estimated, with a Monte Carlo estimate."""
    z = np.linspace(-3, 5, 600)
    p = _gauss(z, 1.0, 0.8)
    f = lambda t: 0.25 + 0.12 * t + 0.18 * np.sin(1.6 * t)  # noqa: E731
    rng = np.random.default_rng(1)
    zs = rng.normal(1.0, 0.8, 12)
    from scipy.integrate import quad
    Ef = quad(lambda t: f(t) * _gauss(t, 1.0, 0.8), -10, 12)[0]
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    ax.plot(z, p, color=common.RED, label=r"$p(z)=\mathcal{N}(z\,|\,1,0.8^2)$")
    ax.plot(z, f(z), color=common.GREEN, label=r"$f(z)$")
    ax.plot(zs, np.zeros_like(zs), "|", color=common.BLUE, ms=12, mew=1.5, label=r"12 samples $z^{(l)}\sim p$")
    ax.plot(zs, f(zs), "o", color=common.BLUE, ms=3.5)
    ax.axhline(Ef, color="k", lw=0.9, ls="--", label=r"$\mathbb{E}[f]=%.3f$" % Ef)
    ax.axhline(f(zs).mean(), color=common.BLUE, lw=0.9, ls=":", label=r"$\widehat{f}=%.3f$ (14.2)" % f(zs).mean())
    ax.set_xlabel(r"$z$")
    ax.set_xlim(-3, 5)
    ax.set_ylim(-0.15, 1.1)
    ax.legend(fontsize=7.5, loc="upper left", frameon=False)
    return savefig(fig, CH, "fig14-1", out_dir)


def fig_14_2(out_dir=None):
    """Figure 14.2: the transformation method; y = h^{-1}(z) with h the CDF of the desired density."""
    a = 3.0
    y = np.linspace(0, 10, 500)
    p = stats.gamma.pdf(y, a)
    h = stats.gamma.cdf(y, a)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.0))
    ax = axes[0]
    ax.plot(y, p / p.max(), color=common.RED, label=r"$p(y)=\mathrm{Gam}(y\,|\,3,1)$ (scaled)")
    ax.plot(y, h, color=common.BLUE, label=r"$h(y)=\int_{-\infty}^y p(\widehat y)\,d\widehat y$")
    for zu in (0.15, 0.5, 0.85):
        yy = stats.gamma.ppf(zu, a)
        ax.annotate("", xy=(yy, zu), xytext=(0, zu), arrowprops=dict(arrowstyle="->", color=common.GREY, lw=0.9))
        ax.annotate("", xy=(yy, 0), xytext=(yy, zu), arrowprops=dict(arrowstyle="->", color=common.GREY, lw=0.9))
        ax.text(0.15, zu + 0.02, r"$z=%.2f$" % zu, fontsize=7.5, color=common.GREY)
    ax.set_xlabel(r"$y$")
    ax.set_xlim(0, 10)
    ax.set_ylim(0, 1.05)
    ax.legend(fontsize=7.5, loc="center right", frameon=False)
    ax = axes[1]
    rng = np.random.default_rng(2)
    ys = stats.gamma.ppf(rng.random(5000), a)
    ax.hist(ys, bins=50, range=(0, 12), density=True, color="#c9d6ec", edgecolor="white")
    yy = np.linspace(0, 12, 400)
    ax.plot(yy, stats.gamma.pdf(yy, a), color=common.RED)
    ax.set_xlabel(r"$y=h^{-1}(z)$, $z\sim\mathcal{U}(0,1)$")
    ax.set_title("5000 transformed uniforms", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-2", out_dir)


def fig_14_3(out_dir=None):
    """Figure 14.3: the polar Box-Muller method starts from points uniform in the unit disc."""
    rng = np.random.default_rng(3)
    y, Z, A = box_muller_polar(1000, rng)
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.2))
    ax = axes[0]
    ax.plot(Z[~A, 0], Z[~A, 1], ".", color="#bbbbbb", ms=3)
    ax.plot(Z[A, 0], Z[A, 1], ".", color=common.BLUE, ms=3)
    ax.add_patch(Circle((0, 0), 1, fill=False, color="k", lw=1))
    ax.set_xlim(-1.05, 1.05)
    ax.set_ylim(-1.05, 1.05)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$z_1$")
    ax.set_ylabel(r"$z_2$")
    ax.set_title(r"accepted %d of %d ($\pi/4=%.3f$)" % (A.sum(), len(A), math.pi / 4), fontsize=9)
    ax = axes[1]
    ax.plot(y[:, 0], y[:, 1], ".", color=common.GREEN, ms=3)
    ax.set_aspect("equal")
    ax.set_xlim(-4, 4)
    ax.set_ylim(-4, 4)
    ax.set_xlabel(r"$y_1$")
    ax.set_ylabel(r"$y_2$")
    ax.set_title("(14.10)-(14.11) applied", fontsize=9)
    ax = axes[2]
    ax.hist(y.ravel(), bins=40, range=(-4, 4), density=True, color="#c9e6c9", edgecolor="white")
    t = np.linspace(-4, 4, 300)
    ax.plot(t, _gauss(t, 0, 1), color=common.RED)
    ax.set_xlabel(r"$y_1$ and $y_2$ pooled")
    ax.set_title(r"against $\mathcal{N}(0,1)$", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-3", out_dir)


def _p4(z):
    return 2.0 * (0.6 * _gauss(z, -1.0, 0.6) + 0.4 * _gauss(z, 1.5, 0.9))   # unnormalised: area 2


def fig_14_4(out_dir=None):
    """Figure 14.4: rejection sampling under a comparison function k q(z) >= p~(z)."""
    z = np.linspace(-5, 6, 2000)
    q = _gauss(z, 0.3, 1.6)
    k = float(np.max(_p4(z) / q)) * 1.0001
    rng = np.random.default_rng(4)
    z0s = rng.normal(0.3, 1.6, 20000)
    u0s = rng.random(20000) * k * _gauss(z0s, 0.3, 1.6)
    keep = u0s <= _p4(z0s)
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.1))
    ax = axes[0]
    ax.fill_between(z, _p4(z), k * q, color="#dddddd")
    ax.plot(z, k * q, color=common.RED, label=r"$kq(z)$")
    ax.plot(z, _p4(z), color=common.GREEN, label=r"$\widetilde p(z)$")
    zz, uu = 2.6, 0.25
    ax.plot([zz, zz], [0, k * _gauss(zz, 0.3, 1.6)], color=common.BLUE, lw=1)
    ax.plot([zz], [uu], "o", color=common.BLUE, ms=4)
    ax.text(zz + 0.1, uu, r"$u_0$ (rejected: $u_0>\widetilde p(z_0)$)", fontsize=7.5, va="center")
    ax.text(zz, -0.06, r"$z_0$", ha="center", fontsize=9)
    ax.plot(z0s[:300][keep[:300]], u0s[:300][keep[:300]], ".", color=common.GREEN, ms=2.5)
    ax.plot(z0s[:300][~keep[:300]], u0s[:300][~keep[:300]], ".", color=common.GREY, ms=2.5)
    ax.set_xlim(-5, 6)
    ax.set_ylim(0, None)
    ax.set_xlabel(r"$z$")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title(r"$k=%.2f$; acceptance $\int\widetilde p/k=%.3f$" % (k, 2.0 / k), fontsize=9)
    ax = axes[1]
    ax.hist(z0s[keep], bins=60, range=(-4, 5), density=True, color="#c9e6c9", edgecolor="white")
    ax.plot(z, _p4(z) / 2.0, color=common.GREEN)
    ax.set_xlim(-4, 5)
    ax.set_xlabel(r"$z$")
    ax.set_title("accepted $z_0$: %d of 20000 (%.3f)" % (keep.sum(), keep.mean()), fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-4", out_dir)


def gamma_cauchy_optimal(a):
    """The Cauchy comparison function (c, s) with the highest acceptance rate for Gam(z | a, 1)
    (Nelder-Mead over c and ln s, with k recomputed for every candidate)."""
    from scipy.optimize import minimize
    fobj = lambda v: -gamma_cauchy_envelope(a, v[0], math.exp(v[1]))[3]  # noqa: E731
    r = minimize(fobj, [a - 1, 0.5 * math.log(2 * a - 1)], method="Nelder-Mead", options=dict(xatol=1e-5, fatol=1e-9))
    return gamma_cauchy_envelope(a, r.x[0], math.exp(r.x[1]))


def fig_14_5(out_dir=None):
    """Figure 14.5: a gamma density under a scaled Cauchy comparison function."""
    a = 10.0
    z = np.linspace(0, 30, 800)
    c, s, k, acc = gamma_cauchy_envelope(a)
    co, so, ko, acco = gamma_cauchy_optimal(a)
    fig, ax = plt.subplots(figsize=(5.2, 3.1))
    ax.plot(z, gamma_pdf(z, a), color=common.GREEN, label=r"$\mathrm{Gam}(z\,|\,10,1)$")
    ax.plot(z, k / (1 + (z - c) ** 2 / s ** 2), color=common.RED,
            label=r"$c=a-1$, $b^2=2a-1$: acceptance %.3f" % acc)
    ax.plot(z, ko / (1 + (z - co) ** 2 / so ** 2), color=common.ORANGE, ls="--",
            label=r"best $c=%.2f$, $b^2=%.2f$: %.3f" % (co, so * so, acco))
    ax.set_xlim(0, 30)
    ax.set_ylim(0, 0.2)
    ax.set_xlabel(r"$z$")
    ax.set_ylabel(r"$p(z)$")
    ax.legend(fontsize=7.5, frameon=False, loc="upper right")
    return savefig(fig, CH, "fig14-5", out_dir)


ARS_A = 4.0


def _ars_logp(z):
    return (ARS_A - 1) * math.log(z) - z - math.lgamma(ARS_A)


def _ars_dlogp(z):
    return (ARS_A - 1) / z - 1


def fig_14_6(out_dir=None):
    """Figure 14.6: tangent lines at grid points give a piecewise-linear envelope of ln p(z)."""
    zs = [1.2, 2.6, 5.5]
    env = ars_envelope(zs, _ars_logp, _ars_dlogp, 0.0, np.inf)
    z = np.linspace(0.35, 10, 600)
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.1))
    ax = axes[0]
    ax.plot(z, [_ars_logp(t) for t in z], color=common.RED, label=r"$\ln p(z)$, $p=\mathrm{Gam}(z\,|\,4,1)$")
    ax.plot(z, ars_logq(env, z), color=common.BLUE, label="envelope (tangents)")
    for i, t in enumerate(zs):
        ax.plot([t, t], [-9, _ars_logp(t)], color=common.BLUE, ls="--", lw=0.9)
        ax.text(t, -8.9, r"$z_%d$" % (i + 1), ha="center", va="bottom", fontsize=9)
    ax.set_ylim(-9, 0.2)
    ax.set_xlim(0.35, 10)
    ax.set_xlabel(r"$z$")
    ax.legend(fontsize=7.5, frameon=False, loc="upper right")
    ax = axes[1]
    rng = np.random.default_rng(6)
    _, tried, zfin, flags = ars_run(3000, _ars_logp, _ars_dlogp, zs, rng, 0.0, np.inf)
    rej = np.cumsum(~flags)
    ax.plot(np.arange(1, len(flags) + 1), rej, color=common.BLUE)
    ax.set_xscale("log")
    ax.set_xlabel("proposals drawn")
    ax.set_ylabel("cumulative rejections")
    ax.set_title("adaptive: %d rejections in %d proposals; %d abscissae" % (rej[-1], tried, len(zfin)), fontsize=8.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-6", out_dir)


def fig_14_7(out_dir=None):
    """Figure 14.7: rejection sampling of a Gaussian with a slightly wider Gaussian, and the exponential decay with dimension."""
    sp, sq = 1.0, 1.1
    z = np.linspace(-5, 5, 500)
    k = sq / sp
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.1))
    ax = axes[0]
    ax.plot(z, k * _gauss(z, 0, sq), color=common.RED, label=r"$kq(z)$, $\sigma_q=1.1$, $k=\sigma_q/\sigma_p$")
    ax.plot(z, _gauss(z, 0, sp), color=common.GREEN, label=r"$p(z)$, $\sigma_p=1$")
    ax.set_xlim(-5, 5)
    ax.set_ylim(0, 0.5)
    ax.set_xlabel(r"$z$")
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[1]
    D = np.unique(np.round(np.logspace(0, 3, 60)).astype(int))
    for ratio, col in ((1.01, common.BLUE), (1.05, common.GREEN), (1.1, common.RED)):
        ax.plot(D, ratio ** (-D.astype(float)), color=col, label=r"$\sigma_q/\sigma_p=%s$" % ratio)
    rng = np.random.default_rng(7)
    for Dd in (1, 5, 10, 20, 40):
        n = 20000
        zq = rng.normal(0, 1.1, (n, Dd))
        logr = (-0.5 * (zq ** 2).sum(1) - Dd * math.log(1.0)) - (-0.5 * (zq ** 2).sum(1) / 1.21 - Dd * math.log(1.1))
        acc = np.mean(rng.random(n) < np.exp(logr - Dd * math.log(1.1)))
        ax.plot([Dd], [acc], "o", color=common.RED, ms=4)
    ax.plot([1000], [1.01 ** -1000], "s", color=common.BLUE, ms=4)
    ax.annotate(r"$D=1000$: $1/%d$" % round(1.01 ** 1000), (1000, 1.01 ** -1000), (60, 2e-6), fontsize=8,
                arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.set_xscale("log")
    ax.set_yscale("log")
    ax.set_ylim(1e-9, 2)
    ax.set_xlabel(r"dimension $D$")
    ax.set_ylabel(r"acceptance $1/k=(\sigma_p/\sigma_q)^D$")
    ax.legend(fontsize=7.5, frameon=False, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-7", out_dir)


def fig_14_8(out_dir=None):
    """Figure 14.8: importance sampling; samples from q weighted by p/q."""
    z = np.linspace(-4, 6, 800)
    p = 0.7 * _gauss(z, 0.0, 0.7) + 0.3 * _gauss(z, 2.2, 0.5)
    f = lambda t: 0.15 + 0.5 / (1 + np.exp(-2.5 * (t - 1.5)))  # noqa: E731
    q = _gauss(z, 1.0, 1.8)
    rng = np.random.default_rng(8)
    L = 25
    zs = rng.normal(1.0, 1.8, L)
    pz = 0.7 * _gauss(zs, 0.0, 0.7) + 0.3 * _gauss(zs, 2.2, 0.5)
    r = pz / _gauss(zs, 1.0, 1.8)
    fig, ax = plt.subplots(figsize=(5.6, 3.2))
    ax.plot(z, p, color=common.RED, label=r"$p(z)$")
    ax.plot(z, q, color=common.BLUE, label=r"$q(z)$")
    ax.plot(z, f(z), color=common.GREEN, label=r"$f(z)$")
    ml, sl, bl = ax.stem(zs, -0.04 * r, linefmt="-", markerfmt=" ", basefmt=" ")
    plt.setp(sl, color=common.PURPLE, lw=1.2)
    ax.axhline(0, color="k", lw=0.6)
    ax.text(-3.8, -0.1, r"weights $r_l=p(z^{(l)})/q(z^{(l)})$ (down)", fontsize=7.5, color=common.PURPLE)
    est = float(np.sum(r * f(zs)) / np.sum(r))
    from scipy.integrate import quad
    true = quad(lambda t: f(t) * (0.7 * _gauss(t, 0.0, 0.7) + 0.3 * _gauss(t, 2.2, 0.5)), -10, 12)[0]
    ax.set_title(r"$L=%d$: (14.22) gives %.3f; exact $\mathbb{E}_p[f]=%.3f$" % (L, est, true), fontsize=9)
    ax.set_xlim(-4, 6)
    ax.set_xlabel(r"$z$")
    ax.legend(fontsize=8, frameon=False, loc="upper right")
    return savefig(fig, CH, "fig14-8", out_dir)


# =========================================================================== figures: Section 14.2
FIG9_MU = np.array([1.5, 1.5])
FIG9_COV = np.array([[0.5, 0.45], [0.45, 0.5]])


def fig_14_9(out_dir=None):
    """Figure 14.9: random-walk Metropolis on a correlated two-dimensional Gaussian, accepted and rejected steps."""
    P = np.linalg.inv(FIG9_COV)
    logp = lambda z: -0.5 * (z - FIG9_MU) @ P @ (z - FIG9_MU)  # noqa: E731
    rng = np.random.default_rng(9)
    S, Z, A = metropolis(logp, [1.0, 1.2], 0.2, 150, rng)
    fig, ax = plt.subplots(figsize=(4.2, 4.2))
    ex, ey = common.ellipse_xy(FIG9_MU, FIG9_COV, 1.0)
    ax.plot(ex, ey, color=common.RED, lw=1.6, zorder=5)
    for t in range(150):
        col = common.GREEN if A[t] else common.RED
        ax.plot([S[t, 0], Z[t, 0]], [S[t, 1], Z[t, 1]], color=col, lw=1.0)
    ax.set_xlim(0, 3)
    ax.set_ylim(0, 3)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$z_1$")
    ax.set_ylabel(r"$z_2$")
    ax.set_title("150 candidates, %d rejected (proposal s.d. 0.2)" % (~A).sum(), fontsize=9)
    return savefig(fig, CH, "fig14-9", out_dir)


def mh_iat_long_axis(kappa, n, rng):
    """IAT of the long-axis coordinate for random-walk Metropolis on N(0, diag(kappa^2, 1)) with an
    isotropic proposal of standard deviation rho = sigma_min = 1."""
    z = np.zeros(2)
    lp = 0.0
    xs = np.empty(n)
    E = rng.standard_normal((n, 2))
    U = np.log(rng.random(n))
    ik2 = 1.0 / kappa ** 2
    for t in range(n):
        zs = z + E[t]
        lps = -0.5 * (zs[0] * zs[0] * ik2 + zs[1] * zs[1])
        if U[t] < lps - lp:
            z, lp = zs, lps
        xs[t] = z[0]
    return iat(xs)


def fig_14_10(out_dir=None):
    """Figure 14.10: an isotropic proposal of scale rho ~ sigma_min explores a long Gaussian by a slow random walk."""
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.6))
    ax = axes[0]
    th = math.radians(35)
    R = _rot(35)
    smax, smin = 2.0, 0.25
    Sig = R @ np.diag([smax ** 2, smin ** 2]) @ R.T
    ex, ey = common.ellipse_xy(np.zeros(2), Sig, 1.0)
    ax.plot(ex, ey, color=common.RED, lw=1.4)
    P = np.linalg.inv(Sig)
    rng = np.random.default_rng(10)
    S, _, A = metropolis(lambda z: -0.5 * z @ P @ z, [0.0, 0.0], smin, 400, rng)
    ax.plot(S[:, 0], S[:, 1], color=common.GREY, lw=0.7)
    ax.add_patch(Circle((S[-1, 0], S[-1, 1]), smin, fill=False, color=common.BLUE, lw=1.4))
    ax.annotate("", xy=(smax * math.cos(th), smax * math.sin(th)), xytext=(0, 0),
                arrowprops=dict(arrowstyle="<->", color="k", lw=0.8))
    ax.text(smax * math.cos(th) * 0.5 - 0.1, smax * math.sin(th) * 0.5 + 0.12, r"$\sigma_{\max}$", fontsize=10)
    ax.annotate("", xy=(-smin * math.sin(th), smin * math.cos(th)), xytext=(0, 0),
                arrowprops=dict(arrowstyle="<->", color="k", lw=0.8))
    ax.text(-0.75, 0.25, r"$\sigma_{\min}$", fontsize=10)
    ax.text(S[-1, 0] + 0.28, S[-1, 1] - 0.05, r"$\rho$", color=common.BLUE, fontsize=10)
    ax.set_xlim(-3.6, 3.6)
    ax.set_ylim(-2.6, 2.6)
    ax.set_aspect("equal")
    ax.set_title(r"400 Metropolis steps, $\rho=\sigma_{\min}$, acceptance %.2f" % A.mean(), fontsize=9)
    ax = axes[1]
    ks = [1, 2, 4, 8, 16]
    rng = np.random.default_rng(11)
    taus = [np.mean([mh_iat_long_axis(k, 200000 if k < 16 else 400000, rng) for _ in range(2)]) for k in ks]
    ks = np.array(ks, float)
    ax.loglog(ks ** 2, taus, "o", color=common.BLUE, label="measured IAT, long axis")
    cfit = np.exp(np.mean(np.log(taus[2:]) - np.log(ks[2:] ** 2)))
    ax.loglog(ks ** 2, cfit * ks ** 2, "--", color=common.GREY, label=r"$%.1f\,(\sigma_{\max}/\sigma_{\min})^2$" % cfit)
    ax.set_xlabel(r"$(\sigma_{\max}/\sigma_{\min})^2$")
    ax.set_ylabel("integrated autocorrelation time")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("steps per independent sample grow like the square", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-10", out_dir)


def fig_14_11(out_dir=None):
    """Figure 14.11: Gibbs sampling of a correlated Gaussian moves in steps of the conditional width l."""
    r = 0.95
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.8))
    ax = axes[0]
    Sig = np.array([[1, r], [r, 1]])
    ex, ey = common.ellipse_xy(np.zeros(2), Sig, 1.0)
    ax.plot(ex, ey, color=common.RED, lw=1.4)
    rng = np.random.default_rng(12)
    path = gibbs_gauss2(r, [-1.0, -1.2], 12, rng)
    ax.plot(path[:, 0], path[:, 1], color=common.BLUE, lw=1.0, marker="o", ms=2)
    l_ = math.sqrt(1 - r * r)
    z2 = 0.6
    zz = np.linspace(-1.6, 1.6, 300)
    ax.plot(zz, z2 + 0.25 * np.exp(-(zz - r * z2) ** 2 / (2 * l_ * l_)), color=common.GREEN, lw=1.2)
    ax.axhline(z2, color=common.GREEN, lw=0.6, ls=":")
    ax.annotate("", xy=(r * z2 - l_, z2 - 0.08), xytext=(r * z2 + l_, z2 - 0.08), arrowprops=dict(arrowstyle="<->", lw=0.8))
    ax.text(r * z2 + l_ + 0.05, z2 - 0.18, r"$l$", fontsize=10)
    ax.annotate("", xy=(-1.0, -1.85), xytext=(1.0, -1.85), arrowprops=dict(arrowstyle="<->", lw=0.8))
    ax.text(0, -1.8, r"$L$", ha="center", fontsize=10)
    ax.set_xlim(-2, 2)
    ax.set_ylim(-2, 2)
    ax.set_aspect("equal")
    ax.set_xlabel(r"$z_1$")
    ax.set_ylabel(r"$z_2$")
    ax.set_title(r"12 Gibbs sweeps, correlation 0.95: $L/l=%.1f$" % (1 / l_), fontsize=9)
    ax = axes[1]
    rs = np.array([0.0, 0.5, 0.8, 0.9, 0.95, 0.98, 0.99])
    rng = np.random.default_rng(13)
    meas = []
    for rr in rs:
        p = gibbs_gauss2(rr, [0.0, 0.0], 100000, rng)
        meas.append(iat(p[2::2, 0]))
    Ll2 = 1 / (1 - rs ** 2)
    xx = np.linspace(1, Ll2.max(), 200)
    ax.loglog(xx, 2 * xx - 1, color=common.GREY, ls="--", label=r"exact: $2(L/l)^2-1$")
    ax.loglog(Ll2, meas, "o", color=common.BLUE, label=r"measured IAT of $z_1$")
    ax.set_xlabel(r"$(L/l)^2=1/(1-r^2)$")
    ax.set_ylabel("integrated autocorrelation time")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("sweeps per independent sample", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-11", out_dir)


def _disc_gibbs(discs, z0, n, rng):
    """Gibbs sampling of the uniform distribution on a union of discs: each conditional is uniform
    on the union of the chords cut by the line z_j = const."""
    z = np.array(z0, float)
    path = [z.copy()]
    for _ in range(n):
        for i in (0, 1):
            j = 1 - i
            segs = []
            for (cx, cy, rad) in discs:
                c = (cx, cy)
                d = z[j] - c[j]
                if abs(d) < rad:
                    hw = math.sqrt(rad * rad - d * d)
                    segs.append((c[i] - hw, c[i] + hw))
            lens = np.array([b - a for a, b in segs])
            k = rng.choice(len(segs), p=lens / lens.sum())
            z[i] = segs[k][0] + rng.random() * lens[k]
            path.append(z.copy())
    return np.array(path)


def fig_14_14(out_dir=None):
    """Figure 14.14: a uniform distribution on two regions with disjoint projections; Gibbs sampling is not ergodic."""
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.9))
    for ax, discs, title in ((axes[0], [(0.28, 0.28, 0.17), (0.75, 0.75, 0.17)], "disjoint projections: stuck"),
                             (axes[1], [(0.32, 0.36, 0.22), (0.68, 0.66, 0.22)], "overlapping projections: ergodic")):
        for (cx, cy, rad) in discs:
            ax.add_patch(Circle((cx, cy), rad, color="#ff8080", alpha=0.8, lw=0))
        rng = np.random.default_rng(14)
        p = _disc_gibbs(discs, [discs[0][0], discs[0][1]], 300, rng)
        ax.plot(p[:, 0], p[:, 1], color=common.BLUE, lw=0.5, alpha=0.8)
        ax.plot(p[-1, 0], p[-1, 1], "o", color=common.BLUE, ms=4)
        frac = np.mean([(z[0] - discs[1][0]) ** 2 + (z[1] - discs[1][1]) ** 2 < discs[1][2] ** 2 for z in p])
        ax.set_title("%s (%.0f%% of the path in the upper disc)" % (title, 100 * frac), fontsize=8.5)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_aspect("equal")
        ax.set_xlabel(r"$z_1$")
        ax.set_ylabel(r"$z_2$")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-14", out_dir)


# =========================================================================== figures: Section 14.3
def fig_14_13(out_dir=None):
    """Figure 14.13: maximum likelihood for an energy-based model pushes the energy down at data and up at model samples."""
    model = EBM1D()
    w = ebm_w0(model)
    X = ebm_data()
    x = model.x
    E = model.energy(x, w)
    pM = model.density(w)
    pD = ebm_pdata(x)
    rng = JSRandom(5)
    xs = [3.0 * rng.norm() for _ in range(8)]
    langevin_1d(model, w, xs, 3000, 0.05, rng)
    xd = X[:6]
    fig, ax = plt.subplots(figsize=(7.4, 3.6))
    Es = (E - E.min()) / (E.max() - E.min()) * 0.9 + 0.12
    sel = (x > -4.5) & (x < 5.5)
    ax.plot(x[sel], Es[sel], color=common.GREEN, lw=1.6, label=r"$E(x,\mathbf{w})$ (rescaled)")
    ax.plot(x[sel], pD[sel] / pM.max() * 0.85, "--", color=common.RED, label=r"$p_{\mathcal{D}}(x)$")
    ax.plot(x[sel], pM[sel] / pM.max() * 0.85, "--", color=common.BLUE, label=r"$p_{\mathcal{M}}(x)$")
    Ef = lambda t: (model.energy(np.array([t]), w)[0] - E.min()) / (E.max() - E.min()) * 0.9 + 0.12  # noqa: E731
    for t in xd:
        ax.plot([t, t], [0, Ef(t)], color="#999999", ls="--", lw=0.7)
        ax.annotate("", xy=(t, Ef(t) - 0.09), xytext=(t, Ef(t) + 0.0), arrowprops=dict(arrowstyle="->", color=common.GREEN, lw=1.4))
    for t in xs:
        ax.plot([t, t], [0, Ef(t)], color="#999999", ls="--", lw=0.7)
        ax.annotate("", xy=(t, Ef(t) + 0.09), xytext=(t, Ef(t)), arrowprops=dict(arrowstyle="->", color=common.GREEN, lw=1.4))
    ax.plot(xd, np.zeros_like(xd), "o", color=common.RED, ms=5, clip_on=False, zorder=5, label="data samples (energy pushed down)")
    ax.plot(xs, np.zeros_like(xs), "o", color=common.BLUE, ms=5, clip_on=False, zorder=5, label="model samples, Langevin (pushed up)")
    ax.set_xlim(-4.5, 5.5)
    ax.set_ylim(0, 1.15)
    ax.set_yticks([])
    ax.set_xlabel(r"$x$")
    ax.legend(fontsize=7.5, frameon=False, loc="upper left", ncol=2)
    return savefig(fig, CH, "fig14-13", out_dir)


# =========================================================================== supplementary figures
def fig_14_s1(out_dir=None):
    """Figure 14.S1: Monte Carlo error: 1/sqrt(L) whatever the dimension, inflated by correlation; the random walk's sqrt(tau)."""
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.4))
    ax = axes[0]
    Ls = np.array([10, 30, 100, 300, 1000])
    pstar = 1 - stats.norm.cdf(0.5)
    rng = np.random.default_rng(21)
    for D, col, mk in ((1, common.RED, "o"), (10, common.GREEN, "s"), (1000, common.BLUE, "^")):
        rmse = []
        for L in Ls:
            errs = []
            for _ in range(100):
                Z = rng.standard_normal((L, D))
                f = (Z.sum(1) / math.sqrt(D) > 0.5).astype(float)
                errs.append(f.mean() - pstar)
            rmse.append(math.sqrt(np.mean(np.square(errs))))
        ax.loglog(Ls, rmse, mk, color=col, label=r"$D=%d$" % D, ms=5, mfc="none")
    ax.loglog(Ls, np.sqrt(pstar * (1 - pstar) / Ls), color="k", lw=1, label=r"$\sqrt{\mathrm{var}[f]/L}$ (14.4)")
    ax.set_xlabel(r"number of samples $L$")
    ax.set_ylabel("root mean square error")
    ax.set_title(r"$f=\mathbb{1}[\sum_i z_i/\sqrt{D}>0.5]$, $\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_D)$", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[1]
    rng = np.random.default_rng(22)
    Ls = np.array([100, 300, 1000, 3000, 10000])
    for rho, col in ((0.0, common.RED), (0.5, common.GREEN), (0.9, common.BLUE), (0.99, common.PURPLE)):
        se = []
        for L in Ls:
            means = [ar1_chain(rho, L, rng).mean() for _ in range(150)]
            se.append(np.std(means))
        ax.loglog(Ls, se, "o", color=col, ms=4, mfc="none")
        ax.loglog(Ls, np.sqrt(ar1_iat(rho) / Ls), color=col, lw=1, label=r"$\rho=%s$: $\tau=%.0f$" % (rho, ar1_iat(rho)))
    ax.set_xlabel(r"chain length $L$")
    ax.set_ylabel(r"s.d. of the chain average")
    ax.set_title(r"AR(1) chains: $\mathrm{var}[\widehat f]\approx\tau\,\mathrm{var}[f]/L$", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[2]
    rng = np.random.default_rng(23)
    Zw = random_walk(400, 4000, rng)
    t = np.arange(401)
    ax.plot(t, (Zw.astype(float) ** 2).mean(0), color=common.BLUE, label=r"$\mathbb{E}[(z^{(\tau)})^2]$, 4000 walks")
    ax.plot(t, t / 2, "--", color="k", lw=1, label=r"$\tau/2$ (Exercise 14.11)")
    for i in range(3):
        ax.plot(t, Zw[i], color=common.GREY, lw=0.6)
    ax.set_xlabel(r"step $\tau$")
    ax.set_title(r"random walk (14.28)-(14.30): distance $\sim\sqrt{\tau/2}$", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s1", out_dir)


def _target_grid(name, xs, ys):
    Z = np.array([[target_logp_grad(name, x, y)[0] for x in xs] for y in ys])
    return Z - Z.max()


S2_ROWS = (("gauss", 0.2, "Gaussian"), ("banana", 0.1, "banana"), ("wells", 0.2, "two wells (0.7 / 0.3)"))


def _minor_var(X):
    """Sample variance of the Gaussian target's minor axis (direction at 135 degrees)."""
    u = _RG[:, 1]
    return float(np.var(X @ u))


def fig_14_s3(out_dir=None):
    """Figure 14.S3: Langevin sampling (14.61), its Metropolis-adjusted version, and plain gradient ascent on three energy landscapes."""
    fig, axes = plt.subplots(3, 4, figsize=(12.4, 8.6))
    xs = np.linspace(-5, 5, 160)
    ys = np.linspace(-3.5, 4.5, 140)
    for row, (name, big, rlab) in enumerate(S2_ROWS):
        G = _target_grid(name, xs, ys)
        runs = (("ula", 0.02, 1.0, r"Langevin $\eta=0.02$"), ("ula", big, 1.0, r"Langevin $\eta=%s$" % big),
                ("mala", big, 1.0, r"MALA $\eta=%s$" % big), ("ula", 0.02, 0.0, r"no noise, $\eta=0.02$"))
        m, C = target_moments(name)
        for col, (meth, eta, noise, lab) in enumerate(runs):
            ax = axes[row, col]
            ax.contour(xs, ys, G, levels=[-8, -4.5, -2, -0.5], colors="#bbbbbb", linewidths=0.7)
            X, rate, path = langevin_run(name, meth, eta, 1000, 300, noise, seed=1, keep_path=80)
            ax.plot(X[:, 0], X[:, 1], ".", color=common.BLUE, ms=2.2)
            ax.plot(path[:, 0], path[:, 1], color=common.RED, lw=0.7)
            Ct = np.cov(X.T)
            extra = (", acc. %.2f" % rate) if meth == "mala" else ""
            ax.set_title("%s%s" % (lab, extra), fontsize=8.5)
            if name == "gauss":
                txt = "minor-axis var %.3f (true 0.160)" % _minor_var(X)
                if meth == "ula" and noise > 0:
                    txt += "\nLangevin theory %.3f" % ula_gauss_var(0.16, eta)
            elif name == "wells":
                txt = "right well: %.2f (true 0.30)" % np.mean(X[:, 0] > 0)
            else:
                txt = "var $x$ %.2f (4.00), var $y$ %.2f (2.50)" % (Ct[0, 0], Ct[1, 1])
            ax.text(0.02, 0.02, txt, transform=ax.transAxes, fontsize=7, va="bottom")
            ax.set_xlim(-5, 5)
            ax.set_ylim(-3.5, 4.5)
            ax.set_xticks([])
            ax.set_yticks([])
        axes[row, 0].set_ylabel(rlab)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s3", out_dir)


def wells_grad_vec(X):
    """Vectorised gradient of ln p for the 'wells' target (for Figure 14.S4 only)."""
    s2 = WELL_SD ** 2
    L = np.stack([math.log(p) - ((X - np.array(mu)) ** 2).sum(1) / (2 * s2) for p, mu in WELLS], 1)
    R = np.exp(L - L.max(1, keepdims=True))
    R /= R.sum(1, keepdims=True)
    mus = np.array([mu for _, mu in WELLS])
    return -(X - R @ mus) / s2


def ula_1d(sigma2, eta, n, steps, rng, mala=False):
    """Langevin (or MALA) chains for N(0, sigma2) started at stationarity-ish 0; returns the final states."""
    x = np.zeros(n)
    acc = 0
    for _ in range(steps):
        e = rng.standard_normal(n)
        g = -x / sigma2
        xn = x + eta * g + math.sqrt(2 * eta) * e
        if not mala:
            x = xn
            continue
        gn = -xn / sigma2
        la = (-(xn ** 2) + x ** 2) / (2 * sigma2) - ((x - xn - eta * gn) ** 2 - (xn - x - eta * g) ** 2) / (4 * eta)
        ok = np.log(rng.random(n)) < la
        acc += ok.sum()
        x = np.where(ok, xn, x)
    return x, acc / float(n * steps)


def fig_14_s4(out_dir=None):
    """Figure 14.S4: Langevin sampling is biased for any step eta > 0 (exactly sigma^2/(1 - eta/2sigma^2) for a Gaussian); MALA is not; mixing slows as eta shrinks."""
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.4))
    etas = np.array([0.02, 0.05, 0.1, 0.2, 0.4, 0.7, 1.0, 1.4, 1.8])
    rng = np.random.default_rng(31)
    ax = axes[0]
    vu, vm = [], []
    for eta in etas:
        x, _ = ula_1d(1.0, eta, 20000, int(40 / eta) + 50, rng)
        vu.append(x.var())
        x, _ = ula_1d(1.0, eta, 20000, int(40 / eta) + 50, rng, mala=True)
        vm.append(x.var())
    ee = np.linspace(0.01, 1.9, 300)
    ax.plot(ee, ula_gauss_var(1.0, ee), color=common.RED, label=r"Langevin, exact: $1/(1-\eta/2)$")
    ax.plot(etas, vu, "o", color=common.RED, ms=4, mfc="none", label="Langevin, 20000 chains")
    ax.plot(etas, vm, "s", color=common.BLUE, ms=4, mfc="none", label="MALA, 20000 chains")
    ax.axhline(1.0, color="k", lw=0.8, ls=":")
    ax.set_yscale("log")
    ax.set_xlabel(r"step size $\eta$")
    ax.set_ylabel(r"stationary variance (target 1)")
    ax.set_title(r"target $\mathcal{N}(0,1)$: bias $\approx\eta/2$", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[1]
    rng = np.random.default_rng(32)
    tu, tm, accs = [], [], []
    for eta in etas:
        n = int(4000 / eta)
        x = np.zeros(n)
        xx = 0.0
        e = rng.standard_normal(n)
        for t in range(n):
            xx = xx - eta * xx + math.sqrt(2 * eta) * e[t]
            x[t] = xx
        tu.append(iat(x[n // 10:]))
        # MALA chain
        xx = 0.0
        e = rng.standard_normal(n)
        lu = np.log(rng.random(n))
        a_ = 0
        for t in range(n):
            xn = xx - eta * xx + math.sqrt(2 * eta) * e[t]
            la = (-(xn ** 2) + xx ** 2) / 2 - ((xx - xn + eta * xn) ** 2 - (xn - xx + eta * xx) ** 2) / (4 * eta)
            if lu[t] < la:
                xx = xn
                a_ += 1
            x[t] = xx
        tm.append(iat(x[n // 10:]))
        accs.append(a_ / n)
    ax.loglog(ee, 2 / ee - 1, color=common.RED, label=r"Langevin, exact: $2\sigma^2/\eta-1$")
    ax.loglog(etas, tu, "o", color=common.RED, ms=4, mfc="none")
    ax.loglog(etas, tm, "s", color=common.BLUE, ms=4, mfc="none", label="MALA, measured")
    for eta, a_, t_ in zip(etas, accs, tm):
        if eta in (0.1, 0.7, 1.8):
            ax.annotate("acc. %.2f" % a_, (eta, t_), (4, 6), textcoords="offset points", fontsize=7, color=common.BLUE)
    ax.set_xlabel(r"step size $\eta$")
    ax.set_ylabel("integrated autocorrelation time")
    ax.set_title("small steps mix slowly", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[2]
    steps = 4000
    for eta, col, seed in ((0.05, common.BLUE, 7), (0.2, common.GREEN, 8)):
        rng = np.random.default_rng(seed)
        n = 400
        Xa = 2.0 * rng.standard_normal((n, 2))
        frac = []
        sq = math.sqrt(2 * eta)
        for t in range(steps):
            Xa = Xa + eta * wells_grad_vec(Xa) + sq * rng.standard_normal((n, 2))
            if t % 20 == 0:
                frac.append((t, np.mean(Xa[:, 0] > 0)))
        frac = np.array(frac)
        ax.plot(frac[:, 0] * eta, frac[:, 1], color=col, label=r"$\eta=%s$" % eta)
    ax.axhline(0.3, color="k", ls="--", lw=0.9, label="target 0.3")
    ax.set_xlabel(r"time $\tau\eta$")
    ax.set_ylabel("fraction of 400 chains in the right well")
    ax.set_ylim(0, 0.7)
    ax.set_title("two wells: the split between the modes equilibrates very slowly", fontsize=9)
    ax.legend(fontsize=7.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s4", out_dir)


S4_RUNS = (("exact", {}, "exact gradient (quadrature)", common.GREEN),
           ("noise", {"T": 100, "M": 100}, r"Langevin from noise, $T=100$", common.ORANGE),
           ("cd", {"k": 1, "M": 100}, "contrastive divergence, 1 step", common.RED),
           ("pcd", {"k": 5, "M": 100}, "persistent chains, 5 steps", common.BLUE))


def fig_14_s5(out_dir=None):
    """Figure 14.S5: training an energy-based model by (14.57) with four ways of estimating the negative phase."""
    model = EBM1D()
    X = ebm_data()
    fig, axes = plt.subplots(1, 2, figsize=(10.4, 3.5))
    x = model.x
    axes[0].fill_between(x, ebm_pdata(x), color="#f3c6c6", label=r"$p_{\mathcal{D}}$")
    axes[0].plot(x, model.density(ebm_w0(model)), color=common.GREY, ls=":", label="start")
    for meth, kw, lab, col in S4_RUNS:
        w, h = ebm_train(meth, iters=300, lr=1.0, **kw)
        axes[0].plot(x, model.density(w), color=col, lw=1.3, label=lab)
        axes[1].plot(h["ll"], color=col, label=lab)
    axes[0].plot(X, np.full_like(X, -0.02), "|", color=common.RED, ms=6)
    axes[0].set_xlim(-5, 6)
    axes[0].set_xlabel(r"$x$")
    axes[0].set_title("model densities after 300 iterations", fontsize=9)
    axes[0].legend(fontsize=7, frameon=False, loc="upper right")
    best = np.mean(np.log(ebm_pdata(X)))
    axes[1].axhline(best, color="k", ls="--", lw=0.8, label=r"$\frac{1}{N}\sum\ln p_{\mathcal{D}}(x_n)$")
    axes[1].set_xlabel("iteration")
    axes[1].set_ylabel("average log likelihood (exact)")
    axes[1].set_ylim(-5, -1.2)
    axes[1].legend(fontsize=7, frameon=False, loc="lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s5", out_dir)


def cd1_expected_update(model, X, w, eta, n_gh=40):
    """E[phi(x')] - phi(x) averaged over the data, with x' one Langevin step (14.61) from x, by
    Gauss-Hermite quadrature over the noise: the expected CD-1 update direction of w."""
    t, wt = np.polynomial.hermite_e.hermegauss(n_gh)
    wt = wt / wt.sum()
    s = model.score(X, w)
    xp = X[:, None] + eta * s[:, None] + math.sqrt(2 * eta) * t[None, :]
    Pp = model.phi(xp.ravel()).reshape(len(X), n_gh, -1)
    return (np.einsum("nqk,q->nk", Pp, wt) - model.phi(X)).mean(0)


def fig_14_s6(out_dir=None):
    """Figure 14.S6: one-step Langevin contrastive divergence follows the negative score-matching gradient."""
    model = EBM1D()
    X = ebm_data()
    rng = np.random.default_rng(51)
    w = ebm_w0(model) + 0.5 * rng.standard_normal(len(model.c))
    gsm = -score_matching_grad(model, X, w)
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.5))
    ax = axes[0]
    eta = 0.01
    g = cd1_expected_update(model, X, w, eta) / eta
    ax.plot(gsm, g, "o", color=common.BLUE, ms=4)
    lim = 1.1 * np.abs(np.concatenate([gsm, g])).max()
    ax.plot([-lim, lim], [-lim, lim], "k--", lw=0.8)
    ax.set_xlabel(r"$-\partial J_{\mathrm{SM}}/\partial w_k$")
    ax.set_ylabel(r"expected CD-1 update $/\eta$")
    ax.set_title(r"$\eta=0.01$, one point per weight $w_k$", fontsize=9)
    ax = axes[1]
    etas = np.logspace(-4, -0.5, 12)
    err = [np.linalg.norm(cd1_expected_update(model, X, w, e) / e - gsm) / np.linalg.norm(gsm) for e in etas]
    ax.loglog(etas, err, "o-", color=common.BLUE, ms=4)
    ax.loglog(etas, err[0] * etas / etas[0], "--", color=common.GREY, label=r"slope 1: error $O(\eta)$")
    ax.set_xlabel(r"step size $\eta$")
    ax.set_ylabel("relative difference")
    ax.legend(fontsize=8, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s6", out_dir)


def fig_14_s2(out_dir=None):
    """Figure 14.S2: score-function versus reparameterisation estimators of a gradient of an expectation."""
    fig, axes = plt.subplots(1, 3, figsize=(12.2, 3.4))
    ax = axes[0]
    mu, sig = 2.0, 1.0
    sf, rp = grad_estimates("quad", mu, sig, 0.0, "mu", L=1, R=20000, seed=3)
    bins = np.linspace(-20, 30, 151)
    ax.hist(sf, bins=bins, density=True, color=common.RED, alpha=0.5, label="score function, var %.1f" % sf.var())
    ax.hist(rp, bins=bins, density=True, color=common.BLUE, alpha=0.6, label="reparameterisation, var %.1f" % rp.var())
    ax.axvline(2 * mu, color="k", lw=1, ls="--", label=r"true $\partial_\mu\mathbb{E}[z^2]=4$")
    ax.set_xlim(-20, 30)
    ax.set_xlabel("single-sample estimate")
    ax.set_title(r"$f(z)=z^2$, $z\sim\mathcal{N}(2,1)$", fontsize=9)
    ax.legend(fontsize=7, frameon=False)
    ax = axes[1]
    mus = np.linspace(-3, 3, 61)
    ax.semilogy(mus, [quad_score_var_mu(m_, 1.0) for m_ in mus], color=common.RED, label="score function")
    ax.semilogy(mus, [grad_moments("quad", m_, 1.0, 0.0, "mu", True)[0][1] for m_ in mus], color=common.ORANGE, ls="--",
                label=r"score function, baseline $\mathbb{E}[f]$")
    ax.semilogy(mus, np.full_like(mus, 4.0), color=common.BLUE, label=r"reparameterisation ($4\sigma^2$)")
    ax.set_xlabel(r"$\mu$")
    ax.set_ylabel("variance of one-sample estimate")
    ax.set_title(r"$f(z)=z^2$, $\sigma=1$ (exact)", fontsize=9)
    ax.legend(fontsize=7, frameon=False)
    ax = axes[2]
    mus = np.linspace(-3, 3, 25)
    true = [grad_true("step", m_, 1.0, 0.0)[1] for m_ in mus]
    ests = np.array([grad_estimates("step", m_, 1.0, 0.0, "mu", L=100, R=400, seed=5)[0] for m_ in mus])
    ax.plot(mus, true, color="k", lw=1, label=r"true $\phi(\mu)$")
    ax.errorbar(mus, ests.mean(1), yerr=2 * ests.std(1), fmt="o", color=common.RED, ms=3, lw=0.8,
                label=r"score function, $L=100$ ($\pm2$ s.d.)")
    ax.plot(mus, np.zeros_like(mus), color=common.BLUE, lw=1.5, label="reparameterisation: always 0")
    ax.set_xlabel(r"$\mu$")
    ax.set_title(r"$f(z)=\mathbb{1}[z>0]$: $\partial_\mu P(z>0)$", fontsize=9)
    ax.legend(fontsize=7, frameon=False, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-s2", out_dir)


def fig_data(out_dir=None):
    """Data file for ebm-training-demo.html (no figure)."""
    export_ebm_json()


FIGURES = {"14.1": fig_14_1, "14.2": fig_14_2, "14.3": fig_14_3, "14.4": fig_14_4, "14.5": fig_14_5,
           "14.6": fig_14_6, "14.7": fig_14_7, "14.8": fig_14_8, "14.9": fig_14_9, "14.10": fig_14_10,
           "14.11": fig_14_11, "14.13": fig_14_13, "14.14": fig_14_14,
           "14.S1": fig_14_s1, "14.S2": fig_14_s2, "14.S3": fig_14_s3, "14.S4": fig_14_s4, "14.S5": fig_14_s5,
           "14.S6": fig_14_s6, "data": fig_data}


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