"""Wasserman (2006), Chapter 6: Density Estimation.

Companion code for Chapter 6 of L. Wasserman, All of Nonparametric Statistics (Springer, 2006),
pp. 125-144, written from scratch with numpy, scipy and matplotlib, to be read next to the lecture
notes (../ch06-density-estimation.html). Every method of the chapter is implemented here; scipy and
statsmodels are only used to confirm the implementations.

Methods
* The Bart Simpson (claw) density (6.2): bart_pdf, bart_cdf, bart_sample, and bart_sample_js (the
  same draws as the browser demonstrations, from the generator of courses/demo-kit.js).
* Section 6.1-6.2, histograms: hist_counts, hist_fhat (6.7), hist_J (the closed form (6.16)),
  hist_J_brute (the definition (6.5), for comparison), hist_mise_exact (the exact risk), hist_asym
  (Theorem 6.11 and the optimal width (6.13)), hist_band (the band (6.21)-(6.22) of Theorem 6.20, on any
  interval [a, b]).
* Section 6.3, kernel density estimation: kernel (Gaussian, Epanechnikov, boxcar, tricube), kconv (the
  convolution K*K in closed form), kde (6.26), kde_lscv (the exact cross-validation score (6.33)),
  kde_lscv_brute (the definition with a numerical integral), kde_lscv_635 (the approximation (6.35)),
  kde_hcv (minimiser), normal_reference_h (the Normal reference rule), amise_h (6.30), mise_mixture
  (the exact risk of a Gaussian-kernel estimate of a Normal mixture), silverman_table (the sample sizes
  of the table on p. 139, recomputed exactly), kde_band (a simultaneous band for E fhat from the square
  root transform and the tube formula).
* Section 6.4: local_likelihood_density (local polynomial log-likelihood (6.43), degrees 0, 1, 2, with a
  Gaussian kernel, maximised by Newton's method in closed form).
* Section 6.5: kde2 (the product-kernel estimator (6.47)) and kde2_lscv.
* Section 6.6: root_bin (the transform (6.49)), ll_weights (local linear smoothing weights), loo_cv,
  tube_kappa0 and tube_c (the tube formula of Chapter 5), density_by_regression (estimate and band).

Data. The galaxy redshifts (galaxy.dat, third column) are restricted to redshift below 0.2, which
leaves the n = 1266 galaxies of Example 6.8; histograms are on [0, 0.2]. The glass data (glass.dat,
column RI, n = 214) are used for Exercises 6, 7 and 9, and the Old Faithful data (faithful.dat) for the
two-dimensional illustration of Section 6.5. All three come from the book's website. The Bart Simpson
samples are simulated with fixed seeds.

Figures. All six figures of the chapter (6.1-6.6) are computed from data or a simulation and are
reproduced; none is skipped. Supplementary figures for the gaps filled in the notes:
  6.S1 the exact risk of a histogram against Theorem 6.11 (and the O(1/n) term the theorem drops);
  6.S2 the coverage of the histogram band (6.21) in simulation, as the number of bins grows;
  6.S3 the exact risk of the kernel estimator of the Bart Simpson density, with the asymptotic formula
       (6.29), the Normal reference bandwidth and the cross-validated bandwidths of 200 samples;
  6.S4 local likelihood density estimates of degree 0, 1 and 2 (Section 6.4, Exercise 9);
  6.S5 the product-kernel estimator in two dimensions (Section 6.5, Old Faithful);
  6.S6 Exercise 6: histogram and kernel estimates of the glass refractive index, with bands;
  6.S7 Exercise 7: kernel estimates with bands over a range of bandwidths;
  6.S8 Exercise 10: kernel estimation against the regression method of Section 6.6, n = 25 to 1000.
Run `python3 ch06_density_estimation.py --list`, `python3 ch06_density_estimation.py` (all figures,
about four minutes on one CPU thread; the simulations are cached in cache/) or
`python3 ch06_density_estimation.py --fig 6.2`. Files go to ../img/ch06/; the data used by the browser
demonstrations go to ../data/ch06-*.json.
"""
import json
import math
import os

import numpy as np
from scipy import optimize, stats

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, nps_file, savefig

CH = 6
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
M32 = 0xFFFFFFFF
SQ2PI = math.sqrt(2 * math.pi)
SEED_BART = 6061          # the n = 1000 Bart Simpson sample of Figures 6.1 and 6.6 and of the demos


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


class JSRandom:
    """The seeded generator of the browser demonstrations (DK.rng in courses/demo-kit.js): u() is
    mulberry32 and norm() the Box-Muller transform, which returns r cos(t) and keeps r sin(t)."""

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

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

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


# =========================================================================== data
def galaxy():
    """Redshifts below 0.2 of galaxy.dat (third column): the n = 1266 galaxies of Example 6.8."""
    z = np.loadtxt(nps_file("galaxy.dat"))[:, 2]
    return np.sort(z[z < 0.2])


def glass_ri():
    """Refractive index (column RI) of the 214 glass fragments (Exercise 6)."""
    return common.nps_data("glass.dat")["RI"].to_numpy(dtype=float)


def faithful():
    """Old Faithful: eruption time (min) and waiting time (min), 272 eruptions."""
    d = common.nps_data("faithful.dat")
    return d[["eruptions", "waiting"]].to_numpy(dtype=float)


# =========================================================================== the Bart Simpson density
BART_W = np.array([0.5] + [0.1] * 5)
BART_MU = np.array([0.0] + [j / 2 - 1 for j in range(5)])
BART_SD = np.array([1.0] + [0.1] * 5)


def bart_pdf(x):
    """The Bart Simpson density (6.2): 0.5 N(0,1) + 0.1 sum_j N(j/2 - 1, 0.1^2), j = 0..4."""
    x = np.asarray(x, dtype=float)[..., None]
    return (BART_W * stats.norm.pdf(x, BART_MU, BART_SD)).sum(-1)


def bart_cdf(x):
    x = np.asarray(x, dtype=float)[..., None]
    return (BART_W * stats.norm.cdf(x, BART_MU, BART_SD)).sum(-1)


def bart_sample(n, rng):
    """n draws from (6.2) with a numpy Generator."""
    comp = rng.choice(6, size=n, p=BART_W)
    return BART_MU[comp] + BART_SD[comp] * rng.standard_normal(n)


def bart_sample_js(n, seed):
    """n draws with the browser generator: u < 1/2 gives N(0,1), otherwise the claw component
    j = floor(10 (u - 1/2)) with mean j/2 - 1 and sd 0.1. The demos draw exactly these values."""
    r = JSRandom(seed)
    out = np.empty(n)
    for i in range(n):
        u = r.u()
        if u < 0.5:
            out[i] = r.norm()
        else:
            j = min(int(math.floor((u - 0.5) * 10)), 4)
            out[i] = j / 2 - 1 + 0.1 * r.norm()
    return out


def bart_data(n=1000):
    return bart_sample_js(n, SEED_BART)


# =========================================================================== histograms (Section 6.2)
def hist_counts(x, m, a, b):
    """Counts Y_j of the m bins of width h = (b - a)/m on [a, b] (6.6); the last bin is closed."""
    h = (b - a) / m
    j = np.clip(np.floor((np.asarray(x) - a) / h).astype(int), 0, m - 1)
    return np.bincount(j, minlength=m), h


def hist_fhat(x, m, a, b, grid):
    """The histogram (6.7) evaluated on grid."""
    c, h = hist_counts(x, m, a, b)
    j = np.clip(np.floor((np.asarray(grid) - a) / h).astype(int), 0, m - 1)
    out = c[j] / (len(x) * h)
    return np.where((grid >= a) & (grid <= b), out, 0.0)


def hist_J(x, m, a, b):
    """Closed form (6.16) of the cross-validation score: 2/((n-1)h) - (n+1)/((n-1)h) sum_j phat_j^2."""
    n = len(x)
    c, h = hist_counts(x, m, a, b)
    p = c / n
    return 2.0 / ((n - 1) * h) - (n + 1) / ((n - 1) * h) * np.sum(p ** 2)


def hist_J_brute(x, m, a, b):
    """The score from its definition (6.5): int fhat^2 - (2/n) sum_i fhat_(-i)(X_i), refitting n times."""
    x = np.asarray(x)
    n = len(x)
    c, h = hist_counts(x, m, a, b)
    int_f2 = np.sum((c / (n * h)) ** 2) * h
    loo = 0.0
    for i in range(n):
        ci, _ = hist_counts(np.delete(x, i), m, a, b)
        j = min(int(math.floor((x[i] - a) / h)), m - 1)
        loo += ci[j] / ((n - 1) * h)
    return int_f2 - 2.0 * loo / n


def hist_cv_curve(x, a, b, mmax):
    ms = np.arange(1, mmax + 1)
    return ms, np.array([hist_J(x, m, a, b) for m in ms])


def bin_probs(cdf, m, a, b):
    e = np.linspace(a, b, m + 1)
    return np.diff(cdf(e)), (b - a) / m


def hist_mise_exact(cdf, int_f2, m, n, a, b):
    """Exact risk of the histogram when f lives on [a, b]:
    int f^2 - sum p_j^2/h + (1 - sum p_j^2)/(nh)   (integrated squared bias + integrated variance)."""
    p, h = bin_probs(cdf, m, a, b)
    s = np.sum(p ** 2)
    return int_f2 - s / h + (1 - s) / (n * h)


def hist_asym(h, n, int_fp2):
    """Theorem 6.11: h^2/12 int f'^2 + 1/(nh)."""
    return h * h / 12 * int_fp2 + 1 / (n * h)


def hist_hstar(n, int_fp2):
    """(6.13) h* = n^(-1/3) (6 / int f'^2)^(1/3) and the constant C of (6.14)."""
    hs = n ** (-1 / 3) * (6 / int_fp2) ** (1 / 3)
    C = (3 / 4) ** (2 / 3) * int_fp2 ** (1 / 3)
    return hs, C


def hist_band(x, m, a, b, alpha=0.05):
    """The band (6.21) of Theorem 6.20 for fbar = E fhat. On [a, b] with h = (b - a)/m the constant
    (6.22) becomes c = z_{alpha/(2m)} / (2 sqrt(n h)), which is (6.22) when [a, b] = [0, 1].
    Returns the bin heights fhat_j, lower_j, upper_j, c and h."""
    n = len(x)
    cnt, h = hist_counts(x, m, a, b)
    fh = cnt / (n * h)
    z = stats.norm.isf(alpha / (2 * m))
    c = z / (2 * math.sqrt(n * h))
    lo = np.maximum(np.sqrt(fh) - c, 0) ** 2
    hi = (np.sqrt(fh) + c) ** 2
    return fh, lo, hi, c, h


def hist_band_coverage(sampler, cdf, n, m, a, b, reps, rng, alpha=0.05):
    """Fraction of samples for which the band (6.21) contains fbar on all of [a, b]."""
    p, h = bin_probs(cdf, m, a, b)
    fbar = p / h
    hit = 0
    for _ in range(reps):
        x = sampler(n, rng)
        x = x[(x >= a) & (x <= b)]          # condition on [a, b]: renormalise below
        fh, lo, hi, c, _ = hist_band(x, m, a, b, alpha)
        fb = fbar / p.sum()
        hit += np.all((lo <= fb + 1e-15) & (fb <= hi + 1e-15))
    return hit / reps


# =========================================================================== kernels and the KDE (Section 6.3)
def kernel(u, kind="gauss"):
    """Kernels: gauss, epan (Epanechnikov on [-1, 1]), boxcar (1/2 on [-1, 1]), tricube."""
    u = np.asarray(u, dtype=float)
    a = np.abs(u)
    if kind == "gauss":
        return np.exp(-0.5 * u * u) / SQ2PI
    if kind == "epan":
        return np.where(a <= 1, 0.75 * (1 - u * u), 0.0)
    if kind == "boxcar":
        return np.where(a <= 1, 0.5, 0.0)
    if kind == "tricube":
        return np.where(a < 1, 70.0 / 81.0 * (1 - a ** 3) ** 3, 0.0)
    raise ValueError(kind)


def kconv(z, kind="gauss"):
    """K^(2)(z) = int K(z - y) K(y) dy in closed form (Remark 6.36 for the Gaussian kernel)."""
    z = np.asarray(z, dtype=float)
    a = np.abs(z)
    if kind == "gauss":
        return np.exp(-0.25 * z * z) / (2 * math.sqrt(math.pi))
    if kind == "epan":
        return np.where(a <= 2, 3.0 / 160.0 * (2 - a) ** 3 * (a * a + 6 * a + 4), 0.0)
    if kind == "boxcar":
        return np.where(a <= 2, 0.25 * (2 - a), 0.0)
    raise ValueError(kind)


KCONST = {   # sigma_K^2 = int u^2 K, R(K) = int K^2
    "gauss": (1.0, 1 / (2 * math.sqrt(math.pi))),
    "epan": (0.2, 0.6),
    "boxcar": (1 / 3, 0.5),
    "tricube": (35 / 243, 175 / 247),
}


def kde(x, grid, h, kind="gauss"):
    """The kernel density estimator (6.26)."""
    x = np.asarray(x, dtype=float)
    grid = np.asarray(grid, dtype=float)
    out = np.empty(len(grid))
    for s in range(0, len(grid), 2000):
        g = grid[s:s + 2000]
        out[s:s + 2000] = kernel((g[:, None] - x[None, :]) / h, kind).sum(1) / (len(x) * h)
    return out


def kde_lscv(x, h, kind="gauss", D=None):
    """Exact cross-validation score (6.33):
    J = (1/(n^2 h)) sum_ij K2((Xi - Xj)/h) - (2/(n(n-1)h)) sum_{i != j} K((Xi - Xj)/h)."""
    x = np.asarray(x, dtype=float)
    n = len(x)
    if D is None:
        D = x[:, None] - x[None, :]
    U = D / h
    a = kconv(U, kind).sum() / (n * n * h)
    off = kernel(U, kind).sum() - n * kernel(0.0, kind)
    return a - 2 * off / (n * (n - 1) * h)


def kde_lscv_brute(x, h, kind="gauss", ngrid=20001):
    """The definition: int fhat^2 by the trapezoid rule, and n leave-one-out estimates."""
    x = np.asarray(x, dtype=float)
    n = len(x)
    pad = 5 * h if kind == "gauss" else 1.01 * h
    g = np.linspace(x.min() - pad, x.max() + pad, ngrid)
    f = kde(x, g, h, kind)
    int_f2 = np.trapz(f * f, g)
    loo = np.array([kde(np.delete(x, i), x[i:i + 1], h, kind)[0] for i in range(n)])
    return int_f2 - 2 * loo.mean()


def kde_lscv_635(x, h, kind="gauss"):
    """The approximation (6.35): (1/(h n^2)) sum_ij K*((Xi - Xj)/h) + 2 K(0)/(nh), K* = K2 - 2K."""
    x = np.asarray(x, dtype=float)
    n = len(x)
    U = (x[:, None] - x[None, :]) / h
    return (kconv(U, kind) - 2 * kernel(U, kind)).sum() / (h * n * n) + 2 * kernel(0.0, kind) / (n * h)


def kde_cv_curve(x, hs, kind="gauss"):
    D = np.asarray(x)[:, None] - np.asarray(x)[None, :]
    return np.array([kde_lscv(x, h, kind, D) for h in hs])


def kde_hcv(x, hs, kind="gauss"):
    """Minimise the score over the grid hs, then refine by a bounded scalar search."""
    D = np.asarray(x)[:, None] - np.asarray(x)[None, :]
    J = np.array([kde_lscv(x, h, kind, D) for h in hs])
    k = int(np.argmin(J))
    lo, hi = hs[max(k - 1, 0)], hs[min(k + 1, len(hs) - 1)]
    r = optimize.minimize_scalar(lambda h: kde_lscv(x, h, kind, D), bounds=(lo, hi), method="bounded",
                                 options={"xatol": 1e-10 * hi})
    return float(r.x), float(r.fun), J


def iqr(x):
    q = np.percentile(x, [25, 75])
    return q[1] - q[0]


def normal_reference_h(x):
    """1.06 sigma n^(-1/5) with sigma = min(s, IQR/1.34)."""
    s = min(np.std(x, ddof=1), iqr(x) / 1.34)
    return 1.06 * s * len(x) ** (-0.2)


def amise_h(n, A, kind="gauss"):
    """(6.30): h* = (c2 / (c1^2 A n))^(1/5), c1 = sigma_K^2, c2 = R(K), and the risk at h*."""
    c1, c2 = KCONST[kind]
    h = (c2 / (c1 ** 2 * A * n)) ** 0.2
    R = 0.25 * c1 ** 2 * h ** 4 * A + c2 / (n * h)
    return h, R


def mixture_A(w, mu, sd):
    """A(f) = int f''^2 for a Normal mixture (exact): sum_ll' w w' phi''''(mu - mu'; s^2 + s'^2)."""
    w, mu, sd = map(np.asarray, (w, mu, sd))
    S = np.sqrt(sd[:, None] ** 2 + sd[None, :] ** 2)
    d = (mu[:, None] - mu[None, :]) / S
    phi4 = stats.norm.pdf(d) * (d ** 4 - 6 * d ** 2 + 3) / S ** 5
    return float(w @ phi4 @ w)


def mise_mixture(h, n, w, mu, sd):
    """Exact MISE of the Gaussian-kernel estimator of a Normal mixture (Marron and Wand 1992):
    1/(2 sqrt(pi) n h) + w' [(1 - 1/n) O2 - 2 O1 + O0] w, O_a[l,l'] = phi(mu_l - mu_l'; a h^2 + s_l^2 + s_l'^2)."""
    w, mu, sd = map(np.asarray, (w, mu, sd))
    dm = mu[:, None] - mu[None, :]
    ss = sd[:, None] ** 2 + sd[None, :] ** 2

    def Om(a):
        return stats.norm.pdf(dm, 0, np.sqrt(a * h * h + ss))
    return 1 / (2 * math.sqrt(math.pi) * n * h) + w @ ((1 - 1 / n) * Om(2) - 2 * Om(1) + Om(0)) @ w


def mise_bias_var(h, n, w, mu, sd):
    """Integrated squared bias and integrated variance of the same estimator."""
    w, mu, sd = map(np.asarray, (w, mu, sd))
    dm = mu[:, None] - mu[None, :]
    ss = sd[:, None] ** 2 + sd[None, :] ** 2

    def Om(a):
        return stats.norm.pdf(dm, 0, np.sqrt(a * h * h + ss))
    ib = w @ (Om(2) - 2 * Om(1) + Om(0)) @ w
    iv = 1 / (2 * math.sqrt(math.pi) * n * h) - (w @ Om(2) @ w) / n
    return ib, iv


def relmse0(h, n, d):
    """Exact relative mean squared error at 0 of the Gaussian product-kernel estimator of N(0, I_d)
    with bandwidth h in every coordinate."""
    f0 = (2 * math.pi) ** (-d / 2)
    m = (2 * math.pi * (1 + h * h)) ** (-d / 2)
    ek2 = (4 * math.pi * h * h) ** (-d / 2) * (2 * math.pi * (1 + h * h / 2)) ** (-d / 2)
    var = (ek2 - m * m) / n
    return ((m - f0) ** 2 + var) / f0 ** 2


def silverman_table(dmax=10, target=0.1):
    """Smallest n for which min_h relmse0(h, n, d) <= target, for d = 1..dmax (the table on p. 139)."""
    out = []
    for d in range(1, dmax + 1):
        def best(n):
            r = optimize.minimize_scalar(lambda t: relmse0(math.exp(t), n, d), bounds=(-6, 2), method="bounded",
                                         options={"xatol": 1e-9})
            return r.fun
        lo, hi = 1, 2
        while best(hi) > target:
            hi *= 2
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if best(mid) > target:
                lo = mid
            else:
                hi = mid
        out.append(hi)
    return out


def tube_c(kappa0, alpha=0.05):
    """Solve 2(1 - Phi(c)) + (kappa0/pi) exp(-c^2/2) = alpha (the tube formula (5.102))."""
    f = lambda c: 2 * stats.norm.sf(c) + kappa0 / math.pi * math.exp(-c * c / 2) - alpha
    return float(optimize.brentq(f, 0.5, 30))


def kde_band(x, grid, h, kind="gauss", alpha=0.05):
    """An approximate simultaneous band for fbar = E fhat on [grid[0], grid[-1]].

    Since V fhat(x) ~ f(x) R(K)/(nh), the square root has nearly constant standard deviation
    sqrt(R(K)/(4nh)); the process (sqrt fhat - sqrt fbar)/sd is close to a stationary Gaussian process
    whose correlation is that of K*K, so the tube formula applies with
    kappa0 = (length/h) sqrt(int K'^2 / int K^2) (= length/(h sqrt 2) for the Gaussian kernel)."""
    n = len(x)
    f = kde(x, grid, h, kind)
    RK = KCONST[kind][1]
    if kind == "gauss":
        ratio = 0.5
    elif kind == "epan":
        ratio = 5.0                         # int K'^2 = 3/2, int K^2 = 3/5
    else:
        raise ValueError("band implemented for gauss and epan")
    kappa0 = (grid[-1] - grid[0]) / h * math.sqrt(ratio)
    c = tube_c(kappa0, alpha)
    sd = math.sqrt(RK / (4 * n * h))
    lo = np.maximum(np.sqrt(f) - c * sd, 0) ** 2
    hi = (np.sqrt(f) + c * sd) ** 2
    return f, lo, hi, c, kappa0


def kde_mean_mixture(grid, h, w, mu, sd):
    """fbar = E fhat for a Gaussian kernel and a Normal mixture: the mixture with variances s^2 + h^2."""
    return (np.asarray(w) * stats.norm.pdf(np.asarray(grid)[:, None], mu, np.sqrt(np.asarray(sd) ** 2 + h * h))).sum(1)


# =========================================================================== local likelihood (Section 6.4)
def _tilt_moments(b1, b2, kmax):
    """E t^k, k = 0..kmax, under N(mu, s^2) with s^2 = 1/(1 - b2), mu = b1 s^2, and the normaliser
    int phi(t) exp(b1 t + b2 t^2/2) dt = s exp(mu^2/(2 s^2))."""
    s2 = 1.0 / (1.0 - b2)
    mu = b1 * s2
    m = [1.0, mu]
    for k in range(2, kmax + 1):            # E t^k = mu E t^(k-1) + (k-1) s^2 E t^(k-2)
        m.append(mu * m[k - 1] + (k - 1) * s2 * m[k - 2])
    logZ = 0.5 * math.log(s2) + 0.5 * mu * mu / s2
    return np.array(m), logZ


def local_likelihood_density(x, grid, h, p=1, iters=100, tol=1e-12):
    """Local polynomial likelihood density estimate (Definition 6.44) with a Gaussian kernel.

    In the scaled variable t = (u - x)/h the local polynomial is b0 + b1 t + b2 t^2/2 (degree p <= 2),
    so (6.43) divided by h is concave in b:
      L(b) = sum_i phi(t_i) P(b, t_i) - n h int phi(t) exp(P(b, t)) dt,
    and the integral is exp(b0) s exp(mu^2/(2 s^2)) with s^2 = 1/(1 - b2), mu = b1 s^2 (needs b2 < 1).
    Newton's method with step halving; fhat(x) = exp(b0). (The book writes powers of x - u: the sign
    of b1 flips, the estimate does not change.)"""
    x = np.asarray(x, dtype=float)
    n = len(x)
    out = np.empty(len(grid))
    fact = np.array([math.factorial(k) for k in range(2 * p + 1)])
    for g, x0 in enumerate(grid):
        t = (x - x0) / h
        K = kernel(t, "gauss")
        T = np.vstack([t ** k / fact[k] for k in range(p + 1)])          # (p+1, n)
        S = T @ K
        if S[0] <= 1e-300:
            out[g] = 0.0
            continue
        b = np.zeros(p + 1)
        b[0] = math.log(S[0] / (n * h))
        def obj(bb):
            b1 = bb[1] if p >= 1 else 0.0
            b2 = bb[2] if p >= 2 else 0.0
            if b2 >= 1:
                return -np.inf, None, None
            mom, logZ = _tilt_moments(b1, b2, 2 * p)
            Z = math.exp(bb[0] + logZ)
            val = float(S @ bb) - n * h * Z
            mk = mom / fact[:2 * p + 1]
            grad = S - n * h * Z * np.array([mom[k] / fact[k] for k in range(p + 1)])
            H = -n * h * Z * np.array([[mom[k + l] / (fact[k] * fact[l]) for l in range(p + 1)] for k in range(p + 1)])
            return val, grad, H
        val, grad, H = obj(b)
        for _ in range(iters):
            step = np.linalg.solve(H, -grad)
            lam = 1.0
            while True:
                nb = b + lam * step
                nv, ng, nH = obj(nb)
                if nv >= val - 1e-12 * abs(val) or lam < 1e-10:
                    break
                lam /= 2
            done = np.max(np.abs(nb - b)) < tol
            b, val, grad, H = nb, nv, ng, nH
            if done:
                break
        out[g] = math.exp(b[0])
    return out


# =========================================================================== two dimensions (Section 6.5)
def kde2(X, G, h):
    """Product Gaussian kernel estimator (6.47) at the rows of G, bandwidths h = (h1, h2)."""
    h = np.asarray(h, dtype=float)
    U = (G[:, None, :] - X[None, :, :]) / h
    return kernel(U, "gauss").prod(-1).sum(1) / (len(X) * h.prod())


def kde2_lscv(X, h):
    """Exact cross-validation score of the product Gaussian estimator."""
    h = np.asarray(h, dtype=float)
    n = len(X)
    U = (X[:, None, :] - X[None, :, :]) / h
    a = kconv(U, "gauss").prod(-1).sum() / (n * n * h.prod())
    K = kernel(U, "gauss").prod(-1)
    off = K.sum() - n * kernel(0.0, "gauss") ** 2
    return a - 2 * off / (n * (n - 1) * h.prod())


# =========================================================================== density estimation as regression (Section 6.6)
def root_bin(x, k, a, b):
    """(6.49): bin midpoints t_j and Y_j = sqrt(k'/n) sqrt(N_j + 1/4), where k' = k/(b - a) is the number
    of bins per unit length (k' = k on [0, 1]); sigma = sqrt(k'/(4n))."""
    n = len(x)
    N, w = hist_counts(x, k, a, b)
    t = a + w * (np.arange(k) + 0.5)
    Y = np.sqrt(N + 0.25) / math.sqrt(n * w)
    return t, Y, N, 1 / math.sqrt(4 * n * w)


def ll_weights(x, grid, h, kind="tricube"):
    """Local linear weights l_i(x) (Theorem 5.60, closed form (5.61)) on grid."""
    D = np.asarray(x)[None, :] - np.asarray(grid)[:, None]
    W = kernel(D / h, kind)
    S1 = (W * D).sum(1, keepdims=True)
    S2 = (W * D * D).sum(1, keepdims=True)
    B = W * (S2 - D * S1)
    with np.errstate(invalid="ignore", divide="ignore"):
        return B / B.sum(1, keepdims=True)


def loo_cv(L, y):
    """Leave-one-out score of a linear smoother in one fit, mean((y - Ly)/(1 - L_ii))^2 (5.35)."""
    r = (y - L @ y) / (1 - np.diag(L))
    return float(np.mean(r ** 2))


def tube_kappa0(Lg, xg):
    """kappa0 = int ||T'(x)|| dx, T(x) = l(x)/||l(x)|| (5.101), by central differences."""
    T = Lg / np.linalg.norm(Lg, axis=1, keepdims=True)
    dT = np.gradient(T, xg, axis=0)
    return float(np.trapz(np.linalg.norm(dT, axis=1), xg))


def regression_h_grid(t):
    w = t[1] - t[0]
    return np.exp(np.linspace(np.log(0.5 * w), np.log(0.4 * (t[-1] - t[0])), 60))


def density_by_regression(x, k, a, b, hs=None, grid=None, alpha=0.05, h=None, score="cp"):
    """Section 6.6: bin, root-transform, local linear regression (Gaussian kernel), a tube-formula band
    for sqrt fbar, then square, clip at zero and normalise.

    The bandwidth minimises either the leave-one-out score (score="cv", (5.35)) or the unbiased risk
    estimate that uses the known noise level sigma^2 = k'/(4n) (score="cp"):
        Cp(h) = (1/k) ||Y - L Y||^2 - sigma^2 + 2 sigma^2 tr(L)/k.
    Returns a dict with both score curves (against tr L), the estimate and the band on grid."""
    t, Y, N, sigma = root_bin(x, k, a, b)
    if hs is None:
        hs = regression_h_grid(t)
    cv, cp, df = [], [], []
    for hh in hs:
        L = ll_weights(t, t, hh, "gauss")
        nu = float(np.trace(L))
        cv.append(loo_cv(L, Y))
        cp.append(float(np.mean((Y - L @ Y) ** 2)) - sigma ** 2 + 2 * sigma ** 2 * nu / k)
        df.append(nu)
    cv, cp, df = np.array(cv), np.array(cp), np.array(df)
    if h is None:
        h = float(hs[int(np.argmin(cp if score == "cp" else cv))])
    if grid is None:
        grid = np.linspace(a, b, 601)
    Lg = ll_weights(t, grid, h, "gauss")
    r = Lg @ Y
    kappa0 = tube_kappa0(Lg, grid)
    c = tube_c(kappa0, alpha)
    se = sigma * np.linalg.norm(Lg, axis=1)
    rp = np.maximum(r, 0)
    norm = np.trapz(rp ** 2, grid)
    f = rp ** 2 / norm
    lo = np.maximum(r - c * se, 0) ** 2 / norm
    hi = np.maximum(r + c * se, 0) ** 2 / norm
    return dict(t=t, Y=Y, N=N, sigma=sigma, hs=hs, cv=cv, cp=cp, df=df, h=h, grid=grid, r=r, f=f, lo=lo, hi=hi,
                kappa0=kappa0, c=c, norm=norm, nu=float(np.trace(ll_weights(t, t, h, "gauss"))))


# =========================================================================== reference numbers
H_GAL = np.linspace(0.0002, 0.01, 99)       # bandwidth grid for the galaxy data
H_BART = np.exp(np.linspace(np.log(0.01), np.log(0.6), 80))


def galaxy_summary():
    x = galaxy()
    ms, J = hist_cv_curve(x, 0.0, 0.2, len(x))
    mcv = int(ms[np.argmin(J)])
    hcv, Jmin, Jh = kde_hcv(x, H_GAL)
    return dict(x=x, ms=ms, J=J, mcv=mcv, hcv=hcv, Jh=Jh)


def bart_summary():
    x = bart_data()
    hcv, Jmin, Jh = kde_hcv(x, H_BART)
    return dict(x=x, hcv=hcv, Jh=Jh, hnr=normal_reference_h(x))


# =========================================================================== figures
def _style(ax, xl=None, yl=None):
    if xl:
        ax.set_xlabel(xl)
    if yl:
        ax.set_ylabel(yl)


def fig_6_1(out=None):
    """The Bart Simpson density and kernel estimates with h by CV, h/10 and 10h (n = 1000)."""
    B = bart_summary()
    x, h = B["x"], B["hcv"]
    g = np.linspace(-3, 3, 1201)
    fig, ax = common.panel_grid(2, 2, size=(3.4, 2.5))
    panels = [(ax[0, 0], None, "True density"), (ax[0, 1], h / 10, "Undersmoothed (h = %.4f)" % (h / 10)),
              (ax[1, 0], h, "Just right (h = %.4f, by CV)" % h), (ax[1, 1], 10 * h, "Oversmoothed (h = %.3f)" % (10 * h))]
    for a, hh, t in panels:
        if hh is None:
            a.plot(g, bart_pdf(g), color="black", lw=1.3)
        else:
            a.plot(g, bart_pdf(g), color=GREY, lw=0.9, ls="--")
            a.plot(g, kde(x, g, hh), color=BLUE, lw=1.1)
        a.set_xlim(-3, 3)
        a.set_ylim(0, 1.0 if hh is None or hh >= h else 1.25)
        a.set_title(t)
    fig.tight_layout()
    savefig(fig, CH, "fig6-1", out)


def _hist_panel(ax, x, m, title, a=0.0, b=0.2):
    c, h = hist_counts(x, m, a, b)
    ax.bar(a + np.arange(m) * h + h / 2, c / (len(x) * h), width=h, color="#7fd3e6" if m < 60 else "black",
           edgecolor="black", lw=0.6 if m < 60 else 0)
    ax.set_xlim(a, b)
    ax.set_ylim(0, 85)
    _style(ax, "redshift", r"$\widehat f_n$")
    ax.set_title(title)


def fig_6_2(out=None):
    """Histograms of the galaxy redshifts with too many, CV-chosen and too few bins; the CV score."""
    G = galaxy_summary()
    x, ms, J, mcv = G["x"], G["ms"], G["J"], G["mcv"]
    fig, ax = common.panel_grid(2, 2, size=(3.4, 2.6))
    _hist_panel(ax[0, 0], x, 1000, "Undersmoothed (m = 1000)")
    _hist_panel(ax[0, 1], x, mcv, "Just right (m = %d, by CV)" % mcv)
    _hist_panel(ax[1, 0], x, 10, "Oversmoothed (m = 10)")
    a = ax[1, 1]
    a.plot(ms, J, color="black", lw=0.9)
    a.axvline(mcv, color=RED, ls="--", lw=1)
    a.set_ylim(J.min() - 1.5, J.min() + 12)
    _style(a, "number of bins m", r"$\widehat J$ (estimated risk)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-2", out)


def fig_6_3(out=None):
    """95 percent band (6.21) for the galaxy histogram with the CV number of bins (and with m = 308)."""
    G = galaxy_summary()
    x = G["x"]
    fig, axes = common.panel_grid(2, 1, size=(6.4, 2.5))
    for a, m in zip(axes[:, 0], (G["mcv"], 308)):
        fh, lo, hi, c, h = hist_band(x, m, 0.0, 0.2)
        e = np.arange(m + 1) * h
        a.fill_between(np.repeat(e, 2)[1:-1], np.repeat(lo, 2), np.repeat(hi, 2), color="#9ecae1", lw=0, label="95% band")
        a.step(e, np.r_[fh, fh[-1]], where="post", color="black", lw=0.7, label=r"$\widehat f_n$")
        a.set_xlim(0, 0.2)
        a.set_ylim(0, 160)
        a.set_title("m = %d bins%s: c = %.3f" % (m, " (by CV)" if m == G["mcv"] else " (the book's choice)", c))
        _style(a, "redshift", "density")
        a.legend(loc="upper right", frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig6-3", out)


def fig_6_4(out=None):
    """A kernel density estimate as an average of bumps of mass 1/n (to scale)."""
    x = np.array([-6.2, -4.9, -2.3, -1.6, -1.0, 0.4, 2.8, 4.1, 4.6, 7.3])
    h = 1.2
    g = np.linspace(-10, 10, 1001)
    n = len(x)
    fig, ax = common.panel_grid(1, 1, size=(6.4, 2.8))
    a = ax[0, 0]
    for xi in x:
        a.plot(g, kernel((g - xi) / h) / (n * h), color=BLUE, lw=0.8)
    a.plot(g, kde(x, g, h), color="black", lw=1.6)
    for xi in x:
        a.plot([xi, xi], [0, 0.012], color=RED, lw=1.4)
    a.set_xlim(-10, 10)
    a.set_ylim(0, None)
    _style(a, "x", r"$\widehat f_n(x)$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-4", out)


def fig_6_5(out=None):
    """Kernel estimates of the galaxy redshifts and the CV score against h."""
    G = galaxy_summary()
    x, hcv, Jh = G["x"], G["hcv"], G["Jh"]
    g = np.linspace(0, 0.2, 1601)
    fig, ax = common.panel_grid(2, 2, size=(3.4, 2.6))
    for a, h, t in [(ax[0, 0], 0.01, "Oversmoothed (h = 0.01)"), (ax[0, 1], hcv, "Just right (h = %.5f, by CV)" % hcv),
                    (ax[1, 0], hcv / 4, "Undersmoothed (h = %.5f)" % (hcv / 4))]:
        a.plot(g, kde(x, g, h), color="black", lw=0.9)
        a.set_xlim(0, 0.2)
        a.set_title(t)
        _style(a, "redshift", r"$\widehat f_n$")
    a = ax[1, 1]
    a.plot(H_GAL, Jh, color="black", lw=1.1)
    a.axvline(hcv, color=RED, ls="--", lw=1)
    _style(a, "h", r"$\widehat J(h)$ (estimated risk)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-5", out)


def bart_regression():
    x = bart_data()
    return x, density_by_regression(x, 100, -3.0, 3.0)


def fig_6_6(out=None):
    """Density estimation by regression on root counts: CV score against df; estimate and band."""
    x, R = bart_regression()
    fig, axes = common.panel_grid(2, 1, size=(6.2, 2.6))
    a = axes[0, 0]
    ok = (R["df"] > 15) & (R["df"] < 80)
    a.plot(R["df"][ok], R["cp"][ok], color="black", lw=1.4, label=r"unbiased risk estimate ($\sigma$ known)")
    a.plot(R["df"][ok], R["cv"][ok] - R["sigma"] ** 2, color=BLUE, lw=1.1, ls="--", label=r"leave-one-out score $-\,\sigma^2$")
    a.axvline(R["nu"], color=RED, ls=":", lw=1)
    a.legend(frameon=False, fontsize=8)
    _style(a, r"effective degrees of freedom $\nu=\mathrm{tr}\,L$", "estimated risk")
    a.set_title("k = 100 bins, n = 1000: h = %.4f, $\\nu$ = %.1f" % (R["h"], R["nu"]))
    a = axes[1, 0]
    g = R["grid"]
    a.fill_between(g, R["lo"], R["hi"], color="#c6dbef", lw=0, label="95% band")
    a.plot(g, R["f"], color="black", lw=1.4, label="estimate")
    a.plot(g, bart_pdf(g), color=RED, lw=1, ls="--", label="true density")
    a.set_xlim(-3, 3)
    a.set_ylim(0, None)
    a.legend(frameon=False, loc="upper left", fontsize=8)
    _style(a, "x", "density")
    fig.tight_layout()
    savefig(fig, CH, "fig6-6", out)


# =========================================================================== supplementary figures
BETA22 = dict(cdf=lambda x: 3 * x ** 2 - 2 * x ** 3, int_f2=1.2, int_fp2=12.0)


def fig_6_S1(out=None):
    """Exact risk of a histogram of Beta(2,2) data against (6.12), and n times the gap."""
    fig, ax = common.panel_grid(1, 2, size=(3.5, 2.8))
    a = ax[0, 0]
    n = 1000
    ms = np.arange(2, 61)
    ex = np.array([hist_mise_exact(BETA22["cdf"], BETA22["int_f2"], m, n, 0, 1) for m in ms])
    asy = hist_asym(1 / ms, n, BETA22["int_fp2"])
    a.plot(ms, ex, color="black", lw=1.5, label="exact risk")
    a.plot(ms, asy, color=BLUE, lw=1.2, ls="--", label="(6.12)")
    a.plot(ms, asy - BETA22["int_f2"] / n, color=ORANGE, lw=1.2, ls=":", label=r"(6.12) $-\int f^2/n$")
    hs, C = hist_hstar(n, BETA22["int_fp2"])
    a.axvline(1 / hs, color=RED, lw=0.8, ls="--")
    a.set_ylim(0, 0.06)
    a.legend(frameon=False, fontsize=8)
    _style(a, "number of bins m (n = 1000)", "risk")
    a = ax[0, 1]
    ns = np.unique(np.round(np.exp(np.linspace(np.log(100), np.log(1e6), 25))).astype(int))
    gap = []
    for nn in ns:
        m = max(1, int(round(1 / hist_hstar(nn, BETA22["int_fp2"])[0])))
        gap.append(nn * (hist_mise_exact(BETA22["cdf"], BETA22["int_f2"], m, nn, 0, 1) - hist_asym(1 / m, nn, BETA22["int_fp2"])))
    a.semilogx(ns, gap, "o-", color="black", ms=3, lw=1)
    a.axhline(-BETA22["int_f2"], color=RED, ls="--", lw=1, label=r"$-\int f^2=-1.2$")
    a.set_ylim(-1.6, 0.2)
    a.legend(frameon=False, fontsize=8)
    _style(a, "n", r"$n\times$(exact $-$ (6.12)) at $m\approx 1/h^*$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S1", out)


def band_coverage_table(reps=400):
    """Coverage of the band (6.21) for fbar for the Bart Simpson density restricted to [-1.5, 1.5]
    (where f >= 0.12) and to [-3, 3] (where f falls to 0.004), n = 1000 and 10000."""
    path = os.path.join(CACHE_DIR, "ch06_band_cov.json")
    if os.path.exists(path):
        return json.load(open(path))
    os.makedirs(CACHE_DIR, exist_ok=True)
    rng = np.random.default_rng(20)
    res = {}
    for lab, (a, b) in (("inner", (-1.5, 1.5)), ("full", (-3.0, 3.0))):
        for n in (1000, 10000):
            ms = [5, 10, 20, 40, 80, 160] if n == 1000 else [10, 20, 40, 80, 160, 320]
            res["%s %d" % (lab, n)] = [[m, hist_band_coverage(bart_sample, bart_cdf, n, m, a, b, reps, rng)] for m in ms]
    json.dump(res, open(path, "w"))
    return res


def fig_6_S2(out=None):
    """Simulated coverage of the histogram band for fbar as the number of bins grows."""
    res = band_coverage_table()
    fig, ax = common.panel_grid(1, 2, size=(3.5, 2.8))
    for a, lab, t in ((ax[0, 0], "inner", "[-1.5, 1.5]: f bounded below"), (ax[0, 1], "full", "[-3, 3]: f nearly 0 in the tails")):
        for n, col in ((1000, BLUE), (10000, MAGENTA)):
            rows = np.array(res["%s %d" % (lab, n)])
            a.semilogx(rows[:, 0], rows[:, 1], "o-", color=col, label="n = %d" % n, ms=4)
        a.axhline(0.95, color="black", ls="--", lw=0.8)
        a.set_ylim(0.5, 1.0)
        a.set_title(t, fontsize=9.5)
        a.legend(frameon=False, loc="lower left")
        _style(a, "number of bins m", "coverage of fbar")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S2", out)


def bart_cv_sims(reps=200, n=1000):
    """Cross-validated bandwidths of reps Bart Simpson samples (cached)."""
    path = os.path.join(CACHE_DIR, "ch06_bart_hcv.json")
    if os.path.exists(path):
        return json.load(open(path))
    os.makedirs(CACHE_DIR, exist_ok=True)
    rng = np.random.default_rng(7)
    hs = np.exp(np.linspace(np.log(0.015), np.log(0.5), 40))
    out = []
    for _ in range(reps):
        x = bart_sample(n, rng)
        D = x[:, None] - x[None, :]
        J = [kde_lscv(x, h, "gauss", D) for h in hs]
        out.append([float(hs[int(np.argmin(J))]), float(normal_reference_h(x))])
    json.dump(out, open(path, "w"))
    return out


def fig_6_S3(out=None):
    """Exact MISE of the Gaussian-kernel estimator of the Bart Simpson density (n = 1000)."""
    n = 1000
    hs = np.exp(np.linspace(np.log(0.01), np.log(1.0), 300))
    mise = np.array([mise_mixture(h, n, BART_W, BART_MU, BART_SD) for h in hs])
    A = mixture_A(BART_W, BART_MU, BART_SD)
    amise = 0.25 * hs ** 4 * A + KCONST["gauss"][1] / (n * hs)
    sims = np.array(bart_cv_sims())
    fig, ax = common.panel_grid(1, 1, size=(6.0, 3.0))
    a = ax[0, 0]
    a.loglog(hs, mise, color="black", lw=1.6, label="exact MISE")
    a.loglog(hs, amise, color=BLUE, ls="--", lw=1.2, label="(6.29) without remainders")
    a.axvline(hs[np.argmin(mise)], color="black", lw=0.8, ls=":")
    a.axvline(np.median(sims[:, 1]), color=ORANGE, lw=1.2, label="Normal reference (median)")
    yl = a.get_ylim()
    a.plot(sims[:, 0], np.full(len(sims), 0.0035) * np.exp(np.random.default_rng(1).uniform(-0.25, 0.25, len(sims))),
           "|", color=MAGENTA, ms=8, label="CV bandwidths, 200 samples")
    a.set_ylim(0.002, 2.0)
    a.legend(frameon=False, fontsize=8, loc="upper left")
    _style(a, "bandwidth h", "MISE")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S3", out)


def fig_6_S4(out=None):
    """Local likelihood density estimates of degree 0, 1, 2 for the glass refractive index."""
    x = glass_ri()
    g = np.linspace(-8, 17, 501)
    fig, ax = common.panel_grid(1, 2, size=(3.5, 2.8))
    for a, h in zip(ax[0], (0.6, 1.5)):
        a.plot(np.sort(x), np.full(len(x), -0.004), "|", color=GREY, ms=5)
        for p, col, ls in ((0, BLUE, "-"), (1, MAGENTA, "--"), (2, GREEN, ":")):
            a.plot(g, local_likelihood_density(x, g, h, p), color=col, ls=ls, lw=1.3, label="degree %d" % p)
        a.set_title("h = %.1f" % h)
        a.legend(frameon=False, fontsize=8)
        _style(a, "refractive index (coded)", "density")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S4", out)


def faithful_fit():
    X = faithful()
    n = len(X)
    sd = X.std(0, ddof=1)
    hnr = sd * n ** (-1 / 6)                     # Normal reference in d = 2
    ss = np.exp(np.linspace(np.log(0.1), np.log(1.5), 40))
    J = np.array([kde2_lscv(X, s * hnr) for s in ss])
    s = float(ss[np.argmin(J)])
    return X, hnr, s * hnr


def fig_6_S5(out=None):
    """Product-kernel estimate for Old Faithful with the Normal reference and the CV bandwidths."""
    X, hnr, hcv = faithful_fit()
    gx = np.linspace(1.3, 5.5, 120)
    gy = np.linspace(40, 100, 120)
    GX, GY = np.meshgrid(gx, gy)
    G = np.c_[GX.ravel(), GY.ravel()]
    fig, ax = common.panel_grid(1, 2, size=(3.5, 3.0))
    for a, h, t in ((ax[0, 0], hnr, "Normal reference"), (ax[0, 1], hcv, "cross-validation")):
        Z = kde2(X, G, h).reshape(GX.shape)
        a.contour(GX, GY, Z, levels=8, colors=BLUE, linewidths=0.9)
        a.plot(X[:, 0], X[:, 1], ".", color=GREY, ms=2.5)
        a.set_title("%s: h = (%.2f, %.1f)" % (t, h[0], h[1]))
        _style(a, "eruption time (min)", "waiting time (min)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S5", out)


def glass_summary():
    x = glass_ri()
    a, b = -7.0, 16.0
    ms, J = hist_cv_curve(x, a, b, 120)
    mcv = int(ms[np.argmin(J)])
    hs = np.exp(np.linspace(np.log(0.05), np.log(4), 80))
    res = dict(x=x, a=a, b=b, ms=ms, J=J, mcv=mcv, hs=hs)
    for kind in ("gauss", "epan", "boxcar"):
        hk, _, Jk = kde_hcv(x, hs * (2.2 if kind != "gauss" else 1.0), kind)
        res["h_" + kind] = hk
        res["J_" + kind] = Jk
    res["hnr"] = normal_reference_h(x)
    return res


def fig_6_S6(out=None):
    """Exercise 6: glass refractive index, histogram with band (CV m) and kernel estimates with bands."""
    S = glass_summary()
    x, a0, b0 = S["x"], S["a"], S["b"]
    fig, ax = common.panel_grid(2, 2, size=(3.5, 2.6))
    a = ax[0, 0]
    a.plot(S["ms"], S["J"], color="black", lw=1)
    a.axvline(S["mcv"], color=RED, ls="--", lw=1)
    _style(a, "number of bins m", r"$\widehat J$")
    a.set_title("histogram CV: m = %d" % S["mcv"])
    a = ax[0, 1]
    m = S["mcv"]
    fh, lo, hi, c, h = hist_band(x, m, a0, b0)
    e = a0 + np.arange(m + 1) * h
    a.fill_between(np.repeat(e, 2)[1:-1], np.repeat(lo, 2), np.repeat(hi, 2), color="#9ecae1", lw=0)
    a.step(e, np.r_[fh, fh[-1]], where="post", color="black", lw=0.8)
    a.set_xlim(a0, b0)
    a.set_title("histogram, 95% band")
    _style(a, "refractive index (coded)", "density")
    g = np.linspace(a0, b0, 801)
    a = ax[1, 0]
    for kind, col in (("gauss", BLUE), ("epan", MAGENTA), ("boxcar", GREEN)):
        a.plot(g, kde(x, g, S["h_" + kind], kind), color=col, lw=1.1, label="%s, h = %.2f" % (kind, S["h_" + kind]))
    a.legend(frameon=False, fontsize=7.5)
    a.set_title("kernel estimates, h by CV")
    _style(a, "refractive index (coded)", "density")
    a = ax[1, 1]
    f, lo, hi, c, k0 = kde_band(x, g, S["h_gauss"])
    a.fill_between(g, lo, hi, color="#c6dbef", lw=0)
    a.plot(g, f, color=BLUE, lw=1.2)
    f2 = kde(x, g, S["hnr"])
    a.plot(g, f2, color=ORANGE, lw=1, ls="--", label="Normal reference h = %.2f" % S["hnr"])
    a.legend(frameon=False, fontsize=7.5)
    a.set_title("Gaussian, h = %.2f: 95%% band" % S["h_gauss"])
    _style(a, "refractive index (coded)", "density")
    fig.tight_layout()
    savefig(fig, CH, "fig6-S6", out)


def fig_6_S7(out=None):
    """Exercise 7: Gaussian kernel estimates of the glass data with bands, for six bandwidths."""
    x = glass_ri()
    g = np.linspace(-7, 16, 801)
    fig, ax = common.panel_grid(2, 3, size=(2.6, 2.2))
    for a, h in zip(ax.ravel(), (0.15, 0.3, 0.5, 0.8, 1.3, 2.2)):
        f, lo, hi, c, k0 = kde_band(x, g, h)
        a.fill_between(g, lo, hi, color="#c6dbef", lw=0)
        a.plot(g, f, color=BLUE, lw=1)
        a.set_title("h = %.2f (c = %.2f)" % (h, c))
        a.set_ylim(0, 0.6)
        a.set_xlim(-7, 16)
    fig.tight_layout()
    savefig(fig, CH, "fig6-S7", out)


def ex10_sims(reps=100):
    """Monte Carlo ISE of the CV kernel estimator and of the regression method, n = 25..1000."""
    path = os.path.join(CACHE_DIR, "ch06_ex10.json")
    if os.path.exists(path):
        return json.load(open(path))
    os.makedirs(CACHE_DIR, exist_ok=True)
    rng = np.random.default_rng(10)
    g = np.linspace(-3, 3, 601)
    f0 = bart_pdf(g)
    out = {}
    for n in (25, 50, 100, 1000):
        hs = np.exp(np.linspace(np.log(0.02), np.log(1.5), 40))
        rows = []
        for _ in range(reps):
            x = bart_sample(n, rng)
            D = x[:, None] - x[None, :]
            J = [kde_lscv(x, h, "gauss", D) for h in hs]
            hk = hs[int(np.argmin(J))]
            e1 = np.trapz((kde(x, g, hk) - f0) ** 2, g)
            k = max(int(round(n / 10)), 10)
            R = density_by_regression(x, k, -3.0, 3.0, grid=g)
            e2 = np.trapz((R["f"] - f0) ** 2, g)
            rows.append([e1, e2])
        out[str(n)] = rows
    json.dump(out, open(path, "w"))
    return out


def fig_6_S8(out=None):
    """Exercise 10: one sample at each n with both estimates, and the Monte Carlo ISE."""
    g = np.linspace(-3, 3, 601)
    fig, ax = common.panel_grid(2, 2, size=(3.4, 2.5))
    for a, n in zip(ax.ravel(), (25, 50, 100, 1000)):
        x = bart_data(n)
        hs = np.exp(np.linspace(np.log(0.02), np.log(1.5), 40))
        hk, _, _ = kde_hcv(x, hs)
        k = max(int(round(n / 10)), 10)
        R = density_by_regression(x, k, -3.0, 3.0, grid=g)
        a.plot(g, bart_pdf(g), color=GREY, lw=0.9, ls="--")
        a.plot(g, kde(x, g, hk), color=BLUE, lw=1.1, label="kernel, CV")
        a.plot(g, R["f"], color=MAGENTA, lw=1.1, label="regression (k = %d)" % k)
        a.set_title("n = %d" % n)
        a.set_ylim(0, 1.0)
        a.set_xlim(-3, 3)
    ax[0, 0].legend(frameon=False, fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig6-S8", out)


FIGURES = {"6.1": fig_6_1, "6.2": fig_6_2, "6.3": fig_6_3, "6.4": fig_6_4, "6.5": fig_6_5, "6.6": fig_6_6,
           "6.S1": fig_6_S1, "6.S2": fig_6_S2, "6.S3": fig_6_S3, "6.S4": fig_6_S4, "6.S5": fig_6_S5,
           "6.S6": fig_6_S6, "6.S7": fig_6_S7, "6.S8": fig_6_S8}


# =========================================================================== demo data
def export_json():
    """Data for the browser demonstrations: galaxy redshifts, the glass refractive index and the
    n = 1000 Bart Simpson sample (the demos regenerate it from the seed and check it)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    d = dict(galaxy=[round(float(v), 6) for v in galaxy()], glass=[float(v) for v in glass_ri()],
             bart=[round(float(v), 6) for v in bart_data()], bart_seed=SEED_BART)
    path = os.path.join(DATA_OUT, "ch06-density.json")
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


if __name__ == "__main__":
    import sys
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
