"""Murphy (2023), Chapter 29: State-space models (and Supplement Chapter 29).

Companion code for Chapter 29 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press, 2023;
December 2025 draft), pp. 1013-1076 of the PDF (979-1042 printed), and the supplement, pp. 219-226. Written from scratch
with numpy, scipy and matplotlib (statsmodels only for the data),
to be read next to the lecture notes (../ch29-state-space-models.html).

Methods implemented here (all by hand)
* Sections 29.2 and 29.4: scaled forwards-backwards for batches of sequences (hmm_forward, hmm_backward, hmm_estep),
  Viterbi, Baum-Welch (baum_welch_discrete), the HMM log-likelihood gradient as expected counts (hmm_loglik_and_grad) and
  gradient-descent training with softmax parameters (train_sgd), label-switching matching.
* Sections 29.3.1 and 29.5.6: Poisson HMM by EM with a log-normal rate prior (poisson_hmm_map), the chained-state duration law
  (neg_binomial_duration), exact Bayesian online changepoint detection with a conjugate Gaussian predictive (bocpd_gaussian,
  bocpd_changepoints).
* Sections 29.6 to 29.8, 29.11: Kalman filter and RTS smoother with lag-one covariances and missing data (kalman_filter,
  rts_smoother), EM for the LDS with inputs (lds_em_step), the constant-velocity model (cv_model), recursive least squares,
  Laplace-approximation EM for a Poisson LDS (poisson_lds_mode, poisson_lds_em).
* Section 29.12: local linear trend plus seasonal structural time series (sts_matrices, sts_fit, sts_forecast), predictive
  z-scores for anomaly detection, closed-form counterfactual forecasts and causal impact with the joint forecast covariance
  (causal_impact).
* Supplement 29.1: generalised bilinear discretisation (gbt_discretise), RK2 integration, an EKF with an RK2 prediction step.

Data. No data website exists for the book. Mauna Loa CO2 (Figure 29.33) uses the weekly 1958-2001 record shipped with statsmodels
averaged by month (the book uses 1966-2019); everything else is simulated from the models stated in the captions (the casino HMM,
a Poisson count series with rates 40, 3, 20, 50, a 4-segment Gaussian series, the 2d AR-HMM, a Poisson LDS).

Skipped figures, with reasons: 29.1, 29.9, 29.11, 29.12, 29.16 to 29.21, 29.25, 29.27 to 29.29, 29.32, 29.38 to 29.40, 29.42 to 29.45 and
S29.1, S29.2, S29.6 are diagrams or schematics; 29.10 and 29.37 are a photograph and a figure taken from other papers; 29.23 repeats
Figure 8.2 (reproduced in Chapter 8); 29.34 to 29.36 need the 2014 Victoria electricity demand and temperature series, which are not
available (Figure x29.a shows predictive-z-score anomaly detection on a simulated series instead). Figures 29.6 to 29.8 and 29.22 use
simulated series with the generating parameters stated in the book.

Differences from the text, all stated in the notes: the AR-HMM uses a damped (0.93) 7-degree rotation (a pure rotation has no steady state);
the emission update divides by the expected state count over ALL time steps; Figure 29.8 reports the maximised log-likelihood and the
maximised log posterior (the quantity the book calls the marginal likelihood is a maximised score).

Own figure (not in the book): x29.a (anomaly detection by one-step predictive z-scores).

Run `python ch29_state_space_models.py` (all figures, about 6 minutes the first time; the casino fits are cached in cache/ch29),
`--fig 29.22` for one, `--fig data` to write the JSON files used by the demonstration pages.
"""
import os
import sys
import json
import time

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

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

CH = 29
CACHE_DIR = os.path.join(HERE, "cache", "ch29")
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
STATE_COLS = [RED, BLUE, GREEN, ORANGE, PURPLE, CYAN, MAGENTA, GREY]


def save_json(name, obj):
    path = os.path.join(DATA_OUT, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%d bytes)" % os.path.getsize(path))


def softmax(x, axis=-1):
    x = np.asarray(x, dtype=float)
    z = np.exp(x - x.max(axis=axis, keepdims=True))
    return z / z.sum(axis=axis, keepdims=True)


def _shade_states(ax, z, cols=STATE_COLS, alpha=0.22, t0=0):
    """Colour the background of ax by the discrete state sequence z."""
    z = np.asarray(z)
    start = 0
    for t in range(1, len(z) + 1):
        if t == len(z) or z[t] != z[start]:
            ax.axvspan(t0 + start - 0.5, t0 + t - 0.5, color=cols[int(z[start]) % len(cols)], alpha=alpha, lw=0)
            start = t


# =============================================================================== HMM core (Sections 29.2, 29.4)
def hmm_forward(lik, A, pi):
    """Scaled forwards algorithm for a batch of sequences.

    lik has shape (N, T, K) with lik[n, t, k] = p(y_{n,t} | z_t = k). Returns the filtered beliefs alpha
    (N, T, K) = p(z_t | y_{1:t}) and the one-step predictive normalisers c (N, T) = p(y_t | y_{1:t-1}),
    so that log p(y_{1:T}) = sum_t log c_t (29.36)-(29.37).
    """
    N, T, K = lik.shape
    alpha = np.empty((N, T, K))
    c = np.empty((N, T))
    a = pi[None, :] * lik[:, 0]
    c[:, 0] = a.sum(1)
    alpha[:, 0] = a / c[:, 0:1]
    for t in range(1, T):
        a = (alpha[:, t - 1] @ A) * lik[:, t]
        c[:, t] = a.sum(1)
        alpha[:, t] = a / c[:, t:t + 1]
    return alpha, c


def hmm_backward(lik, A, c):
    """Scaled backwards messages beta_t(j) = p(y_{t+1:T} | z_t = j) / prod_{s>t} c_s."""
    N, T, K = lik.shape
    beta = np.ones((N, T, K))
    for t in range(T - 2, -1, -1):
        beta[:, t] = ((lik[:, t + 1] * beta[:, t + 1]) @ A.T) / c[:, t + 1:t + 2]
    return beta


def hmm_estep(lik, A, pi):
    """Forwards-backwards: node marginals gamma (N,T,K), summed edge marginals xi (K,K), log-likelihood."""
    alpha, c = hmm_forward(lik, A, pi)
    beta = hmm_backward(lik, A, c)
    gamma = alpha * beta
    w = lik[:, 1:] * beta[:, 1:] / c[:, 1:, None]
    xi = A * np.einsum("ntj,ntk->jk", alpha[:, :-1], w)
    return gamma, xi, float(np.log(c).sum()), alpha, c


def hmm_viterbi(lik, A, pi):
    """Most probable state sequence of ONE sequence (lik shape (T, K)), in the log domain."""
    T, K = lik.shape
    with np.errstate(divide="ignore"):
        lA, lL, lp = np.log(A), np.log(lik), np.log(pi)
    d = lp + lL[0]
    back = np.zeros((T, K), dtype=int)
    for t in range(1, T):
        s = d[:, None] + lA
        back[t] = s.argmax(0)
        d = s.max(0) + lL[t]
    z = np.empty(T, dtype=int)
    z[-1] = int(d.argmax())
    for t in range(T - 1, 0, -1):
        z[t - 1] = back[t, z[t]]
    return z, float(d.max())


def hmm_sample(A, pi, T, rng):
    """Hidden state path of length T."""
    K = len(pi)
    z = np.empty(T, dtype=int)
    z[0] = rng.choice(K, p=pi)
    for t in range(1, T):
        z[t] = rng.choice(K, p=A[z[t - 1]])
    return z


def discrete_lik(Y, B):
    """lik (N, T, K) for categorical emissions B (K, V) and data Y (N, T)."""
    return B[:, Y].transpose(1, 2, 0)


def baum_welch_discrete(Y, K, V, A0, B0, pi0, n_iter=200, fix=()):
    """Baum-Welch (EM) for a categorical-emission HMM on the batch Y of shape (N, T).

    E step: forwards-backwards (29.26)-(29.27) and expected counts (29.28); M step: normalised counts
    (29.30) and (29.32), with the emission denominator summed over ALL time steps (see the notes, errata).
    Returns (A, B, pi, history of the average negative log-likelihood per observation).
    """
    A, B, pi = A0.copy(), B0.copy(), pi0.copy()
    N, T = Y.shape
    hist = []
    onehot = np.eye(V)[Y]                                 # (N, T, V)
    for it in range(n_iter):
        lik = discrete_lik(Y, B)
        gamma, xi, ll, _, _ = hmm_estep(lik, A, pi)
        hist.append(-ll / (N * T))
        pi = gamma[:, 0].sum(0) / N
        A = xi / xi.sum(1, keepdims=True)
        Mkv = np.einsum("ntk,ntv->kv", gamma, onehot)
        B = Mkv / Mkv.sum(1, keepdims=True)
    lik = discrete_lik(Y, B)
    hist.append(-hmm_estep(lik, A, pi)[2] / (N * T))
    return A, B, pi, np.array(hist)


def hmm_loglik_and_grad(Y, a_logits, b_logits, p_logits):
    """Average negative log-likelihood per observation and its gradient wrt the unconstrained logits.

    A = softmax(a_logits) row-wise, B = softmax(b_logits), pi = softmax(p_logits). By the identity
    d log p(y) / d log A_jk = E[N_jk] (expected counts), the gradient needs one forwards-backwards pass:
    d(-L)/d a_jk = -(E[N_jk] - A_jk sum_k' E[N_jk'])/(N T), and likewise for B and pi.
    """
    A, B, pi = softmax(a_logits), softmax(b_logits), softmax(p_logits)
    N, T = Y.shape
    K, V = B.shape
    lik = discrete_lik(Y, B)
    gamma, xi, ll, _, _ = hmm_estep(lik, A, pi)
    Mkv = np.einsum("ntk,ntv->kv", gamma, np.eye(V)[Y])
    n0 = gamma[:, 0].sum(0)
    ga = xi - A * xi.sum(1, keepdims=True)
    gb = Mkv - B * Mkv.sum(1, keepdims=True)
    gp = n0 - pi * n0.sum()
    s = -1.0 / (N * T)
    return -ll / (N * T), s * ga, s * gb, s * gp


def casino_true():
    """The occasionally dishonest casino of Section 9.2.1.1 (state 0 fair, state 1 loaded)."""
    A = np.array([[0.95, 0.05], [0.10, 0.90]])
    B = np.array([[1 / 6] * 6, [0.1] * 5 + [0.5]])
    pi = np.array([0.5, 0.5])
    return A, B, pi


def sample_discrete_hmm(A, B, pi, T, rng):
    z = hmm_sample(A, pi, T, rng)
    cum = np.cumsum(B, axis=1)
    u = rng.random(T)
    y = (u[:, None] > cum[z]).sum(1)
    return z, np.minimum(y, B.shape[1] - 1)


def sample_casino_data(N=4, T=5000, seed=0):
    A, B, pi = casino_true()
    rng = np.random.default_rng(seed)
    Z, Y = [], []
    for _ in range(N):
        z, y = sample_discrete_hmm(A, B, pi, T, rng)
        Z.append(z), Y.append(y)
    return np.array(Z), np.array(Y)


def casino_random_init(seed):
    rng = np.random.default_rng(seed)
    A0 = 0.7 * np.eye(2) + 0.3 * rng.dirichlet(np.ones(2), size=2)      # sticky random start
    B0 = rng.dirichlet(np.ones(6) * 8, size=2)
    pi0 = rng.dirichlet(np.ones(2) * 2)
    return A0, B0, pi0


def train_sgd(Y, init, n_epochs=200, batch=1, lr=0.5, seed=0):
    """Minimise the average NLL by (mini-batch) gradient descent on softmax-reparameterised parameters.

    One 'step' of the learning curve is one pass over the data (epoch); batch=1 updates after every sequence,
    batch=len(Y) is full-batch gradient descent.
    """
    A0, B0, pi0 = init
    a, b, p = np.log(A0), np.log(B0), np.log(pi0)
    rng = np.random.default_rng(seed)
    N = len(Y)
    hist = []
    for ep in range(n_epochs):
        hist.append(hmm_loglik_and_grad(Y, a, b, p)[0])
        order = rng.permutation(N)
        for s in range(0, N, batch):
            idx = order[s:s + batch]
            _, ga, gb, gp = hmm_loglik_and_grad(Y[idx], a, b, p)
            a, b, p = a - lr * ga, b - lr * gb, p - lr * gp
    hist.append(hmm_loglik_and_grad(Y, a, b, p)[0])
    return softmax(a), softmax(b), softmax(p), np.array(hist)


def match_states(B_est, B_true):
    """Permutation of the estimated states that best matches the true ones (label switching, Section 28.2.6)."""
    import itertools
    K = len(B_true)
    best, bp = np.inf, None
    for perm in itertools.permutations(range(K)):
        d = np.abs(B_est[list(perm)] - B_true).sum()
        if d < best:
            best, bp = d, perm
    return list(bp)


# =============================================================================== Figures 29.2 to 29.5
def bernoulli_hmm(K=5, D=10, stay=0.95, seed=3):
    rng = np.random.default_rng(seed)
    A = np.full((K, K), (1 - stay) / (K - 1))
    np.fill_diagonal(A, stay)
    theta = rng.beta(0.6, 0.6, size=(K, D))
    return A, theta, np.ones(K) / K


def fig_29_2(out_dir=None):
    """Samples from an HMM with 5 hidden states and 10 Bernoulli observables."""
    A, theta, pi = bernoulli_hmm()
    rng = np.random.default_rng(1)
    T = 400
    z = hmm_sample(A, pi, T, rng)
    Y = (rng.random((T, theta.shape[1])) < theta[z]).astype(int)
    fig, ax = plt.subplots(2, 1, figsize=(7.4, 3.8), sharex=True, gridspec_kw=dict(height_ratios=[2.2, 1]))
    ax[0].imshow(Y.T, aspect="auto", cmap="Greys", interpolation="nearest", extent=[-0.5, T - 0.5, 9.5, -0.5])
    ax[0].set_ylabel("observable")
    ax[1].step(np.arange(T), z, where="mid", color=BLUE)
    ax[1].set_ylabel("state"), ax[1].set_xlabel("time"), ax[1].set_yticks(range(5)), ax[1].set_xlim(-0.5, T - 0.5)
    savefig(fig, CH, "fig29-2", out_dir)


def gaussian_hmm_2d(seed=2):
    """5-state HMM whose states emit from 2-d Gaussians placed on a ring (the 'lily pads')."""
    K = 5
    ang = 2 * np.pi * np.arange(K) / K + 0.4
    mu = 0.75 * np.stack([np.cos(ang), np.sin(ang)], 1)
    Sig = np.array([np.diag([0.012, 0.03]) if k % 2 == 0 else np.diag([0.03, 0.012]) for k in range(K)])
    A = np.full((K, K), 0.07 / (K - 1))
    np.fill_diagonal(A, 0.93)
    return A, mu, Sig, np.ones(K) / K


def fig_29_3(out_dir=None):
    """2-d data sampled from a 5-state Gaussian HMM, and the data as a time series."""
    A, mu, Sig, pi = gaussian_hmm_2d()
    rng = np.random.default_rng(1)
    T = 200
    z = hmm_sample(A, pi, T, rng)
    Y = np.array([rng.multivariate_normal(mu[k], Sig[k]) for k in z])
    fig, ax = plt.subplots(1, 2, figsize=(9.2, 3.3), gridspec_kw=dict(width_ratios=[1, 1.5]))
    for k in range(5):
        ex, ey = common.ellipse_xy(mu[k], Sig[k], nsd=2.0)
        ax[0].plot(ex, ey, color=STATE_COLS[k], lw=2)
        pts = Y[z == k]
        ax[0].plot(pts[:, 0], pts[:, 1], ".", color=STATE_COLS[k], ms=4, alpha=0.6)
    ax[0].set_xlabel("$y_1$"), ax[0].set_ylabel("$y_2$"), ax[0].set_aspect("equal"), ax[0].set_title("Generating HMM")
    _shade_states(ax[1], z)
    ax[1].plot(Y[:, 0], color="k", lw=1.1, label="$y_1$")
    ax[1].plot(Y[:, 1] - 2.2, color="0.35", lw=1.1, label="$y_2$ (shifted)")
    ax[1].set_xlim(0, T - 1), ax[1].set_xlabel("time"), ax[1].set_title("Simulated data from an HMM"), ax[1].legend(loc="upper right")
    panel_label(ax[0], "a"), panel_label(ax[1], "b", "lower left")
    savefig(fig, CH, "fig29-3", out_dir)


def ar_hmm_model(K=5, deg=7.0, rho=0.93, r=0.59, offset_deg=-9.8):
    """Left-to-right 5-state AR(1) HMM that cycles through its states (Section 29.2.5). E is a damped 7-degree rotation."""
    th = np.radians(deg)
    E = rho * np.array([[np.cos(th), -np.sin(th)], [np.sin(th), np.cos(th)]])
    phi = np.radians(offset_deg + 72.0 * np.arange(K))
    mu = r * np.stack([np.cos(phi), np.sin(phi)], 1)
    A = np.zeros((K, K))
    for k in range(K):
        A[k, k] = 0.97
        A[k, (k + 1) % K] = 0.03
    Sig = 0.002 * np.eye(2)
    steady = np.array([np.linalg.solve(np.eye(2) - E, m) for m in mu])
    return dict(E=E, mu=mu, A=A, Sig=Sig, steady=steady, pi=np.ones(K) / K)


def sample_ar_hmm(M, T, rng, y0=(-0.8, 0.5)):
    z = np.empty(T, dtype=int)
    z[0] = 1
    for t in range(1, T):
        z[t] = rng.choice(len(M["pi"]), p=M["A"][z[t - 1]])
    y = np.zeros((T, 2))
    y[0] = y0
    L = np.linalg.cholesky(M["Sig"])
    for t in range(1, T):
        y[t] = M["E"] @ y[t - 1] + M["mu"][z[t]] + L @ rng.standard_normal(2)
    return z, y


def fig_29_4(out_dir=None):
    """Observation dynamics (vector fields) of each state of the 2-d AR-HMM."""
    M = ar_hmm_model()
    g = np.linspace(-6, 6, 13)
    X, Y = np.meshgrid(g, g)
    P = np.stack([X.ravel(), Y.ravel()], 1)
    fig, ax = plt.subplots(1, 5, figsize=(13, 2.7), sharex=True, sharey=True)
    for k in range(5):
        nxt = P @ M["E"].T + M["mu"][k]
        d = nxt - P
        ax[k].quiver(P[:, 0], P[:, 1], d[:, 0], d[:, 1], color=STATE_COLS[k], angles="xy", scale_units="xy", scale=1.0, width=0.004)
        s = M["steady"][k]
        ax[k].plot(*s, "k*", ms=9)
        ax[k].set_title("state %d: attractor (%.1f, %.1f)" % (k + 1, s[0], s[1]), fontsize=9)
        ax[k].set_aspect("equal"), ax[k].set_xlim(-6.5, 6.5), ax[k].set_ylim(-6.5, 6.5)
    ax[0].set_ylabel("$y_2$")
    for a in ax:
        a.set_xlabel("$y_1$")
    savefig(fig, CH, "fig29-4", out_dir)


def fig_29_5(out_dir=None):
    """A sampled trajectory of the 2-d AR-HMM: time series and scatter plot."""
    M = ar_hmm_model()
    rng = np.random.default_rng(8)
    T = 200
    z, y = sample_ar_hmm(M, T, rng)
    fig, ax = plt.subplots(1, 2, figsize=(10, 3.6), gridspec_kw=dict(width_ratios=[1.5, 1]))
    _shade_states(ax[0], z)
    ax[0].plot(y[:, 0], "k", lw=1.2)
    ax[0].plot(y[:, 1] + 4.7, "0.35", lw=1.2)
    for k in range(5):
        for comp, off in ((0, 0.0), (1, 4.7)):
            m = z == k
            if m.any():
                ax[0].axhline(M["steady"][k][comp] + off, color=STATE_COLS[k], ls=":", lw=1.0, xmin=0, xmax=1, alpha=0.7)
    ax[0].set_xlim(0, T - 1), ax[0].set_xlabel("time"), ax[0].set_ylabel("$y_1$, $y_2$ (shifted by 4.7)")
    for k in range(5):
        pts = y[z == k]
        ax[1].plot(pts[:, 0], pts[:, 1], ".", color=STATE_COLS[k], ms=5, label="state %d" % (k + 1))
        ax[1].plot(*M["steady"][k], "*", color=STATE_COLS[k], mec="k", ms=10)
    ax[1].plot(y[:, 0], y[:, 1], "-", color="0.6", lw=0.6, zorder=0)
    ax[1].set_xlabel("$y_1$"), ax[1].set_ylabel("$y_2$"), ax[1].set_aspect("equal"), ax[1].legend(fontsize=7, loc="lower right")
    panel_label(ax[0], "a", "lower left"), panel_label(ax[1], "b")
    savefig(fig, CH, "fig29-5", out_dir)


# =============================================================================== Figures 29.13 to 29.15
_CASINO_CACHE = os.path.join(CACHE_DIR, "casino_fits.npz")


def casino_fits(force=False):
    """EM (200 iterations), SGD with minibatch 1 and full-batch GD on the 4 x 5000 casino data (Section 29.4)."""
    if os.path.exists(_CASINO_CACHE) and not force:
        d = np.load(_CASINO_CACHE)
        return {k: d[k] for k in d.files}
    Z, Y = sample_casino_data()
    init = casino_random_init(4)
    Ae, Be, pie, he = baum_welch_discrete(Y, 2, 6, *init, n_iter=200)
    As, Bs, pis, hs = train_sgd(Y, init, n_epochs=200, batch=1, lr=2.0, seed=0)
    Ag, Bg, pig, hg = train_sgd(Y, init, n_epochs=200, batch=len(Y), lr=2.0, seed=0)
    out = dict(Ae=Ae, Be=Be, pie=pie, he=he, As=As, Bs=Bs, pis=pis, hs=hs, Ag=Ag, Bg=Bg, pig=pig, hg=hg)
    np.savez(_CASINO_CACHE, **out)
    return out


def _casino_panel(ax, A, B, title, order=(0, 1)):
    """A small picture of a 2-state casino HMM: emission bars and self/cross transition probabilities."""
    ax.set_xlim(0, 10), ax.set_ylim(0, 6.6), ax.axis("off")
    ax.set_title(title, fontsize=9.5)
    for slot, k in enumerate(order):
        x0 = 0.2 + slot * 5.3
        ax.add_patch(plt.Rectangle((x0, 0.2), 4.4, 4.4, fill=False, ec="k", lw=1))
        ax.text(x0 + 2.2, 4.8, "state %d" % (slot + 1), ha="center", fontsize=9)
        for v in range(6):
            h = B[k, v] * 7.0
            ax.add_patch(plt.Rectangle((x0 + 0.3 + v * 0.65, 0.4), 0.5, h, color=BLUE if slot == 0 else RED, alpha=0.8))
            ax.text(x0 + 0.55 + v * 0.65, 0.05, str(v + 1), ha="center", va="top", fontsize=6)
        ax.text(x0 + 2.2, 4.1, "emit: " + " ".join("%.2f" % b for b in B[k])[:40], ha="center", fontsize=5.6)
    s0, s1 = order
    ax.text(2.4, 5.7, "stay %.2f" % A[s0, s0], ha="center", fontsize=8)
    ax.text(7.7, 5.7, "stay %.2f" % A[s1, s1], ha="center", fontsize=8)
    ax.annotate("", xy=(5.4, 5.35), xytext=(4.7, 5.35), arrowprops=dict(arrowstyle="->"))
    ax.text(5.0, 6.05, "%.2f" % A[s0, s1], ha="center", fontsize=7)
    ax.annotate("", xy=(4.7, 4.95), xytext=(5.4, 4.95), arrowprops=dict(arrowstyle="->"))
    ax.text(5.05, 4.55, "%.2f" % A[s1, s0], ha="center", fontsize=7)


def fig_29_13(out_dir=None):
    """The casino HMM: true parameters, EM estimates and SGD estimates."""
    f = casino_fits()
    At, Bt, _ = casino_true()
    fig, ax = plt.subplots(1, 3, figsize=(11, 3.4))
    _casino_panel(ax[0], At, Bt, "(a) true parameters")
    pe = match_states(f["Be"], Bt)
    _casino_panel(ax[1], f["Ae"], f["Be"], "(b) estimated by EM", order=tuple(pe))
    ps = match_states(f["Bs"], Bt)
    _casino_panel(ax[2], f["As"], f["Bs"], "(c) estimated by SGD", order=tuple(ps))
    savefig(fig, CH, "fig29-13", out_dir)


def fig_29_14(out_dir=None):
    """Average negative log-likelihood per observation against the learning step, for EM, SGD and full-batch GD."""
    f = casino_fits()
    Z, Y = sample_casino_data()
    At, Bt, pit = casino_true()
    nll_true = -hmm_estep(discrete_lik(Y, Bt), At, pit)[2] / Y.size
    fig, ax = plt.subplots(1, 3, figsize=(11.5, 3.0), sharey=True)
    for a, (key, ttl) in zip(ax, (("he", "EM algorithm"), ("hs", "stochastic gradient descent (minibatch 1)"), ("hg", "full-batch gradient descent"))):
        a.plot(f[key], color=BLUE)
        a.axhline(nll_true, color=GREY, ls="--", lw=1, label="at the true parameters")
        a.set_title(ttl, fontsize=9.5), a.set_xlabel("learning step (one pass over the data)")
    ax[0].set_ylabel("average negative log-likelihood"), ax[0].legend(fontsize=8)
    ax[0].set_ylim(nll_true - 0.01, nll_true + 0.09)
    panel_label(ax[0], "a", "upper right"), panel_label(ax[1], "b", "upper right"), panel_label(ax[2], "c", "upper right")
    savefig(fig, CH, "fig29-14", out_dir)


def neg_binomial_duration(d, n, p):
    """p(d) = C(d-1, n-1) p^(d-n) (1-p)^n, the law of a path through n chained states with self-loop p (29.51)."""
    d = np.asarray(d)
    out = np.zeros(d.shape)
    m = d >= n
    out[m] = np.exp(special.gammaln(d[m]) - special.gammaln(n) - special.gammaln(d[m] - n + 1) + (d[m] - n) * np.log(p) + n * np.log1p(-p))
    return out


def fig_29_15(out_dir=None):
    """Distribution of the sequence length for n repeated states with self-loops (hidden semi-Markov models)."""
    p = 0.99
    d = np.arange(1, 1001)
    fig, ax = plt.subplots(1, 1, figsize=(5.4, 3.2))
    for n, col in zip((1, 2, 5), (BLUE, GREEN, RED)):
        ax.plot(d, neg_binomial_duration(d, n, p), color=col, label="n = %d (mean %d)" % (n, round(n / (1 - p))))
    ax.set_xlabel("sequence length d"), ax.set_ylabel("p(d)"), ax.legend()
    ax.set_title("p = 0.99")
    savefig(fig, CH, "fig29-15", out_dir)


# =============================================================================== Poisson HMM and changepoints (Section 29.3.1)
def poisson_segments(seed=0):
    """Counts with generating rates (40, 3, 20, 50) and changepoints at 10, 30, 35 (T = 70)."""
    rng = np.random.default_rng(seed)
    rates = np.array([40.0, 3.0, 20.0, 50.0])
    bounds = [0, 10, 30, 35, 70]
    lam = np.concatenate([np.full(bounds[i + 1] - bounds[i], rates[i]) for i in range(4)])
    return rng.poisson(lam), lam


def sticky_transition(K, p=0.95):
    if K == 1:
        return np.ones((1, 1))
    A = np.full((K, K), (1 - p) / (K - 1))
    np.fill_diagonal(A, p)
    return A


def poisson_lik(y, lam):
    return stats.poisson.pmf(np.asarray(y)[None, :, None], lam[None, None, :])


def poisson_hmm_map(y, K, p=0.95, prior=(5.0, 5.0), n_iter=200, n_restart=20, seed=0):
    """MAP estimate of the Poisson rates of a K-state HMM with fixed sticky transitions by EM.

    The prior is log lambda_k ~ N(prior[0], prior[1]) (mean, variance). Returns (rates, log-likelihood at the
    optimum, log posterior at the optimum, smoothed state posteriors, restarts' best log posterior).
    """
    A = sticky_transition(K, p)
    pi = np.ones(K) / K
    m0, v0 = prior
    rng = np.random.default_rng(seed)
    y = np.asarray(y)
    best = None
    for r in range(n_restart):
        u = np.log(max(y.mean(), 1.0)) + rng.normal(0, 1.0, K)
        prev = -np.inf
        for it in range(n_iter):
            lik = poisson_lik(y, np.exp(u))
            gamma, _, ll, _, _ = hmm_estep(lik, A, pi)
            lp = ll - 0.5 * np.sum((u - m0) ** 2) / v0
            S0 = gamma[0].sum(0)
            S1 = (gamma[0] * y[:, None]).sum(0)
            for _ in range(20):                       # Newton on the concave function of u
                g = S1 - S0 * np.exp(u) - (u - m0) / v0
                h = -S0 * np.exp(u) - 1.0 / v0
                u = u - g / h
            if abs(lp - prev) < 1e-10:
                break
            prev = lp
        lik = poisson_lik(y, np.exp(u))
        gamma, _, ll, _, _ = hmm_estep(lik, A, pi)
        lp = ll - 0.5 * np.sum((u - m0) ** 2) / v0
        if best is None or lp > best[2]:
            best = (np.exp(u), ll, lp, gamma[0])
    return best


def poisson_fits():
    y, lam = poisson_segments()
    out = {}
    for K in range(1, 7):
        out[K] = poisson_hmm_map(y, K)
    return y, lam, out


def fig_29_6(out_dir=None):
    """A count series and its segmentation by a 4-state Poisson HMM."""
    y, lam = poisson_segments()
    rates, ll, lp, gam = poisson_hmm_map(y, 4)
    inferred = gam @ rates
    fig, ax = plt.subplots(1, 2, figsize=(10, 3.1), sharey=True)
    t = np.arange(len(y))
    ax[0].plot(t, y, "o-", color=GREEN, ms=3.5, lw=0.8)
    ax[0].set_xlabel("time"), ax[0].set_ylabel("count")
    ax[1].plot(t, y, "o", color=GREEN, ms=3, alpha=0.6, label="observed counts")
    ax[1].plot(t, inferred, color=RED, lw=2, label="inferred rate")
    ax[1].plot(t, lam, color="k", lw=0.8, ls=":", label="generating rate")
    ax[1].set_xlabel("time"), ax[1].legend(fontsize=8)
    panel_label(ax[0], "a"), panel_label(ax[1], "b", "upper right")
    savefig(fig, CH, "fig29-6", out_dir)


def fig_29_7(out_dir=None):
    """Segmentations by Poisson HMMs with K = 1 to 6 states."""
    y, lam, fits = poisson_fits()
    fig, ax = plt.subplots(2, 3, figsize=(10, 4.8), sharex=True, sharey=True)
    t = np.arange(len(y))
    for K, a in zip(range(1, 7), ax.ravel()):
        rates, ll, lp, gam = fits[K]
        a.plot(t, y, "o", color=GREEN, ms=2.5, alpha=0.6, label="observed counts")
        a.plot(t, gam @ rates, color=RED, lw=1.8, label="inferred rate")
        a.set_title("%d-state model" % K, fontsize=9.5)
    ax[0, 0].legend(fontsize=7)
    for a in ax[1]:
        a.set_xlabel("time")
    for a in ax[:, 0]:
        a.set_ylabel("latent rate")
    savefig(fig, CH, "fig29-7", out_dir)


def fig_29_8(out_dir=None):
    """Maximised log-likelihood (empirical Bayes) against the number of states K in the Poisson HMM."""
    y, lam, fits = poisson_fits()
    Ks = np.arange(1, 7)
    ll = np.array([fits[K][1] for K in Ks])
    lp = np.array([fits[K][2] for K in Ks])
    fig, ax = plt.subplots(1, 1, figsize=(4.8, 3.2))
    ax.plot(Ks, ll, "o-", color=BLUE, label="max log-likelihood (29.21)")
    ax.plot(Ks, lp, "s--", color=RED, label="max log posterior (with the rate prior)")
    ax.set_ylim(-275, -220), ax.set_xlabel("number of latent states"), ax.set_ylabel("log p(y | K)"), ax.legend(fontsize=8, loc="lower right")
    savefig(fig, CH, "fig29-8", out_dir)


# =============================================================================== Bayesian online changepoint detection (Section 29.5.6)
def bocpd_gaussian(y, hazard, mu0=0.0, v0=4.0, s2=1.0):
    """Exact BOCPD for a Gaussian segment mean with known variance s2 and a conjugate N(mu0, v0) prior.

    Run-length convention of (29.63)-(29.70): r_t is the number of earlier observations in y_t's segment.
    A constant hazard (a number) or a function H(tau) can be given. Returns the matrix P[t, r] = p(r_t = r | y_{1:t})
    (rows t = 0..T-1 are times 1..T), the one-step predictive means and the log evidence.
    """
    y = np.asarray(y, dtype=float)
    T = len(y)
    H = (lambda tau: hazard) if np.isscalar(hazard) else hazard
    P = np.zeros((T, T + 1))
    prev = np.array([1.0])                              # the run before the first observation starts at r_1 = 0
    n = np.array([0.0])                                  # sufficient statistics of every run-length hypothesis
    S = np.array([0.0])
    logev = 0.0
    pred_mean = np.zeros(T)
    for t in range(T):
        L = len(prev)
        if t == 0:                                       # the first observation starts the first segment: r_1 = 0
            prior, n_t, S_t = np.array([1.0]), np.array([0.0]), np.array([0.0])
        else:
            h = np.array([H(r + 1) for r in range(L)])
            prior = np.empty(L + 1)
            prior[0] = (h * prev).sum()
            prior[1:] = (1 - h) * prev
            # posterior of the segment mean given the n_r observations of each hypothesis; r_t = 0 uses the prior
            n_t = np.concatenate([[0.0], n])
            S_t = np.concatenate([[0.0], S])
        vp = 1.0 / (1.0 / v0 + n_t / s2)
        mp = vp * (mu0 / v0 + S_t / s2)
        like = stats.norm.pdf(y[t], mp, np.sqrt(vp + s2))
        joint = like * prior
        Z = joint.sum()
        logev += np.log(Z)
        post = joint / Z
        pred_mean[t] = (post * mp).sum()
        P[t, :len(post)] = post
        prev, n, S = post, n_t + 1.0, S_t + y[t]
    return P, pred_mean, logev


def bocpd_changepoints(P, lag=10):
    """Changepoint locations read off the run-length posterior: whenever the MAP run length fails to grow by one, the
    start of the new MAP segment, t - r_t, is taken `lag` steps later (so that it has settled)."""
    T = P.shape[0]
    rh = P.argmax(1)
    found = []
    for t in range(1, T - lag):
        if rh[t] < rh[t - 1]:
            s_hat = (t + lag) - rh[t + lag]
            if s_hat > 0:
                found.append(int(s_hat))
    return sorted(set(found))


def bocpd_data(T=200, seed=3):
    """A piecewise-constant mean series with 4 changepoints, unit-variance noise."""
    rng = np.random.default_rng(seed)
    bounds = [0, 45, 80, 130, 160, T]
    means = np.array([0.0, 3.2, -1.5, 2.5, -3.0])
    mu = np.concatenate([np.full(bounds[i + 1] - bounds[i], means[i]) for i in range(5)])
    return mu + rng.standard_normal(T), mu, bounds[1:-1]


def fig_29_22(out_dir=None):
    """Bayesian online changepoint detection on a piecewise-constant series."""
    y, mu, cps = bocpd_data()
    T = len(y)
    H = 4.0 / T
    P, pm, logev = bocpd_gaussian(y, H)
    pcp = P[:, 0]
    est = bocpd_changepoints(P)
    fig, ax = plt.subplots(3, 1, figsize=(8, 6.2), sharex=True, gridspec_kw=dict(height_ratios=[1.2, 0.8, 1.6]))
    ax[0].plot(y, "o-", color="0.3", ms=3, lw=0.7)
    ax[0].step(np.arange(T), mu, where="mid", color=RED, lw=1.5, label="true mean")
    for c in est:
        ax[0].axvline(c, color=BLUE, lw=1.2)
    ax[0].plot([], [], color=BLUE, label="estimated changepoint")
    ax[0].legend(fontsize=8, loc="upper center", ncol=2, bbox_to_anchor=(0.5, 1.28)), ax[0].set_ylabel("$y_t$")
    ax[1].plot(pcp, color=BLUE)
    ax[1].plot(P[:, :3].sum(1), color=GREEN, lw=0.9, label="$p(r_t \\leq 2 | y_{1:t})$")
    ax[1].legend(fontsize=7, loc="upper right")
    for c in cps:
        ax[1].axvline(c, color=RED, ls=":", lw=1)
    ax[1].set_ylabel("$p(r_t=0 | y_{1:t})$")
    ax[2].imshow(np.log10(P.T[:120] + 1e-6), origin="lower", aspect="auto", cmap="Greys", extent=[-0.5, T - 0.5, -0.5, 119.5], vmin=-6, vmax=0)
    ax[2].set_ylabel("run length $r_t$"), ax[2].set_xlabel("time $t$")
    panel_label(ax[0], "a", "lower left"), panel_label(ax[1], "b", "upper left"), panel_label(ax[2], "c (extra)", "upper left")
    savefig(fig, CH, "fig29-22", out_dir)


# =============================================================================== Linear dynamical systems (Sections 29.6 to 29.8)
def kalman_filter(Y, F, H, Q, R, m1, V1, B=None, D=None, U=None, b=None, d=None):
    """Kalman filter for a time-invariant LG-SSM (29.73)-(29.74); H may also be an array (T, Ny, Nz).

    z_1 ~ N(m1, V1) is the prior of the first state. NaN rows of Y are treated as missing. Returns a dict with the
    filtered (mu_f, P_f) and predicted (mu_p, P_p) moments, the log-likelihood, and the innovations (e, S).
    """
    Y = np.asarray(Y, dtype=float)
    T, Ny = Y.shape
    Nz = len(m1)
    Ht = (lambda t: H[t]) if np.ndim(H) == 3 else (lambda t: H)
    Bu = np.zeros((T, Nz)) if B is None else U @ B.T
    Du = np.zeros((T, Ny)) if D is None else U @ D.T
    bb = np.zeros(Nz) if b is None else b
    dd = np.zeros(Ny) if d is None else d
    mu_p, P_p = np.empty((T, Nz)), np.empty((T, Nz, Nz))
    mu_f, P_f = np.empty((T, Nz)), np.empty((T, Nz, Nz))
    E, S = np.zeros((T, Ny)), np.zeros((T, Ny, Ny))
    ll = 0.0
    m, P = np.asarray(m1, float), np.asarray(V1, float)
    for t in range(T):
        if t > 0:
            m = F @ mu_f[t - 1] + Bu[t] + bb
            P = F @ P_f[t - 1] @ F.T + Q
        mu_p[t], P_p[t] = m, P
        if np.any(np.isnan(Y[t])):
            mu_f[t], P_f[t] = m, P
            continue
        Hh = Ht(t)
        e = Y[t] - (Hh @ m + Du[t] + dd)
        St = Hh @ P @ Hh.T + R
        K = np.linalg.solve(St, Hh @ P).T
        mu_f[t] = m + K @ e
        IKH = np.eye(Nz) - K @ Hh
        P_f[t] = IKH @ P @ IKH.T + K @ R @ K.T          # Joseph form
        P_f[t] = 0.5 * (P_f[t] + P_f[t].T)
        E[t], S[t] = e, St
        ll += -0.5 * (Ny * np.log(2 * np.pi) + np.linalg.slogdet(St)[1] + e @ np.linalg.solve(St, e))
    return dict(mu_f=mu_f, P_f=P_f, mu_p=mu_p, P_p=P_p, loglik=ll, e=E, S=S)


def rts_smoother(kf, F):
    """Rauch-Tung-Striebel smoother; returns smoothed moments and the lag-one cross covariances Cov(z_{t+1}, z_t | y_{1:T})."""
    mu_f, P_f, mu_p, P_p = kf["mu_f"], kf["P_f"], kf["mu_p"], kf["P_p"]
    T, Nz = mu_f.shape
    mu_s, P_s = mu_f.copy(), P_f.copy()
    J = np.empty((T - 1, Nz, Nz))
    for t in range(T - 2, -1, -1):
        J[t] = np.linalg.solve(P_p[t + 1], F @ P_f[t]).T            # P_f F' P_p^{-1}
        mu_s[t] = mu_f[t] + J[t] @ (mu_s[t + 1] - mu_p[t + 1])
        P_s[t] = P_f[t] + J[t] @ (P_s[t + 1] - P_p[t + 1]) @ J[t].T
        P_s[t] = 0.5 * (P_s[t] + P_s[t].T)
    cross = np.array([P_s[t + 1] @ J[t].T for t in range(T - 1)])   # Cov(z_{t+1}, z_t | y_{1:T})
    return dict(mu_s=mu_s, P_s=P_s, J=J, cross=cross)


def lgssm_sample(F, H, Q, R, m1, V1, T, rng, B=None, D=None, U=None):
    Nz, Ny = len(m1), H.shape[0]
    z = np.empty((T, Nz))
    y = np.empty((T, Ny))
    Lq = np.linalg.cholesky(Q + 1e-14 * np.eye(Nz))
    Lr = np.linalg.cholesky(R)
    z[0] = m1 + np.linalg.cholesky(V1) @ rng.standard_normal(Nz)
    for t in range(T):
        if t > 0:
            z[t] = F @ z[t - 1] + (0 if B is None else B @ U[t]) + Lq @ rng.standard_normal(Nz)
        y[t] = H @ z[t] + (0 if D is None else D @ U[t]) + Lr @ rng.standard_normal(Ny)
    return z, y


def cv_model(dt=1.0, q=(0.1, 0.1), sig=(1.0, 1.0)):
    """Constant-velocity tracking model (29.81)-(29.82) with state (u, v, udot, vdot); H extracts (u, v).

    Q is the exact discretisation of white-noise acceleration with diffusion coefficients q.
    """
    F = np.array([[1, 0, dt, 0], [0, 1, 0, dt], [0, 0, 1, 0], [0, 0, 0, 1.0]])
    q1, q2 = q
    Q = np.array([[q1 * dt ** 3 / 3, 0, q1 * dt ** 2 / 2, 0], [0, q2 * dt ** 3 / 3, 0, q2 * dt ** 2 / 2],
                  [q1 * dt ** 2 / 2, 0, q1 * dt, 0], [0, q2 * dt ** 2 / 2, 0, q2 * dt]])
    H = np.array([[1, 0, 0, 0], [0, 1, 0, 0.0]])
    R = np.diag(np.square(sig))
    return F, H, Q, R


def fig_29_24(out_dir=None):
    """Recursive least squares: online Bayesian linear regression as a Kalman filter with F = I, Q = 0."""
    rng = np.random.default_rng(3)
    w_true = np.array([-1.5, 0.8])
    T, s2 = 21, 1.0
    x = rng.uniform(-3, 3, T)
    X = np.stack([np.ones(T), x], 1)
    y = X @ w_true + np.sqrt(s2) * rng.standard_normal(T)
    prior_m, prior_V = np.zeros(2), 100.0 * np.eye(2)
    kf = kalman_filter(y[:, None], np.eye(2), X[:, None, :], np.zeros((2, 2)), np.array([[s2]]), prior_m, prior_V)
    mf, Pf = kf["mu_f"], kf["P_f"]
    Vb = np.linalg.inv(np.linalg.inv(prior_V) + X.T @ X / s2)
    mb = Vb @ (X.T @ y / s2)
    fig, ax = plt.subplots(1, 2, figsize=(9.2, 3.3))
    ax[0].plot(x, y, "ko", ms=4)
    xs = np.linspace(-3.2, 3.2, 50)
    ax[0].plot(xs, mb[0] + mb[1] * xs, color=RED, label="batch posterior mean")
    ax[0].set_xlabel("$x$"), ax[0].set_ylabel("$y$"), ax[0].legend(fontsize=8)
    t = np.arange(1, T + 1)
    for j, col in enumerate((BLUE, GREEN)):
        sd = np.sqrt(Pf[:, j, j])
        ax[1].plot(t, mf[:, j], color=col, label="$w_%d$" % j)
        ax[1].fill_between(t, mf[:, j] - sd, mf[:, j] + sd, color=col, alpha=0.2)
        ax[1].axhline(mb[j], color=col, ls="--", lw=1)
    ax[1].set_ylim(-4, 3), ax[1].set_xlabel("number of data points seen"), ax[1].legend(fontsize=8)
    ax[1].set_ylabel("posterior mean $\\pm$ 1 sd")
    panel_label(ax[0], "a", "upper left"), panel_label(ax[1], "b", "lower right")
    savefig(fig, CH, "fig29-24", out_dir)


def fig_29_26(out_dir=None):
    """Kalman filtering and smoothing of four independent moving objects, in parallel."""
    F, H, Q, R = cv_model(1.0, (0.004, 0.004), (1.0, 1.0))
    rng = np.random.default_rng(6)
    T = 30
    fig, ax = plt.subplots(1, 3, figsize=(11.5, 3.5), sharex=True, sharey=True)
    cols = [RED, BLUE, GREEN, ORANGE]
    for i in range(4):
        m1 = np.array([2.0 * i, 8.0 - 2.5 * i, 0.4 + 0.3 * i, 0.5 * ((-1) ** i) * (0.6 + 0.2 * i)])
        z, y = lgssm_sample(F, H, Q, R, m1, 0.05 * np.eye(4), T, rng)
        kf = kalman_filter(y, F, H, Q, R, m1, 0.5 * np.eye(4))
        sm = rts_smoother(kf, F)
        ax[0].plot(y[:, 0], y[:, 1], "o", color=cols[i], ms=3, alpha=0.7, label="trajectory %d" % (i + 1))
        ax[0].plot(z[:, 0], z[:, 1], "-", color=cols[i], lw=1)
        for a, mu, P in ((ax[1], kf["mu_f"], kf["P_f"]), (ax[2], sm["mu_s"], sm["P_s"])):
            a.plot(mu[:, 0], mu[:, 1], "-", color=cols[i], lw=1.6)
            for t in range(0, T, 3):
                ex, ey = common.ellipse_xy(mu[t, :2], P[t][:2, :2], nsd=2.0)
                a.plot(ex, ey, color=cols[i], lw=0.7)
    ax[0].legend(fontsize=7, loc="lower right")
    for a, ttl in zip(ax, ("data", "filtered posterior", "smoothed posterior")):
        a.set_title(ttl, fontsize=10), a.set_xlabel("$u$")
    ax[0].set_ylabel("$v$")
    savefig(fig, CH, "fig29-26", out_dir)


# =============================================================================== EM for LDS (Section 29.8.1), Poisson LDS (Section 29.11.1)
def lds_estep_moments(kf, sm, F):
    """Expected sufficient statistics (29.92)-(29.93): z_hat, P_t = E[z z'], P_{t,t-1} = E[z_t z_{t-1}']."""
    zh = sm["mu_s"]
    P = sm["P_s"] + np.einsum("ti,tj->tij", zh, zh)
    Pc = sm["cross"] + np.einsum("ti,tj->tij", zh[1:], zh[:-1])
    return zh, P, Pc


def lds_em_step(Y, U, F, H, Q, R, B, D, m1, V1):
    """One EM iteration for z_t = F z_{t-1} + B u_t + q_t, y_t = H z_t + D u_t + r_t, using (29.95)-(29.108).

    U is (T, Nu) (bias terms are included by a constant column) or None. Returns the updated parameters and the
    log-likelihood of the parameters BEFORE the update.
    """
    T, Ny = Y.shape
    Nz = len(m1)
    if U is None:
        U = np.zeros((T, 0))
        B = np.zeros((Nz, 0))
        D = np.zeros((Ny, 0))
    kf = kalman_filter(Y, F, H, Q, R, m1, V1, B=B if B.shape[1] else None, D=D if D.shape[1] else None, U=U)
    # the smoother needs the input-driven offsets in the prediction; they cancel in the RTS recursion because
    # the predicted means already contain B u_t
    sm = rts_smoother(kf, F)
    zh, P, Pc = lds_estep_moments(kf, sm, F)
    Nu = U.shape[1]
    # output matrices [H, D]: (29.97), noise: (29.99)
    Pout = np.zeros((Nz + Nu, Nz + Nu))
    Syx = np.zeros((Ny, Nz + Nu))
    for t in range(T):
        xo = np.concatenate([zh[t], U[t]])
        Pout[:Nz, :Nz] += P[t]
        Pout[:Nz, Nz:] += np.outer(zh[t], U[t])
        Pout[Nz:, :Nz] += np.outer(U[t], zh[t])
        Pout[Nz:, Nz:] += np.outer(U[t], U[t])
        Syx += np.outer(Y[t], xo)
    Aout = Syx @ np.linalg.inv(Pout)
    R_new = (Y.T @ Y - Aout @ Syx.T) / T
    # dynamics [F, B]: (29.101), noise (29.104)
    Pdyn = np.zeros((Nz + Nu, Nz + Nu))
    Szx = np.zeros((Nz, Nz + Nu))
    for t in range(1, T):
        Pdyn[:Nz, :Nz] += P[t - 1]
        Pdyn[:Nz, Nz:] += np.outer(zh[t - 1], U[t])
        Pdyn[Nz:, :Nz] += np.outer(U[t], zh[t - 1])
        Pdyn[Nz:, Nz:] += np.outer(U[t], U[t])
        Szx[:, :Nz] += Pc[t - 1]
        Szx[:, Nz:] += np.outer(zh[t], U[t])
    Adyn = Szx @ np.linalg.inv(Pdyn)
    Q_new = (P[1:].sum(0) - Adyn @ Szx.T) / (T - 1)
    m1_new = zh[0]
    V1_new = P[0] - np.outer(zh[0], zh[0])
    sym = lambda M: 0.5 * (M + M.T)
    return dict(F=Adyn[:, :Nz], B=Adyn[:, Nz:], H=Aout[:, :Nz], D=Aout[:, Nz:], Q=sym(Q_new), R=sym(R_new), m1=m1_new, V1=sym(V1_new)), kf["loglik"]


def rotation(theta):
    return np.array([[np.cos(theta), -np.sin(theta)], [np.sin(theta), np.cos(theta)]])


def poisson_lds_model(seed=0, rho=0.97, theta=0.35, q=0.05, D=5):
    rng = np.random.default_rng(seed)
    A = rho * rotation(theta)
    W = 0.9 * rng.standard_normal((D, 2))
    return dict(A=A, Q=q * np.eye(2), W=W, m1=np.zeros(2), V1=np.eye(2) * 0.5)


def poisson_lds_sample(M, T, rng):
    z = np.empty((T, 2))
    z[0] = M["m1"] + np.linalg.cholesky(M["V1"]) @ rng.standard_normal(2)
    L = np.linalg.cholesky(M["Q"])
    for t in range(1, T):
        z[t] = M["A"] @ z[t - 1] + L @ rng.standard_normal(2)
    return z, rng.poisson(np.exp(z @ M["W"].T))


def poisson_lds_mode(Y, M, Z0=None, n_newton=40):
    """Laplace approximation of p(z_{1:T} | y_{1:T}): the mode by Newton's method and the block-tridiagonal precision.

    Returns the mode (T, Nz), the posterior covariance (dense, (T Nz)^2), and the log joint at the mode.
    """
    T, D = Y.shape
    Nz = M["A"].shape[0]
    A, Qi, W = M["A"], np.linalg.inv(M["Q"]), M["W"]
    V1i = np.linalg.inv(M["V1"])
    Z = np.zeros((T, Nz)) if Z0 is None else Z0.copy()

    def logjoint(Z):
        r = Z[1:] - Z[:-1] @ A.T
        lp = -0.5 * np.einsum("ti,ij,tj->", r, Qi, r) - 0.5 * (Z[0] - M["m1"]) @ V1i @ (Z[0] - M["m1"])
        eta = np.clip(Z @ W.T, -30, 30)
        return lp + np.sum(Y * eta - np.exp(eta))

    def grad_prec(Z):
        eta = np.clip(Z @ W.T, -30, 30)
        lam = np.exp(eta)
        g = (Y - lam) @ W
        r = Z[1:] - Z[:-1] @ A.T
        g[1:] -= r @ Qi
        g[:-1] += r @ Qi @ A
        g[0] -= V1i @ (Z[0] - M["m1"])
        Lam = np.zeros((T * Nz, T * Nz))
        for t in range(T):
            blk = (W.T * lam[t]) @ W
            blk = blk + (V1i if t == 0 else Qi) + (A.T @ Qi @ A if t < T - 1 else 0)
            Lam[t * Nz:(t + 1) * Nz, t * Nz:(t + 1) * Nz] = blk
            if t > 0:
                Lam[t * Nz:(t + 1) * Nz, (t - 1) * Nz:t * Nz] = -Qi @ A
                Lam[(t - 1) * Nz:t * Nz, t * Nz:(t + 1) * Nz] = -A.T @ Qi
        return g, Lam

    f = logjoint(Z)
    for _ in range(n_newton):
        g, Lam = grad_prec(Z)
        step = np.linalg.solve(Lam, g.ravel()).reshape(T, Nz)
        s = 1.0
        while s > 1e-6:
            Zn = Z + s * step
            fn = logjoint(Zn)
            if fn >= f - 1e-12:
                break
            s *= 0.5
        Z, fold, f = Zn, f, fn
        if abs(f - fold) < 1e-9:
            break
    g, Lam = grad_prec(Z)
    return Z, np.linalg.inv(Lam), f


def poisson_lds_em(Y, M0, n_iter=60, Z0=None):
    """EM for the Poisson LDS (29.128): E step = Laplace approximation of the whole trajectory (Gaussian with the
    mode as mean and the inverse Hessian as covariance), then the Kalman-smoother M step (29.101)-(29.108) for A, Q,
    m1, V1, and a few Newton steps on the expected Poisson log-likelihood for the rows of W."""
    M = {k: v.copy() for k, v in M0.items()}
    T, D = Y.shape
    Nz = M["A"].shape[0]
    Z = Z0
    hist = []
    for it in range(n_iter):
        Z, Sig, lj = poisson_lds_mode(Y, M, Z)
        hist.append(lj)
        S = np.array([Sig[t * Nz:(t + 1) * Nz, t * Nz:(t + 1) * Nz] for t in range(T)])
        C = np.array([Sig[(t + 1) * Nz:(t + 2) * Nz, t * Nz:(t + 1) * Nz] for t in range(T - 1)])      # Cov(z_{t+1}, z_t)
        P = S + np.einsum("ti,tj->tij", Z, Z)
        Pc = C + np.einsum("ti,tj->tij", Z[1:], Z[:-1])
        A = Pc.sum(0) @ np.linalg.inv(P[:-1].sum(0))
        Q = (P[1:].sum(0) - A @ Pc.sum(0).T) / (T - 1)
        M["A"], M["Q"] = A, 0.5 * (Q + Q.T)
        M["m1"], M["V1"] = Z[0], S[0] + 1e-6 * np.eye(Nz)
        for d in range(D):
            w = M["W"][d].copy()
            for _ in range(8):
                v = np.einsum("i,tij,j->t", w, S, w)
                e = np.exp(np.clip(Z @ w + 0.5 * v, -30, 30))
                g = ((Y[:, d] - e)[:, None] * Z).sum(0) - (e[:, None] * (np.einsum("tij,j->ti", S, w))).sum(0)
                Hs = -(e[:, None, None] * (np.einsum("ti,tj->tij", Z + np.einsum("tij,j->ti", S, w), Z + np.einsum("tij,j->ti", S, w)) + S)).sum(0)
                w = w - np.linalg.solve(Hs, g)
            M["W"][d] = w
    return M, Z, hist


def fig_29_30(out_dir=None):
    """Samples from a 2-d LDS with 5 Poisson observation terms."""
    M = poisson_lds_model()
    rng = np.random.default_rng(1)
    T = 200
    z, Y = poisson_lds_sample(M, T, rng)
    fig, ax = plt.subplots(2, 1, figsize=(7.4, 4.4), sharex=True, gridspec_kw=dict(height_ratios=[1, 1.4]))
    ax[0].plot(z[:, 0], color=BLUE, label="$z_1$"), ax[0].plot(z[:, 1], color=RED, label="$z_2$")
    ax[0].set_ylabel("latent state"), ax[0].legend(fontsize=8, ncol=2, loc="upper right")
    for d in range(Y.shape[1]):
        ax[1].plot(np.arange(T), Y[:, d] + 6 * d, drawstyle="steps-mid", lw=0.9, color=STATE_COLS[d % 8])
    ax[1].set_ylabel("counts (each channel shifted by 6)"), ax[1].set_xlabel("time"), ax[1].set_xlim(0, T - 1)
    savefig(fig, CH, "fig29-30", out_dir)


_PLDS_CACHE = os.path.join(CACHE_DIR, "poisson_lds.npz")


def poisson_lds_fit(force=False):
    M = poisson_lds_model()
    rng = np.random.default_rng(1)
    z, Y = poisson_lds_sample(M, 400, rng)
    # start from a rough random model (an exactly known state dimension, a damped rotation guess)
    rng2 = np.random.default_rng(5)
    M0 = dict(A=0.9 * np.eye(2), Q=0.1 * np.eye(2), W=0.5 * rng2.standard_normal((5, 2)), m1=np.zeros(2), V1=np.eye(2))
    Mh, Zh, hist = poisson_lds_em(Y, M0, n_iter=60)
    return M, z, Y, Mh, Zh, hist


def fig_29_31(out_dir=None):
    """Latent trajectory and dynamics matrix of the true and the estimated Poisson LDS."""
    M, z, Y, Mh, Zh, hist = poisson_lds_fit()
    G = np.linalg.lstsq(Zh, z, rcond=None)[0].T           # map the estimated latent space onto the true one
    Ah = G @ Mh["A"] @ np.linalg.inv(G)
    Zh_al = Zh @ G.T
    fig, ax = plt.subplots(1, 2, figsize=(8.6, 3.8), sharex=True, sharey=True)
    g = np.linspace(-2.4, 2.4, 9)
    X, Yg = np.meshgrid(g, g)
    P = np.stack([X.ravel(), Yg.ravel()], 1)
    for a, A, traj, ttl in ((ax[0], M["A"], z, "true model"), (ax[1], Ah, Zh_al, "estimated model (aligned)")):
        d = P @ A.T - P
        a.quiver(P[:, 0], P[:, 1], d[:, 0], d[:, 1], color=GREY, angles="xy", scale_units="xy", scale=1.0, width=0.004)
        a.plot(traj[:, 0], traj[:, 1], color=BLUE, lw=1.1)
        a.plot(*traj[0], "*", color=RED, ms=11, mec="k")
        a.set_title(ttl, fontsize=10), a.set_xlabel("$z_1$"), a.set_aspect("equal")
    ax[0].set_ylabel("$z_2$")
    savefig(fig, CH, "fig29-31", out_dir)


# =============================================================================== Structural time series (Section 29.12)
def sts_matrices(sig, S=12, seasonal=True):
    """Local linear trend plus seasonal model (29.144)-(29.149), state (s_t, ..., s_{t-S+2}, mu_t, delta_t).

    sig = (sigma_y, sigma_mu, sigma_delta, sigma_s). Returns F, H, Q, R.
    """
    sy, smu, sde, ss = sig
    ns = S - 1 if seasonal else 0
    n = ns + 2
    F = np.zeros((n, n))
    if seasonal:
        F[0, :ns] = -1.0
        for i in range(1, ns):
            F[i, i - 1] = 1.0
    F[ns, ns], F[ns, ns + 1], F[ns + 1, ns + 1] = 1.0, 1.0, 1.0
    H = np.zeros((1, n))
    H[0, ns] = 1.0
    if seasonal:
        H[0, 0] = 1.0
    q = np.zeros(n)
    q[ns], q[ns + 1] = smu ** 2, sde ** 2
    if seasonal:
        q[0] = ss ** 2
    return F, H, np.diag(q), np.array([[sy ** 2]])


def sts_prior(y0, n, kappa=1e4, ns=11):
    m1 = np.zeros(n)
    m1[ns] = y0
    return m1, kappa * np.eye(n)


def sts_negloglik(logsig, y, S=12, seasonal=True):
    sig = np.exp(logsig)
    F, H, Q, R = sts_matrices(sig, S, seasonal)
    m1, V1 = sts_prior(np.nanmean(y[:12]), F.shape[0], ns=S - 1 if seasonal else 0)
    return -kalman_filter(y[:, None], F, H, Q, R, m1, V1)["loglik"]


def sts_fit(y, S=12, init=(0.2, 0.2, 0.01, 0.04)):
    r = optimize.minimize(sts_negloglik, np.log(init), args=(y, S), method="Nelder-Mead", options=dict(xatol=1e-4, fatol=1e-6, maxiter=800))
    return np.exp(r.x), -r.fun


def sts_forecast(kf, F, H, Q, R, h):
    """h-step-ahead forecast means and standard deviations of y from the last filtered state (29.150)."""
    m, P = kf["mu_f"][-1], kf["P_f"][-1]
    mu, sd = np.empty(h), np.empty(h)
    for k in range(h):
        m = F @ m
        P = F @ P @ F.T + Q
        mu[k] = (H @ m)[0]
        sd[k] = np.sqrt((H @ P @ H.T + R)[0, 0])
    return mu, sd


def co2_monthly():
    """Monthly mean atmospheric CO2 (ppm), Mauna Loa, March 1958 to December 2001, on a regular monthly grid (NaN = no record).

    The 1966-2019 record of the book is not bundled; this is the weekly series shipped with statsmodels averaged by month.
    """
    import statsmodels.api as sm
    df = sm.datasets.co2.load_pandas().data.dropna()
    m = df["co2"].groupby([df.index.year, df.index.month]).mean()
    full = np.full((2001 - 1958 + 1) * 12, np.nan)
    for (yr, mo), v in m.items():
        full[(yr - 1958) * 12 + mo - 1] = v
    first = np.where(~np.isnan(full))[0][0]
    return full[first:], 1958 + first / 12.0


def fig_29_33(out_dir=None):
    """CO2 at Mauna Loa: a local linear trend plus seasonal model, forecasts of the last 10 years and the learned components."""
    y, t0 = co2_monthly()
    h = 120
    ytr = y[:-h]
    sig, ll = sts_fit(ytr)
    F, H, Q, R = sts_matrices(sig)
    m1, V1 = sts_prior(np.nanmean(ytr[:12]), F.shape[0])
    kf = kalman_filter(ytr[:, None], F, H, Q, R, m1, V1)
    sm = rts_smoother(kf, F)
    mu, sd = sts_forecast(kf, F, H, Q, R, h)
    t = t0 + np.arange(len(y)) / 12.0
    ntr = len(ytr)
    fig = plt.figure(figsize=(11.2, 3.8))
    gs = fig.add_gridspec(2, 2, width_ratios=[1.35, 1])
    ax0 = fig.add_subplot(gs[:, 0])
    ax0.plot(t, y, color="k", lw=1, label="ground truth")
    ax0.plot(t[ntr:], mu, color=ORANGE, lw=1.5, label="forecast (mean $\\pm$ 2 sd)")
    ax0.fill_between(t[ntr:], mu - 2 * sd, mu + 2 * sd, color=ORANGE, alpha=0.3)
    ax0.set_xlabel("year"), ax0.set_ylabel("CO$_2$ (ppm)"), ax0.legend(fontsize=8, loc="upper left")
    ax1, ax2 = fig.add_subplot(gs[0, 1]), fig.add_subplot(gs[1, 1], sharex=None)
    ax1.plot(t[:ntr], sm["mu_s"][:, 11], color=BLUE, lw=1.3), ax1.set_ylabel("trend $\\mu_t$ (ppm)")
    ax2.plot(t[:ntr], sm["mu_s"][:, 0], color=GREEN, lw=0.9), ax2.set_ylabel("seasonal $s_t$ (ppm)"), ax2.set_xlabel("year")
    panel_label(ax0, "a", "lower right"), panel_label(ax1, "b", "lower right"), panel_label(ax2, "c", "lower right")
    savefig(fig, CH, "fig29-33", out_dir)
    return sig, ll


def anomaly_series(seed=4, T=24 * 21):
    """Hourly-like series: local level + 24-step seasonal + noise, with a few injected anomalies."""
    rng = np.random.default_rng(seed)
    S = 24
    sig = (0.3, 0.05, 0.0, 0.01)
    pat = 2.0 * np.sin(2 * np.pi * np.arange(S) / S) + 0.8 * np.sin(4 * np.pi * np.arange(S) / S + 1.0)
    pat -= pat.mean()
    level = 10 + np.cumsum(sig[1] * rng.standard_normal(T))
    seas = np.array([pat[t % S] for t in range(T)])
    y = level + seas + sig[0] * rng.standard_normal(T)
    anom = np.array([100, 190, 260, 330, 430])
    y[anom] += np.array([2.5, -3.0, 2.2, 3.5, -2.8])
    return y, anom, sig, pat


def fig_x29_a(out_dir=None):
    """Anomaly detection from one-step-ahead predictive z-scores (29.150), on a simulated seasonal series."""
    y, anom, sig, pat = anomaly_series()
    S = 24
    F, H, Q, R = sts_matrices((sig[0], sig[1], 1e-4, 1e-3), S=S)
    m1 = np.zeros(F.shape[0])
    m1[S - 1] = y[0]
    V1 = 10.0 * np.eye(F.shape[0])
    kf = kalman_filter(y[:, None], F, H, Q, R, m1, V1)
    z = kf["e"][:, 0] / np.sqrt(kf["S"][:, 0, 0])
    pred = y - kf["e"][:, 0]
    sd = np.sqrt(kf["S"][:, 0, 0])
    T = len(y)
    flag = (np.abs(z) > 3) & (np.arange(T) > 2 * S)
    fig, ax = plt.subplots(2, 1, figsize=(8.4, 4.6), sharex=True)
    ax[0].plot(y, color=BLUE, lw=1, label="observed")
    ax[0].plot(pred, color=ORANGE, lw=1, label="one-step prediction")
    ax[0].fill_between(np.arange(T), pred - 3 * sd, pred + 3 * sd, color=ORANGE, alpha=0.15)
    ax[0].plot(np.where(flag)[0], y[flag], "kx", ms=7, label="flagged ($|z|>3$)")
    ax[0].legend(fontsize=8, ncol=3, loc="upper left"), ax[0].set_ylabel("$y_t$"), ax[0].set_ylim(0, 22)
    ax[1].plot(z, color=GREY, lw=0.9)
    ax[1].axhline(3, color=RED, ls=":", lw=1), ax[1].axhline(-3, color=RED, ls=":", lw=1)
    ax[1].set_ylabel("predictive z-score"), ax[1].set_xlabel("time step")
    savefig(fig, CH, "figx29-a", out_dir)


# =============================================================================== Causal impact (Section 29.12.6)
def causal_data(T=100, n=70, seed=2, effect=10.0):
    rng = np.random.default_rng(seed)
    x = np.empty(T)
    x[0] = rng.standard_normal()
    for t in range(1, T):
        x[t] = 0.9 * x[t - 1] + rng.standard_normal()
    y = 1.2 * x + 0.5 * rng.standard_normal(T)
    y_obs = y.copy()
    y_obs[n:] += effect
    return x, y, y_obs


def causal_model(sig):
    """Local level with slope and a regression coefficient as a static state: state (mu, delta, beta)."""
    sy, smu, sde = sig
    F = np.array([[1, 1, 0], [0, 1, 0], [0, 0, 1.0]])
    Q = np.diag([smu ** 2, sde ** 2, 0.0])
    return F, Q, np.array([[sy ** 2]])


def causal_negloglik(logsig, y, x, n):
    F, Q, R = causal_model(np.exp(logsig))
    Hs = np.stack([np.array([[1.0, 0.0, x[t]]]) for t in range(n)])
    return -kalman_filter(y[:n, None], F, Hs, Q, R, np.array([y[0], 0.0, 0.0]), np.diag([100.0, 1.0, 100.0]))["loglik"]


def causal_impact(x, y_obs, n, sig=None):
    """Counterfactual forecast of y after time n and the pointwise and cumulative impact (mean, sd), all in closed form.

    The joint Gaussian forecast of the whole post-intervention path is built from the filtered state at time n, so the
    cumulative impact variance includes the correlation between the forecasts of different days.
    """
    T = len(y_obs)
    if sig is None:
        r = optimize.minimize(causal_negloglik, np.log([0.5, 0.2, 0.02]), args=(y_obs, x, n), method="Nelder-Mead", options=dict(xatol=1e-4, fatol=1e-6, maxiter=600))
        sig = np.exp(r.x)
    F, Q, R = causal_model(sig)
    Hs = np.stack([np.array([[1.0, 0.0, x[t]]]) for t in range(T)])
    kf = kalman_filter(y_obs[:n, None], F, Hs[:n], Q, R, np.array([y_obs[0], 0.0, 0.0]), np.diag([100.0, 1.0, 100.0]))
    m, P = kf["mu_f"][-1], kf["P_f"][-1]
    k = T - n
    mean_y, Cy = np.empty(k), np.zeros((k, k))
    Ps, mus = [], []
    for i in range(k):
        m = F @ m
        P = F @ P @ F.T + Q
        Ps.append(P.copy()), mus.append(m.copy())
        mean_y[i] = (Hs[n + i] @ m)[0]
    for i in range(k):
        for j in range(i + 1):
            Fp = np.linalg.matrix_power(F, i - j)
            c = (Hs[n + i] @ Fp @ Ps[j] @ Hs[n + j].T)[0, 0]
            Cy[i, j] = Cy[j, i] = c + (R[0, 0] if i == j else 0.0)
    tau = y_obs[n:] - mean_y
    one = np.ones(k)
    cum_mean = np.cumsum(tau)
    cum_sd = np.array([np.sqrt(one[:i + 1] @ Cy[:i + 1, :i + 1] @ one[:i + 1]) for i in range(k)])
    return dict(sig=sig, mean_y=mean_y, Cy=Cy, tau=tau, point_sd=np.sqrt(np.diag(Cy)), cum_mean=cum_mean, cum_sd=cum_sd, kf=kf)


def fig_29_41(out_dir=None):
    """Causal impact of an intervention at t = 70 on simulated data: original series, pointwise and cumulative impact."""
    x, y, y_obs = causal_data()
    n = 70
    ci = causal_impact(x, y_obs, n)
    T = len(y_obs)
    t = np.arange(T)
    fig, ax = plt.subplots(3, 1, figsize=(7.6, 7.2), sharex=True)
    ax[0].plot(t, y_obs, color="k", lw=1.2, label="observed")
    ax[0].plot(t[n:], ci["mean_y"], color=BLUE, lw=1.6, label="counterfactual forecast")
    ax[0].fill_between(t[n:], ci["mean_y"] - 1.96 * ci["point_sd"], ci["mean_y"] + 1.96 * ci["point_sd"], color=BLUE, alpha=0.25)
    ax[0].plot(t, x, color=GREY, lw=0.8, label="covariate $x_t$")
    ax[0].axvline(n, color=RED, ls=":"), ax[0].legend(fontsize=8, loc="upper left"), ax[0].set_ylabel("original series")
    ax[1].plot(t[n:], ci["tau"], color="k", lw=1.2)
    ax[1].fill_between(t[n:], ci["tau"] - 1.96 * ci["point_sd"], ci["tau"] + 1.96 * ci["point_sd"], color=BLUE, alpha=0.25)
    ax[1].axhline(0, color=GREY, lw=0.8), ax[1].axvline(n, color=RED, ls=":"), ax[1].set_ylabel("pointwise impact $\\tau_t$")
    ax[2].plot(t[n:], ci["cum_mean"], color="k", lw=1.2)
    ax[2].fill_between(t[n:], ci["cum_mean"] - 1.96 * ci["cum_sd"], ci["cum_mean"] + 1.96 * ci["cum_sd"], color=BLUE, alpha=0.25)
    ax[2].axhline(0, color=GREY, lw=0.8), ax[2].axvline(n, color=RED, ls=":"), ax[2].set_ylabel("cumulative impact"), ax[2].set_xlabel("time $t$")
    savefig(fig, CH, "fig29-41", out_dir)


# =============================================================================== Supplement: continuous-time SSMs
def spring_mass(m=1.0, b=0.2, c=1.0):
    F = np.array([[0.0, 1.0], [-c / m, -b / m]])
    B = np.array([[0.0], [1.0 / m]])
    Hc = np.array([[1.0, 0.0]])
    return F, B, Hc


def gbt_discretise(F, B, dt, alpha=0.5):
    """Generalised bilinear transform (S29.11): alpha = 0 Euler, 1/2 bilinear, 1 backward Euler."""
    I = np.eye(F.shape[0])
    M = np.linalg.inv(I - alpha * dt * F)
    return M @ (I + (1 - alpha) * dt * F), dt * (M @ B)


def simulate_discrete(Fd, Bd, Hc, u, z0=None):
    z = np.zeros(Fd.shape[0]) if z0 is None else z0
    out = []
    for uk in u:
        z = Fd @ z + (Bd @ np.atleast_1d(uk))
        out.append((Hc @ z)[0])
    return np.array(out)


def fig_S29_3(out_dir=None):
    """Spring-mass system driven by a force: discretisations by Euler, bilinear and the exact (matrix exponential) rule."""
    F, B, Hc = spring_mass()
    dt, T = 0.5, 160
    u = np.zeros(T)
    for s, e in ((10, 20), (60, 70), (110, 125)):
        u[s:e] = np.sin(np.pi * (np.arange(e - s)) / (e - s))
    exact_F = linalg.expm(F * dt)
    exact_B = np.linalg.solve(F, (exact_F - np.eye(2)) @ B)
    Fe, Be = gbt_discretise(F, B, dt, 0.0)
    Fb, Bb = gbt_discretise(F, B, dt, 0.5)
    t = np.arange(T) * dt
    fig, ax = plt.subplots(2, 1, figsize=(7.4, 4.8), sharex=True)
    ax[0].plot(t, u, color=BLUE), ax[0].set_ylabel("force $u(t)$")
    ax[1].plot(t, simulate_discrete(exact_F, exact_B, Hc, u), color="k", lw=1.6, label="exact (zero-order hold)")
    ax[1].plot(t, simulate_discrete(Fb, Bb, Hc, u), color=GREEN, ls="--", lw=1.4, label="bilinear, $\\alpha=1/2$")
    ax[1].plot(t, simulate_discrete(Fe, Be, Hc, u), color=RED, lw=1.0, label="Euler, $\\alpha=0$")
    ax[1].set_ylim(-4, 4), ax[1].set_ylabel("position $x(t)$"), ax[1].set_xlabel("time"), ax[1].legend(fontsize=8, loc="upper left")
    savefig(fig, CH, "figS29-3", out_dir)


def rk2_step(f, z, dt):
    k1 = f(z)
    k2 = f(z + dt * k1)
    return z + 0.5 * dt * (k1 + k2)


def rk2_flow(f, z, T, h):
    for _ in range(int(round(T / h))):
        z = rk2_step(f, z, h)
    return z


def circle_f(z):
    return np.array([z[1], -z[0]])


def fig_S29_4(out_dir=None):
    """Kalman filtering of noisy observations of a particle moving on a circle in continuous time."""
    rng = np.random.default_rng(2)
    K, T, h = 70, 7.5, 0.01
    Fc = np.array([[0.0, 1.0], [-1.0, 0.0]])
    dt = T / K
    steps = int(round(dt / h))
    z = np.array([1.0, 0.0])
    Z = []
    for _ in range(K):
        for _ in range(steps):
            z = rk2_step(circle_f, z, h)
        Z.append(z.copy())
    Z = np.array(Z)
    R = 0.01 * np.eye(2)
    y = Z + 0.1 * rng.standard_normal(Z.shape)
    Fd = linalg.expm(Fc * dt)
    kf = kalman_filter(y, Fd, np.eye(2), 0.001 * np.eye(2), R, np.array([1.0, 0.0]), 0.1 * np.eye(2))
    fig, ax = plt.subplots(1, 2, figsize=(8.4, 3.8), sharex=True, sharey=True)
    ax[0].plot(Z[:, 0], Z[:, 1], color=BLUE, label="state space"), ax[0].plot(y[:, 0], y[:, 1], "+", color=GREEN, label="observations")
    ax[1].plot(kf["mu_f"][:, 0], kf["mu_f"][:, 1], color=RED, label="Kalman filter")
    ax[1].plot(y[:, 0], y[:, 1], "+", color=GREEN)
    for t in range(0, K, 6):
        ex, ey = common.ellipse_xy(kf["mu_f"][t], kf["P_f"][t], nsd=2.0)
        ax[1].plot(ex, ey, color="k", lw=0.7)
    for a, ttl in zip(ax, ("(a) true state and data", "(b) filtered estimate")):
        a.set_title(ttl, fontsize=10), a.set_aspect("equal"), a.legend(fontsize=8, loc="upper right"), a.set_xlabel("$z_1$")
    ax[0].set_ylabel("$z_2$")
    savefig(fig, CH, "figS29-4", out_dir)


def duffing_f(z):
    return np.array([z[1], z[0] - z[0] ** 3])


def ekf_predict_flow(m, P, Qd, dt, h=0.01):
    """EKF prediction for a continuous-time ODE: integrate the mean with RK2 and the state-transition Jacobian along the path."""
    Phi = np.eye(2)
    z = m.copy()
    for _ in range(int(round(dt / h))):
        J = np.array([[0.0, 1.0], [1.0 - 3.0 * z[0] ** 2, 0.0]])
        Phi = (np.eye(2) + h * J + 0.5 * h * h * J @ J) @ Phi
        z = rk2_step(duffing_f, z, h)
    return z, Phi @ P @ Phi.T + Qd


def fig_S29_5(out_dir=None):
    """Extended Kalman filter for a particle in a double-well potential, observed with noise at 70 times."""
    rng = np.random.default_rng(3)
    K, T, h = 70, 7.5, 0.01
    dt = T / K
    z = np.array([-1.2, 0.8])
    Z = []
    for _ in range(K):
        for _ in range(int(round(dt / h))):
            z = rk2_step(duffing_f, z, h)
        Z.append(z.copy())
    Z = np.array(Z)
    R = 0.04 * np.eye(2)
    y = Z + 0.2 * rng.standard_normal(Z.shape)
    m, P = np.array([-1.2, 0.8]), 0.1 * np.eye(2)
    Qd = 0.001 * np.eye(2)
    M = []
    Ps = []
    for k in range(K):
        m, P = ekf_predict_flow(m, P, Qd, dt)
        S = P + R
        Kg = P @ np.linalg.inv(S)
        m = m + Kg @ (y[k] - m)
        P = (np.eye(2) - Kg) @ P
        M.append(m.copy()), Ps.append(P.copy())
    M = np.array(M)
    fig, ax = plt.subplots(1, 2, figsize=(8.6, 3.8), sharex=True, sharey=True)
    g = np.linspace(-1.7, 1.7, 15)
    X, Yg = np.meshgrid(g, g)
    for a in ax:
        v = np.stack([X.ravel(), Yg.ravel()], 1)
        d = np.array([duffing_f(p) for p in v])
        a.quiver(v[:, 0], v[:, 1], d[:, 0], d[:, 1], color="0.8", angles="xy", width=0.003)
    ax[0].plot(Z[:, 0], Z[:, 1], color=BLUE, label="state space"), ax[0].plot(y[:, 0], y[:, 1], "+", color=GREEN, label="observations")
    ax[1].plot(M[:, 0], M[:, 1], color=RED, label="EKF estimate"), ax[1].plot(y[:, 0], y[:, 1], "+", color=GREEN)
    for t in range(0, K, 5):
        ex, ey = common.ellipse_xy(M[t], Ps[t], nsd=2.0)
        ax[1].plot(ex, ey, color="k", lw=0.7)
    for a, ttl in zip(ax, ("(a) true state and data", "(b) EKF estimate")):
        a.set_title(ttl, fontsize=10), a.legend(fontsize=8, loc="lower right"), a.set_xlabel("$z_1$"), a.set_xlim(-1.7, 1.7), a.set_ylim(-1.7, 1.7)
    ax[0].set_ylabel("$z_2$")
    savefig(fig, CH, "figS29-5", out_dir)


# =============================================================================== data for the browser demonstrations
def baum_welch_single(y, K, V, A0, B0, pi0, n_iter):
    """Baum-Welch on one sequence; returns the history of the TOTAL log-likelihood (n_iter + 1 values) and the final parameters."""
    Y = np.asarray(y)[None, :]
    A, B, pi, h = baum_welch_discrete(Y, K, V, A0, B0, pi0, n_iter=n_iter)
    return -h * Y.size, A, B, pi


def demo_casino_init():
    """The default (deliberately poor) start used by the Baum-Welch demonstration."""
    A0 = np.array([[0.6, 0.4], [0.4, 0.6]])
    B0 = np.array([[0.20, 0.18, 0.16, 0.16, 0.15, 0.15], [0.12, 0.14, 0.16, 0.18, 0.20, 0.20]])
    return A0, B0, np.array([0.5, 0.5])


def export_demo_data():
    # === Baum-Welch demo
    A, B, pi = casino_true()
    rng = np.random.default_rng(21)
    z, y = sample_discrete_hmm(A, B, pi, 1000, rng)
    A0, B0, pi0 = demo_casino_init()
    ll, Af, Bf, pif = baum_welch_single(y[:300], 2, 6, A0, B0, pi0, 100)
    lik = discrete_lik(y[None, :300], B)
    ll_true = float(hmm_estep(lik, A, pi)[2])
    zv, _ = hmm_viterbi(lik[0], A, pi)
    save_json("ch29-casino.json", dict(y=(y + 1).tolist(), z=z.tolist(), A_true=A.tolist(), B_true=B.tolist(), pi_true=pi.tolist(),
                                       A0=A0.tolist(), B0=B0.tolist(), pi0=pi0.tolist(),
                                       ref=dict(T=300, loglik=[float(v) for v in ll[[0, 1, 2, 5, 10, 20, 50, 100]]], iters=[0, 1, 2, 5, 10, 20, 50, 100],
                                                A100=Af.tolist(), B100=Bf.tolist(), pi100=pif.tolist(), loglik_true_params=ll_true,
                                                viterbi_errors=int((zv != z[:300]).sum()))))
    # === BOCPD demo
    yb, mu, cps = bocpd_data()
    yb = np.round(yb, 5)
    P, pm, le = bocpd_gaussian(yb, 0.02)
    rng = np.random.default_rng(5)
    ynull = np.round(rng.standard_normal(200), 5)
    Pn, _, len_ = bocpd_gaussian(ynull, 0.02)
    P2, _, le2 = bocpd_gaussian(yb, 0.1, v0=1.0)
    save_json("ch29-bocpd.json", dict(y=yb.tolist(), mu=mu.tolist(), changepoints=cps, y_null=ynull.tolist(),
                                      ref=dict(hazard=0.02, mu0=0.0, v0=4.0, s2=1.0, logev=float(le), p_cp_at=[[t, float(P[t, 0])] for t in (45, 80, 130, 160)],
                                               map_rl_at=[[t, int(P[t].argmax())] for t in (44, 60, 100, 150, 199)], estimated=bocpd_changepoints(P),
                                               logev_null=float(len_), logev_h01_v1=float(le2))))
    # === STS demo
    yc, t0 = co2_monthly()
    yc = np.round(yc, 3)                              # the demonstration reads the rounded values
    h = 120
    ytr = yc[:-h]
    sig, ll = sts_fit(ytr)
    out = dict(t0=t0, y=[None if np.isnan(v) else round(float(v), 3) for v in yc], n_train=len(ytr), sig_ml=[float(v) for v in sig], loglik_ml=float(ll), ref={})
    for name, s in (("ml", (0.168, 0.214, 0.002, 1e-4)), ("rigid", (0.17, 0.02, 1e-4, 1e-4)), ("flexible", (0.17, 0.6, 0.05, 1e-4)), ("evolving", (0.17, 0.2, 0.002, 0.1))):
        s = tuple(float(v) for v in s)
        F, H, Q, R = sts_matrices(s)
        m1, V1 = sts_prior(np.nanmean(ytr[:12]), F.shape[0])
        kf = kalman_filter(ytr[:, None], F, H, Q, R, m1, V1)
        mu, sd = sts_forecast(kf, F, H, Q, R, h)
        rmse = float(np.sqrt(np.nanmean((mu - yc[-h:]) ** 2)))
        out["ref"][name] = dict(sig=list(s), loglik=float(kf["loglik"]), fc_mean_last=float(mu[-1]), fc_sd_last=float(sd[-1]), rmse=rmse,
                                level_last=float(kf["mu_f"][-1, 11]), slope_last=float(kf["mu_f"][-1, 12]))
    save_json("ch29-sts.json", out)


def data_demo(out_dir=None):
    """Export the small data sets used by the demonstration pages."""
    export_demo_data()


FIGURES = {
    "29.2": fig_29_2, "29.3": fig_29_3, "29.4": fig_29_4, "29.5": fig_29_5, "29.6": fig_29_6, "29.7": fig_29_7, "29.8": fig_29_8,
    "29.13": fig_29_13, "29.14": fig_29_14, "29.15": fig_29_15, "29.22": fig_29_22, "29.24": fig_29_24, "29.26": fig_29_26,
    "29.30": fig_29_30, "29.31": fig_29_31, "29.33": fig_29_33, "29.41": fig_29_41,
    "S29.3": fig_S29_3, "S29.4": fig_S29_4, "S29.5": fig_S29_5, "x29.a": fig_x29_a, "data": data_demo,
}

if __name__ == "__main__":
    if len(sys.argv) == 1:
        common.run(FIGURES, CH, [])
    else:
        common.run(FIGURES, CH)
