"""Murphy (2023), Chapter 13: Sequential Monte Carlo (and Supplement 13).

Companion code for Chapter 13 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 543-571, and its supplement (pp. 149-155), written from
scratch with numpy and scipy, to be read next to the lecture notes (../ch13-sequential-monte-carlo.html).

Everything is implemented here: the resampling schemes (inverse cdf, multinomial, stratified, systematic),
sequential importance sampling and resampling (SIS, SISR, the bootstrap filter), guided filters with a
Laplace Gaussian proposal, Rao-Blackwellised filters for switching linear systems (mixture of Kalman
filters), the extended and unscented Kalman filters used as comparison, SMC samplers (adaptive likelihood
tempering, data tempering/IBIS, rare events, SMC-ABC), Hamiltonian Monte Carlo and the No-U-Turn sampler
used as baselines, and particle marginal Metropolis-Hastings.

Figures reproduced (book numbering; the supplement's figure is called S13.1)
* 13.1  bootstrap filter on a 2-d nonlinear tracking problem
* 13.2a weight degeneracy of SIS (the non-Markovian model (13.6)); 13.3a diversity under SISR and 13.3b
        path degeneracy (genealogy of the survivors)
* 13.4  the inverse-cdf construction of ancestors
* 13.5  effective sample size of the bootstrap and the guided filter (Poisson neural decoding)
* 13.6, 13.7  a mixture of Kalman filters (RBPF) against the bootstrap filter for a switching linear system
* 13.10, 13.11  likelihood tempering of a bimodal target, HMC and NUTS baselines
* 13.12 IBIS for a 1-d Gaussian
* S13.1 EKF, UKF and bootstrap filter on a pendulum with 40% outliers
Own figures (labelled as such in the notes): own13-1 offspring counts of the three resampling schemes,
own13-2 HMC and NUTS with the book's tiny step and with a tuned step, own13-3 rare-event SMC and SMC-ABC,
own13-4 particle marginal Metropolis-Hastings against exact-likelihood Metropolis-Hastings.

Skipped (nothing computed): Figure 13.2b (diagram of the bootstrap filter), Figures 13.8 and 13.9 (SLAM
graphical model and a sketch of loop closing), and Supplement Figures 13.2 and 13.3 (photographs and a
robot-localisation sketch from other sources).

Parameters the book does not give (its code is not part of the text) are my own choices, stated in the
captions: the spiral model constants, the neural-decoding model, the pendulum constants.

Data: none; everything is simulated (seeds fixed in the code). The uniform/normal generator DKRng is a
port of the one used by the interactive pages (functions dk_*), written with the same order of draws.
"""
import os
import sys

import numpy as np
from scipy import special, stats

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

CH = 13
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
os.makedirs(CACHE_DIR, exist_ok=True)
M32 = 0xFFFFFFFF


# ====================================================================== seeded generator shared with the pages
class DKRng:
    """Port of DK.rng (mulberry32 uniforms, Box-Muller normals) of the demonstration pages."""

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

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

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


# ====================================================================== resampling (Section 13.2.4)
def icdf(weights, u):
    """Ancestors by the inverse cdf (13.33): index a with sum_{j<a} W_j <= u < sum_{j<=a} W_j (0-based)."""
    cs = np.cumsum(weights)
    idx = np.searchsorted(cs, u, side="right")
    return np.clip(idx, 0, len(weights) - 1)


def resample_multinomial(W, rng):
    n = len(W)
    return icdf(W, np.sort(rng.uniform(size=n)))


def resample_stratified(W, rng):
    n = len(W)
    return icdf(W, (np.arange(n) + rng.uniform(size=n)) / n)


def resample_systematic(W, rng):
    n = len(W)
    return icdf(W, (np.arange(n) + rng.uniform()) / n)


def resample_residual(W, rng):
    """Residual resampling (not in the book; a further unbiased scheme)."""
    n = len(W)
    cnt = np.floor(n * W).astype(int)
    rest = n - cnt.sum()
    out = np.repeat(np.arange(n), cnt)
    if rest > 0:
        r = n * W - cnt
        out = np.concatenate([out, rng.choice(n, size=rest, p=r / r.sum())])
    return out


RESAMPLERS = {"multinomial": resample_multinomial, "stratified": resample_stratified,
              "systematic": resample_systematic, "residual": resample_residual}


def offspring(anc, n):
    """Number of times each particle was chosen as ancestor."""
    return np.bincount(anc, minlength=n)


def ess_normalised(W):
    """ESS (13.36) for normalised weights."""
    return 1.0 / np.sum(np.asarray(W) ** 2)


def ess_unnormalised(w):
    """ESS (13.37) for unnormalised weights."""
    w = np.asarray(w, float)
    return w.sum() ** 2 / np.sum(w ** 2)


def ess_logw(lw):
    """ESS from log weights (the function ESS_LW used in (13.78))."""
    lw = np.asarray(lw, float)
    return float(np.exp(2 * logsumexp(lw) - logsumexp(2 * lw)))


def normalise_logw(lw):
    lw = np.asarray(lw, float)
    return np.exp(lw - logsumexp(lw))


def lnorm(x, m, v):
    """log N(x | m, v) (v is the variance), elementwise."""
    return -0.5 * (np.log(2 * np.pi * v) + (x - m) ** 2 / v)


# ====================================================================== the non-Markovian model (13.6)
NM_PAR = dict(phi=0.9, q=10.0, beta=0.5, r=1.0)


def nm_simulate(T, par, rng):
    """z_t ~ N(phi z_{t-1}, q), y_t ~ N(sum_s beta^{t-s} z_s, r); z_1 ~ N(0, q/(1-phi^2))."""
    phi, q, beta, r = par["phi"], par["q"], par["beta"], par["r"]
    z = np.zeros(T)
    m = np.zeros(T)
    z[0] = rng.normal(0, np.sqrt(q / (1 - phi ** 2)))
    m[0] = z[0]
    for t in range(1, T):
        z[t] = phi * z[t - 1] + rng.normal(0, np.sqrt(q))
        m[t] = beta * m[t - 1] + z[t]
    return z, m + rng.normal(0, np.sqrt(r), size=T)


def nm_kalman_loglik(y, par):
    """Exact log p(y_{1:T}) by a Kalman filter on the augmented state (z_t, m_t), m_t = beta m_{t-1} + z_t."""
    phi, q, beta, r = par["phi"], par["q"], par["beta"], par["r"]
    A = np.array([[phi, 0.0], [phi, beta]])
    Qn = q * np.ones((2, 2))
    H = np.array([0.0, 1.0])
    P1 = q / (1 - phi ** 2)
    mu = np.zeros(2)
    P = P1 * np.ones((2, 2))
    ll = 0.0
    for t, yt in enumerate(y):
        if t > 0:
            mu = A @ mu
            P = A @ P @ A.T + Qn
        S = H @ P @ H + r
        ll += lnorm(yt, H @ mu, S)
        K = P @ H / S
        mu = mu + K * (yt - H @ mu)
        P = P - np.outer(K, K) * S
    return ll


def nm_smc(y, N, par, rng, resample="systematic", ess_frac=None, record=False):
    """Bootstrap-proposal SMC for the non-Markovian model.

    resample None: SIS (Algorithm 13.1); resample name with ess_frac None: SISR, resampling at every step
    (Algorithm 13.2); ess_frac a number: adaptive resampling when ESS < ess_frac N (Algorithm 13.3).
    Returns log Z-hat (13.26), and with record=True the weights, ancestors, particles and ESS per step.
    """
    phi, q, beta, r = par["phi"], par["q"], par["beta"], par["r"]
    T = len(y)
    z = rng.normal(0, np.sqrt(q / (1 - phi ** 2)), size=N)
    m = z.copy()
    lw = lnorm(y[0], m, r)                       # alpha_1 (proposal = prior), weights are w-tilde
    logZ = logsumexp(lw) - np.log(N)
    rec = dict(W=[normalise_logw(lw)], A=[np.arange(N)], ESS=[ess_logw(lw)], z=[z.copy()], resampled=[False])
    for t in range(1, T):
        # decide whether to resample the particles of step t-1 before extending them
        do = False
        if resample is not None:
            do = True if ess_frac is None else ess_logw(lw) < ess_frac * N
        if do:
            W = normalise_logw(lw)
            a = RESAMPLERS[resample](W, rng)
            z, m = z[a], m[a]
            lw_prev = np.full(N, -np.log(N))
        else:
            a = np.arange(N)
            lw_prev = lw - logsumexp(lw)
        z = phi * z + rng.normal(0, np.sqrt(q), size=N)
        m = beta * m + z
        alpha = lnorm(y[t], m, r)
        logZ += logsumexp(lw_prev + alpha)       # Z_t / Z_{t-1}, (13.28)
        lw = lw_prev + alpha                     # normalised previous weights times incremental weights
        rec["W"].append(normalise_logw(lw))
        rec["A"].append(a)
        rec["ESS"].append(ess_logw(lw))
        rec["z"].append(z.copy())
        rec["resampled"].append(do)
    return (logZ, rec) if record else logZ


def fig_13_2(out_dir=None):
    """Figure 13.2a: weight degeneracy of sequential importance sampling (T = 6, Ns = 5)."""
    T, N = 6, 5
    rng = np.random.default_rng(3)
    _, y = nm_simulate(T, NM_PAR, rng)
    _, rec = nm_smc(y, N, NM_PAR, np.random.default_rng(11), resample=None, record=True)
    fig, ax = plt.subplots(figsize=(4.6, 2.9))
    for t in range(T):
        for i in range(N):
            if t > 0:
                ax.annotate("", xy=(t + 1 - 0.12, i), xytext=(t + 0.12, i),
                            arrowprops=dict(arrowstyle="->", color=GREY, lw=0.7))
            ax.scatter([t + 1], [i], s=900 * rec["W"][t][i], color=RED, zorder=3, edgecolor="none")
    ax.set_xticks(range(1, T + 1))
    ax.set_yticks(range(N))
    ax.set_xlim(0.5, T + 0.5)
    ax.set_ylim(-0.7, N - 0.3)
    ax.set_xlabel("iteration $t$")
    ax.set_ylabel("particle index $i$")
    ax.set_title("SIS: weights $W_t^i$ (area proportional)", fontsize=9.5)
    savefig(fig, CH, "fig13-2")
    return rec


def genealogy_survivors(A):
    """Boolean arrays alive[t] of the particles at step t that are ancestors of some final particle."""
    T, N = len(A), len(A[0])
    alive = [None] * T
    alive[T - 1] = np.ones(N, bool)
    for t in range(T - 1, 0, -1):
        prev = np.zeros(N, bool)
        prev[np.unique(np.asarray(A[t])[alive[t]])] = True
        alive[t - 1] = prev
    return alive


def fig_13_3(out_dir=None):
    """Figure 13.3: (a) diversity of SMC (weights under resampling), (b) path degeneracy (genealogy)."""
    T, N = 7, 5
    rng = np.random.default_rng(3)
    _, y = nm_simulate(T, NM_PAR, rng)
    _, rec = nm_smc(y, N, NM_PAR, np.random.default_rng(5), resample="multinomial", record=True)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 2.9))
    ax = axes[0]
    for t in range(T):
        for i in range(N):
            if t > 0:
                a = rec["A"][t][i]
                ax.plot([t, t + 1], [a, i], color=GREY, lw=0.7, zorder=1)
            ax.scatter([t + 1], [i], s=700 * rec["W"][t][i], color=RED, zorder=3, edgecolor="none")
    ax.set_title("SMC: weights $W_t^i$ and parent links", fontsize=9.5)
    ax = axes[1]
    alive = genealogy_survivors(rec["A"])
    for t in range(T):
        for i in range(N):
            if alive[t][i]:
                if t > 0:
                    ax.plot([t, t + 1], [rec["A"][t][i], i], color=BLUE, lw=1.1, zorder=1)
                ax.scatter([t + 1], [i], s=26, color=BLUE, zorder=3)
            else:
                ax.scatter([t + 1], [i], s=10, color="#cccccc", zorder=2)
    ax.set_title("paths that survive to $t=%d$" % T, fontsize=9.5)
    for ax in axes:
        ax.set_xticks(range(1, T + 1))
        ax.set_yticks(range(N))
        ax.set_xlim(0.5, T + 0.5)
        ax.set_ylim(-0.7, N - 0.3)
        ax.set_xlabel("iteration $t$")
        ax.set_ylabel("particle index $i$")
    savefig(fig, CH, "fig13-3")
    return rec


def fig_13_4(out_dir=None):
    """Figure 13.4: the inverse-cdf construction of ancestors for three particles."""
    W = np.array([0.4, 0.35, 0.25])
    u = np.array([0.18, 0.46, 0.71])
    anc = icdf(W, u)
    cs = np.cumsum(W)
    fig, ax = plt.subplots(figsize=(4.2, 3.0))
    xs = np.arange(0, 4)
    cdf = np.concatenate([[0.0], cs])
    ax.step(np.arange(0, 4), np.concatenate([[0], cs]), where="post", color="k", lw=1.6)
    ax.plot([0, 0], [0, 0], color="k")
    for n in range(3):
        ax.plot([n + 1, n + 1], [cdf[n], cdf[n + 1]], color="k", lw=1.0)
    for j, uj in enumerate(u):
        n = anc[j]
        ax.axhline(uj, color=[RED, BLUE, GREEN][j], lw=1.0, ls="--")
        ax.plot([n, n + 1], [uj, uj], color=[RED, BLUE, GREEN][j], lw=2.4)
        ax.text(3.28, uj, "$U^{(%d)}$ $\\to$ ancestor %d" % (j + 1, n + 1), va="center", fontsize=8.5, color=[RED, BLUE, GREEN][j])
    ax.set_xlim(0, 3)
    ax.set_xticks([0.5, 1.5, 2.5])
    ax.set_xticklabels(["1", "2", "3"])
    ax.set_xlabel("particle $n$ (step height $W^n$)")
    ax.set_ylabel("empirical cdf")
    ax.set_ylim(0, 1.02)
    ax.set_title("$W=(0.40,0.35,0.25)$", fontsize=9.5)
    savefig(fig, CH, "fig13-4")
    return anc


def fig_own13_1(out_dir=None):
    """Own figure: offspring counts of multinomial, stratified and systematic resampling."""
    n = 20
    rng0 = np.random.default_rng(0)
    W = rng0.dirichlet(np.ones(n) * 0.7)
    R = 20000
    rng = np.random.default_rng(1)
    names = ["multinomial", "stratified", "systematic"]
    cols = [RED, BLUE, GREEN]
    counts = {k: np.zeros((R, n)) for k in names}
    for k in names:
        for r in range(R):
            counts[k][r] = offspring(RESAMPLERS[k](W, rng), n)
    fig, axes = plt.subplots(1, 3, figsize=(10.4, 2.8))
    ax = axes[0]
    ax.bar(np.arange(n), n * W, color="#dddddd", edgecolor="none", label="$NW^n$ (target)")
    ax.set_title("weights times $N$", fontsize=9.5)
    ax.set_xlabel("particle $n$")
    ax = axes[1]
    for j, k in enumerate(names):
        ax.plot(np.arange(n), counts[k].var(0), "o-", ms=3, color=cols[j], label=k, lw=0.9)
    ax.plot(np.arange(n), n * W * (1 - W), color="k", lw=0.9, ls="--", label="$NW^n(1-W^n)$")
    ax.set_title("variance of the offspring count", fontsize=9.5)
    ax.set_xlabel("particle $n$")
    ax.legend(fontsize=7.5)
    ax = axes[2]
    Ns = [10, 30, 100, 300, 1000]
    sd = {k: [] for k in names}
    for nn in Ns:
        r0 = np.random.default_rng(nn)
        Wn = np.exp(r0.normal(0, 1.0, nn))
        Wn /= Wn.sum()
        fn = r0.normal(size=nn)
        for k in names:
            ests = []
            for r in range(1500):
                perm = rng.permutation(nn)           # the order of particles is arbitrary in SMC
                a = RESAMPLERS[k](Wn[perm], rng)
                ests.append(fn[perm][a].mean())
            sd[k].append(np.std(ests))
    for j, k in enumerate(names):
        ax.loglog(Ns, sd[k], "o-", ms=3.5, color=cols[j], label=k, lw=1.2)
    ax.set_xlabel("number of particles $N$")
    ax.set_title("sd of the resampled estimate of $\\sum_n W^n f(z^n)$", fontsize=9)
    ax.legend(fontsize=7.5)
    savefig(fig, CH, "own13-1")
    return {k: (counts[k].mean(0), counts[k].var(0)) for k in names}, W, sd


FIGURES = {}


# ====================================================================== 2-d nonlinear tracking (13.4), Figure 13.1
SPIRAL = dict(delta=0.3, q=0.01, r=0.3)


def spiral_f(z, delta):
    return np.stack([z[..., 0] + delta * np.sin(z[..., 1]), z[..., 1] + delta * np.cos(z[..., 0])], -1)


def spiral_simulate(T, rng, par=SPIRAL, z0=(1.5, 0.2)):
    z = np.zeros((T, 2))
    z[0] = z0
    for t in range(1, T):
        z[t] = spiral_f(z[t - 1], par["delta"]) + rng.normal(0, np.sqrt(par["q"]), 2)
    return z, z + rng.normal(0, np.sqrt(par["r"]), (T, 2))


def bootstrap_filter_spiral(y, N, rng, par=SPIRAL, z0=(1.5, 0.2), resample="systematic"):
    """Bootstrap filter (Section 13.2.3.1): proposal = dynamics, weight = p(y_t | z_t); resample every step.
    The initial particles are spread around z0 (the model's initial condition)."""
    T = len(y)
    z = np.asarray(z0) + rng.normal(0, np.sqrt(par["q"]), (N, 2))
    means = np.zeros((T, 2))
    ess = np.zeros(T)
    logZ = 0.0
    for t in range(T):
        if t > 0:
            z = spiral_f(z, par["delta"]) + rng.normal(0, np.sqrt(par["q"]), (N, 2))
        lw = lnorm(y[t, 0], z[:, 0], par["r"]) + lnorm(y[t, 1], z[:, 1], par["r"])
        logZ += logsumexp(lw) - np.log(N)
        W = normalise_logw(lw)
        ess[t] = ess_normalised(W)
        means[t] = W @ z
        z = z[RESAMPLERS[resample](W, rng)]
    return means, ess, logZ


def fig_13_1(out_dir=None):
    """Figure 13.1: bootstrap filter on a 2-d nonlinear tracking problem (own constants)."""
    T = 100
    z, y = spiral_simulate(T, np.random.default_rng(4))
    means, ess, logZ = bootstrap_filter_spiral(y, 2000, np.random.default_rng(0))
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.2), sharex=True, sharey=True)
    ax = axes[0]
    ax.plot(z[:, 0], z[:, 1], color=BLUE, lw=1.3, label="state")
    ax.plot(y[:, 0], y[:, 1], "+", color=GREEN, ms=5, label="observations")
    ax.set_title("noisy observations from the hidden trajectory", fontsize=9)
    ax.legend(fontsize=7.5, loc="upper left")
    ax = axes[1]
    ax.plot(means[:, 0], means[:, 1], color=ORANGE, lw=1.3, label="filtered mean")
    ax.plot(y[:, 0], y[:, 1], "+", color=GREEN, ms=5)
    ax.set_title("bootstrap filter, 2000 particles", fontsize=9)
    ax.legend(fontsize=7.5, loc="upper left")
    for ax in axes:
        ax.set_aspect("equal")
        ax.set_xlabel("$z_1$")
    axes[0].set_ylabel("$z_2$")
    savefig(fig, CH, "fig13-1")
    return z, y, means, ess, logZ


# ====================================================================== neural decoding (13.3.3.1), Figure 13.5
def decoding_model(K, rng, delta=0.03, sigma=1.0):
    """Brownian hand model (13.49)-(13.50) for 3-d position and velocity, with K Poisson neurons (13.51)-(13.52)."""
    I3 = np.eye(3)
    F = np.block([[I3, delta * I3], [np.zeros((3, 3)), I3]])
    Q = sigma ** 2 * np.block([[delta ** 3 / 3 * I3, delta ** 2 / 2 * I3], [delta ** 2 / 2 * I3, delta * I3]])
    beta = rng.normal(size=(K, 6))
    beta /= np.linalg.norm(beta, axis=1, keepdims=True)         # tuning directions on the unit sphere
    alpha = rng.normal(2.5, 1.0, size=K)
    return dict(F=F, Q=Q, beta=beta, alpha=alpha)


def decoding_simulate(T, mod, rng):
    z = np.zeros((T, 6))
    L = np.linalg.cholesky(mod["Q"])
    for t in range(1, T):
        z[t] = mod["F"] @ z[t - 1] + L @ rng.normal(size=6)
    lam = np.exp(mod["alpha"] + z @ mod["beta"].T)
    return z, rng.poisson(lam)


def poisson_loglik(y, Z, mod):
    """log p(y_t | z) for each row of Z, with y_t a vector of K counts."""
    eta = mod["alpha"] + Z @ mod["beta"].T
    return (y * eta - np.exp(eta) - special.gammaln(y + 1)).sum(1)


def laplace_likelihood(y, mod, z_init):
    """Gaussian approximation (13.48) of z -> p(y_t | z): the maximiser z* (Newton-Raphson) and the
    precision -H* = sum_k lambda_k(z*) beta_k beta_k^T."""
    beta, alpha = mod["beta"], mod["alpha"]
    z = z_init.copy()
    for _ in range(50):
        lam = np.exp(alpha + beta @ z)
        g = beta.T @ (y - lam)
        P = (beta * lam[:, None]).T @ beta
        step = np.linalg.solve(P + 1e-9 * np.eye(6), g)
        z = z + step
        if np.max(np.abs(step)) < 1e-10:
            break
    lam = np.exp(alpha + beta @ z)
    return z, (beta * lam[:, None]).T @ beta


def decoding_filter(y, mod, N, rng, guided):
    """Bootstrap (guided=False) or Laplace-guided (guided=True) particle filter; returns ESS per step, log Z-hat,
    and the filtering means."""
    T = len(y)
    F, Q = mod["F"], mod["Q"]
    Linv = np.linalg.inv(Q)
    Lc = np.linalg.cholesky(Q)
    z = np.zeros((N, 6))
    ess = np.zeros(T)
    means = np.zeros((T, 6))
    logZ = 0.0
    zstar = np.zeros(6)
    for t in range(T):
        if t == 0:
            lw = poisson_loglik(y[0], z, mod)
        else:
            mu = z @ F.T
            if not guided:
                znew = mu + rng.normal(size=(N, 6)) @ Lc.T
                lw = poisson_loglik(y[t], znew, mod)
            else:
                zstar, PL = laplace_likelihood(y[t], mod, zstar)
                Sp = np.linalg.inv(Linv + PL)
                Lp = np.linalg.cholesky(Sp)
                mp = (mu @ Linv + PL @ zstar) @ Sp            # row-wise Sp (Linv mu + PL z*)
                znew = mp + rng.normal(size=(N, 6)) @ Lp.T
                d1 = znew - mu
                d2 = znew - mp
                lprior = -0.5 * np.einsum("ni,ij,nj->n", d1, Linv, d1)
                lprop = -0.5 * np.einsum("ni,ij,nj->n", d2, np.linalg.inv(Sp), d2)
                const = 0.5 * (np.linalg.slogdet(Sp)[1] - np.linalg.slogdet(Q)[1])
                lw = poisson_loglik(y[t], znew, mod) + lprior - lprop + const
            z = znew
        logZ += logsumexp(lw) - np.log(N)
        W = normalise_logw(lw)
        ess[t] = ess_normalised(W)
        means[t] = W @ z
        z = z[resample_systematic(W, rng)]
    return ess, logZ, means


def fig_13_5(out_dir=None):
    """Figure 13.5: ESS of the bootstrap and the guided filter for the Poisson neural-decoding model."""
    T, K, N = 25, 50, 1000
    mod = decoding_model(K, np.random.default_rng(2))
    zt, y = decoding_simulate(T, mod, np.random.default_rng(3))
    res = {}
    fig, ax = plt.subplots(figsize=(4.4, 3.0))
    for name, guided, col in (("bootstrap", False, RED), ("guided (Laplace)", True, BLUE)):
        ess_runs = []
        for rep in range(5):
            ess, lz, _ = decoding_filter(y, mod, N, np.random.default_rng(10 + rep), guided)
            ess_runs.append(ess)
            ax.plot(ess, color=col, lw=0.7, alpha=0.5)
        ax.plot(np.mean(ess_runs, 0), color=col, lw=2.0, label=name)
        res[name] = np.mean(ess_runs, 0)
    ax.set_xlabel("$t$")
    ax.set_ylabel("ESS")
    ax.set_ylim(0, N * 1.02)
    ax.legend(fontsize=8.5)
    savefig(fig, CH, "fig13-5")
    return res


# ====================================================================== maneuvering object, RBPF (13.4.2), Figures 13.6, 13.7
def maneuver_model():
    D = 0.1
    F = np.array([[1, D, 0, 0], [0, 1, 0, 0], [0, 0, 1, D], [0, 0, 0, 1]], float)
    b = np.array([[0, 0, 0, 0], [-1.225, -0.35, 1.225, 0.35], [1.225, 0.35, -1.225, -0.35]], float)
    A = np.array([[0.8, 0.1, 0.1], [0.1, 0.8, 0.1], [0.1, 0.1, 0.8]])
    return dict(F=F, b=b, A=A, Q=0.2 * np.eye(4), R=10 * np.diag([2.0, 1.0, 2.0, 1.0]), H=np.eye(4))


def maneuver_simulate(T, mod, rng):
    m = np.zeros(T, int)
    z = np.zeros((T, 4))
    m[0] = rng.integers(3)
    zprev = np.zeros(4)
    Lq = np.linalg.cholesky(mod["Q"])
    for t in range(T):
        if t > 0:
            m[t] = rng.choice(3, p=mod["A"][m[t - 1]])
        z[t] = mod["F"] @ zprev + mod["b"][m[t]] + Lq @ rng.normal(size=4)
        zprev = z[t]
    y = z + rng.normal(size=(T, 4)) * np.sqrt(np.diag(mod["R"]))
    return m, z, y


def mvn_logpdf_batch(x, mean, S):
    """log N(x | mean_n, S_n) for batches: x (4,), mean (n,4), S (n,4,4)."""
    d = x - mean
    L = np.linalg.cholesky(S)
    sol = np.linalg.solve(L, d[..., None])[..., 0]
    return -0.5 * (4 * np.log(2 * np.pi) + (sol ** 2).sum(-1)) - np.log(np.diagonal(L, axis1=-2, axis2=-1)).sum(-1)


def rbpf_maneuver(y, mod, N, rng, ess_frac=0.5):
    """Mixture-of-Kalman-filters RBPF (Algorithm 13.4 with the optimal discrete proposal of Section 13.4.1.1):
    the discrete state of each particle is sampled from q(k) proportional to A[m_{t-1}, k] L_{tk}; the weight
    increment is sum_k A[m_{t-1}, k] L_{tk}; each particle carries a Gaussian (mu, Sigma)."""
    T = len(y)
    F, b, A, Q, R = mod["F"], mod["b"], mod["A"], mod["Q"], mod["R"]
    mu = np.zeros((N, 4))
    P = np.tile(np.eye(4), (N, 1, 1))
    m = rng.integers(3, size=N)
    lw = np.zeros(N)
    out = dict(mean=np.zeros((T, 4)), pm=np.zeros((T, 3)), mu=[], P=[], W=[], ess=np.zeros(T), logZ=0.0, nres=0)
    for t in range(T):
        mu_pred = np.einsum("ij,nj->ni", F, mu)[:, None, :] + b[None]          # (N,3,4)
        P_pred = np.einsum("ij,njk,lk->nil", F, P, F) + Q                        # (N,4,4)
        S = P_pred + R
        L = np.stack([mvn_logpdf_batch(y[t], mu_pred[:, k], S) for k in range(3)], 1)    # log L_{tk}
        lq = np.log(A[m]) + L                                                    # log A L
        inc = logsumexp(lq, axis=1)
        wprev = normalise_logw(lw)
        out["logZ"] += logsumexp(np.log(wprev) + inc)
        lw = np.log(wprev) + inc
        cdf = np.cumsum(np.exp(lq - inc[:, None]), 1)
        k = np.minimum((rng.uniform(size=N)[:, None] > cdf).sum(1), 2)
        m = k
        Sk = S
        K = np.einsum("nij,njk->nik", P_pred, np.linalg.inv(Sk))
        mu_new = mu_pred[np.arange(N), k] + np.einsum("nij,nj->ni", K, y[t] - mu_pred[np.arange(N), k])
        P = P_pred - np.einsum("nij,njk->nik", K, P_pred)
        P = 0.5 * (P + P.transpose(0, 2, 1))
        mu = mu_new
        W = normalise_logw(lw)
        out["ess"][t] = ess_normalised(W)
        out["mean"][t] = W @ mu
        out["pm"][t] = np.bincount(m, weights=W, minlength=3)
        out["mu"].append(mu.copy())
        out["P"].append(P.copy())
        out["W"].append(W.copy())
        if out["ess"][t] < ess_frac * N:
            a = resample_systematic(W, rng)
            mu, P, m = mu[a], P[a], m[a]
            lw = np.zeros(N)
            out["nres"] += 1
    return out


def bootstrap_maneuver(y, mod, N, rng, ess_frac=0.5):
    """Bootstrap filter for the same model: sample (m_t, z_t) from the prior, weight by N(y_t | z_t, R)."""
    T = len(y)
    F, b, A, Q, R = mod["F"], mod["b"], mod["A"], mod["Q"], mod["R"]
    Lq = np.linalg.cholesky(Q)
    z = np.zeros((N, 4))
    m = rng.integers(3, size=N)
    lw = np.zeros(N)
    out = dict(mean=np.zeros((T, 4)), pm=np.zeros((T, 3)), ess=np.zeros(T), logZ=0.0)
    sd = np.sqrt(np.diag(R))
    for t in range(T):
        if t > 0:
            u = rng.uniform(size=N)
            cdf = np.cumsum(A[m], 1)
            m = np.minimum((u[:, None] > cdf).sum(1), 2)
        z = z @ F.T + b[m] + rng.normal(size=(N, 4)) @ Lq.T
        ll = lnorm(y[t][None], z, np.diag(R)[None]).sum(1)
        wprev = normalise_logw(lw)
        out["logZ"] += logsumexp(np.log(wprev) + ll)
        lw = np.log(wprev) + ll
        W = normalise_logw(lw)
        out["ess"][t] = ess_normalised(W)
        out["mean"][t] = W @ z
        out["pm"][t] = np.bincount(m, weights=W, minlength=3)
        if out["ess"][t] < ess_frac * N:
            a = resample_systematic(W, rng)
            z, m = z[a], m[a]
            lw = np.zeros(N)
    return out


def fig_13_6_7(out_dir=None):
    """Figures 13.6 and 13.7: RBPF against the bootstrap filter on the maneuvering-object model."""
    mod = maneuver_model()
    T = 100
    m, z, y = maneuver_simulate(T, mod, np.random.default_rng(7))
    N = 1000
    rb = rbpf_maneuver(y, mod, N, np.random.default_rng(1))
    bo = bootstrap_maneuver(y, mod, N, np.random.default_rng(2))
    mse = lambda est: float(np.mean(np.sum((est[:, [0, 2]] - z[:, [0, 2]]) ** 2, 1)))
    mse_rb, mse_bo = mse(rb["mean"]), mse(bo["mean"])
    cols = [RED, GREEN, BLUE]
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 3.2), sharex=True, sharey=True)
    for ax, title in zip(axes, ["data", "RBPF, 1000 particles, MSE %.2f" % mse_rb, "bootstrap filter, MSE %.2f" % mse_bo]):
        ax.set_title(title, fontsize=9)
        ax.set_xlabel("$x_1$")
    ax = axes[0]
    ax.plot(y[:, 0], y[:, 2], ".", color="k", ms=3)
    for k in range(3):
        sel = m == k
        ax.scatter(z[sel, 0], z[sel, 2], facecolor="none", edgecolor=cols[k], s=22, lw=1.0)
    for ax, est in ((axes[1], rb["mean"]), (axes[2], bo["mean"])):
        for k in range(3):
            sel = m == k
            ax.scatter(z[sel, 0], z[sel, 2], facecolor="none", edgecolor=cols[k], s=22, lw=0.8, alpha=0.7)
        ax.plot(est[:, 0], est[:, 2], "k-", lw=1.1)
    axes[0].set_ylabel("$x_2$")
    savefig(fig, CH, "fig13-6")

    # Figure 13.7: posterior marginals from the mixture-of-Gaussians representation
    fig, axes = plt.subplots(2, 2, figsize=(9.0, 5.2))
    for d, ax, name in ((0, axes[0, 0], "x location (dimension 0)"), (2, axes[0, 1], "y location (dimension 2)")):
        lo, hi = z[:, d].min() - 12, z[:, d].max() + 12
        grid = np.linspace(lo, hi, 220)
        dens = np.zeros((len(grid), T))
        for t in range(T):
            mu_d = rb["mu"][t][:, d]
            var_d = rb["P"][t][:, d, d]
            dens[:, t] = (rb["W"][t][None, :] * stats.norm.pdf(grid[:, None], mu_d[None, :], np.sqrt(var_d)[None, :])).sum(1)
        dens /= dens.max(0, keepdims=True)
        ax.imshow(dens, origin="lower", aspect="auto", extent=[0, T, lo, hi], cmap="gray_r")
        ax.plot(np.arange(T) + 0.5, z[:, d], color=RED, lw=1.0)
        ax.set_xlabel("$t$")
        ax.set_ylabel(name, fontsize=8.5)
        ax.set_title("posterior $p(x_{d,t}|y_{1:t})$ (columns scaled to 1), true path in red", fontsize=8.5)
    ax = axes[1, 0]
    ax.imshow(np.eye(3)[m].T, origin="lower", aspect="auto", cmap="gray_r", extent=[0, T, -0.5, 2.5], interpolation="nearest")
    ax.set_yticks([0, 1, 2])
    ax.set_xlabel("$t$")
    ax.set_title("true discrete state $m_t$", fontsize=9)
    ax = axes[1, 1]
    map_state = rb["pm"].argmax(1)
    err = float(np.mean(map_state != m))
    ax.imshow(rb["pm"].T, origin="lower", aspect="auto", cmap="gray_r", extent=[0, T, -0.5, 2.5], vmin=0, vmax=1, interpolation="nearest")
    ax.set_yticks([0, 1, 2])
    ax.set_xlabel("$t$")
    ax.set_title("posterior $p(m_t|y_{1:t})$, MAP error rate %.2f" % err, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig13-7")
    return dict(mse_rb=mse_rb, mse_bo=mse_bo, err=err, rb=rb, bo=bo, m=m, z=z, y=y)


# ====================================================================== tempered SMC sampler (13.6.2), Figures 13.10, 13.11
def bimodal_energy(th, c=5.0):
    """E(theta) = c (theta^2 - 1)^2 of (13.79) in one dimension."""
    return c * (th ** 2 - 1.0) ** 2


def bimodal_logprior(th):
    return -0.5 * th ** 2 - 0.5 * np.log(2 * np.pi)


def bimodal_Z(c=5.0, lam=1.0):
    """Z(lambda) = int N(theta | 0, 1) exp(-lambda E(theta)) d theta by quadrature."""
    xs = np.linspace(-8, 8, 160001)
    return float(np.trapz(np.exp(bimodal_logprior(xs) - lam * bimodal_energy(xs, c)), xs))


def find_delta(E, remaining, target):
    """Increment delta in (0, remaining] with ESS of exp(-delta E) equal to target (13.78); if even
    delta = remaining leaves the ESS above target, return remaining."""
    f = lambda d: ess_logw(-d * E) - target
    if f(remaining) >= 0:
        return remaining
    lo, hi = 0.0, remaining
    for _ in range(80):
        mid = 0.5 * (lo + hi)
        if f(mid) > 0:
            lo = mid
        else:
            hi = mid
    return 0.5 * (lo + hi)


def rwmh_moves(th, logpi, scale, K, rng):
    """K sweeps of random-walk Metropolis on every particle with proposal std `scale`."""
    lp = logpi(th)
    acc = 0.0
    for _ in range(K):
        prop = th + scale * rng.normal(size=th.shape)
        lpp = logpi(prop)
        ok = np.log(rng.uniform(size=th.shape)) < lpp - lp
        th = np.where(ok, prop, th)
        lp = np.where(ok, lpp, lp)
        acc += ok.mean() / K
    return th, acc


def hmc_vec(th, logpi_grad, eps, L, rng):
    """One HMC transition for every particle (vectorised leapfrog) with unit mass."""
    lp0, g = logpi_grad(th)
    p = rng.normal(size=th.shape)
    x, pp = th.copy(), p + 0.5 * eps * g
    for i in range(L):
        x = x + eps * pp
        lpx, gx = logpi_grad(x)
        pp = pp + (eps if i < L - 1 else 0.5 * eps) * gx
    ok = np.log(rng.uniform(size=th.shape)) < (lpx - 0.5 * pp ** 2) - (lp0 - 0.5 * p ** 2)
    return np.where(ok, x, th), ok.mean()


def tempered_smc(c, N, rng, ess_frac=0.5, kernel="rwmh", K=1, scale=None, hmc=(0.1, 10)):
    """SMC sampler with adaptive likelihood tempering (Algorithm 13.5) for the target (13.79).

    Returns dict with lambdas, the weighted particle sets after each reweighting, the final unweighted
    resample, the log-evidence estimate log Z-hat = sum_t log mean(exp(-delta_t E)), and the number of steps."""
    th = rng.normal(size=N)
    lam = 0.0
    lams, sets, logZ, acc_hist = [0.0], [(th.copy(), np.full(N, 1.0 / N))], 0.0, []
    while lam < 1.0 - 1e-15:
        E = bimodal_energy(th, c)
        d = find_delta(E, 1.0 - lam, ess_frac * N)
        lw = -d * E
        logZ += logsumexp(lw) - np.log(N)
        lam = min(1.0, lam + d)
        W = normalise_logw(lw)
        lams.append(lam)
        sets.append((th.copy(), W))
        th = th[resample_systematic(W, rng)]
        if lam < 1.0 - 1e-15 or True:
            logpi = lambda x, l=lam: bimodal_logprior(x) - l * bimodal_energy(x, c)
            if kernel == "rwmh":
                s = (scale if scale is not None else 2.38) * th.std()
                th, acc = rwmh_moves(th, logpi, s, K, rng)
            else:
                def lpg(x, l=lam):
                    return bimodal_logprior(x) - l * bimodal_energy(x, c), -x - l * 4 * c * x * (x ** 2 - 1.0)
                acc = 0.0
                for _ in range(K):
                    th, a = hmc_vec(th, lpg, hmc[0], hmc[1], rng)
                    acc += a / K
            acc_hist.append(acc)
    return dict(lams=np.array(lams), sets=sets, th=th, logZ=logZ, steps=len(lams) - 1, acc=acc_hist)


def hmc_chain(c, th0, n, eps, L, rng):
    """Plain HMC on the target (13.79) (scalar leapfrog), unit mass."""
    lg = lambda x: (bimodal_logprior(x) - bimodal_energy(x, c), -x - 4 * c * x * (x ** 2 - 1.0))
    out = np.zeros(n)
    x = th0
    nacc = 0
    for i in range(n):
        lp0, g = lg(x)
        p0 = rng.normal()
        xx, pp = x, p0 + 0.5 * eps * g
        for j in range(L):
            xx = xx + eps * pp
            lpx, gx = lg(xx)
            pp = pp + (eps if j < L - 1 else 0.5 * eps) * gx
        if np.log(rng.uniform()) < (lpx - 0.5 * pp ** 2) - (lp0 - 0.5 * p0 ** 2):
            x = xx
            nacc += 1
        out[i] = x
    return out, nacc / n


def nuts_chain(c, th0, n, eps, rng, max_depth=10):
    """No-U-Turn sampler (Hoffman and Gelman 2014, Algorithm 3: efficient NUTS with a slice variable),
    scalar parameter, fixed step size eps, unit mass."""
    def lg(x):
        return bimodal_logprior(x) - bimodal_energy(x, c), -x - 4 * c * x * (x ** 2 - 1.0)

    def leap(x, r, v):
        _, g = lg(x)
        r = r + 0.5 * v * eps * g
        x = x + v * eps * r
        lp, g = lg(x)
        r = r + 0.5 * v * eps * g
        return x, r, lp

    def build(x, r, logu, v, j):
        if j == 0:
            x1, r1, lp = leap(x, r, v)
            joint = lp - 0.5 * r1 ** 2
            return x1, r1, x1, r1, x1, int(logu <= joint), int(logu < 1000.0 + joint)
        xm, rm, xp, rp, x1, n1, s1 = build(x, r, logu, v, j - 1)
        if s1 == 1:
            if v == -1:
                xm, rm, _, _, x2, n2, s2 = build(xm, rm, logu, v, j - 1)
            else:
                _, _, xp, rp, x2, n2, s2 = build(xp, rp, logu, v, j - 1)
            if n1 + n2 > 0 and rng.uniform() < n2 / (n1 + n2):
                x1 = x2
            s1 = s2 * int((xp - xm) * rm >= 0) * int((xp - xm) * rp >= 0)
            n1 += n2
        return xm, rm, xp, rp, x1, n1, s1

    out = np.zeros(n)
    x = th0
    depth = np.zeros(n, int)
    for i in range(n):
        r0 = rng.normal()
        lp0, _ = lg(x)
        logu = lp0 - 0.5 * r0 ** 2 - rng.exponential(1.0)
        xm = xp = x
        rm = rp = r0
        j, nn, s, xnew = 0, 1, 1, x
        while s == 1 and j < max_depth:
            v = -1 if rng.uniform() < 0.5 else 1
            if v == -1:
                xm, rm, _, _, x1, n1, s1 = build(xm, rm, logu, v, j)
            else:
                _, _, xp, rp, x1, n1, s1 = build(xp, rp, logu, v, j)
            if s1 == 1 and rng.uniform() < min(1.0, n1 / nn):
                xnew = x1
            nn += n1
            s = s1 * int((xp - xm) * rm >= 0) * int((xp - xm) * rp >= 0)
            j += 1
        x = xnew
        out[i] = x
        depth[i] = j
    return out, depth


def fig_13_10_11(out_dir=None):
    """Figures 13.10 and 13.11: the bimodal target, tempered versions, HMC, NUTS and tempered SMC."""
    c = 5.0
    xs = np.linspace(-2.2, 2.2, 2000)
    Z1 = bimodal_Z(c)
    dens = lambda lam: np.exp(bimodal_logprior(xs) - lam * bimodal_energy(xs, c)) / bimodal_Z(c, lam)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 2.8), sharey=True)
    axes[0].plot(xs, dens(1.0), color=BLUE, lw=1.8)
    axes[0].set_title("bimodal target, $c=5$", fontsize=9.5)
    lams = np.linspace(0, 1, 5)
    for lam, col in zip(lams, plt.cm.viridis(np.linspace(0.0, 0.9, 5))):
        axes[1].plot(xs, dens(lam), color=col, lw=1.3, label="$\\lambda=%.2f$" % lam)
    axes[1].legend(fontsize=7.5, frameon=False)
    axes[1].set_title("tempered targets $\\propto\\mathcal{N}(\\theta|0,1)e^{-\\lambda E(\\theta)}$", fontsize=9.5)
    for ax in axes:
        ax.set_xlabel("$\\theta$")
    savefig(fig, CH, "fig13-10")

    ref = dens(1.0)
    hm, acc_h = hmc_chain(c, 1.0, 10000, 1e-4, 50, np.random.default_rng(0))
    nu, depth = nuts_chain(c, 1.0, 2000, 1e-4, np.random.default_rng(1))
    sm = tempered_smc(c, 10000, np.random.default_rng(2), ess_frac=0.95, kernel="hmc", K=1, hmc=(0.1, 10))
    fig, axes = plt.subplots(1, 4, figsize=(11.6, 2.7))
    for ax, smp, title in ((axes[0], hm, "(a) HMC, $\\epsilon=10^{-4}$, $L=50$"), (axes[1], nu, "(b) NUTS, $\\epsilon=10^{-4}$"),
                           (axes[2], sm["th"], "(c) tempered SMC, HMC kernel")):
        ax.hist(smp, bins=70, range=(-2.2, 2.2), density=True, color="#9db6e0", edgecolor="none")
        ax.plot(xs, ref, color=RED, lw=1.2)
        ax.set_title(title, fontsize=8.8)
        ax.set_xlabel("$\\theta$")
        ax.set_ylim(0, 4)
    axes[3].plot(sm["lams"], "o-", color=BLUE, ms=3.5, lw=1.2)
    axes[3].set_xlabel("$t$")
    axes[3].set_ylabel("tempering exponent $\\lambda_t$")
    axes[3].set_title("(d) schedule, $ESS_{min}=0.95N$: %d steps" % sm["steps"], fontsize=8.8)
    savefig(fig, CH, "fig13-11")
    return dict(Z1=Z1, hm=hm, nu=nu, sm=sm, depth=depth, acc_h=acc_h)


def fig_own13_2(out_dir=None):
    """Own figure: HMC and NUTS from theta_0 = 1 with the book's tiny step and with a tuned step."""
    c = 5.0
    xs = np.linspace(-2.2, 2.2, 1000)
    ref = np.exp(bimodal_logprior(xs) - bimodal_energy(xs, c)) / bimodal_Z(c)
    rows = {}
    hm, _ = hmc_chain(c, 1.0, 20000, 0.1, 25, np.random.default_rng(5))
    nu, dep = nuts_chain(c, 1.0, 5000, 0.1, np.random.default_rng(6))
    rows["HMC, $\\epsilon=0.1$, $L=25$"] = hm
    rows["NUTS, $\\epsilon=0.1$"] = nu
    fig, axes = plt.subplots(2, 2, figsize=(8.4, 4.4), gridspec_kw=dict(width_ratios=[1.6, 1]))
    for r, (name, smp) in enumerate(rows.items()):
        axes[r, 0].plot(smp[:2000] if r == 0 else smp[:1500], lw=0.5, color=BLUE)
        axes[r, 0].set_title(name + ": trace", fontsize=9)
        axes[r, 0].set_ylabel("$\\theta$")
        axes[r, 1].hist(smp, bins=60, range=(-2.2, 2.2), density=True, color="#9db6e0", edgecolor="none")
        axes[r, 1].plot(xs, ref, color=RED, lw=1.1)
        axes[r, 1].set_title("fraction with $\\theta>0$: %.2f" % np.mean(smp > 0), fontsize=9)
    axes[1, 0].set_xlabel("iteration")
    axes[1, 1].set_xlabel("$\\theta$")
    fig.tight_layout()
    savefig(fig, CH, "own13-2")
    return dict(hm=hm, nu=nu)


# ====================================================================== IBIS (13.6.3), Figure 13.12
def ibis_gauss(y, N, rng, ess_frac=0.5, K=5, mu_prior_sd=1.0):
    """Iterated batch importance sampling (data tempering) for y_t ~ N(mu, sigma^2), prior N(mu|0, sd^2) Ga(sigma|1,1).

    Particles live in phi = (mu, log sigma). When the ESS of the weights drops below ess_frac N, the
    particles are resampled and moved by K random-walk Metropolis steps (proposal covariance
    (2.38^2/2) times the empirical covariance) that leave the posterior given all data so far invariant."""
    T = len(y)

    def logprior(ph):
        mu, ls = ph[:, 0], ph[:, 1]
        return stats.norm.logpdf(mu, 0, mu_prior_sd) + (-np.exp(ls) + ls)       # Ga(1,1) with Jacobian of log sigma

    def loglik(ph, ys):
        mu, sg = ph[:, 0], np.exp(ph[:, 1])
        return (stats.norm.logpdf(np.asarray(ys)[:, None], mu[None], sg[None])).sum(0)

    ph = np.stack([rng.normal(0, mu_prior_sd, N), np.log(rng.gamma(1.0, 1.0, N))], 1)
    lw = np.zeros(N)
    ess = np.zeros(T)
    snaps = {}
    nmove = 0
    logZ = 0.0
    for t in range(T):
        inc = stats.norm.logpdf(y[t], ph[:, 0], np.exp(ph[:, 1]))
        logZ += logsumexp(lw - logsumexp(lw) + inc)
        lw = lw + inc
        W = normalise_logw(lw)
        ess[t] = ess_normalised(W)
        snaps[t] = (ph.copy(), W.copy())
        if ess[t] < ess_frac * N:
            a = resample_systematic(W, rng)
            ph = ph[a]
            lw = np.zeros(N)
            cov = np.cov(ph.T)
            Lc = np.linalg.cholesky(2.38 ** 2 / 2 * cov + 1e-12 * np.eye(2))
            lp = logprior(ph) + loglik(ph, y[:t + 1])
            for _ in range(K):
                prop = ph + rng.normal(size=ph.shape) @ Lc.T
                lpp = logprior(prop) + loglik(prop, y[:t + 1])
                ok = np.log(rng.uniform(size=N)) < lpp - lp
                ph = np.where(ok[:, None], prop, ph)
                lp = np.where(ok, lpp, lp)
            nmove += 1
    return dict(ess=ess, snaps=snaps, nmove=nmove, logZ=logZ, ph=ph, lw=lw)


def fig_13_12(out_dir=None):
    """Figure 13.12: IBIS for 30 observations from N(3.14, 1)."""
    T = 30
    y = np.random.default_rng(5).normal(3.14, 1.0, T)
    res = ibis_gauss(y, 1000, np.random.default_rng(1))
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 2.8), gridspec_kw=dict(width_ratios=[1, 1, 1.15]))
    for ax, j, name, rng_ in ((axes[0], 0, "$\\mu$", (-2, 5)), (axes[1], 1, "$\\sigma$", (0, 3.5))):
        for t, col in ((1, BLUE), (29, ORANGE)):
            ph, W = res["snaps"][t]
            v = ph[:, j] if j == 0 else np.exp(ph[:, 1])
            ax.hist(v, bins=40, range=rng_, weights=W, density=True, color=col, alpha=0.55, label="t=%d" % t)
        ax.set_xlabel(name)
        ax.legend(fontsize=8, frameon=False)
    axes[0].set_title("posterior after $t=1$ and $t=29$ (0-based)", fontsize=8.6)
    ax = axes[2]
    ax.plot(res["ess"], color=BLUE, lw=1.3)
    ax.axhline(500, color=GREY, lw=1.0)
    ax.set_xlabel("$t$")
    ax.set_ylabel("ESS")
    ax.set_title("ESS (1000 particles), moves at %d steps" % res["nmove"], fontsize=8.6)
    savefig(fig, CH, "fig13-12")
    return res, y


# ====================================================================== pendulum with outliers (Supplement 13.1.1), Figure S13.1
PEND = dict(dt=0.01, g=9.81, qw=1.0, r_in=0.1 ** 2, p_out=0.4, lim=2.0, T=300)


def pendulum_simulate(rng, par=PEND, th0=1.2):
    dt, g, qw, T = par["dt"], par["g"], par["qw"], par["T"]
    s = np.zeros((T, 2))
    s[0] = [th0, 0.0]
    for t in range(1, T):
        th, w = s[t - 1]
        s[t] = [th + dt * w, w - dt * g * np.sin(th) + np.sqrt(dt * qw) * rng.normal()]
    out = rng.uniform(size=T) < par["p_out"]
    y = s[:, 0] + np.sqrt(par["r_in"]) * rng.normal(size=T)
    y[out] = rng.uniform(-par["lim"], par["lim"], out.sum())
    return s, y, out


def _pend_step(s, par):
    return np.stack([s[..., 0] + par["dt"] * s[..., 1], s[..., 1] - par["dt"] * par["g"] * np.sin(s[..., 0])], -1)


def pend_ekf(y, par=PEND):
    dt, g = par["dt"], par["g"]
    Q = np.array([[0, 0], [0, dt * par["qw"]]])
    m = np.array([1.0, 0.0])
    P = np.diag([0.5 ** 2, 1.0])
    est = np.zeros((len(y), 2))
    for t in range(len(y)):
        if t > 0:
            F = np.array([[1, dt], [-dt * g * np.cos(m[0]), 1]])
            m = _pend_step(m, par)
            P = F @ P @ F.T + Q
        S = P[0, 0] + par["r_in"]
        K = P[:, 0] / S
        m = m + K * (y[t] - m[0])
        P = P - np.outer(K, K) * S
        est[t] = m
    return est


def pend_ukf(y, par=PEND, alpha=1.0, kappa=0.0, beta=2.0):
    n = 2
    lam = alpha ** 2 * (n + kappa) - n
    wm = np.full(2 * n + 1, 1 / (2 * (n + lam)))
    wc = wm.copy()
    wm[0] = lam / (n + lam)
    wc[0] = lam / (n + lam) + 1 - alpha ** 2 + beta
    Q = np.array([[0, 0], [0, par["dt"] * par["qw"]]])
    m = np.array([1.0, 0.0])
    P = np.diag([0.5 ** 2, 1.0])
    est = np.zeros((len(y), 2))
    for t in range(len(y)):
        if t > 0:
            L = np.linalg.cholesky((n + lam) * P + 1e-12 * np.eye(2))
            X = np.vstack([m, m + L.T, m - L.T])
            Xp = _pend_step(X, par)
            m = wm @ Xp
            d = Xp - m
            P = (wc[:, None, None] * np.einsum("ni,nj->nij", d, d)).sum(0) + Q
        L = np.linalg.cholesky((n + lam) * P + 1e-12 * np.eye(2))
        X = np.vstack([m, m + L.T, m - L.T])
        Y = X[:, 0]                                            # the observation function is linear
        ym = wm @ Y
        S = (wc * (Y - ym) ** 2).sum() + par["r_in"]
        Cxy = (wc[:, None] * (X - m) * (Y - ym)[:, None]).sum(0)
        K = Cxy / S
        m = m + K * (y[t] - ym)
        P = P - np.outer(K, K) * S
        est[t] = m
    return est


def pend_pf(y, N, rng, par=PEND):
    """Bootstrap filter with the true mixture likelihood (inlier Gaussian plus uniform outliers)."""
    dt = par["dt"]
    s = np.stack([1.0 + 0.5 * rng.normal(size=N), rng.normal(size=N)], 1)
    est = np.zeros((len(y), 2))
    for t in range(len(y)):
        if t > 0:
            s = _pend_step(s, par)
            s[:, 1] += np.sqrt(dt * par["qw"]) * rng.normal(size=N)
        lik = (1 - par["p_out"]) * stats.norm.pdf(y[t], s[:, 0], np.sqrt(par["r_in"])) + par["p_out"] / (2 * par["lim"])
        W = lik / lik.sum()
        est[t] = W @ s
        s = s[resample_systematic(W, rng)]
    return est


def fig_S13_1(out_dir=None):
    """Supplement Figure 13.1: EKF, UKF and bootstrap filter on the pendulum with 40% outliers (own constants)."""
    s, y, out = pendulum_simulate(np.random.default_rng(3))
    ts = np.arange(len(y)) * PEND["dt"]
    ests = [("extended Kalman filter", pend_ekf(y)), ("unscented Kalman filter", pend_ukf(y)),
            ("bootstrap filter (500 particles)", pend_pf(y, 500, np.random.default_rng(0)))]
    fig, axes = plt.subplots(1, 3, figsize=(10.8, 3.0), sharey=True)
    rm = []
    for ax, (name, est), col in zip(axes, ests, [RED, PURPLE, BLUE]):
        ax.plot(ts[~out], y[~out], ".", color="#bbbbbb", ms=3)
        ax.plot(ts[out], y[out], ".", color=RED, ms=3.5, alpha=0.6)
        ax.plot(ts, s[:, 0], "k-", lw=1.0, label="true angle")
        ax.plot(ts, est[:, 0], color=col if col != RED else ORANGE, lw=1.6, label="estimate")
        rmse = float(np.sqrt(np.mean((est[:, 0] - s[:, 0]) ** 2)))
        rm.append(rmse)
        ax.set_title("%s, rmse %.2f" % (name, rmse), fontsize=8.8)
        ax.set_xlabel("time")
        ax.set_ylim(-2.3, 2.3)
    axes[0].set_ylabel("angle")
    axes[0].legend(fontsize=7.5, loc="lower left")
    savefig(fig, CH, "figS13-1")
    return dict(rmse=rm, out=out)


# ====================================================================== particle MCMC (Supplement 13.2) and an own figure
LG = dict(q=1.0, r=1.0)          # AR(1) latent state z_t = phi z_{t-1} + N(0, q), y_t = z_t + N(0, r)


def lg_simulate(T, phi, rng, par=LG):
    z = np.zeros(T)
    z[0] = rng.normal(0, np.sqrt(par["q"] / (1 - phi ** 2)))
    for t in range(1, T):
        z[t] = phi * z[t - 1] + rng.normal(0, np.sqrt(par["q"]))
    return z, z + rng.normal(0, np.sqrt(par["r"]), T)


def lg_loglik_exact(y, phi, par=LG):
    """Kalman-filter log p(y_{1:T} | phi), vectorised over an array of phi."""
    phi = np.atleast_1d(np.asarray(phi, float))
    q, r = par["q"], par["r"]
    m = np.zeros_like(phi)
    P = q / (1 - phi ** 2)
    ll = np.zeros_like(phi)
    for t, yt in enumerate(y):
        if t > 0:
            m = phi * m
            P = phi ** 2 * P + q
        S = P + r
        ll += lnorm(yt, m, S)
        K = P / S
        m = m + K * (yt - m)
        P = (1 - K) * P
    return ll


def lg_loglik_pf(y, phi, N, rng, par=LG):
    """Bootstrap-filter estimate log Z-hat(phi) (13.26) of log p(y_{1:T} | phi); exp of it is unbiased."""
    q, r = par["q"], par["r"]
    z = rng.normal(0, np.sqrt(q / (1 - phi ** 2)), N)
    logZ = 0.0
    for t, yt in enumerate(y):
        if t > 0:
            z = phi * z + rng.normal(0, np.sqrt(q), N)
        lw = lnorm(yt, z, r)
        mx = lw.max()
        w = np.exp(lw - mx)
        logZ += mx + np.log(w.mean())
        z = z[resample_systematic(w / w.sum(), rng)]
    return logZ


def pmmh(y, N, n_iter, rng, step=0.12, phi0=0.5, exact=False):
    """Particle marginal Metropolis-Hastings (Algorithm S13.1) for phi with a U(-0.98, 0.98) prior; with
    exact=True the exact Kalman likelihood replaces the SMC estimate (ordinary Metropolis-Hastings)."""
    ll = (lambda p: lg_loglik_exact(y, p)[0]) if exact else (lambda p: lg_loglik_pf(y, p, N, rng))
    phi, cur = phi0, ll(phi0)
    chain = np.zeros(n_iter)
    nacc = 0
    for j in range(n_iter):
        prop = phi + step * rng.normal()
        if abs(prop) < 0.98:
            lp = ll(prop)
            if np.log(rng.uniform()) < lp - cur:
                phi, cur = prop, lp
                nacc += 1
        chain[j] = phi
    return chain, nacc / n_iter


def fig_own13_4(out_dir=None):
    """Own figure: PMMH with 100 and 10 particles against Metropolis-Hastings with the exact likelihood."""
    T = 40
    z, y = lg_simulate(T, 0.8, np.random.default_rng(1))
    grid = np.linspace(-0.97, 0.97, 600)
    post = np.exp(lg_loglik_exact(y, grid) - lg_loglik_exact(y, grid).max())
    post /= np.trapz(post, grid)
    runs = {}
    for N in (100, 10):
        runs[N] = pmmh(y, N, 3000, np.random.default_rng(N), phi0=0.5)
    sd_ll = {}
    for N in (10, 100, 1000):
        v = [lg_loglik_pf(y, 0.8, N, np.random.default_rng(100 + i)) for i in range(200)]
        sd_ll[N] = float(np.std(v))
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 2.8))
    ax = axes[0]
    for N, col in ((100, BLUE), (10, ORANGE)):
        ax.hist(runs[N][0][300:], bins=40, range=(0, 1), density=True, histtype="stepfilled", alpha=0.45, color=col,
                label="PMMH, $N=%d$ (acc. %.2f)" % (N, runs[N][1]))
    ax.plot(grid, post, color=RED, lw=1.4, label="exact likelihood")
    ax.set_xlim(0, 1)
    ax.set_xlabel("$\\phi$")
    ax.legend(fontsize=7.2, frameon=False)
    ax.set_title("posterior of the AR coefficient", fontsize=9)
    ax = axes[1]
    ax.plot(runs[100][0][:1500], lw=0.5, color=BLUE, label="$N=100$")
    ax.plot(runs[10][0][:1500], lw=0.5, color=ORANGE, label="$N=10$")
    ax.set_xlabel("iteration")
    ax.set_ylabel("$\\phi$")
    ax.legend(fontsize=7.5, frameon=False, ncol=2)
    ax.set_title("traces: noisy likelihood, sticky chain", fontsize=9)
    ax = axes[2]
    Ns = sorted(sd_ll)
    ax.loglog(Ns, [sd_ll[n] for n in Ns], "o-", color=PURPLE)
    ax.set_xlabel("particles $N$")
    ax.set_ylabel("sd of $\\log\\hat Z$")
    ax.set_title("noise of $\\log\\hat Z$ at $\\phi=0.8$", fontsize=9)
    savefig(fig, CH, "own13-4")
    return dict(runs=runs, sd_ll=sd_ll, grid=grid, post=post)


# ====================================================================== rare events (13.6.4) and SMC-ABC (13.6.5)
def rare_event_smc(lam_star, N, rng, alpha=0.5, K=10):
    """Adaptive-threshold SMC (Section 13.6.4) for P(theta > lam_star), theta ~ N(0,1): at each stage the
    next threshold is the (1-alpha) quantile of the current population (or lam_star once it is exceeded), the
    particles above it are resampled and moved by random-walk Metropolis steps inside the constraint."""
    th = rng.normal(size=N)
    logZ = 0.0
    lams = []
    while True:
        lam = np.quantile(th, 1 - alpha)
        if lam >= lam_star:
            lam = lam_star
        keep = th >= lam
        logZ += np.log(keep.mean())
        lams.append(lam)
        if lam >= lam_star:
            th = th[keep]
            th = th[rng.integers(0, len(th), N)]
            break
        th = th[keep][rng.integers(0, keep.sum(), N)]
        s = 1.0 * th.std()
        for _ in range(K):
            prop = th + s * rng.normal(size=N)
            ok = (prop >= lam) & (np.log(rng.uniform(size=N)) < -0.5 * prop ** 2 + 0.5 * th ** 2)
            th = np.where(ok, prop, th)
    return logZ, np.array(lams), th


def abc_smc(ybar_obs, n, N, rng, eps_final=0.02, alpha=0.5, K=3, prior_sd=3.0, tau=None):
    """SMC-ABC (Section 13.6.5) for y_i ~ N(mu, 1), i = 1..n, summary statistic = sample mean, prior N(0, prior_sd^2).
    The target at stage t is pi_0(mu) p(s | mu) 1[|s - s*| < eps_t] with s | mu ~ N(mu, 1/n) simulated."""
    th = rng.normal(0, prior_sd, N)
    s = th + rng.normal(0, 1 / np.sqrt(n), N)
    d = np.abs(s - ybar_obs)
    eps = np.inf
    pops = []
    while eps > eps_final:
        eps_new = max(eps_final, np.quantile(d, alpha)) if np.isfinite(eps) else np.quantile(d, alpha)
        keep = d < eps_new
        idx = np.flatnonzero(keep)
        pick = idx[rng.integers(0, len(idx), N)]
        th, s, d = th[pick], s[pick], d[pick]
        eps = eps_new
        tau_t = th.std() if tau is None else tau
        for _ in range(K):
            prop = th + tau_t * rng.normal(size=N)
            sp = prop + rng.normal(0, 1 / np.sqrt(n), N)
            dp = np.abs(sp - ybar_obs)
            ok = (dp < eps) & (np.log(rng.uniform(size=N)) < (-0.5 * prop ** 2 + 0.5 * th ** 2) / prior_sd ** 2)
            th = np.where(ok, prop, th)
            s = np.where(ok, sp, s)
            d = np.where(ok, dp, d)
        pops.append((eps, th.copy()))
    return pops


def abc_exact_posterior(ybar_obs, n, eps, prior_sd=3.0):
    """Density function of the eps-ABC posterior: pi_0(mu)[Phi((s*+eps-mu) sqrt n) - Phi((s*-eps-mu) sqrt n)]
    on a grid (eps = 0 gives the exact Gaussian posterior given the sufficient statistic)."""
    xs = np.linspace(-3, 4, 4001)
    sq = np.sqrt(n)
    if eps > 0:
        lik = stats.norm.cdf((ybar_obs + eps - xs) * sq) - stats.norm.cdf((ybar_obs - eps - xs) * sq)
    else:
        lik = stats.norm.pdf((ybar_obs - xs) * sq)
    p = stats.norm.pdf(xs, 0, prior_sd) * lik
    return xs, p / np.trapz(p, xs)


def fig_own13_3(out_dir=None):
    """Own figure: (a,b) rare-event SMC for P(N(0,1) > 4), (c) SMC-ABC for a Gaussian mean."""
    lam_star = 4.0
    exact = stats.norm.sf(lam_star)
    logZs = []
    for i in range(100):
        lz, lams, th = rare_event_smc(lam_star, 1000, np.random.default_rng(i))
        logZs.append(lz)
    logZs = np.array(logZs)
    lz0, lams0, th0 = rare_event_smc(lam_star, 1000, np.random.default_rng(0))
    crude = np.array([np.mean(np.random.default_rng(1000 + i).normal(size=1000 * len(lams0) * 11) > lam_star) for i in range(100)])
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 2.9))
    ax = axes[0]
    ax.plot(lams0, "o-", color=BLUE, ms=3.5)
    ax.axhline(lam_star, color=GREY, lw=0.9, ls="--")
    ax.set_xlabel("stage $t$")
    ax.set_ylabel("threshold $\\lambda_t$")
    ax.set_title("adaptive thresholds ($\\alpha=0.5$, %d stages)" % len(lams0), fontsize=9)
    ax = axes[1]
    ax.boxplot([np.exp(logZs) / exact], positions=[1], widths=0.5, showfliers=True)
    ax.boxplot([crude / exact], positions=[2], widths=0.5)
    ax.axhline(1.0, color=RED, lw=1.0)
    ax.set_xticks([1, 2])
    ax.set_xticklabels(["SMC", "crude MC\n(same draws)"], fontsize=8.5)
    ax.set_ylim(0, 3.0)
    ax.set_ylabel("estimate / exact")
    ax.set_title("$P(\\theta>4)=3.17\\times10^{-5}$, 100 runs", fontsize=9)
    ax = axes[2]
    n, ybar = 20, 1.0
    pops = abc_smc(ybar, n, 3000, np.random.default_rng(7))
    cols = plt.cm.viridis(np.linspace(0, 0.9, len(pops)))
    xs0, p0 = abc_exact_posterior(ybar, n, 0.0)
    for (eps, th), col in zip(pops[::max(1, len(pops) // 4)] + [pops[-1]], plt.cm.viridis(np.linspace(0, 0.9, len(pops[::max(1, len(pops) // 4)]) + 1))):
        ax.hist(th, bins=40, range=(-1, 3), density=True, histtype="step", color=col, lw=1.0, label="$\\epsilon=%.2f$" % eps)
    ax.plot(xs0, p0, color=RED, lw=1.3, label="exact")
    ax.set_xlim(-1, 3)
    ax.set_xlabel("$\\mu$")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("SMC-ABC populations", fontsize=9)
    savefig(fig, CH, "own13-3")
    return dict(logZs=logZs, exact=exact, lams=lams0, pops=pops, crude=crude)


# ====================================================================== references for the interactive pages
# Python versions of the three interactive pages, using DKRng and the same order of random draws.
def dk_icdf(W, u):
    cs = []
    acc = 0.0
    for w in W:
        acc += w
        cs.append(acc)
    n = len(W)
    out = []
    j = 0
    for x in u:
        while j < n - 1 and cs[j] <= x:
            j += 1
        out.append(j)
    return out


def dk_resample(method, W, rng):
    """Ancestors by the named scheme with the page's order of draws (u values are sorted for multinomial)."""
    n = len(W)
    if method == "multinomial":
        u = sorted(rng.u() for _ in range(n))
    elif method == "stratified":
        u = [(i + rng.u()) / n for i in range(n)]
    else:
        u0 = rng.u()
        u = [(i + u0) / n for i in range(n)]
    return dk_icdf(W, u)


def dk_lg_data(T, phi, q, r, seed):
    rng = DKRng(seed)
    z = np.zeros(T)
    y = np.zeros(T)
    z[0] = np.sqrt(q / (1 - phi ** 2)) * rng.norm()
    y[0] = z[0] + np.sqrt(r) * rng.norm()
    for t in range(1, T):
        z[t] = phi * z[t - 1] + np.sqrt(q) * rng.norm()
        y[t] = z[t] + np.sqrt(r) * rng.norm()
    return z, y


def lg_kalman(y, phi, q, r):
    """Exact filtering means, variances and log p(y_{1:T}) of the AR(1)-plus-noise model."""
    m, P = 0.0, q / (1 - phi ** 2)
    ms, Ps, ll = [], [], 0.0
    for t, yt in enumerate(y):
        if t > 0:
            m, P = phi * m, phi ** 2 * P + q
        S = P + r
        ll += lnorm(yt, m, S)
        K = P / S
        m, P = m + K * (yt - m), (1 - K) * P
        ms.append(m)
        Ps.append(P)
    return np.array(ms), np.array(Ps), float(ll)


def dk_pf_lg(y, phi, q, r, N, method, thr, seed):
    """The bootstrap filter of the first page. method in multinomial/stratified/systematic; resample when the
    ESS of the current weights is below thr*N (thr = 0: never, i.e. SIS; thr = 1: at every step)."""
    rng = DKRng(seed)
    T = len(y)
    P1 = q / (1 - phi ** 2)
    z = np.array([np.sqrt(P1) * rng.norm() for _ in range(N)])
    anc1 = np.arange(N)
    W = np.full(N, 1.0 / N)
    mean = np.zeros(T)
    ess = np.zeros(T)
    nres = 0
    logZ = 0.0
    ess_prev = float(N)
    resampled = []
    for t in range(T):
        did = False
        if t > 0:
            if thr > 0 and ess_prev < thr * N:
                a = dk_resample(method, W, rng)
                z, anc1 = z[a], anc1[a]
                W = np.full(N, 1.0 / N)
                nres += 1
                did = True
            z = phi * z + np.sqrt(q) * np.array([rng.norm() for _ in range(N)])
        resampled.append(did)
        ll = lnorm(y[t], z, r)
        mx = ll.max()
        lik = np.exp(ll - mx)
        logZ += mx + np.log(np.sum(W * lik))
        W = W * lik
        W = W / W.sum()
        ess[t] = 1.0 / np.sum(W ** 2)
        ess_prev = ess[t]
        mean[t] = np.sum(W * z)
    return dict(mean=mean, ess=ess, logZ=logZ, nres=nres, distinct=int(len(np.unique(anc1))), resampled=resampled)


def dk_pf_spiral(y, par, z0, N, method, thr, seed):
    """Bootstrap filter for the spiral model with the page's order of draws; returns the filtered means."""
    rng = DKRng(seed)
    T = len(y)
    sq = np.sqrt(par["q"])
    z = np.zeros((N, 2))
    for i in range(N):
        z[i, 0] = z0[0] + sq * rng.norm()
        z[i, 1] = z0[1] + sq * rng.norm()
    W = np.full(N, 1.0 / N)
    mean = np.zeros((T, 2))
    ess = np.zeros(T)
    logZ = 0.0
    ess_prev = float(N)
    nres = 0
    for t in range(T):
        if t > 0:
            if thr > 0 and ess_prev < thr * N:
                a = dk_resample(method, W, rng)
                z = z[a]
                W = np.full(N, 1.0 / N)
                nres += 1
            zn = spiral_f(z, par["delta"])
            for i in range(N):
                zn[i, 0] += sq * rng.norm()
                zn[i, 1] += sq * rng.norm()
            z = zn
        ll = lnorm(y[t, 0], z[:, 0], par["r"]) + lnorm(y[t, 1], z[:, 1], par["r"])
        mx = ll.max()
        lik = np.exp(ll - mx)
        logZ += mx + np.log(np.sum(W * lik))
        W = W * lik
        W = W / W.sum()
        ess[t] = 1.0 / np.sum(W ** 2)
        ess_prev = ess[t]
        mean[t] = W @ z
    return dict(mean=mean, ess=ess, logZ=logZ, nres=nres)


def dk_tempered(c, N, ess_frac, K, step, seed, nbisect=60):
    """The tempering page: SMC sampler with adaptive tempering (Algorithm 13.5), systematic resampling, K sweeps of
    random-walk Metropolis (proposal std = step * std of the particles) after each resampling."""
    rng = DKRng(seed)
    th = np.array([rng.norm() for _ in range(N)])
    lam, logZ = 0.0, 0.0
    lams, sets, accs = [0.0], [(th.copy(), np.full(N, 1.0 / N))], []
    while lam < 1.0 - 1e-12:
        E = c * (th ** 2 - 1) ** 2
        target = ess_frac * N
        remaining = 1.0 - lam

        def f(d):
            return ess_logw(-d * E) - target
        if f(remaining) >= 0:
            d = remaining
        else:
            lo, hi = 0.0, remaining
            for _ in range(nbisect):
                mid = 0.5 * (lo + hi)
                if f(mid) > 0:
                    lo = mid
                else:
                    hi = mid
            d = 0.5 * (lo + hi)
        lw = -d * E
        logZ += logsumexp(lw) - np.log(N)
        lam = min(1.0, lam + d)
        W = normalise_logw(lw)
        lams.append(lam)
        sets.append((th.copy(), W))
        # systematic resampling
        u0 = rng.u()
        a = dk_icdf(W, [(i + u0) / N for i in range(N)])
        th = th[a]
        if K > 0:
            sd = th.std()
            lp = -0.5 * th ** 2 - lam * c * (th ** 2 - 1) ** 2
            nacc = 0
            for _ in range(K):
                for i in range(N):
                    prop = th[i] + step * sd * rng.norm()
                    lpp = -0.5 * prop ** 2 - lam * c * (prop ** 2 - 1) ** 2
                    if np.log(rng.u()) < lpp - lp[i]:
                        th[i], lp[i] = prop, lpp
                        nacc += 1
            accs.append(nacc / (K * N))
    return dict(lams=np.array(lams), sets=sets, th=th, logZ=logZ, steps=len(lams) - 1, acc=accs)


def dk_rwmh_chain(c, th0, n, step, seed):
    """Baseline of the tempering page: one random-walk Metropolis chain on the final target."""
    rng = DKRng(seed)
    x = th0
    lp = -0.5 * x ** 2 - c * (x ** 2 - 1) ** 2
    xs = np.zeros(n)
    for i in range(n):
        prop = x + step * rng.norm()
        lpp = -0.5 * prop ** 2 - c * (prop ** 2 - 1) ** 2
        if np.log(rng.u()) < lpp - lp:
            x, lp = prop, lpp
        xs[i] = x
    return xs


def resampling_theory(W):
    """Exact offspring-count variances: multinomial N W (1 - W); systematic frac(N W)(1 - frac(N W));
    stratified sum_k p_k (1 - p_k), p_k the chance that the stratum-k point falls in the particle's interval."""
    W = np.asarray(W, float)
    n = len(W)
    cs = np.concatenate([[0.0], np.cumsum(W)])
    multi = n * W * (1 - W)
    fr = n * W - np.floor(n * W)
    syst = fr * (1 - fr)
    strat = np.zeros(n)
    for i in range(n):
        lo, hi = cs[i], cs[i + 1]
        for k in range(n):
            ov = max(0.0, min(hi, (k + 1) / n) - max(lo, k / n))
            p = ov * n
            strat[i] += p * (1 - p)
    return dict(multinomial=multi, stratified=strat, systematic=syst)


def resampling_pzero(W):
    """Exact probability that a particle receives no offspring, averaged over the particles: multinomial
    (1 - W)^N, systematic max(0, 1 - N W), stratified prod_k (1 - p_k) with p_k as in resampling_theory."""
    W = np.asarray(W, float)
    n = len(W)
    cs = np.concatenate([[0.0], np.cumsum(W)])
    multi = (1 - W) ** n
    syst = np.maximum(0.0, 1 - n * W)
    strat = np.ones(n)
    for i in range(n):
        for k in range(n):
            ov = max(0.0, min(cs[i + 1], (k + 1) / n) - max(cs[i], k / n))
            strat[i] *= 1 - ov * n
    return dict(multinomial=float(multi.mean()), stratified=float(strat.mean()), systematic=float(syst.mean()))


def dk_resampling_page(N, spread, seed, reps):
    """The resampling page: weights W_i proportional to exp(spread g_i) with g from DK.rng(seed); the test function
    f from DK.rng(seed+10); Monte Carlo over `reps` resamplings per scheme (generators seed+1, seed+2, seed+3 for
    multinomial, stratified, systematic). Returns the exact theory and, per scheme, the total offspring variance, the
    average fraction of particles with no offspring and the standard deviation of the resampled mean of f."""
    rg = DKRng(seed)
    g = np.array([rg.norm() for _ in range(N)])
    W = normalise_logw(spread * g)
    rf = DKRng(seed + 10)
    f = np.array([rf.norm() for _ in range(N)])
    out = dict(W=W, f=f, target=float(W @ f), theory=resampling_theory(W), pzero_theory=resampling_pzero(W))
    for k, name in enumerate(["multinomial", "stratified", "systematic"]):
        rng = DKRng(seed + 1 + k)
        cnt = np.zeros((reps, N))
        est = np.zeros(reps)
        for r in range(reps):
            a = dk_resample(name, W, rng)
            cnt[r] = np.bincount(a, minlength=N)
            est[r] = f[a].mean()
        out[name] = dict(mean=cnt.mean(0), var=cnt.var(0), totvar=float(cnt.var(0).sum()), pzero=float((cnt == 0).mean()),
                         est_sd=float(est.std()), est_mean=float(est.mean()))
    return out


# ====================================================================== data exported for the pages
def export_spiral_json():
    """Data of the 2-d tracking pages: the simulated trajectory and observations of Figure 13.1."""
    import json
    T = 100
    z, y = spiral_simulate(T, np.random.default_rng(4))
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch13-spiral.json")
    with open(path, "w") as f:
        json.dump(dict(delta=SPIRAL["delta"], q=SPIRAL["q"], r=SPIRAL["r"], z0=[1.5, 0.2],
                       z=np.round(z, 5).tolist(), y=np.round(y, 5).tolist()), f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    return path


FIGURES = {
    "13.1": fig_13_1, "13.2": fig_13_2, "13.3": fig_13_3, "13.4": fig_13_4, "13.5": fig_13_5,
    "13.6": fig_13_6_7, "13.10": fig_13_10_11, "13.12": fig_13_12, "S13.1": fig_S13_1,
    "own13.1": fig_own13_1, "own13.2": fig_own13_2, "own13.3": fig_own13_3, "own13.4": fig_own13_4,
    "data": lambda out_dir=None: export_spiral_json(),
}
FIGURES["13.6"].__doc__ = "Figures 13.6 and 13.7: RBPF against the bootstrap filter (maneuvering object)"
FIGURES["13.10"].__doc__ = "Figures 13.10 and 13.11: tempered SMC on the bimodal target, HMC and NUTS"

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