"""Murphy (2023), Chapter 31: Nonparametric Bayesian models (and Supplement Chapter 31).

Companion code for Chapter 31 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 1081-1082, and the supplement, Chapter 31, pp. 267-300,
where almost all of the chapter lives. Written from scratch with numpy, scipy and matplotlib, to be
read next to the lecture notes (../ch31-nonparametric-bayes.html).

Methods implemented here (all by hand)
* Supplement 31.1: Dirichlet processes by stick breaking (stick_breaking), the Chinese restaurant
  process and its Pitman-Yor generalisation (crp), the exact law and moments of the number of tables
  (expected_tables, var_tables_dp, table_count_pmf_dp), the Ewens and Pitman-Yor partition
  probabilities (log_eppf_pyp).
* Supplement 31.2: sampling a DP mixture of Gaussians with a normal-inverse-Wishart base measure
  (dpmm_sample), the collapsed Gibbs sampler of Algorithm 31.1 (dpmm_gibbs, with the NIW and the
  known-variance Gaussian models), the auxiliary-variable update of the concentration (escobar_west_alpha),
  truncated mean-field variational inference, Algorithm 31.2 (dpmm_vi), DP-means, Algorithm 31.3 (dp_means).
* Supplement 31.4: the Indian buffet process (ibp) and the stick-breaking beta process (beta_process_sticks).
* Supplement 31.6-31.7: the gamma process from its Poisson construction (gamma_process), Brownian motion and
  the Cauchy process.
* Supplement 31.8: homogeneous and thinned Poisson processes, a Strauss process by birth-death
  Metropolis-Hastings (strauss_bd), a Thomas cluster process, Hawkes processes by Ogata thinning
  (hawkes_simulate, hawkes_loglik, hawkes_mle) and determinantal point processes (dpp_sample,
  dpp_inclusion_kernel).
* Mulberry32: the same seeded generator as the browser demos, so a demo and this module draw the same
  random numbers (crp_mulberry, hawkes_mulberry).

Figures. All figures of the chapter are in the supplement and are numbered S31.k here
(supplement Figure 31.k). Reproduced: S31.1, S31.2, S31.3(b), S31.4, S31.6, S31.7, S31.8, S31.9, S31.10,
S31.11, S31.12. Stand-ins: the book's data for Figure S31.6 are not given, so two simulated data sets
with four clear and an unclear number of clusters are used; the Swedish pines and California redwoods
of Figure S31.11 are not available, so a simulated Strauss process (repulsive) and a Thomas cluster
process (clustered) take their place.

Skipped figures, with reasons: S31.3(a) (the broken stick), S31.5 (two graphical models) and S31.13 (a
parallelogram spanned by two vectors) are diagrams with nothing computed.

Own figures (not in the book): x31.1 (Dirichlet against Pitman-Yor: growth of the number of tables and
the table-size distribution), x31.2 (truncated variational inference against collapsed Gibbs for the DP
mixture), x31.3 (DP-means: clusters, number of clusters against the penalty, and the monotone objective),
x31.4 (a determinantal point process against independent sampling with the same inclusion probabilities).
"""
import os
import sys
import json
import math

import numpy as np
from scipy import special, stats

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

CH = 31
CACHE_DIR = os.path.join(HERE, "cache", "ch31")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)
os.makedirs(DATA_OUT, exist_ok=True)
logsumexp = special.logsumexp
PALETTE = [BLUE, RED, GREEN, ORANGE, PURPLE, CYAN, MAGENTA, "#8c564b", "#bcbd22", GREY, "#393b79", "#e377c2"]


# =========================================================================== the demos' random numbers
class Mulberry32:
    """The mulberry32 generator with Box-Muller normals, bit-for-bit the same as DK.rng in demo-kit.js."""

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

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

    def u(self):
        a = (self.a + 0x6D2B79F5) & 0xFFFFFFFF
        self.a = a
        t = self._imul(a ^ (a >> 15), 1 | a)
        t = ((t + self._imul(t ^ (t >> 7), 61 | t)) & 0xFFFFFFFF) ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 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)


# =========================================================================== S31.1 Dirichlet process
def stick_breaking(alpha, K, rng, d=0.0):
    """First K weights of a Pitman-Yor stick-breaking sequence, beta_k ~ Beta(1 - d, alpha + k d)
    (S31.36); d = 0 gives GEM(alpha) (S31.9)-(S31.10). Returns (pi, leftover mass)."""
    k = np.arange(1, K + 1)
    b = rng.beta(1.0 - d, alpha + k * d)
    rest = np.concatenate([[1.0], np.cumprod(1.0 - b)])
    return b * rest[:-1], rest[-1]


def dp_draw(alpha, base_sampler, rng, tol=1e-10, kmax=200000):
    """Atoms and weights of G ~ DP(alpha, H), truncated when the leftover mass is below tol."""
    w, left = [], 1.0
    while left > tol and len(w) < kmax:
        b = rng.beta(1.0, alpha)
        w.append(left * b)
        left *= 1.0 - b
    w = np.array(w)
    return base_sampler(len(w)), w


def crp(N, alpha, rng, d=0.0):
    """Table assignments z (0-based) of N customers under the CRP (S31.14) or its Pitman-Yor version:
    join table k with weight N_k - d, a new table with weight alpha + d K."""
    z = np.empty(N, dtype=int)
    counts = []
    for n in range(N):
        K = len(counts)
        p = np.array([c - d for c in counts] + [alpha + d * K])
        k = rng.choice(K + 1, p=p / p.sum())
        if k == K:
            counts.append(1)
        else:
            counts[k] += 1
        z[n] = k
    return z, np.array(counts)


def crp_mulberry(N, alpha, d, seed):
    """The CRP / PY-CRP drawn with Mulberry32 exactly as crp-pitman-yor-demo.html draws it.
    Returns the table counts in order of creation and the number of tables after each customer."""
    rng = Mulberry32(seed)
    counts, path = [], []
    for n in range(N):
        K = len(counts)
        r = rng.u() * (alpha + n)
        new_w = alpha + d * K
        if r < new_w or K == 0:
            counts.append(1)
        else:
            r -= new_w
            j = 0
            while j < K - 1:
                r -= counts[j] - d
                if r < 0:
                    break
                j += 1
            counts[j] += 1
        path.append(len(counts))
    return counts, path


def expected_tables(N, alpha, d=0.0):
    """E[K_n] for n = 1..N under the (Pitman-Yor) CRP, by the exact linear recursion
    E K_{n+1} = E K_n (1 + d/(alpha + n)) + alpha/(alpha + n), E K_1 = 1."""
    out = np.empty(N)
    e = 1.0
    out[0] = e
    for n in range(1, N):
        e = e * (1.0 + d / (alpha + n)) + alpha / (alpha + n)
        out[n] = e
    return out


def var_tables_dp(N, alpha):
    """Var K_N = sum_{i=0}^{N-1} alpha i/(alpha + i)^2 under the DP (independent Bernoulli new-table events)."""
    i = np.arange(N)
    return float(np.sum(alpha * i / (alpha + i) ** 2))


def stirling1_unsigned(N):
    """Table |s(n, k)| for n, k <= N as Python integers (exact)."""
    S = [[0] * (N + 1) for _ in range(N + 1)]
    S[0][0] = 1
    for n in range(N):
        for k in range(1, n + 2):
            S[n + 1][k] = n * S[n][k] + S[n][k - 1]
    return S


def table_count_pmf_dp(N, alpha):
    """p(K_N = k) = |s(N, k)| alpha^k Gamma(alpha)/Gamma(alpha + N), k = 1..N (Antoniak 1974)."""
    S = stirling1_unsigned(N)
    k = np.arange(1, N + 1)
    logs = np.array([math.log(S[N][kk]) for kk in k])
    lp = logs + k * math.log(alpha) + special.gammaln(alpha) - special.gammaln(alpha + N)
    return np.exp(lp)


def log_eppf_pyp(sizes, alpha, d=0.0):
    """Log probability of one particular partition of [N] with block sizes `sizes` under PYP(alpha, d)
    (Ewens's formula when d = 0): prod_{i=1}^{K-1}(alpha + i d) prod_k (1 - d)_{n_k - 1} / (alpha + 1)_{N-1}."""
    sizes = np.asarray(sizes)
    N, K = sizes.sum(), len(sizes)
    lp = sum(math.log(alpha + i * d) for i in range(1, K))
    lp += sum(special.gammaln(n - d) - special.gammaln(1 - d) for n in sizes)
    lp -= special.gammaln(alpha + N) - special.gammaln(alpha + 1)
    return float(lp)


def log_ewens_book(sizes, alpha):
    """Equation S(31.15) exactly as printed (it does not sum to one; see the notes)."""
    sizes = np.asarray(sizes)
    N, K = sizes.sum(), len(sizes)
    rising = sum(math.log(alpha + 1 + i) for i in range(N))
    return (K - 1) * math.log(alpha) - rising + float(np.sum(special.gammaln(sizes + 1)))


def set_partitions(n):
    """All set partitions of {0..n-1} as lists of blocks (restricted growth strings)."""
    def rec(i, a, m):
        if i == n:
            blocks = [[] for _ in range(m + 1)]
            for j, b in enumerate(a):
                blocks[b].append(j)
            yield blocks
            return
        for b in range(m + 2):
            a.append(b)
            yield from rec(i + 1, a, max(m, b))
            a.pop()
    if n == 0:
        yield []
        return
    yield from rec(1, [0], 0)


# =========================================================================== S31.2 DP mixtures
def niw_sample(m0, kappa0, nu0, S0, rng, n=1):
    """n draws (mu, Sigma) from NIW(m0, kappa0, nu0, S0): Sigma ~ IW(S0, nu0), mu | Sigma ~ N(m0, Sigma/kappa0)."""
    out = []
    for _ in range(n):
        Sig = stats.invwishart.rvs(df=nu0, scale=S0, random_state=rng)
        mu = rng.multivariate_normal(m0, Sig / kappa0)
        out.append((mu, Sig))
    return out


def dpmm_sample(N, alpha, m0, kappa0, nu0, S0, rng):
    """N draws from a DP mixture of Gaussians with NIW base measure, by the CRP (S31.16)-(S31.19)."""
    z, counts = crp(N, alpha, rng)
    params = niw_sample(m0, kappa0, nu0, S0, rng, n=len(counts))
    X = np.array([rng.multivariate_normal(*params[k]) for k in z])
    return X, z, params


class NIWModel:
    """Conjugate Gaussian cluster model with a normal-inverse-Wishart prior; the posterior predictive of a
    cluster is a multivariate Student t (proved in Chapter 3 of this course, gap 3.10)."""

    def __init__(self, m0, kappa0, nu0, S0):
        self.m0, self.k0, self.v0, self.S0 = np.asarray(m0, float), float(kappa0), float(nu0), np.asarray(S0, float)
        self.D = len(self.m0)

    def empty(self):
        return [0, np.zeros(self.D), np.zeros((self.D, self.D))]

    def add(self, st, x, sgn=1):
        st[0] += sgn
        st[1] = st[1] + sgn * x
        st[2] = st[2] + sgn * np.outer(x, x)

    def post(self, st):
        n, s, ss = st
        kn, vn = self.k0 + n, self.v0 + n
        mn = (self.k0 * self.m0 + s) / kn
        Sn = self.S0 + ss + self.k0 * np.outer(self.m0, self.m0) - kn * np.outer(mn, mn)
        return kn, vn, mn, Sn

    def logpred(self, x, st):
        kn, vn, mn, Sn = self.post(st)
        D = self.D
        df = vn - D + 1
        scale = Sn * (kn + 1) / (kn * df)
        r = np.asarray(x, float) - mn
        if D == 2:                                   # closed-form 2 x 2 determinant and inverse (fast path)
            det = scale[0, 0] * scale[1, 1] - scale[0, 1] * scale[1, 0]
            maha = (scale[1, 1] * r[0] ** 2 - 2 * scale[0, 1] * r[0] * r[1] + scale[0, 0] * r[1] ** 2) / det
            logdet = math.log(det)
        else:
            logdet = np.linalg.slogdet(scale)[1]
            maha = float(r @ np.linalg.solve(scale, r))
        return float(special.gammaln((df + D) / 2) - special.gammaln(df / 2) - 0.5 * D * math.log(df * math.pi)
                     - 0.5 * logdet - 0.5 * (df + D) * math.log1p(maha / df))

    def logmarg(self, X):
        """log p(X) for the points of one cluster (the ratio of NIW normalisers)."""
        st = self.empty()
        for x in X:
            self.add(st, x)
        kn, vn, mn, Sn = self.post(st)
        n, D = len(X), self.D
        return float(-0.5 * n * D * np.log(np.pi) + special.multigammaln(vn / 2, D) - special.multigammaln(self.v0 / 2, D)
                     + 0.5 * self.v0 * np.linalg.slogdet(self.S0)[1] - 0.5 * vn * np.linalg.slogdet(Sn)[1]
                     + 0.5 * D * (np.log(self.k0) - np.log(kn)))


class GaussKnownVarModel:
    """Clusters N(mu, sigma2 I) with prior mu ~ N(m0, rho2 I): the predictive is N(m_n, (s_n^2 + sigma2) I)."""

    def __init__(self, m0, rho2, sigma2):
        self.m0, self.r2, self.s2 = np.atleast_1d(np.asarray(m0, float)), float(rho2), float(sigma2)
        self.D = len(self.m0)

    def empty(self):
        return [0, np.zeros(self.D), None]

    def add(self, st, x, sgn=1):
        st[0] += sgn
        st[1] = st[1] + sgn * np.atleast_1d(x)

    def logpred(self, x, st):
        n, s = st[0], st[1]
        prec = 1.0 / self.r2 + n / self.s2
        v = 1.0 / prec
        m = v * (self.m0 / self.r2 + s / self.s2)
        x = np.atleast_1d(x)
        return float(-0.5 * self.D * np.log(2 * np.pi * (v + self.s2)) - 0.5 * np.sum((x - m) ** 2) / (v + self.s2))

    def logmarg(self, X):
        lp, st = 0.0, self.empty()
        for x in X:
            lp += self.logpred(x, st)
            self.add(st, x)
        return lp


def escobar_west_alpha(alpha, K, N, a, b, rng):
    """One auxiliary-variable update of alpha ~ Ga(a, rate b) given K clusters among N (Escobar and West 1995)."""
    eta = rng.beta(alpha + 1.0, N)
    rate = b - np.log(eta)
    odds = (a + K - 1.0) / (N * rate)
    shape = a + K if rng.random() < odds / (1.0 + odds) else a + K - 1.0
    return rng.gamma(shape, 1.0 / rate)


def dpmm_gibbs(X, model, alpha, n_sweeps, rng, z0=None, record=None, alpha_prior=None):
    """Collapsed Gibbs sampler for the DP mixture, Algorithm S31.1 (Neal 2000, Algorithm 3).
    Returns the final labels, the traces of the number of clusters, of alpha (updated when alpha_prior=(a, b))
    and of the number of clusters holding at least 3% of the points, and the recorded label vectors."""
    N = len(X)
    z = np.zeros(N, dtype=int) if z0 is None else np.array(z0)
    labels = sorted(set(z))
    relabel = {l: i for i, l in enumerate(labels)}
    z = np.array([relabel[l] for l in z])
    stats_ = [model.empty() for _ in labels]
    for i in range(N):
        model.add(stats_[z[i]], X[i])
    Ks, alphas, samples, Kbig = [], [], [], []
    for sweep in range(n_sweeps):
        for i in rng.permutation(N):
            k = z[i]
            model.add(stats_[k], X[i], -1)
            if stats_[k][0] == 0:                       # drop the empty cluster and renumber
                stats_.pop(k)
                z[z > k] -= 1
            K = len(stats_)
            lw = np.empty(K + 1)
            for c in range(K):
                lw[c] = np.log(stats_[c][0]) + model.logpred(X[i], stats_[c])
            lw[K] = np.log(alpha) + model.logpred(X[i], model.empty())
            p = np.exp(lw - lw.max())
            c = rng.choice(K + 1, p=p / p.sum())
            if c == K:
                stats_.append(model.empty())
            z[i] = c
            model.add(stats_[c], X[i])
        if alpha_prior is not None:
            alpha = escobar_west_alpha(alpha, len(stats_), N, alpha_prior[0], alpha_prior[1], rng)
        Ks.append(len(stats_))
        Kbig.append(sum(st_[0] >= 0.03 * N for st_ in stats_))
        alphas.append(alpha)
        if record is not None and sweep in record:
            samples.append(z.copy())
    return z, np.array(Ks), np.array(alphas), np.array(Kbig), samples


def dpmm_vi(X, alpha, T, sigma2, m0, rho2, rng, n_iter=200, tol=1e-9):
    """Truncated mean-field VI for a DP mixture of N(mu_t, sigma2 I) with mu_t ~ N(m0, rho2 I), Algorithm S31.2
    (Blei and Jordan 2006). Returns the variational parameters and the ELBO after every full sweep."""
    N, D = X.shape
    phi = rng.dirichlet(np.ones(T), size=N)
    elbos = []
    for it in range(n_iter):
        Nt = phi.sum(0)
        g1 = 1.0 + Nt[:-1]
        g2 = alpha + np.cumsum(Nt[::-1])[::-1][1:]                      # sum_{j > t} N_j
        s2 = 1.0 / (1.0 / rho2 + Nt / sigma2)
        m = s2[:, None] * (m0 / rho2 + (phi.T @ X) / sigma2)
        Elb = special.digamma(g1) - special.digamma(g1 + g2)
        El1b = special.digamma(g2) - special.digamma(g1 + g2)
        Elogpi = np.concatenate([Elb, [0.0]]) + np.concatenate([[0.0], np.cumsum(El1b)])
        sq = ((X[:, None, :] - m[None]) ** 2).sum(-1) + D * s2[None]
        S = Elogpi[None] - sq / (2 * sigma2)
        phi = np.exp(S - logsumexp(S, axis=1, keepdims=True))
        elbos.append(dpmm_vi_elbo(X, alpha, sigma2, m0, rho2, phi, g1, g2, m, s2))
        if it > 2 and abs(elbos[-1] - elbos[-2]) < tol * abs(elbos[-1]):
            break
    return dict(phi=phi, g1=g1, g2=g2, m=m, s2=s2, elbo=np.array(elbos))


def dpmm_vi_elbo(X, alpha, sigma2, m0, rho2, phi, g1, g2, m, s2):
    N, D = X.shape
    Elb = special.digamma(g1) - special.digamma(g1 + g2)
    El1b = special.digamma(g2) - special.digamma(g1 + g2)
    Elogpi = np.concatenate([Elb, [0.0]]) + np.concatenate([[0.0], np.cumsum(El1b)])
    sq = ((X[:, None, :] - m[None]) ** 2).sum(-1) + D * s2[None]
    e = np.sum(np.log(alpha) + (alpha - 1) * El1b)
    e += np.sum(-0.5 * D * np.log(2 * np.pi * rho2) - (((m - m0) ** 2).sum(1) + D * s2) / (2 * rho2))
    e += np.sum(phi * Elogpi[None])
    e += np.sum(phi * (-0.5 * D * np.log(2 * np.pi * sigma2) - sq / (2 * sigma2)))
    e += np.sum(stats.beta.entropy(g1, g2))
    e += np.sum(0.5 * D * np.log(2 * np.pi * np.e * s2))
    e -= np.sum(special.xlogy(phi, phi))
    return float(e)


def dp_means(X, lam, max_iter=100):
    """DP-means, Algorithm S31.3 (Kulis and Jordan 2012). lam is the penalty on the squared distance.
    Returns labels, centres and the objective (S31.53) after every phase (assignments, then means)."""
    N = len(X)
    mu = [X.mean(0)]
    z = np.zeros(N, dtype=int)
    objs = [dp_means_objective(X, z, lam)]
    for it in range(max_iter):
        z_old = z.copy()
        for i in range(N):
            dists = [float(np.sum((X[i] - c) ** 2)) for c in mu]
            j = int(np.argmin(dists))
            if dists[j] > lam:
                mu.append(X[i].copy())
                z[i] = len(mu) - 1
            else:
                z[i] = j
        used = sorted(set(z.tolist()))                      # drop clusters that lost all their points
        remap = {u: t for t, u in enumerate(used)}
        z = np.array([remap[v] for v in z])
        objs.append(dp_means_objective(X, z, lam, [mu[u] for u in used]))
        mu = [X[z == k].mean(0) for k in range(len(used))]
        objs.append(dp_means_objective(X, z, lam))
        if it > 0 and np.array_equal(z, z_old):
            break
    return z, np.array(mu), np.array(objs)


def dp_means_objective(X, z, lam, centres=None):
    K = int(z.max()) + 1
    if centres is None:
        centres = [X[z == k].mean(0) for k in range(K)]
    return float(sum(np.sum((X[z == k] - centres[k]) ** 2) for k in range(K)) + lam * K)


# =========================================================================== S31.3 Pitman-Yor, HDP
def franchise_first_dish_share(alpha, alpha0, n_sim, rng):
    """Chinese restaurant franchise: do the first customers of two restaurants eat the same dish?"""
    hits = 0
    for _ in range(n_sim):
        hits += rng.random() < 1.0 / (1.0 + alpha0)      # second table in the top CRP joins the first dish
    return hits / n_sim


# =========================================================================== S31.4 IBP and beta process
def ibp(N, alpha, rng):
    """Binary feature matrix (N x K) of the Indian buffet process with mass alpha."""
    counts = []
    rows = []
    for i in range(1, N + 1):
        row = [int(rng.random() < m / i) for m in counts]
        new = rng.poisson(alpha / i)
        for j, r in enumerate(row):
            counts[j] += r
        row += [1] * new
        counts += [1] * new
        rows.append(row)
    K = len(counts)
    Z = np.zeros((N, K), dtype=int)
    for i, r in enumerate(rows):
        Z[i, :len(r)] = r
    return Z


def beta_process_sticks(alpha, K, rng):
    """Weights pi_k = prod_{l <= k} beta_l, beta_l ~ Beta(alpha, 1) (S31.51)-(S31.52)."""
    return np.cumprod(rng.beta(alpha, 1.0, size=K))


# =========================================================================== S31.6 CRMs, S31.7 Levy processes
def gamma_process(alpha, eps, rng):
    """Atoms of a gamma process with Levy intensity alpha w^{-1} e^{-w} dw (total mass ~ Ga(alpha, 1)),
    keeping the atoms with weight > eps: their number is Poisson(alpha E_1(eps)) and each weight has
    density proportional to w^{-1} e^{-w} on (eps, inf) (drawn by rejection from an exponential tail and
    a log-uniform body)."""
    mass = alpha * special.exp1(eps)
    n = rng.poisson(mass)
    w = np.empty(n)
    # mixture proposal: on (eps, 1] density ~ 1/w (log-uniform) with acceptance e^{-w};
    # on (1, inf) density ~ e^{-w} (shifted exponential) with acceptance 1/w.
    m1 = np.log(1.0 / eps) if eps < 1 else 0.0
    m2 = np.exp(-1.0)
    for i in range(n):
        while True:
            if rng.random() < m1 / (m1 + m2):
                x = eps * np.exp(rng.random() * m1)
                if rng.random() < np.exp(-x):
                    break
            else:
                x = 1.0 + rng.exponential()
                if rng.random() < 1.0 / x:
                    break
        w[i] = x
    return w


# =========================================================================== S31.8 point processes
def poisson_process_thinning(lam, lam_max, T, rng):
    """Inhomogeneous Poisson process on [0, T] by thinning a rate-lam_max process (Lewis and Shedler 1979)."""
    n = rng.poisson(lam_max * T)
    t = np.sort(rng.uniform(0, T, n))
    keep = rng.random(n) < lam(t) / lam_max
    return t[keep]


def strauss_bd(kappa, gamma, R, n_steps, rng, init=None):
    """Strauss process on the unit square, density proportional to kappa^n gamma^{s(x)} with respect to
    a unit-rate Poisson process (s = number of pairs closer than R), by birth-death Metropolis-Hastings
    (Geyer and Moller 1994). gamma = exp(-beta a) in the notation of S(31.62)."""
    P = np.empty((0, 2)) if init is None else np.array(init)
    for _ in range(n_steps):
        n = len(P)
        if rng.random() < 0.5:                                  # birth
            x = rng.random(2)
            close = np.sum(np.sum((P - x) ** 2, 1) < R * R) if n else 0
            ratio = kappa * gamma ** close / (n + 1)
            if rng.random() < ratio:
                P = np.vstack([P, x])
        elif n > 0:                                             # death
            j = rng.integers(n)
            others = np.delete(P, j, 0)
            close = np.sum(np.sum((others - P[j]) ** 2, 1) < R * R)
            ratio = n / (kappa * gamma ** close) if gamma > 0 or close == 0 else np.inf
            if rng.random() < ratio:
                P = others
    return P


def thomas_process(kappa, mu, sigma, rng):
    """Thomas cluster process on the unit square (parents Poisson(kappa), Poisson(mu) children each,
    displaced by N(0, sigma^2 I); periodic wrapping so the window has no edge effect)."""
    parents = rng.random((rng.poisson(kappa), 2))
    pts = [p + sigma * rng.standard_normal((rng.poisson(mu), 2)) for p in parents]
    pts = np.vstack(pts) if pts else np.empty((0, 2))
    return pts % 1.0


def hawkes_simulate(gamma, beta, tau, T, rng):
    """Univariate Hawkes process with kernel beta exp(-t/tau) on [0, T] by Ogata thinning."""
    t, S, ev = 0.0, 0.0, []
    while True:
        M = gamma + S
        w = rng.exponential(1.0 / M)
        t += w
        S *= np.exp(-w / tau)
        if t > T:
            return np.array(ev)
        if rng.random() * M <= gamma + S:
            ev.append(t)
            S += beta


def hawkes_mulberry(gamma, beta, tau, T, seed):
    """The same Ogata thinning with the demo's Mulberry32 generator (hawkes-process-demo.html)."""
    rng = Mulberry32(seed)
    t, S, ev = 0.0, 0.0, []
    while True:
        M = gamma + S
        w = -math.log(rng.pos()) / M
        t += w
        S *= math.exp(-w / tau)
        if t > T:
            return ev
        if rng.u() * M <= gamma + S:
            ev.append(t)
            S += beta


def hawkes_intensity(t_grid, ev, gamma, beta, tau):
    ev = np.asarray(ev)
    lam = np.full_like(t_grid, gamma, dtype=float)
    for tk in ev:
        m = t_grid >= tk
        lam[m] += beta * np.exp(-(t_grid[m] - tk) / tau)
    return lam


def hawkes_loglik(ev, gamma, beta, tau, T):
    """Log-likelihood S(31.59) for the exponential kernel, with the recursion A_i = e^{-dt/tau}(1 + A_{i-1})."""
    ev = np.asarray(ev)
    ll, A = 0.0, 0.0
    for i, t in enumerate(ev):
        if i > 0:
            A = np.exp(-(t - ev[i - 1]) / tau) * (1.0 + A)
        ll += np.log(gamma + beta * A)
    comp = gamma * T + beta * tau * np.sum(1.0 - np.exp(-(T - ev) / tau))
    return float(ll - comp)


def hawkes_expected_count(gamma, beta, tau, T):
    """E N(T) from an empty history: the mean intensity solves m' = gamma/tau - (1/tau - beta) m."""
    n = beta * tau
    minf = gamma / (1.0 - n)
    return float(minf * T + (gamma - minf) * tau / (1.0 - n) * (1.0 - np.exp(-(1.0 - n) * T / tau)))


def hawkes_mle(ev, T, x0=(0.5, 0.5, 1.0)):
    """Maximum likelihood (gamma, beta, tau) by L-BFGS on the log scale."""
    from scipy.optimize import minimize
    f = lambda p: -hawkes_loglik(ev, *np.exp(p), T)
    r = minimize(f, np.log(x0), method="L-BFGS-B")
    return np.exp(r.x), -r.fun


def hawkes2_simulate(gam, B, tau, T, rng):
    """Bivariate Hawkes process: lambda_i = gam_i + sum_j sum_{t in H_j} B[i, j] exp(-(t - t_k)/tau)."""
    t, S, ev = 0.0, np.zeros(2), [[], []]
    while True:
        M = gam.sum() + S.sum()
        w = rng.exponential(1.0 / M)
        t += w
        S *= np.exp(-w / tau)
        if t > T:
            return [np.array(e) for e in ev]
        lam = gam + S
        u = rng.random() * M
        if u <= lam.sum():
            i = 0 if u <= lam[0] else 1
            ev[i].append(t)
            S += B[:, i]


def dpp_inclusion_kernel(L):
    """Marginal kernel K = L (I + L)^{-1} of the L-ensemble with kernel L."""
    return L @ np.linalg.inv(np.eye(len(L)) + L)


def dpp_sample(L, rng):
    """Exact sample of the L-ensemble DPP by the spectral algorithm (Hough et al. 2006; Kulesza and Taskar
    2012): pick eigenvectors independently with probability lambda/(1 + lambda), then sample the
    projection DPP item by item."""
    lam, V = np.linalg.eigh(L)
    V = V[:, rng.random(len(lam)) < lam / (1.0 + lam)]
    Y = []
    while V.shape[1] > 0:
        p = np.sum(V ** 2, 1) / V.shape[1]
        i = rng.choice(len(p), p=p / p.sum())
        Y.append(i)
        j = np.argmax(np.abs(V[i]))                    # eliminate e_i from the span
        Vj = V[:, j].copy()
        V = np.delete(V, j, 1)
        V = V - np.outer(Vj, V[i] / Vj[i])
        if V.shape[1] > 0:
            V, _ = np.linalg.qr(V)
    return sorted(Y)


def rbf_grid_L(n_side, ell, scale):
    g = (np.arange(n_side) + 0.5) / n_side
    P = np.array([(a, b) for a in g for b in g])
    D2 = ((P[:, None] - P[None]) ** 2).sum(-1)
    return P, scale * np.exp(-D2 / (2 * ell ** 2))


# =========================================================================== data for Figure S31.6 and the DP-means demo
def cluster_data():
    """The two data sets of Figure S31.6 (stand-ins): A has four clear clusters, B an unclear number.
    Coordinates are rounded to 3 decimals, the values exported to the DP-means demo."""
    rng = np.random.default_rng(31)
    A = []
    spec = [((-6, 4), [[1.2, 0.6], [0.6, 0.8]], 70), ((5, 5), [[0.6, 0], [0, 0.6]], 50),
            ((-4, -5), [[0.8, -0.5], [-0.5, 1.0]], 60), ((6, -3), [[1.5, 0], [0, 0.4]], 50)]
    for m, S, n in spec:
        A.append(rng.multivariate_normal(m, S, n))
    A = np.vstack(A)
    B = []
    for m, n in [((-1.2, 0.5), 60), ((1.0, 1.0), 50), ((0.3, -1.2), 60), ((2.0, -0.6), 40), ((-1.8, -1.0), 40)]:
        B.append(rng.multivariate_normal(m, np.eye(2) * 0.9, n))
    B = np.vstack(B)
    A = np.round(A[rng.permutation(len(A))], 3)
    B = np.round(B[rng.permutation(len(B))], 3)
    return A, B


def gibbs_prior(X):
    """The NIW prior used for Figure S31.6: centred at the data mean, kappa0 = 0.05, nu0 = D + 3, S0 = I
    (prior mean covariance I/2)."""
    D = X.shape[1]
    return NIWModel(X.mean(0), 0.05, D + 3, np.eye(D))


def run_fig31_6_chains(n_sweeps=400, burn=100):
    """Collapsed Gibbs on data sets A and B with alpha = 1, started from 10 random clusters."""
    path = os.path.join(CACHE_DIR, "gibbs_31_6.npz")
    if os.path.exists(path):
        f = np.load(path, allow_pickle=True)
        return {k: f[k] for k in f.files}
    A, B = cluster_data()
    out = {}
    for name, X in (("A", A), ("B", B)):
        rng = np.random.default_rng(6)
        z0 = rng.integers(0, 10, len(X))
        z, Ks, _, Kbig, samp = dpmm_gibbs(X, gibbs_prior(X), 1.0, n_sweeps, rng, z0=z0, record={n_sweeps - 1})
        out["K_" + name] = Ks[burn:]
        out["Kbig_" + name] = Kbig[burn:]
        out["z_" + name] = samp[-1]
    np.savez(path, **out)
    return out


# =========================================================================== figures
def _ellipse(ax, mu, S, color="k", nsd=2.0, lw=1.4):
    x, y = common.ellipse_xy(mu, S, nsd)
    ax.plot(x, y, color=color, lw=lw)


def fig_S31_1(out_dir=None):
    """Shading of partitions of the unit square by G(T_k) for one draw of a DP with uniform base."""
    rng = np.random.default_rng(1)
    th, w = dp_draw(5.0, lambda n: rng.random((n, 2)), rng)
    # three cells: T3 = above the line y = 0.45 + 0.55 x, T2 = below y = 0.35 (and not T3), T1 = the rest
    up = lambda p: p[:, 1] > 0.45 + 0.55 * p[:, 0]
    low = lambda p: (p[:, 1] < 0.35) & ~up(p)
    cells3 = {"T3": up(th), "T2": low(th)}
    cells3["T1"] = ~(cells3["T3"] | cells3["T2"])
    split = th[:, 0] + th[:, 1] < 1.25                       # T1 is split by the line x + y = 1.25
    cells4 = {"T3": cells3["T3"], "T2": cells3["T2"], "T11": cells3["T1"] & split, "T12": cells3["T1"] & ~split}
    G3 = {k: float(w[m].sum()) for k, m in cells3.items()}
    G4 = {k: float(w[m].sum()) for k, m in cells4.items()}
    fig, axes = panel_grid(1, 3, size=(2.7, 2.7))
    gx = np.linspace(0, 1, 401)
    XX, YY = np.meshgrid(gx, gx)
    P = np.c_[XX.ravel(), YY.ravel()]
    lab3 = np.where(up(P), 0, np.where(low(P), 1, 2))
    vals3 = np.array([G3["T3"], G3["T2"], G3["T1"]])[lab3]
    s4 = P[:, 0] + P[:, 1] < 1.25
    lab4 = np.where(up(P), 0, np.where(low(P), 1, np.where(s4, 2, 3)))
    vals4 = np.array([G4["T3"], G4["T2"], G4["T11"], G4["T12"]])[lab4]
    vmax = max(max(G3.values()), max(G4.values()))
    for ax, vals, txt in ((axes[0, 0], vals3, G3), (axes[0, 1], vals4, G4)):
        ax.imshow(vals.reshape(XX.shape), origin="lower", extent=(0, 1, 0, 1), cmap="Greys", vmin=0, vmax=vmax * 1.15)
        ax.set_xticks([]); ax.set_yticks([])
    pos3 = {"T3": (0.2, 0.8), "T2": (0.5, 0.15), "T1": (0.75, 0.55)}
    pos4 = {"T3": (0.2, 0.8), "T2": (0.5, 0.15), "T11": (0.55, 0.5), "T12": (0.88, 0.72)}
    for k, (x, y) in pos3.items():
        axes[0, 0].text(x, y, "$%s_{%s}$\n%.3f" % (k[0], k[1:], G3[k]), ha="center", va="center", fontsize=9,
                        color="white" if G3[k] > 0.55 * vmax else "black")
    for k, (x, y) in pos4.items():
        axes[0, 1].text(x, y, "$%s_{%s}$\n%.3f" % (k[0], k[1:], G4[k]), ha="center", va="center", fontsize=8.5,
                        color="white" if G4[k] > 0.55 * vmax else "black")
    nb = 24
    H2, _, _ = np.histogram2d(th[:, 0], th[:, 1], bins=nb, range=[[0, 1], [0, 1]], weights=w)
    axes[0, 2].imshow(H2.T, origin="lower", extent=(0, 1, 0, 1), cmap="Greys")
    axes[0, 2].set_xticks([]); axes[0, 2].set_yticks([])
    axes[0, 0].set_title("K = 3 cells")
    axes[0, 1].set_title("$T_1$ split: K = 4 cells")
    axes[0, 2].set_title("a %d x %d grid" % (nb, nb))
    for j, l in enumerate("abc"):
        panel_label(axes[0, j], l, "lower right")
    return savefig(fig, CH, "figS31-1", out_dir)


def fig_S31_2(out_dir=None):
    """Draws from a DP on the real line (H = N(0,1)) and on the unit square (H uniform)."""
    rng = np.random.default_rng(2)
    fig = plt.figure(figsize=(9.0, 3.2))
    ax = fig.add_subplot(1, 2, 1)
    th, w = dp_draw(5.0, lambda n: rng.standard_normal(n), rng)
    keep = w > 1e-3
    ax.vlines(th[keep], 0, w[keep], color=BLUE, lw=1.3)
    ax.plot(th[keep], w[keep], "o", color=BLUE, ms=3.5)
    x = np.linspace(-3.5, 3.5, 300)
    ax.plot(x, stats.norm.pdf(x) * w.max() / stats.norm.pdf(0) * 0.9, color=RED, lw=1.5, label="base measure H (rescaled)")
    ax.set_xlabel(r"$\theta$"); ax.set_ylabel(r"weight $\pi_k$")
    ax.set_title(r"(a) $G\sim\mathrm{DP}(5,\ \mathcal{N}(0,1))$")
    ax.legend(loc="upper left", frameon=False, fontsize=8.5)
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    th2, w2 = dp_draw(5.0, lambda n: rng.random((n, 2)), rng)
    keep = w2 > 1e-3
    for (a, b), h in zip(th2[keep], w2[keep]):
        ax3.plot([a, a], [b, b], [0, h], color=BLUE, lw=1.2)
    ax3.scatter(th2[keep, 0], th2[keep, 1], w2[keep], color=BLUE, s=8)
    xx, yy = np.meshgrid([0, 1], [0, 1])
    ax3.plot_surface(xx, yy, np.zeros_like(xx, dtype=float), color=RED, alpha=0.12)
    ax3.set_title(r"(b) $H$ uniform on the unit square", fontsize=10)
    ax3.set_zlabel(r"$\pi_k$")
    ax3.view_init(elev=22, azim=-60)
    return savefig(fig, CH, "figS31-2", out_dir)


def fig_S31_3(out_dir=None):
    """Panel (b): stick-breaking weights pi_1..pi_30 for alpha = 1, 2, 5, 10 (two draws each)."""
    rng = np.random.default_rng(3)
    fig, axes = panel_grid(2, 2, size=(3.4, 2.1), sharex=True)
    for ax, a in zip(axes.ravel(), (1, 2, 5, 10)):
        for r, col, off in ((0, BLUE, -0.2), (1, ORANGE, 0.2)):
            pi, _ = stick_breaking(a, 30, rng)
            ax.bar(np.arange(1, 31) + off, pi, width=0.4, color=col)
        ax.set_title(r"$\alpha=%d$" % a)
        ax.set_xlim(0, 31)
    for ax in axes[1]:
        ax.set_xlabel("k")
    for ax in axes[:, 0]:
        ax.set_ylabel(r"$\pi_k$")
    return savefig(fig, CH, "figS31-3", out_dir)


def fig_S31_4(out_dir=None):
    """Samples from a DP mixture of 2-d Gaussians with an NIW base measure, alpha = 1, 2, N = 50, 500, 1000."""
    D = 2
    m0, k0, v0, S0 = np.zeros(D), 0.05, D + 5, np.eye(D)
    fig, axes = panel_grid(3, 2, size=(3.0, 2.7))
    for j, a in enumerate((1.0, 2.0)):
        rng = np.random.default_rng(40 + j)
        X, z, params = dpmm_sample(1000, a, m0, k0, v0, S0, rng)
        for i, n in enumerate((50, 500, 1000)):
            ax = axes[i, j]
            ax.plot(X[:n, 0], X[:n, 1], ".", ms=3, color=BLUE)
            for k in np.unique(z[:n]):
                _ellipse(ax, params[k][0], params[k][1], "k", nsd=1.0, lw=1.2)
            ax.set_title(r"$\alpha=%g$, N=%d, K=%d" % (a, n, len(np.unique(z[:n]))), fontsize=9.5)
            ax.set_xticks([]); ax.set_yticks([])
    return savefig(fig, CH, "figS31-4", out_dir)


def fig_S31_6(out_dir=None):
    """Collapsed Gibbs (Algorithm S31.1) on two data sets: last sample and posterior of K."""
    res = run_fig31_6_chains()
    A, B = cluster_data()
    fig, axes = panel_grid(2, 2, size=(3.6, 2.9))
    for j, (name, X) in enumerate((("A", A), ("B", B))):
        z = res["z_" + name]
        ax = axes[0, j]
        model = gibbs_prior(X)
        for k in np.unique(z):
            Xk = X[z == k]
            ax.plot(Xk[:, 0], Xk[:, 1], ".", ms=3.5, color=PALETTE[k % len(PALETTE)])
            if len(Xk) < 3:
                continue
            st = model.empty()
            for x in Xk:
                model.add(st, x)
            kn, vn, mn, Sn = model.post(st)
            _ellipse(ax, mn, Sn / (vn - X.shape[1] - 1), "k", nsd=2.0, lw=1.1)
        ax.set_xticks([]); ax.set_yticks([])
        ax.set_title("data set %s: one posterior sample (K=%d)" % (name, len(np.unique(z))), fontsize=9.5)
        ks = np.arange(1, 11)
        for key, col, off, lab in (("K_", BLUE, -0.2, "all clusters"), ("Kbig_", ORANGE, 0.2, "clusters with >= 3% of points")):
            Ks = res[key + name]
            freq = np.array([(Ks == k).mean() for k in ks])
            axes[1, j].bar(ks + off, freq, width=0.4, color=col, label=lab)
        axes[1, j].legend(frameon=False, fontsize=7.5, loc="upper left")
        axes[1, j].set_xticks(ks)
        axes[1, j].set_xlabel("number of clusters K")
        axes[1, j].set_ylabel("posterior frequency")
    for l, ax in zip("abcd", axes.ravel()):
        panel_label(ax, l, "upper right")
    return savefig(fig, CH, "figS31-6", out_dir)


def fig_S31_7(out_dir=None):
    """A CRP cluster matrix and an IBP feature matrix (rows = customers)."""
    rng = np.random.default_rng(7)
    N = 40
    z, counts = crp(N, 3.0, rng)
    Zc = np.zeros((N, len(counts)), dtype=int)
    Zc[np.arange(N), z] = 1
    Zi = ibp(N, 3.0, rng)
    fig, axes = panel_grid(1, 2, size=(3.4, 3.6))
    for ax, Z, t in ((axes[0, 0], Zc, "(a) CRP, alpha = 3: one table each"), (axes[0, 1], Zi, "(b) IBP, alpha = 3: a set of dishes each")):
        ax.imshow(Z, cmap="Greys", aspect="auto", interpolation="nearest", vmin=0, vmax=1.2)
        ax.set_xlabel("tables / dishes (K = %d)" % Z.shape[1]); ax.set_ylabel("customers")
        ax.set_title(t, fontsize=9.5)
    return savefig(fig, CH, "figS31-7", out_dir)


def fig_S31_8(out_dir=None):
    """A beta process on [0, 1] (stick-breaking, mass alpha = 2) and rows of the Bernoulli process it drives."""
    rng = np.random.default_rng(8)
    alpha = 2.0
    pi = beta_process_sticks(alpha, 200, rng)
    th = rng.random(200)
    fig, axes = panel_grid(1, 2, size=(3.8, 2.8))
    ax = axes[0, 0]
    o = np.argsort(th)
    ax.vlines(th, 0, pi, color=RED, lw=1.3)
    ax.step(np.r_[0, th[o], 1], np.r_[0, np.cumsum(pi[o]), pi.sum()], where="post", color="k", lw=1.2)
    ax.set_xlabel(r"$\theta$"); ax.set_title(r"(a) atoms $\pi_k$ (red) and $B(\theta)=G([0,\theta])$ (black)", fontsize=9)
    ax2 = axes[0, 1]
    R = 15
    for r in range(R):
        on = rng.random(200) < pi
        ax2.plot(th[on], np.full(on.sum(), r + 1), "s", ms=3.2, color="k")
    ax2.set_xlim(0, 1); ax2.set_ylim(0, R + 1)
    ax2.set_xlabel(r"$\theta$"); ax2.set_ylabel("draw")
    ax2.set_title("(b) Bernoulli process draws", fontsize=9)
    return savefig(fig, CH, "figS31-8", out_dir)


def fig_S31_9(out_dir=None):
    """Poisson construction of a CRM (gamma process with mass 3 and Gaussian base) and its normalisation."""
    rng = np.random.default_rng(9)
    alpha, eps = 3.0, 1e-4
    w = gamma_process(alpha, eps, rng)
    th = rng.standard_normal(len(w))
    fig, axes = panel_grid(1, 2, size=(3.9, 2.9))
    ax = axes[0, 0]
    ax.semilogy(th, w, ".", color=GREY, ms=2.5)
    big = w > 0.02
    ax.semilogy(th[big], w[big], "o", color=BLUE, ms=4)
    ax.set_xlabel(r"location $\theta$"); ax.set_ylabel("weight w (log scale)")
    ax.set_title("(a) Poisson points, intensity $H(\\theta)\\,\\alpha w^{-1}e^{-w}$\n(%d points with w > %g)" % (len(w), eps), fontsize=9)
    ax2 = axes[0, 1]
    Wtot = w.sum()
    ax2.vlines(th[big], 0, w[big] / Wtot, color=BLUE, lw=1.3)
    ax2.plot(th[big], w[big] / Wtot, "o", color=BLUE, ms=3.5)
    x = np.linspace(-3.5, 3.5, 200)
    ax2.plot(x, stats.norm.pdf(x) * (w[big] / Wtot).max() / stats.norm.pdf(0), color=RED, lw=1.3)
    ax2.set_xlabel(r"$\theta$")
    ax2.set_title("(b) $G/G(\\Theta)$, a draw from DP(3, N(0,1));\ntotal mass G($\\Theta$) = %.2f" % Wtot, fontsize=9)
    return savefig(fig, CH, "figS31-9", out_dir)


def fig_S31_10(out_dir=None):
    """A Brownian motion and a Cauchy process (1-stable) on [0, 1]."""
    rng = np.random.default_rng(10)
    n = 2000
    dt = 1.0 / n
    t = np.linspace(0, 1, n + 1)
    bm = np.r_[0, np.cumsum(rng.standard_normal(n) * np.sqrt(dt))] * 0.3
    cp = np.r_[0, np.cumsum(stats.cauchy.rvs(scale=dt, size=n, random_state=rng))] * 0.05
    fig, axes = panel_grid(1, 2, size=(3.6, 2.6))
    axes[0, 0].plot(t, bm, color=BLUE, lw=1)
    axes[0, 0].set_title("(a) Brownian motion (sd 0.3 per unit time)", fontsize=9.5)
    axes[0, 1].plot(t, cp, color=RED, lw=1)
    axes[0, 1].set_title("(b) Cauchy process (scale 0.05 per unit time)", fontsize=9.5)
    for ax in axes[0]:
        ax.set_xlabel("t")
    return savefig(fig, CH, "figS31-10", out_dir)


def fig_S31_11(out_dir=None):
    """Homogeneous Poisson, repulsive (Strauss) and clustered (Thomas) point patterns on the unit square."""
    rng = np.random.default_rng(11)
    P0 = rng.random((rng.poisson(70), 2))
    P1 = strauss_bd(kappa=180.0, gamma=0.0, R=0.07, n_steps=30000, rng=rng)
    P2 = thomas_process(kappa=10, mu=6.5, sigma=0.035, rng=rng)
    fig, axes = panel_grid(1, 3, size=(2.7, 2.8))
    for ax, P, t in zip(axes[0], (P0, P1, P2), ("(a) Poisson", "(b) Strauss (hard core)", "(c) Thomas cluster")):
        ax.plot(P[:, 0], P[:, 1], "o", ms=3.2, color=BLUE)
        d = np.sqrt(((P[:, None] - P[None]) ** 2).sum(-1)) + np.eye(len(P)) * 9
        ax.set_title("%s\nn = %d, mean NN dist %.3f" % (t, len(P), d.min(1).mean()), fontsize=9)
        ax.set_xlim(0, 1); ax.set_ylim(0, 1); ax.set_aspect("equal"); ax.set_xticks([]); ax.set_yticks([])
    return savefig(fig, CH, "figS31-11", out_dir)


def fig_S31_12(out_dir=None):
    """A self-exciting Hawkes process and a pair of mutually exciting ones (exponential kernels)."""
    rng = np.random.default_rng(12)
    T = 20.0
    ev = hawkes_simulate(0.3, 0.8, 1.0, T, rng)
    tg = np.linspace(0, T, 2000)
    fig, axes = panel_grid(1, 2, size=(4.0, 2.8))
    ax = axes[0, 0]
    ax.plot(tg, hawkes_intensity(tg, ev, 0.3, 0.8, 1.0), color=CYAN, lw=1.3)
    ax.plot(ev, np.zeros_like(ev), "o", color=MAGENTA, ms=4, mfc="white")
    ax.set_xlabel("t"); ax.set_ylabel(r"$\lambda(t\,|\,\mathcal{H}(t))$")
    ax.set_title("(a) self-exciting: %d events" % len(ev), fontsize=9.5)
    gam = np.array([0.25, 0.25])
    B = np.array([[0.0, 0.7], [0.7, 0.0]])
    ev2 = hawkes2_simulate(gam, B, 1.0, T, rng)
    ax2 = axes[0, 1]
    for i, (col, off) in enumerate(((CYAN, 0.0), (MAGENTA, -3.0))):
        lam = np.full_like(tg, gam[i])
        for j in range(2):
            for tk in ev2[j]:
                m = tg >= tk
                lam[m] += B[i, j] * np.exp(-(tg[m] - tk))
        ax2.plot(tg, lam + off, color=col, lw=1.3)
        ax2.plot(ev2[i], np.full(len(ev2[i]), off), "o", color=col, ms=4, mfc="white")
    ax2.set_yticks([])
    ax2.set_xlabel("t")
    ax2.set_title("(b) mutually exciting pair (%d and %d events)" % (len(ev2[0]), len(ev2[1])), fontsize=9.5)
    return savefig(fig, CH, "figS31-12", out_dir)


def fig_x31_1(out_dir=None):
    """Own figure: DP against Pitman-Yor, growth of K_N and table sizes."""
    rng = np.random.default_rng(101)
    N = 5000
    fig, axes = panel_grid(1, 2, size=(3.9, 3.0))
    ax = axes[0, 0]
    n = np.arange(1, N + 1)
    for (a, d, col) in ((10.0, 0.0, BLUE), (10.0, 0.25, ORANGE), (10.0, 0.5, RED)):
        ax.loglog(n, expected_tables(N, a, d), color=col, lw=1.6, label=r"$\alpha=%g,\ d=%g$" % (a, d))
        counts, path = crp_mulberry(N, a, d, 7)
        ax.loglog(n, path, color=col, lw=0.8, ls="--")
    ax.loglog(n, 10 * np.log(1 + n / 10), color="k", lw=0.8, ls=":", label=r"$\alpha\log(1+N/\alpha)$")
    ax.set_xlabel("customers N"); ax.set_ylabel("tables K")
    ax.legend(frameon=False, fontsize=8)
    ax.set_title("(a) expected (solid) and one draw (dashed)", fontsize=9.5)
    ax2 = axes[0, 1]
    for (a, d, col) in ((10.0, 0.0, BLUE), (10.0, 0.5, RED)):
        counts, _ = crp_mulberry(N, a, d, 7)
        s = np.sort(counts)[::-1]
        ax2.loglog(np.arange(1, len(s) + 1), s, ".", color=col, ms=3, label="d = %g (K = %d)" % (d, len(s)))
    ax2.set_xlabel("rank of the table"); ax2.set_ylabel("table size")
    ax2.legend(frameon=False, fontsize=8)
    ax2.set_title("(b) table sizes by rank, N = %d" % N, fontsize=9.5)
    return savefig(fig, CH, "fig31-x1", out_dir)


def fig_x31_2(out_dir=None):
    """Own figure: truncated mean-field VI (Algorithm S31.2) on data set A."""
    A, _ = cluster_data()
    rng = np.random.default_rng(22)
    r = dpmm_vi(A, 1.0, 20, 1.0, A.mean(0), 25.0, rng, n_iter=300)
    Epi = vi_expected_weights(r["g1"], r["g2"])
    fig, axes = panel_grid(1, 3, size=(2.9, 2.7))
    lab = r["phi"].argmax(1)
    for k in np.unique(lab):
        axes[0, 0].plot(A[lab == k, 0], A[lab == k, 1], ".", ms=3.5, color=PALETTE[k % len(PALETTE)])
    for t in np.where(Epi > 0.01)[0]:
        axes[0, 0].plot(*r["m"][t], "k+", ms=9, mew=1.8)
    axes[0, 0].set_xticks([]); axes[0, 0].set_yticks([])
    axes[0, 0].set_title("(a) VI, T = 20: hard labels", fontsize=9.5)
    axes[0, 1].bar(np.arange(1, 21), Epi, color=BLUE)
    axes[0, 1].set_xlabel("t"); axes[0, 1].set_title(r"(b) $\mathbb{E}_q[\pi_t]$", fontsize=9.5)
    axes[0, 2].plot(np.arange(1, len(r["elbo"]) + 1), r["elbo"], color=RED)
    axes[0, 2].set_xlabel("sweep"); axes[0, 2].set_title("(c) ELBO (never decreases)", fontsize=9.5)
    return savefig(fig, CH, "fig31-x2", out_dir)


def vi_expected_weights(g1, g2):
    Eb = g1 / (g1 + g2)
    rest = np.concatenate([[1.0], np.cumprod(1 - Eb)])
    return np.concatenate([Eb * rest[:-1], [rest[-1]]])


def fig_x31_3(out_dir=None):
    """Own figure: DP-means on data set A; K against lambda; the monotone objective."""
    A, B = cluster_data()
    fig, axes = panel_grid(1, 3, size=(2.9, 2.7))
    z, mu, objs = dp_means(A, 20.0)
    for k in range(len(mu)):
        axes[0, 0].plot(A[z == k, 0], A[z == k, 1], ".", ms=3.5, color=PALETTE[k % len(PALETTE)])
    axes[0, 0].plot(mu[:, 0], mu[:, 1], "k+", ms=9, mew=1.8)
    axes[0, 0].set_xticks([]); axes[0, 0].set_yticks([])
    axes[0, 0].set_title(r"(a) data set A, $\lambda=20$: K = %d" % len(mu), fontsize=9.5)
    lams = np.geomspace(0.5, 300, 40)
    for X, col, name in ((A, BLUE, "A"), (B, RED, "B")):
        Ks = [len(dp_means(X, l)[1]) for l in lams]
        axes[0, 1].semilogx(lams, Ks, "-o", ms=2.5, color=col, label="data set " + name)
    axes[0, 1].set_xlabel(r"penalty $\lambda$"); axes[0, 1].set_ylabel("K")
    axes[0, 1].legend(frameon=False, fontsize=8)
    axes[0, 1].set_title("(b) number of clusters", fontsize=9.5)
    axes[0, 2].plot(objs, "-o", ms=3, color=GREEN)
    axes[0, 2].set_xlabel("half-iteration"); axes[0, 2].set_title("(c) objective (S31.53), A", fontsize=9.5)
    return savefig(fig, CH, "fig31-x3", out_dir)


def fig_x31_4(out_dir=None):
    """Own figure: a DPP sample on a 20 x 20 grid against independent Bernoulli sampling with the same
    inclusion probabilities, and the pair correlation."""
    rng = np.random.default_rng(44)
    P, L = rbf_grid_L(20, 0.1, 2.0)
    K = dpp_inclusion_kernel(L)
    Y = dpp_sample(L, rng)
    Yi = np.where(rng.random(len(P)) < np.diag(K))[0]
    fig, axes = panel_grid(1, 3, size=(2.8, 2.8))
    for ax, S, t in ((axes[0, 0], Y, "(a) DPP"), (axes[0, 1], Yi, "(b) independent")):
        ax.plot(P[:, 0], P[:, 1], ".", color="0.85", ms=2)
        ax.plot(P[S, 0], P[S, 1], "o", color=BLUE, ms=4)
        ax.set_title("%s: %d points" % (t, len(S)), fontsize=9)
        ax.set_aspect("equal"); ax.set_xticks([]); ax.set_yticks([])
    i0 = 210
    d = np.sqrt(((P - P[i0]) ** 2).sum(1))
    g = (K[i0, i0] * np.diag(K) - K[i0] ** 2) / (K[i0, i0] * np.diag(K))
    o = np.argsort(d)[1:]
    axes[0, 2].plot(d[o], g[o], ".", color=RED, ms=3)
    axes[0, 2].axhline(1, color="k", lw=0.8, ls=":")
    axes[0, 2].set_xlabel("distance"); axes[0, 2].set_ylim(-0.05, 1.1)
    axes[0, 2].set_title(r"(c) $p(\{i,j\}\subseteq Y)/(K_{ii}K_{jj})$", fontsize=9)
    return savefig(fig, CH, "fig31-x4", out_dir)


def export_demo_data():
    """data/ch31-dpmeans.json: the two data sets of Figure S31.6 (in the order DP-means visits them)."""
    A, B = cluster_data()
    with open(os.path.join(DATA_OUT, "ch31-dpmeans.json"), "w") as f:
        json.dump({"A": A.tolist(), "B": B.tolist(),
                   "note": "Simulated stand-ins for the data of Murphy (2023), supplementary Figure 31.6."}, f, separators=(",", ":"))


FIGURES = {
    "S31.1": fig_S31_1, "S31.2": fig_S31_2, "S31.3": fig_S31_3, "S31.4": fig_S31_4, "S31.6": fig_S31_6,
    "S31.7": fig_S31_7, "S31.8": fig_S31_8, "S31.9": fig_S31_9, "S31.10": fig_S31_10, "S31.11": fig_S31_11,
    "S31.12": fig_S31_12, "x31.1": fig_x31_1, "x31.2": fig_x31_2, "x31.3": fig_x31_3, "x31.4": fig_x31_4,
}

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