"""Chapter 10 of Wasserman (2006), All of Nonparametric Statistics: Other Topics.

The chapter has two figures:

* Figure 10.2  the SIMEX extrapolation of the attenuated least squares slope back to rho = -1; the book
               draws a sketch, reproduced here from a simulated errors-in-variables data set.

Skipped:

* Figure 10.1 is a directed graph (X -> Y, X -> X*), a diagram with nothing computed.

The chapter surveys ten topics in a few pages and its exercises are computational, so this module also
makes supplementary figures (named fig10-S1, ...) for the lecture notes:

* S1  Exercise 5: kernel regression with measurement error (true X, naive, the small-sigma correction
      (10.14), SIMEX, and a bandwidth chosen from the observed data only), and the excess bias (10.3);
* S2  Exercise 4: naive, deconvolving and small-sigma corrected kernel density estimates (Normal and
      Cauchy measurement errors) and their exact integrated risks;
* S3  how slowly deconvolution converges: the best integrated risk against n for Normal and Laplace errors,
      and the optimal bandwidth against sigma_u / sqrt(log n);
* S4  Exercise 6: the Backus-Gilbert averaging kernels and regularised estimates of a blurred regression;
* S5  the partially linear model (10.29): naive and double-residual estimates of beta;
* S6  correlated errors: leave-one-out against leave-block-out cross-validation;
* S7  classification: a plug-in rule can be good while the regression estimate is poor;
* S8  a cosine sieve: the risk against the sieve dimension and the growth of the best dimension with n;
* S9  isotonic regression: the pool-adjacent-violators fit, the greatest convex minorant, the n^(-1/3) rate;
* S10 Ingster's detection boundary in the Normal means model (p = 2): exact power and a lower bound;
* S11 Exercise 7: frequentist coverage of Bayesian credible balls in the infinite Normal means model.

Every method the chapter discusses is implemented here from scratch: the method of moments and SIMEX
corrections (with linear and rational extrapolants), kernel and local linear smoothers with their
cross-validation scores, Fourier deconvolution, Tikhonov-regularised inversion with its leave-one-out score,
the double-residual estimator, pool-adjacent-violators, and the conjugate Normal means posterior.
The interactive demonstrations draw their random numbers with DK.rng (mulberry32 with Box-Muller); the
functions js_uniforms / js_normals reproduce those streams exactly.

Usage: python ch10_other_topics.py [--fig 10.2 S1 ...]
"""
import os

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import numpy as np
from scipy.stats import norm, ncx2

import common
from common import BLUE, RED, GREEN, GREY, ORANGE, PURPLE, savefig, run

import matplotlib.pyplot as plt

CH = 10
HERE = os.path.dirname(os.path.abspath(__file__))
M32 = 0xFFFFFFFF


# =========================================================================== DK.rng-compatible streams
def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed) (mulberry32): the j-th output is a hash of
    seed + j * 0x6D2B79F5."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


def js_normals(seed, n):
    """The first n values of DK.rng(seed).norm() (Box-Muller: cosine then sine of each pair)."""
    k = (n + 1) // 2
    u = js_uniforms(seed, 2 * k)
    r = np.sqrt(-2.0 * np.log(u[0::2]))
    th = 2 * np.pi * u[1::2]
    out = np.empty(2 * k)
    out[0::2], out[1::2] = r * np.cos(th), r * np.sin(th)
    return out[:n]


# =========================================================================== 10.1 linear measurement error
RHOS = np.arange(0, 2.0001, 0.25)          # the SIMEX grid used in the figure and the demo


def ls_slope(x, y):
    xc = x - x.mean()
    return float(xc @ (y - y.mean()) / (xc @ xc))


def eiv_data(seed, n, su, sx=1.0, se=0.5, b0=0.0, b1=1.0):
    """The errors-in-variables sample of the SIMEX demo: X ~ N(0, sx^2), Y = b0 + b1 X + eps,
    W = X + U with U ~ N(0, su^2). Draw order: n normals for X, n for eps, n for U."""
    z = js_normals(seed, 3 * n)
    X = sx * z[:n]
    Y = b0 + b1 * X + se * z[n:2 * n]
    W = X + su * z[2 * n:]
    return X, W, Y


def simex_omegas(seed, n, su, B, W, Y, rhos=RHOS):
    """Omega_hat(rho) = mean over b of the slope of Y on W + sqrt(rho) su U*_b, U*_b ~ N(0,1).
    The pseudo-errors continue the same DK.rng stream after the 3n normals of the data."""
    z = js_normals(seed, 3 * n + (len(rhos) - 1) * B * n)[3 * n:]
    out = [ls_slope(W, Y)]
    k = 0
    for rho in rhos[1:]:
        s = 0.0
        for b in range(B):
            s += ls_slope(W + np.sqrt(rho) * su * z[k:k + n], Y)
            k += n
        out.append(s / B)
    return np.array(out)


def fit_quadratic(rhos, om):
    """Least squares fit of gamma1 + gamma2 rho + gamma3 rho^2; returns the coefficients."""
    A = np.vstack([np.ones_like(rhos), rhos, rhos ** 2]).T
    return np.linalg.lstsq(A, om, rcond=None)[0]


def _rational_ls(rhos, om, g3):
    A = np.vstack([np.ones_like(rhos), 1.0 / (g3 + rhos)]).T
    g, *_ = np.linalg.lstsq(A, om, rcond=None)
    return g, float(np.sum((A @ g - om) ** 2))


def fit_rational(rhos, om):
    """Least squares fit of G(rho) = gamma1 + gamma2 / (gamma3 + rho) (10.7) with gamma3 > 1 (so that
    G(-1) is finite): for fixed gamma3 the model is linear, so profile out (gamma1, gamma2) and search
    gamma3 on a log grid of gamma3 - 1, then refine by golden section. Returns (g1, g2, g3)."""
    ts = np.linspace(np.log(1e-3), np.log(1e4), 241)
    sse = np.array([_rational_ls(rhos, om, 1 + np.exp(t))[1] for t in ts])
    i = int(np.argmin(sse))
    a, b = ts[max(i - 1, 0)], ts[min(i + 1, len(ts) - 1)]
    gr = (np.sqrt(5) - 1) / 2
    c, d = b - gr * (b - a), a + gr * (b - a)
    fc, fd = _rational_ls(rhos, om, 1 + np.exp(c))[1], _rational_ls(rhos, om, 1 + np.exp(d))[1]
    for _ in range(80):
        if fc < fd:
            b, d, fd = d, c, fc
            c = b - gr * (b - a)
            fc = _rational_ls(rhos, om, 1 + np.exp(c))[1]
        else:
            a, c, fc = c, d, fd
            d = a + gr * (b - a)
            fd = _rational_ls(rhos, om, 1 + np.exp(d))[1]
    g3 = 1 + np.exp((a + b) / 2)
    g, _ = _rational_ls(rhos, om, g3)
    return float(g[0]), float(g[1]), float(g3)


def simex_all(seed, n, su, B, sx=1.0, se=0.5):
    """Everything the SIMEX demo reports for one data set."""
    X, W, Y = eiv_data(seed, n, su, sx, se)
    om = simex_omegas(seed, n, su, B, W, Y)
    q = fit_quadratic(RHOS, om)
    g1, g2, g3 = fit_rational(RHOS, om)
    s2w = float(np.var(W, ddof=1))
    lam = (s2w - su ** 2) / s2w
    return dict(naive=om[0], lam=lam, mom=om[0] / lam, simex_q=q[0] - q[1] + q[2],
                simex_r=g1 + g2 / (g3 - 1), oracle=ls_slope(X, Y), omegas=om, quad=q, rat=(g1, g2, g3))


def simex_quadratic_limit(lam_ratio, rhos=RHOS, b1=1.0):
    """Large-sample limit of the quadratic SIMEX estimate when sigma_u^2 / sigma_x^2 = lam_ratio."""
    om = b1 / (1 + (1 + rhos) * lam_ratio)
    q = fit_quadratic(rhos, om)
    return q[0] - q[1] + q[2]


FIG102 = dict(seed=1002, n=500, su=0.7, B=100)


def fig_10_2(out=None):
    """SIMEX: Omega_hat(rho) and its extrapolation to rho = -1."""
    p = FIG102
    r = simex_all(p["seed"], p["n"], p["su"], p["B"])
    fig, ax = plt.subplots(figsize=(6.2, 4.0))
    rr = np.linspace(-1, 2.1, 300)
    lam_ratio = p["su"] ** 2
    ax.plot(rr, 1 / (1 + (1 + rr) * lam_ratio), color=GREY, lw=1, ls=":", label=r"large-sample limit $\Omega(\rho)$")
    q = r["quad"]
    g1, g2, g3 = r["rat"]
    on = rr >= 0
    ax.plot(rr[on], q[0] + q[1] * rr[on] + q[2] * rr[on] ** 2, color=BLUE, lw=1.8)
    ax.plot(rr[~on], q[0] + q[1] * rr[~on] + q[2] * rr[~on] ** 2, color=BLUE, lw=1.8, ls="--",
            label="quadratic extrapolant")
    ax.plot(rr, g1 + g2 / (g3 + rr), color=GREEN, lw=1.4, ls="-.", label="rational extrapolant (10.7)")
    ax.plot(RHOS, r["omegas"], "o", color="k", ms=5, label=r"$\widehat\Omega(\rho_j)$, B = %d" % p["B"])
    ax.plot([0], [r["naive"]], "o", color=RED, ms=8, zorder=5)
    ax.annotate("uncorrected least squares %.3f" % r["naive"], (0, r["naive"]), (0.25, r["naive"] + 0.12),
                fontsize=9, arrowprops=dict(arrowstyle="-", color=GREY))
    ax.plot([-1], [r["simex_q"]], "s", color=BLUE, ms=7, zorder=5)
    ax.plot([-1], [r["simex_r"]], "D", color=GREEN, ms=6, zorder=5)
    ax.annotate("SIMEX: quadratic %.3f, rational %.3f" % (r["simex_q"], r["simex_r"]), (-1, r["simex_q"]),
                (-0.9, 1.1), fontsize=9)
    ax.axhline(1.0, color=RED, lw=0.8, ls=(0, (2, 2)))
    ax.text(1.95, 1.01, r"true $\beta_1 = 1$", ha="right", va="bottom", fontsize=9, color=RED)
    ax.axvline(0, color=GREY, lw=0.6)
    ax.set_xlabel(r"$\rho$ (added measurement error variance, in units of $\sigma_u^2$)")
    ax.set_ylabel(r"$\widehat\Omega(\rho)$")
    ax.set_xlim(-1.15, 2.1)
    ax.set_ylim(0.15, 1.3)
    ax.legend(loc="lower left", fontsize=8.5, frameon=False)
    savefig(fig, CH, "fig10-2", out)
    return r


# =========================================================================== kernel regression helpers
def nw_weights(xe, x, h):
    """Unnormalised Gaussian kernel weights K((xe - x_j) / h), shape (len(xe), len(x))."""
    return np.exp(-0.5 * ((xe[:, None] - x[None, :]) / h) ** 2)


def nw(xe, x, y, h):
    K = nw_weights(xe, x, h)
    return (K @ y) / K.sum(1)


def nw_loocv(x, y, h):
    K = nw_weights(x, x, h)
    np.fill_diagonal(K, 0.0)
    return float(np.mean((y - (K @ y) / K.sum(1)) ** 2))


def nw_meas_correction(xe, W, h, su, yfill):
    """Small-sigma correction (10.11)-(10.14) of the Nadaraya-Watson estimator, keeping the dependence of
    every weight on every W_i: b(x) = su^2/2 * sum_i d^2 r_hat(x) / d W_i^2, which equals
    su^2/2 * sum_i (y_i - r_hat(x)) [b_i / D - 2 a_i^2 / D^2] with a_i, b_i the first and second derivatives
    of K((x - W_i)/h) in W_i and D = sum_i K. The unknown r(W_i) is replaced by yfill (a pilot fit)."""
    u = (xe[:, None] - W[None, :]) / h
    K = np.exp(-0.5 * u * u)
    D = K.sum(1)
    a = (u / h) * K
    b = (u * u - 1) / h ** 2 * K
    rhat = (K @ yfill) / D
    lap = ((yfill[None, :] - rhat[:, None]) * (b / D[:, None] - 2 * a * a / D[:, None] ** 2)).sum(1)
    return 0.5 * su ** 2 * lap


def nw_meas_correction_literal(xe, W, h, su, yfill):
    """The correction read literally from (10.13): su^2/2 sum_i r(W_i) l_i''(x, W_i), differentiating only
    the numerator weight K((x - W_i)/h) and keeping the normaliser fixed."""
    u = (xe[:, None] - W[None, :]) / h
    K = np.exp(-0.5 * u * u)
    b = (u * u - 1) / h ** 2 * K
    return 0.5 * su ** 2 * (b @ yfill) / K.sum(1)


def r_ex5(x):
    return x + 3 * np.exp(-16 * x * x)


def r2_ex5(x):
    return 3 * np.exp(-16 * x * x) * (1024 * x * x - 32)


def ex5_data(seed=105, n=1000, se=0.5, su=0.1):
    g = np.random.default_rng(seed)
    X = g.uniform(-2, 2, n)
    Y = r_ex5(X) + se * g.standard_normal(n)
    W = X + su * g.standard_normal(n)
    return X, W, Y


EX5_H = np.geomspace(0.02, 0.4, 40)


def ex5_fit(seed=105, n=1000, se=0.5, su=0.1, B=20, Bcv=8):
    """Exercise 5, parts (a)-(e)."""
    X, W, Y = ex5_data(seed, n, se, su)
    g = np.random.default_rng(seed + 1)
    cvs = np.array([nw_loocv(X, Y, h) for h in EX5_H])
    h = float(EX5_H[np.argmin(cvs)])
    xe = np.linspace(-1.9, 1.9, 381)
    r_star = nw(xe, X, Y, h)
    r_naive = nw(xe, W, Y, h)
    pilot = nw(W, W, Y, h)
    r_corr = r_naive - nw_meas_correction(xe, W, h, su, pilot)
    rhos = np.array([0, 0.5, 1, 1.5, 2])
    fits = [r_naive]
    for rho in rhos[1:]:
        fits.append(np.mean([nw(xe, W + np.sqrt(rho) * su * g.standard_normal(n), Y, h) for _ in range(B)], 0))
    fits = np.array(fits)
    A = np.vstack([np.ones_like(rhos), rhos, rhos ** 2]).T
    coef = np.linalg.lstsq(A, fits, rcond=None)[0]
    r_simex = coef[0] - coef[1] + coef[2]
    # (e) bandwidth from (W, Y) only: SIMEX-extrapolated cross-validation score
    cvw = np.zeros((len(rhos), len(EX5_H)))
    cvw[0] = [nw_loocv(W, Y, hh) for hh in EX5_H]
    for k, rho in enumerate(rhos[1:], 1):
        for _ in range(Bcv):
            Wb = W + np.sqrt(rho) * su * g.standard_normal(n)
            cvw[k] += np.array([nw_loocv(Wb, Y, hh) for hh in EX5_H]) / Bcv
    cc = np.linalg.lstsq(A, cvw, rcond=None)[0]
    cv_ext = cc[0] - cc[1] + cc[2]
    h_e = float(EX5_H[np.argmin(cv_ext)])
    h_w = float(EX5_H[np.argmin(cvw[0])])
    r_e = nw(xe, W, Y, h_e) - nw_meas_correction(xe, W, h_e, su, nw(W, W, Y, h_e))
    tr = r_ex5(xe)
    ise = lambda f: float(np.trapz((f - tr) ** 2, xe))
    return dict(X=X, W=W, Y=Y, h=h, cvs=cvs, xe=xe, r_star=r_star, r_naive=r_naive, r_corr=r_corr,
                r_simex=r_simex, h_e=h_e, h_w=h_w, r_e=r_e, cv_ext=cv_ext, cvw0=cvw[0],
                ise=dict(star=ise(r_star), naive=ise(r_naive), corr=ise(r_corr), simex=ise(r_simex), e=ise(r_e)))


def excess_bias_exact(w, su, lo=-2.0, hi=2.0, m=4001):
    """E[r(X) | W = w] - r(w) for X ~ Unif(lo, hi), W = X + N(0, su^2) (exact, by quadrature)."""
    s = np.linspace(lo, hi, m)
    K = np.exp(-0.5 * ((w[:, None] - s[None, :]) / su) ** 2)
    return np.trapz(K * r_ex5(s)[None, :], s, axis=1) / np.trapz(K, s, axis=1) - r_ex5(w)


def fig_s1(out=None):
    """Exercise 5: kernel regression with measurement error."""
    R = ex5_fit()
    fig, axes = plt.subplots(1, 3, figsize=(12.6, 3.7))
    ax = axes[0]
    ax.plot(R["W"], R["Y"], ".", color=GREY, ms=2, alpha=0.5)
    xe = R["xe"]
    ax.plot(xe, r_ex5(xe), color="k", lw=1.4, label="true r")
    ax.plot(xe, R["r_star"], color=BLUE, lw=1.3, label=r"$r^*_n$ (true X)")
    ax.plot(xe, R["r_naive"], color=RED, lw=1.3, label=r"naive (W)")
    ax.plot(xe, R["r_corr"], color=GREEN, lw=1.3, label="corrected (10.14)")
    ax.plot(xe, R["r_simex"], color=PURPLE, lw=1.1, ls="--", label="SIMEX")
    ax.set_xlim(-1, 1)
    ax.set_ylim(-1.5, 4.2)
    ax.set_title("(a) fits near the peak, h = %.3f" % R["h"])
    ax.set_xlabel("x")
    ax.legend(fontsize=7.5, frameon=False, loc="upper left")
    ax = axes[1]
    ax.plot(EX5_H, R["cvs"], color=BLUE, label="CV on (X, Y)")
    ax.plot(EX5_H, R["cvw0"], color=RED, label="CV on (W, Y)")
    ax.plot(EX5_H, R["cv_ext"], color=GREEN, ls="--", label="SIMEX-extrapolated CV")
    for hh, c in ((R["h"], BLUE), (R["h_w"], RED), (R["h_e"], GREEN)):
        ax.axvline(hh, color=c, lw=0.7, ls=":")
    ax.set_xscale("log")
    ax.set_xlabel("bandwidth h")
    ax.set_ylim(0.2, 0.40)
    ax.set_title("(b) cross-validation scores")
    ax.legend(fontsize=7.5, frameon=False)
    ax = axes[2]
    w = np.linspace(-1, 1, 401)
    for su, c in ((0.05, BLUE), (0.1, RED)):
        ax.plot(w, excess_bias_exact(w, su), color=c, lw=1.4, label=r"exact, $\sigma_u$ = %.2f" % su)
        ax.plot(w, su ** 2 * r2_ex5(w) / 2, color=c, lw=1, ls="--", label=r"$\sigma_u^2 r''/2$ (10.3)")
    ax.set_title(r"(c) excess bias $E[r(X)\,|\,W=w]-r(w)$")
    ax.set_xlabel("w")
    ax.legend(fontsize=7.5, frameon=False, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig10-S1", out)
    return R


# =========================================================================== deconvolution
def psiK(t):
    """Fourier transform of the kernel used for deconvolution: (1 - t^2)^3 on [-1, 1]."""
    t = np.asarray(t, float)
    return np.where(np.abs(t) < 1, (1 - t * t) ** 3, 0.0)


def psiU(t, kind, su):
    """Characteristic function of the measurement error (all symmetric, so real).
    'normal': N(0, su^2); 'laplace': Laplace with variance su^2; 'cauchy': Cauchy with scale su."""
    t = np.asarray(t, float)
    if kind == "normal":
        return np.exp(-0.5 * (su * t) ** 2)
    if kind == "laplace":
        b2 = su * su / 2
        return 1.0 / (1 + b2 * t * t)
    if kind == "cauchy":
        return np.exp(-su * np.abs(t))
    if kind == "none":
        return np.ones_like(t)
    raise ValueError(kind)


def multiplier(t, kind, su, method):
    """m(t) in f_hat(x) = (1/2pi) int e^{-itx} psi_hat_W(t) psiK(th) m(t) dt."""
    if method == "naive":
        return np.ones_like(t)
    if method == "deconv":
        return 1.0 / psiU(t, kind, su)
    if method == "small":
        return 1 + 0.5 * (su * t) ** 2
    raise ValueError(method)


NT = 401


def fourier_kde(xe, W, h, kind, su, method, nt=NT):
    """Density estimate by Fourier inversion on the grid t in [0, 1/h] (trapezoid, nt points):
    f(x) = (1/pi) int_0^{1/h} [C(t) cos tx + S(t) sin tx] psiK(th) m(t) dt, with C, S the empirical
    mean of cos(tW), sin(tW)."""
    t = np.linspace(0, 1 / h, nt)
    C = np.cos(np.outer(t, W)).mean(1)
    S = np.sin(np.outer(t, W)).mean(1)
    g = psiK(t * h) * multiplier(t, kind, su, method)
    wts = np.full(nt, t[1] - t[0])
    wts[0] = wts[-1] = (t[1] - t[0]) / 2
    return (np.cos(np.outer(xe, t)) @ (wts * g * C) + np.sin(np.outer(xe, t)) @ (wts * g * S)) / np.pi


def kstar(u, h, kind, su, nt=4001):
    """The deconvolving kernel K*(u, h) of (10.21): (1/2pi) int e^{-isu} psiK(s) / psiU(s/h) ds."""
    s = np.linspace(0, 1, nt)
    g = psiK(s) / psiU(s / h, kind, su)
    return np.trapz(np.cos(np.outer(np.atleast_1d(u), s)) * g, s, axis=1) / np.pi


def truth_cf(t, truth):
    """|psi(t)|^2 and psi(t) for the true densities used: 'normal' N(0,1), 'bimodal' .5N(-1.5,.5^2)+.5N(1.5,.5^2)."""
    if truth == "normal":
        return np.exp(-0.5 * t * t)
    if truth == "bimodal":
        return np.exp(-0.125 * t * t) * np.cos(1.5 * t)
    raise ValueError(truth)


def truth_pdf(x, truth):
    if truth == "normal":
        return norm.pdf(x)
    return 0.5 * norm.pdf(x, -1.5, 0.5) + 0.5 * norm.pdf(x, 1.5, 0.5)


def exact_mise(h, n, truth, kind, su, method, tmax=60.0, nt=6001):
    """Exact MISE by Parseval: (1/2pi) int (psiK m psiU - 1)^2 psi^2 + psiK^2 m^2 (1 - psi^2 psiU^2)/n dt."""
    t = np.linspace(0, max(tmax, 1.0 / h), nt)
    ps = truth_cf(t, truth)
    pu = psiU(t, kind, su)
    k = psiK(t * h)
    with np.errstate(over="ignore", divide="ignore", invalid="ignore"):
        m = np.where(k > 0, multiplier(t, kind, su, method), 0.0)
        integrand = (k * m * pu - 1) ** 2 * ps ** 2 + k ** 2 * m ** 2 * (1 - ps ** 2 * pu ** 2) / n
        val = float(np.trapz(integrand, t) / np.pi)
    return val if np.isfinite(val) else np.inf


def best_h(n, truth, kind, su, method, hs=None):
    hs = np.geomspace(0.05, 3, 120) if hs is None else hs
    ms = np.array([exact_mise(h, n, truth, kind, su, method) for h in hs])
    i = int(np.argmin(ms))
    return float(hs[i]), float(ms[i])


def deconv_demo_data(seed, n, truth, kind, su):
    """The deconvolution demo's sample: 6n normals of DK.rng(seed); X from the first n (and the signs of the
    next n for the two-component mixture), the error from the last 4n: Normal su*Z, Laplace with variance
    su^2 as b((Z1^2 + Z2^2) - (Z3^2 + Z4^2))/2 with b = su/sqrt(2) (a difference of two Exp(1)), Cauchy su*Z1/Z2."""
    z = js_normals(seed, 6 * n)
    core, sg = z[:n], z[n:2 * n]
    X = core if truth == "normal" else np.where(sg > 0, 1.5, -1.5) + 0.5 * core
    e1, e2, e3, e4 = z[2 * n:3 * n], z[3 * n:4 * n], z[4 * n:5 * n], z[5 * n:]
    if kind == "normal":
        U = su * e1
    elif kind == "laplace":
        U = su / np.sqrt(2) * ((e1 ** 2 + e2 ** 2) - (e3 ** 2 + e4 ** 2)) / 2
    else:
        U = su * e1 / e2
    return X, X + U


def deconv_demo_numbers(seed, n, truth, kind, su, h):
    """ISE of the naive, deconvolving and small-sigma estimates on the demo's grid, and their exact MISE."""
    X, W = deconv_demo_data(seed, n, truth, kind, su)
    xe = np.linspace(-5, 5, 241)
    f = truth_pdf(xe, truth)
    out = {}
    for m in ("naive", "deconv", "small"):
        fh = fourier_kde(xe, W, h, kind, su, m)
        out[m] = (float(np.trapz((fh - f) ** 2, xe)), exact_mise(h, n, truth, kind, su, m))
    return out


def ex4_sample(seed=104, n=100):
    g = np.random.default_rng(seed)
    return g.standard_normal(n), g.standard_normal(n), g.standard_cauchy(n)


EX4_CASES = (("none", 0.0, "(a) X observed"), ("normal", 0.25, r"(b) Normal error, $\sigma_u=0.25$"),
             ("normal", 0.5, r"(c) Normal error, $\sigma_u=0.5$"), ("cauchy", 0.25, r"(d) Cauchy error, scale 0.25"))


def ex4_results():
    X, Z, Cz = ex4_sample()
    xe = np.linspace(-4, 4, 321)
    res = []
    hs = np.geomspace(0.08, 2.5, 90)
    for kind, su, title in EX4_CASES:
        W = X if kind == "none" else X + su * (Z if kind == "normal" else Cz)
        kk = "none" if kind == "none" else kind
        row = dict(kind=kind, su=su, title=title, W=W, fits={}, h={}, mise={})
        methods = ("naive",) if kind == "none" else (("naive", "deconv", "small") if kind == "normal" else ("naive", "deconv"))
        for mth in methods:
            hb, mb = best_h(len(X), "normal", kk, su, mth, hs)
            row["h"][mth], row["mise"][mth] = hb, mb
            row["fits"][mth] = fourier_kde(xe, W, hb, kk, su, mth)
            row["curve_" + mth] = np.array([exact_mise(h, len(X), "normal", kk, su, mth) for h in hs])
        row["ise"] = {m: float(np.trapz((row["fits"][m] - norm.pdf(xe)) ** 2, xe)) for m in methods}
        res.append(row)
    return xe, hs, res


def fig_s2(out=None):
    """Exercise 4: deconvolution with Normal and Cauchy errors."""
    xe, hs, res = ex4_results()
    fig, axes = plt.subplots(2, 4, figsize=(13.2, 6.0))
    cols = dict(naive=RED, deconv=GREEN, small=PURPLE)
    labs = dict(naive="naive KDE of W", deconv="deconvolution (10.20)", small=r"small-$\sigma_u$ correction")
    for j, row in enumerate(res):
        ax = axes[0, j]
        ax.plot(xe, norm.pdf(xe), color="k", lw=1.4, label="true f")
        for m, f in row["fits"].items():
            ax.plot(xe, f, color=cols[m], lw=1.3, ls="--" if m == "small" else "-",
                    label=(labs[m] if row["kind"] != "none" else "KDE of X") + ", h=%.2f" % row["h"][m])
        ax.set_title(row["title"], fontsize=9.5)
        ax.set_ylim(-0.08, 0.6)
        ax.set_xlim(-4, 4)
        ax.legend(fontsize=7, frameon=False, loc="upper left")
        ax = axes[1, j]
        for m in row["fits"]:
            ax.plot(hs, row["curve_" + m], color=cols[m], lw=1.4, ls="--" if m == "small" else "-")
            ax.plot([row["h"][m]], [row["mise"][m]], "o", color=cols[m], ms=4)
        ax.set_xscale("log")
        ax.set_yscale("log")
        ax.set_xlabel("bandwidth h")
        ax.set_ylim(2e-3, 0.3)
        if j == 0:
            ax.set_ylabel("exact MISE (n = 100)")
    fig.tight_layout()
    savefig(fig, CH, "fig10-S2", out)
    return res


S3_NS = np.array([1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6, 3e6, 1e7])


def s3_results(su=0.5):
    hs = np.geomspace(0.005, 3, 220)
    out = {}
    for kind in ("none", "laplace", "normal"):
        hb, mb = [], []
        for n in S3_NS:
            a, b = best_h(n, "normal", kind, su, "deconv" if kind != "none" else "naive", hs)
            hb.append(a)
            mb.append(b)
        out[kind] = (np.array(hb), np.array(mb))
    return out


def fig_s3(out=None):
    """The rate of deconvolution: Normal errors are much harder than Laplace errors."""
    su = 0.5
    R = s3_results(su)
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.6))
    ax = axes[0]
    lab = dict(none="no error: $n^{-4/5}$", laplace="Laplace error: polynomial rate", normal="Normal error: $(\\log n)^{-2}$")
    col = dict(none=BLUE, laplace=GREEN, normal=RED)
    for k in ("none", "laplace", "normal"):
        ax.loglog(S3_NS, R[k][1], "o-", color=col[k], ms=3.5, label=lab[k])
    ax.set_xlabel("sample size n")
    ax.set_ylabel("smallest MISE over h")
    ax.set_title(r"(a) best risk, $f=N(0,1)$, $\sigma_u=0.5$")
    ax.legend(fontsize=8, frameon=False)
    ax = axes[1]
    ax.semilogx(S3_NS, R["normal"][0], "o-", color=RED, ms=3.5, label="optimal h (Normal error)")
    ax.semilogx(S3_NS, su / np.sqrt(np.log(S3_NS)), color=GREY, ls="--", label=r"$\sigma_u/\sqrt{\log n}$")
    ax.semilogx(S3_NS, R["laplace"][0], "o-", color=GREEN, ms=3.5, label="optimal h (Laplace error)")
    ax.set_xlabel("sample size n")
    ax.set_title("(b) optimal bandwidth")
    ax.legend(fontsize=8, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-S3", out)
    return R


# =========================================================================== 10.2 inverse problems
def bspline_basis(x, k=40, lo=-2.0, hi=2.0):
    from scipy.interpolate import BSpline
    inner = np.linspace(lo, hi, k - 2)
    t = np.r_[[lo] * 3, inner, [hi] * 3]
    return BSpline.design_matrix(np.clip(x, lo, hi), t, 3).toarray()


def inverse_setup(b, n=1000, sigma=0.5, seed=106, normalise=True, ns=8001):
    x = 4 * np.arange(1, n + 1) / n - 2
    s = np.linspace(-2, 2, ns)
    ws = np.full(ns, s[1] - s[0])
    ws[0] = ws[-1] = ws[0] / 2
    Kmat = np.exp(-((s[None, :] - x[:, None]) / b) ** 2)
    if normalise:
        Kmat /= b * np.sqrt(np.pi)
    Tr = Kmat @ (ws * r_ex5(s))
    Y = Tr + sigma * np.random.default_rng(seed).standard_normal(n)
    Phi_s = bspline_basis(s)
    Z = Kmat @ (ws[:, None] * Phi_s)
    return dict(x=x, s=s, ws=ws, K=Kmat, Tr=Tr, Y=Y, Phi_s=Phi_s, Z=Z, b=b)


LAMS = np.geomspace(1e-8, 1e3, 56)


def ridge_path(S):
    Z, Y = S["Z"], S["Y"]
    U, d, Vt = np.linalg.svd(Z, full_matrices=False)
    uy = U.T @ Y
    cv, l2 = [], []
    for lam in LAMS:
        f = d * d / (d * d + lam)
        H_diag = (U * U) @ f
        fit = U @ (f * uy)
        cv.append(np.mean(((Y - fit) / (1 - H_diag)) ** 2))
        theta = Vt.T @ (d / (d * d + lam) * uy)
        rs = S["Phi_s"] @ theta
        l2.append(float(np.sum(S["ws"] * (rs - r_ex5(S["s"])) ** 2)))
    return np.array(cv), np.array(l2)


def ridge_fit(S, lam):
    Z = S["Z"]
    k = Z.shape[1]
    Lmat = np.linalg.solve(Z.T @ Z + lam * np.eye(k), Z.T)
    theta = Lmat @ S["Y"]
    return theta, Lmat


def backus_gilbert(S, Lmat, x0):
    """A(x0, s) = sum_i l_i(x0) K_i(s), with l(x0) = L^T phi(x0)."""
    ell = Lmat.T @ bspline_basis(np.array([x0]))[0]
    return S["K"].T @ ell


def fig_s4(out=None):
    """Exercise 6: Backus-Gilbert kernels and regularised estimates."""
    fig, axes = plt.subplots(2, 3, figsize=(12.6, 6.4))
    info = {}
    for j, b in enumerate((0.01, 0.1, 1.0)):
        S = inverse_setup(b)
        cv, l2 = ridge_path(S)
        lam_cv, lam_or = float(LAMS[np.argmin(cv)]), float(LAMS[np.argmin(l2)])
        th, L = ridge_fit(S, lam_cv)
        th_o, _ = ridge_fit(S, lam_or)
        info[b] = dict(lam_cv=lam_cv, lam_or=lam_or, l2_cv=float(l2[np.argmin(cv)]), l2_or=float(l2.min()))
        ax = axes[0, j]
        for x0, c in ((-1.0, BLUE), (0.0, RED), (1.0, GREEN)):
            ax.plot(S["s"], backus_gilbert(S, L, x0), color=c, lw=1.2, label="x = %g" % x0)
        ax.set_title("b = %g: averaging kernels A(x, s)" % b, fontsize=9.5)
        ax.set_xlabel("s")
        ax.legend(fontsize=7.5, frameon=False, loc="upper left")
        ax = axes[1, j]
        ax.plot(S["x"], S["Y"], ".", color=GREY, ms=1.5, alpha=0.5)
        ax.plot(S["s"], r_ex5(S["s"]), color="k", lw=1.4, label="r")
        ax.plot(S["x"], S["Tr"], color=ORANGE, lw=1.0, ls=":", label=r"blurred $\int K_i r$")
        ax.plot(S["s"], S["Phi_s"] @ th, color=RED, lw=1.3, label=r"$\lambda$ by CV")
        ax.plot(S["s"], S["Phi_s"] @ th_o, color=GREEN, lw=1.1, ls="--", label=r"$\lambda$ minimising $L_2$ loss")
        ax.set_ylim(-3.2, 4.8)
        ax.set_xlabel("x")
        ax.legend(fontsize=7.2, frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig10-S4", out)
    return info


# =========================================================================== 10.4 semiparametric
def loclin_matrix(xe, x, h):
    """Local linear smoother matrix with a Gaussian kernel (rows: evaluation points)."""
    d = x[None, :] - xe[:, None]
    K = np.exp(-0.5 * (d / h) ** 2)
    s1 = (K * d).sum(1)
    s2 = (K * d * d).sum(1)
    w = K * (s2[:, None] - d * s1[:, None])
    return w / w.sum(1)[:, None]


def plm_once(g, n=200, beta=1.0, h=0.06):
    Z = g.uniform(0, 1, n)
    X = np.sin(2 * np.pi * Z) + 0.5 * g.standard_normal(n)
    rZ = 2 * np.sin(2 * np.pi * Z) + Z
    Y = beta * X + rZ + 0.5 * g.standard_normal(n)
    S = loclin_matrix(Z, Z, h)
    ry, rx = Y - S @ Y, X - S @ X
    return dict(ols=ls_slope(X, Y), naive=ls_slope(X, ry),
                robinson=float(rx @ ry / (rx @ rx)), oracle=ls_slope(X, Y - rZ))


def plm_sim(reps=400, n=200, seed=1004):
    g = np.random.default_rng(seed)
    out = {k: [] for k in ("ols", "naive", "robinson", "oracle")}
    for _ in range(reps):
        r = plm_once(g, n)
        for k in out:
            out[k].append(r[k])
    return {k: np.array(v) for k, v in out.items()}


def fig_s5(out=None):
    """The partially linear model: naive and double-residual estimates of beta."""
    R = plm_sim()
    fig, ax = plt.subplots(figsize=(6.4, 3.6))
    bins = np.linspace(0.0, 2.4, 70)
    labs = dict(ols="least squares ignoring r", naive=r"regress $Y-\widehat m_Y(Z)$ on $X$",
                robinson=r"double residual (Robinson)", oracle=r"oracle: $Y - r(Z)$ on $X$")
    cols = dict(ols=ORANGE, naive=RED, robinson=GREEN, oracle=BLUE)
    for k in ("ols", "naive", "robinson", "oracle"):
        ax.hist(R[k], bins=bins, histtype="step", lw=1.5, color=cols[k], density=True,
                label="%s: mean %.3f, sd %.3f" % (labs[k], R[k].mean(), R[k].std()))
    ax.axvline(1, color="k", lw=0.8, ls=":")
    ax.set_xlabel(r"estimate of $\beta$ (true value 1), n = 200, 400 samples")
    ax.legend(fontsize=7.5, frameon=False, loc="upper right")
    savefig(fig, CH, "fig10-S5", out)
    return R


# =========================================================================== 10.5 correlated errors
CORR_H = np.geomspace(0.004, 0.2, 40)


def ar1(g, n, phi, sd):
    e = np.empty(n)
    innov = sd * np.sqrt(1 - phi * phi)
    e[0] = sd * g.standard_normal()
    for i in range(1, n):
        e[i] = phi * e[i - 1] + innov * g.standard_normal()
    return e


def r_corr(x):
    return np.sin(4 * np.pi * x) * (1 + x)


def block_cv(x, y, h, l):
    """Leave-out-(2l+1) cross-validation for the local linear smoother (l = 0: leave-one-out)."""
    n = len(x)
    d = x[None, :] - x[:, None]
    K = np.exp(-0.5 * (d / h) ** 2)
    idx = np.arange(n)
    K[np.abs(idx[:, None] - idx[None, :]) <= l] = 0.0
    s0, s1, s2 = K.sum(1), (K * d).sum(1), (K * d * d).sum(1)
    w = K * (s2[:, None] - d * s1[:, None])
    fit = (w @ y) / w.sum(1)
    return float(np.mean((y - fit) ** 2))


def corr_sim(reps=150, n=200, phi=0.6, sd=0.5, l=5, seed=1005):
    g = np.random.default_rng(seed)
    x = (np.arange(n) + 0.5) / n
    hl, hb, ho = [], [], []
    for _ in range(reps):
        y = r_corr(x) + ar1(g, n, phi, sd)
        c0 = [block_cv(x, y, h, 0) for h in CORR_H]
        cl = [block_cv(x, y, h, l) for h in CORR_H]
        ase = [np.mean((loclin_matrix(x, x, h) @ y - r_corr(x)) ** 2) for h in CORR_H]
        hl.append(CORR_H[np.argmin(c0)])
        hb.append(CORR_H[np.argmin(cl)])
        ho.append(CORR_H[np.argmin(ase)])
    return np.array(hl), np.array(hb), np.array(ho)


def fig_s6(out=None):
    """Correlated errors: leave-one-out cross-validation undersmooths."""
    g = np.random.default_rng(2005)
    n, phi, sd, l = 200, 0.6, 0.5, 5
    x = (np.arange(n) + 0.5) / n
    y = r_corr(x) + ar1(g, n, phi, sd)
    c0 = np.array([block_cv(x, y, h, 0) for h in CORR_H])
    cl = np.array([block_cv(x, y, h, l) for h in CORR_H])
    h0, h1 = CORR_H[np.argmin(c0)], CORR_H[np.argmin(cl)]
    hl, hb, ho = corr_sim()
    fig, axes = plt.subplots(1, 3, figsize=(12.6, 3.6))
    ax = axes[0]
    ax.plot(x, y, ".", color=GREY, ms=3)
    ax.plot(x, r_corr(x), color="k", lw=1.3, label="r")
    ax.plot(x, loclin_matrix(x, x, h0) @ y, color=RED, lw=1.2, label="leave-one-out CV, h = %.3f" % h0)
    ax.plot(x, loclin_matrix(x, x, h1) @ y, color=GREEN, lw=1.4, label="leave-11-out CV, h = %.3f" % h1)
    ax.set_title("(a) AR(1) errors, correlation 0.6")
    ax.legend(fontsize=7.5, frameon=False, loc="lower left")
    ax = axes[1]
    ax.semilogx(CORR_H, c0, color=RED, label="leave-one-out")
    ax.semilogx(CORR_H, cl, color=GREEN, label="leave-block-out (l = 5)")
    ax.set_xlabel("bandwidth h")
    ax.set_title("(b) cross-validation scores")
    ax.legend(fontsize=8, frameon=False)
    ax = axes[2]
    bins = np.geomspace(0.004, 0.2, 25)
    ax.hist(hl, bins=bins, histtype="step", color=RED, lw=1.5, label="leave-one-out")
    ax.hist(hb, bins=bins, histtype="step", color=GREEN, lw=1.5, label="leave-block-out")
    ax.hist(ho, bins=bins, histtype="step", color=BLUE, lw=1.2, ls="--", label="best h (needs r)")
    ax.set_xscale("log")
    ax.set_xlabel("selected bandwidth, 150 data sets")
    ax.set_title("(c) the selected bandwidths")
    ax.legend(fontsize=8, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-S6", out)
    return dict(hl=hl, hb=hb, ho=ho, h0=h0, h1=h1)


# =========================================================================== 10.6 classification
def r_cls(x):
    return 0.5 + 0.4 * np.sin(3 * np.pi * x)


CLS_H = np.geomspace(0.005, 0.5, 40)


def cls_sim(reps=200, n=300, seed=1006):
    g = np.random.default_rng(seed)
    xe = np.linspace(0.0005, 0.9995, 1000)
    rt = r_cls(xe)
    ise = np.zeros(len(CLS_H))
    l1 = np.zeros(len(CLS_H))
    exc = np.zeros(len(CLS_H))
    for _ in range(reps):
        x = g.uniform(0, 1, n)
        y = (g.uniform(0, 1, n) < r_cls(x)).astype(float)
        for k, h in enumerate(CLS_H):
            rh = nw(xe, x, y, h)
            ise[k] += np.mean((rh - rt) ** 2) / reps
            l1[k] += np.mean(np.abs(rh - rt)) / reps
            exc[k] += np.mean(np.abs(2 * rt - 1) * ((rh >= 0.5) != (rt >= 0.5))) / reps
    return ise, l1, exc


def fig_s7(out=None):
    """Classification: plug-in rules and the estimation error."""
    ise, l1, exc = cls_sim()
    fig, axes = plt.subplots(1, 2, figsize=(9.8, 3.6))
    ax = axes[0]
    x = np.linspace(0, 1, 400)
    ax.plot(x, r_cls(x), color="k", lw=1.4, label="r(x) = P(Y = 1 | x)")
    ax.axhline(0.5, color=GREY, lw=0.8, ls="--")
    ax.fill_between(x, 0, 1, where=r_cls(x) >= 0.5, color=BLUE, alpha=0.08, label="Bayes rule says 1")
    ax.set_ylim(0, 1)
    ax.set_xlabel("x")
    ax.set_title("(a) the regression function")
    ax.legend(fontsize=8, frameon=False, loc="lower left")
    ax = axes[1]
    ax.loglog(CLS_H, ise, color=RED, label=r"$E\int(\widehat r-r)^2$")
    ax.loglog(CLS_H, 2 * l1, color=ORANGE, ls="--", label=r"bound $2E\int|\widehat r-r|$")
    ax.loglog(CLS_H, exc, color=BLUE, label=r"excess risk $L(\widehat h)-L(h^*)$")
    for arr, c in ((ise, RED), (exc, BLUE)):
        ax.axvline(CLS_H[np.argmin(arr)], color=c, lw=0.7, ls=":")
    ax.set_xlabel("bandwidth h (n = 300, 200 samples)")
    ax.set_title("(b) estimation error against classification error")
    ax.legend(fontsize=8, frameon=False, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig10-S7", out)
    return dict(ise=ise, l1=l1, exc=exc)


# =========================================================================== 10.7 sieves
def r_sieve(x):
    return np.abs(x - 0.3) + np.sin(5 * x)


def sieve_risk(n, sigma=1.0):
    """Exact average risk (1/n) sum E(r_hat(x_i) - r(x_i))^2 of least squares on the first k vectors of
    the orthonormal DCT-II basis, at the design x_i = (i - 1/2)/n: sigma^2 k / n + (1/n) sum_{j>k} theta_j^2."""
    from scipy.fft import dct
    x = (np.arange(n) + 0.5) / n
    th = dct(r_sieve(x), norm="ortho")
    tail = np.r_[np.cumsum((th ** 2)[::-1])[::-1], 0.0]
    k = np.arange(0, n + 1)
    return k, sigma ** 2 * k / n + tail / n


SIEVE_NS = (100, 1000, 10000, 100000)


def fig_s8(out=None):
    """A cosine sieve."""
    fig, axes = plt.subplots(1, 2, figsize=(9.8, 3.6))
    kstars, risks = [], []
    cols = (RED, ORANGE, GREEN, BLUE)
    for n, c in zip(SIEVE_NS, cols):
        k, R = sieve_risk(n)
        m = min(len(k), 2000)
        axes[0].loglog(k[1:m], R[1:m], color=c, label="n = %d" % n)
        ks = int(np.argmin(R))
        kstars.append(ks)
        risks.append(R[ks])
        axes[0].plot([ks], [R[ks]], "o", color=c, ms=4)
    axes[0].set_xlabel("sieve dimension k")
    axes[0].set_ylabel("average risk")
    axes[0].set_title("(a) risk against the dimension of the sieve")
    axes[0].legend(fontsize=8, frameon=False)
    ns = np.array([10 ** e for e in np.arange(2, 6.01, 0.25)])
    kk = [int(np.argmin(sieve_risk(int(n))[1])) for n in ns]
    axes[1].loglog(ns, kk, "o-", color=BLUE, ms=3.5, label="best k")
    axes[1].loglog(ns, kk[-1] * (ns / ns[-1]) ** 0.25, color=GREY, ls="--", label=r"slope 1/4")
    axes[1].set_xlabel("sample size n")
    axes[1].set_title("(b) the best dimension grows with n")
    axes[1].legend(fontsize=8, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-S8", out)
    return dict(kstars=kstars, risks=risks, ns=ns, kk=kk)


# =========================================================================== 10.8 isotonic regression
def pav(y, w=None):
    """Pool-adjacent-violators: the nondecreasing least squares fit to y (weights w). A stack of blocks
    (value, weight, length); each new point is pushed and merged backwards while it violates monotonicity."""
    y = np.asarray(y, float)
    w = np.ones_like(y) if w is None else np.asarray(w, float)
    vals, wts, lens = [], [], []
    for yi, wi in zip(y, w):
        vals.append(yi)
        wts.append(wi)
        lens.append(1)
        while len(vals) > 1 and vals[-2] > vals[-1]:
            v2, w2, l2 = vals.pop(), wts.pop(), lens.pop()
            v1, w1, l1 = vals.pop(), wts.pop(), lens.pop()
            vals.append((v1 * w1 + v2 * w2) / (w1 + w2))
            wts.append(w1 + w2)
            lens.append(l1 + l2)
    return np.repeat(vals, lens)


def minmax_iso(y):
    """The min-max formula: r_hat_i = max_{s <= i} min_{t >= i} mean(y_s..y_t) (O(n^3), for checks)."""
    n = len(y)
    c = np.r_[0, np.cumsum(y)]
    out = np.empty(n)
    for i in range(n):
        out[i] = max(min((c[t + 1] - c[s]) / (t + 1 - s) for t in range(i, n)) for s in range(i + 1))
    return out


def gcm(px, py):
    """Vertices of the greatest convex minorant of the points (px, py) (px increasing): lower hull."""
    hull = []
    for p in zip(px, py):
        while len(hull) >= 2:
            (x1, y1), (x2, y2) = hull[-2], hull[-1]
            if (y2 - y1) * (p[0] - x1) >= (p[1] - y1) * (x2 - x1):
                hull.pop()
            else:
                break
        hull.append(p)
    return np.array(hull)


def r_iso(x):
    return 4 * (x - 0.5) ** 3 + 0.5 * x


def iso_demo_data(seed, n, sigma, fn="cubic"):
    """The isotonic demo's data: x_i = (i - 1/2)/n, Y_i = r(x_i) + sigma * DK.rng(seed).norm()."""
    x = (np.arange(n) + 0.5) / n
    return x, ISO_FUN[fn](x) + sigma * js_normals(seed, n)


ISO_FUN = {
    "cubic": r_iso,
    "step": lambda x: (x > 0.5).astype(float),
    "linear": lambda x: x,
    "flat": lambda x: 0 * x,
    "logistic": lambda x: 1 / (1 + np.exp(-12 * (x - 0.5))),
}
ISO_NS = np.array([50, 100, 200, 500, 1000, 2000, 5000, 10000])


def iso_rates(reps=200, sigma=0.5, seed=1008):
    g = np.random.default_rng(seed)
    R = []
    for n in ISO_NS:
        x = (np.arange(n) + 0.5) / n
        r = r_iso(x)
        R.append(np.sqrt(np.mean([np.mean((pav(r + sigma * g.standard_normal(n)) - r) ** 2) for _ in range(reps)])))
    return np.array(R)


def fig_s9(out=None):
    """Isotonic regression."""
    x, y = iso_demo_data(10, 60, 0.3)
    fit = pav(y)
    fig, axes = plt.subplots(1, 3, figsize=(12.6, 3.7))
    ax = axes[0]
    ax.plot(x, y, "o", color=GREY, ms=3.5)
    ax.plot(x, r_iso(x), color="k", lw=1.3, label="true r")
    ax.step(x, fit, where="mid", color=RED, lw=1.5, label="isotonic fit (PAV)")
    ax.set_title("(a) n = 60, $\\sigma$ = 0.3")
    ax.set_xlabel("x")
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    ax = axes[1]
    px = np.arange(len(y) + 1)
    py = np.r_[0, np.cumsum(y)]
    H = gcm(px, py)
    ax.plot(px, py, "o", color=GREY, ms=2.5, label=r"$P_j=(j,\sum_{i\leq j}Y_i)$")
    ax.plot(H[:, 0], H[:, 1], color=RED, lw=1.4, label="greatest convex minorant")
    ax.set_xlabel("j")
    ax.set_title("(b) cumulative sum diagram")
    ax.legend(fontsize=8, frameon=False, loc="upper left")
    ax = axes[2]
    R = iso_rates()
    ax.loglog(ISO_NS, R, "o-", color=RED, ms=3.5, label=r"$R_{n,2}$ (200 samples, $\sigma$ = 0.5)")
    ax.loglog(ISO_NS, R[0] * (ISO_NS / ISO_NS[0]) ** (-1 / 3), color=GREY, ls="--", label=r"slope $-1/3$")
    ax.loglog(ISO_NS, R[0] * (ISO_NS / ISO_NS[0]) ** (-1 / 2), color=GREY, ls=":", label=r"slope $-1/2$")
    ax.set_xlabel("n")
    ax.set_title("(c) the $n^{-1/3}$ rate")
    ax.legend(fontsize=8, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-S9", out)
    return R


# =========================================================================== 10.9 testing
def chi2_test_power(n, R, alpha=0.05):
    """Exact power of the test rejecting when sum Y_i^2 exceeds its chi^2_n quantile, at ||theta||_2 = R."""
    from scipy.stats import chi2
    c = chi2.ppf(1 - alpha, n)
    return ncx2.sf(c, n, R * R)


def chi2_div_lower_bound(n, R):
    """Lower bound on alpha + max beta from the uniform-sign prior theta_i = +-R/sqrt(n):
    1 - TV >= 1 - sqrt(E_0 L^2 - 1)/2, with E_0 L^2 = cosh(R^2/n)^n."""
    v = n * np.log(np.cosh(R * R / n))
    return np.clip(1 - 0.5 * np.sqrt(np.expm1(v)), 0, 1)


def best_sum_errors(n, R):
    """min over the cut-off of alpha + beta for the chi-square test against ||theta|| = R."""
    from scipy.stats import chi2
    cs = n + np.sqrt(2 * n) * np.linspace(-3, 8, 600) if n > 1 else np.linspace(0.01, 20, 600)
    return float(np.min(chi2.sf(cs, n) + ncx2.cdf(cs, n, R * R)))


def fig_s10(out=None):
    """Ingster's detection boundary, p = 2."""
    cs = np.linspace(0, 4, 161)
    fig, axes = plt.subplots(1, 2, figsize=(9.8, 3.6))
    cols = (RED, GREEN, BLUE)
    for n, c in zip((100, 10000, 1000000), cols):
        R = cs * n ** 0.25
        axes[0].plot(cs, chi2_test_power(n, R), color=c, label="n = %d" % n)
    axes[0].plot(cs, norm.sf(norm.ppf(0.95) - cs ** 2 / np.sqrt(2)), color="k", ls="--", lw=1, label="limit")
    axes[0].set_xlabel(r"$\|\theta\|_2 / n^{1/4}$")
    axes[0].set_ylabel("power")
    axes[0].set_title(r"(a) the $\chi^2$ test at level 0.05")
    axes[0].legend(fontsize=8, frameon=False)
    for n, c in zip((100, 10000, 1000000), cols):
        R = cs * n ** 0.25
        axes[1].plot(cs, [best_sum_errors(n, r) for r in R], color=c, label="n = %d: $\\chi^2$ test" % n)
    axes[1].plot(cs, chi2_div_lower_bound(10 ** 6, cs * 1e6 ** 0.25), color="k", ls="--", lw=1.2,
                 label="lower bound, every test")
    axes[1].set_xlabel(r"$R_n / n^{1/4}$")
    axes[1].set_ylabel(r"$\alpha + \sup\beta$")
    axes[1].set_title(r"(b) $\gamma_n$: upper and lower bounds")
    axes[1].legend(fontsize=8, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-S10", out)


# =========================================================================== Exercise 7
EX7_AS = (1.0, 1.5, 2.0, 3.0, 5.0)
EX7_J = 2000


def ex7_posterior(n, a, J=EX7_J):
    """tau_j^2 = j^(-2a); posterior N(s_j Y_j, v_j) with s_j = tau^2/(tau^2 + 1/n), v_j = tau^2 (1/n)/(tau^2 + 1/n)."""
    j = np.arange(1, J + 1)
    tau2 = j ** (-2.0 * a)
    s = tau2 / (tau2 + 1.0 / n)
    v = s / n
    return j, s, v


def ex7_tail(n, a, J=EX7_J, extra=200000):
    """Mean contributions of the coordinates j > J (deterministic to a very good approximation)."""
    j = np.arange(J + 1, J + extra + 1, dtype=float)
    tau2 = j ** (-2.0 * a)
    s = tau2 / (tau2 + 1.0 / n)
    return float(np.sum(s / n)), j, s


def ex7_coverage(n=100, a=2.0, truth="poly", reps=4000, ndraw=20000, seed=1007):
    g = np.random.default_rng(seed)
    j, s, v = ex7_posterior(n, a)
    tail_v, jt, st = ex7_tail(n, a)
    # 95% posterior radius b_n: ||theta - theta_hat||^2 ~ sum v_j Z_j^2 under the posterior
    D = np.zeros(ndraw)
    for c in range(0, len(v), 200):
        vv = v[c:c + 200]
        D += (g.standard_normal((ndraw, len(vv))) ** 2) @ vv
    D += tail_v
    bn = float(np.sqrt(np.quantile(D, 0.95)))
    th = j ** -4.0 if truth == "poly" else np.zeros_like(s)
    tht = jt ** -4.0 if truth == "poly" else np.zeros_like(st)
    tail_err = float(np.sum((st / np.sqrt(n)) ** 2 + ((1 - st) * tht) ** 2))
    E = np.zeros(reps)
    for c in range(0, len(s), 200):
        ss, tt = s[c:c + 200], th[c:c + 200]
        eps = g.standard_normal((reps, len(ss)))
        E += ((ss * eps / np.sqrt(n)) - (1 - ss) * tt) ** 2 @ np.ones(len(ss))
    E += tail_err
    return float(np.mean(E <= bn * bn)), bn


def ex7_table():
    return {(a, t): ex7_coverage(a=a, truth=t) for a in EX7_AS for t in ("poly", "zero")}


def fig_s11(out=None):
    """Exercise 7: coverage of credible balls."""
    T = ex7_table()
    fig, ax = plt.subplots(figsize=(6.4, 3.5))
    xs = np.arange(len(EX7_AS))
    cp = [T[(a, "poly")][0] for a in EX7_AS]
    cz = [T[(a, "zero")][0] for a in EX7_AS]
    ax.bar(xs - 0.18, cp, 0.36, color=BLUE, label=r"$\theta_j = j^{-4}$")
    ax.bar(xs + 0.18, cz, 0.36, color=GREEN, label=r"$\theta = 0$")
    ax.axhline(0.95, color=RED, ls="--", lw=1)
    for x, c in zip(xs, cp):
        ax.text(x - 0.18, c + 0.01, "%.2f" % c, ha="center", fontsize=8)
    for x, c in zip(xs, cz):
        ax.text(x + 0.18, c + 0.01, "%.2f" % c, ha="center", fontsize=8)
    ax.set_xticks(xs)
    ax.set_xticklabels([r"$\tau_j^2=j^{-%g}$" % (2 * a) for a in EX7_AS])
    ax.set_ylim(0, 1.12)
    ax.set_ylabel("frequentist coverage")
    ax.set_title("95% credible balls, n = 100 (4000 simulated data sets)")
    ax.legend(fontsize=8, frameon=False, loc="lower left")
    savefig(fig, CH, "fig10-S11", out)
    return T


FIGURES = {"10.2": fig_10_2, "S1": fig_s1, "S2": fig_s2, "S3": fig_s3, "S4": fig_s4, "S5": fig_s5,
           "S6": fig_s6, "S7": fig_s7, "S8": fig_s8, "S9": fig_s9, "S10": fig_s10, "S11": fig_s11}

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