"""Wasserman (2006), Chapter 3: The Bootstrap and the Jackknife.

Companion code for Chapter 3 of L. Wasserman, All of Nonparametric Statistics (Springer, 2006),
pp. 27-41, written from scratch with numpy, scipy and matplotlib, to be read next to the lecture
notes (../ch03-bootstrap-jackknife.html).

Contents
* Data: nerve() (799 nerve pulse waiting times, Examples 3.10, 3.14, 3.17) and law() (Efron's law
  school data of Exercise 3.2, with the last GPA read as 2.96; see the notes on the book).
* Plug-in statistics and influence functions: skewness, skew_influence (the correct influence
  function and, with book=True, the expression printed in Example 3.10), corr, corr_influence.
* Section 3.1, the jackknife: jackknife() (b_jack (3.1), T_jack, pseudo-values, v_jack (3.4)) and
  jack_ell() (the influence-function form l_i = (n - 1)(T_n - T_(-i))).
* Sections 3.2-3.4, the bootstrap: boot_index, boot_reps, v_boot (3.11), intervals() (Normal,
  basic pivotal (3.15), studentized pivotal and percentile).
* Section 3.5 and the appendix: edgeworth_mean (the one-term expansion (3.23) for the mean),
  mallows_d2_exp (Mallows' distance between an empirical cdf and Exp(1), exactly), and the
  one-sided coverage study for the mean.
* Generators compatible with DK.rng of courses/demo-kit.js (js_uniforms, js_normals) and the routines
  behind the three demonstration pages, so that the numbers shown there can be reproduced here.

Figures. The chapter has a single figure, Figure 3.1, which is pseudo-code for bootstrapping the
median: nothing is computed in it, so it is skipped as a figure (the notes give it as an algorithm,
and boot_reps(x, np.median, ...) is that algorithm). Supplementary figures (ours):
  3.S1 the jackknife bias correction (exact bias curves and simulation) and l_i against L(X_i);
  3.S2 the four bootstrap intervals for the nerve-data skewness (Example 3.17);
  3.S3 coverage of the four intervals for the skewness of lognormal data (Exercise 3.6);
  3.S4 accuracy of one-sided intervals for a mean, and the Edgeworth expansion (3.23);
  3.S5 parametric against nonparametric bootstrap (Exercises 3.10 and 3.11);
  3.S6 the appendix: Mallows' distance and the Kolmogorov distance of the bootstrap.
Run `python3 ch03_bootstrap_jackknife.py` (all figures and demo data; a few minutes on one thread,
the simulations are cached in ./cache), `--list`, or `--fig 3.S2`.
"""
import json
import math
import os

import numpy as np
from scipy import stats

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

plt = common.plt
CH = 3
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_DIR = os.path.normpath(os.path.join(HERE, "..", "data"))
M32 = 0xFFFFFFFF


# ========================================================================== data
def nerve():
    """The 799 waiting times (seconds) between nerve pulses (Cox and Lewis 1966)."""
    with open(common.nps_file("nerve.dat")) as f:
        return np.array(f.read().split(), dtype=float)


LSAT = np.array([576, 635, 558, 578, 666, 580, 555, 661, 651, 605, 653, 575, 545, 572, 594], float)
# Exercise 3.2 prints 3.96 for the last school; Efron's data (and the correlation 0.776 that the
# companion book quotes for them) have 2.96. GPA_PRINTED keeps the printed value for comparison.
GPA = np.array([3.39, 3.30, 2.81, 3.03, 3.44, 3.07, 3.00, 3.43, 3.36, 3.13, 3.12, 2.74, 2.76, 2.88, 2.96])
GPA_PRINTED = GPA.copy()
GPA_PRINTED[-1] = 3.96


def law(printed=False):
    """15 x 2 array (LSAT, GPA)."""
    return np.column_stack([LSAT, GPA_PRINTED if printed else GPA])


# ========================================================================== statistics
def skewness(x, axis=-1):
    """Plug-in skewness int (x - mu)^3 dF / sigma^3 (divisor n), along an axis."""
    x = np.asarray(x, float)
    d = x - x.mean(axis=axis, keepdims=True)
    return (d ** 3).mean(axis=axis) / (d ** 2).mean(axis=axis) ** 1.5


def skew_influence(x, book=False):
    """Empirical influence function L_hat(X_i) of the skewness at F_n.

    Correct form: [(x-mu)^3 - mu3 - 3 sigma^2 (x-mu)] / sigma^3 - (3/2) T ((x-mu)^2 - sigma^2) / sigma^2.
    book=True drops the term -3 (x - mu) / sigma, as the expression printed in Example 3.10 does."""
    x = np.asarray(x, float)
    mu = x.mean(-1, keepdims=True)
    d = x - mu
    s2 = (d ** 2).mean(-1, keepdims=True)
    s = np.sqrt(s2)
    T = (d ** 3).mean(-1, keepdims=True) / s ** 3
    L = d ** 3 / s ** 3 - T * (1 + 1.5 * (d ** 2 - s2) / s2)
    if not book:
        L = L - 3 * d / s
    return L


def se_influence(L):
    """Nonparametric delta-method standard error sqrt(sum L_i^2) / n (along the last axis)."""
    L = np.asarray(L, float)
    return np.sqrt((L ** 2).sum(-1)) / L.shape[-1]


def corr(xy):
    """Sample correlation of the columns of an (..., n, 2) array."""
    xy = np.asarray(xy, float)
    d = xy - xy.mean(-2, keepdims=True)
    sxy = (d[..., 0] * d[..., 1]).mean(-1)
    return sxy / np.sqrt((d[..., 0] ** 2).mean(-1) * (d[..., 1] ** 2).mean(-1))


def corr_influence(xy):
    """Empirical influence function of the correlation: u v - rho (u^2 + v^2) / 2 with u, v the
    standardised coordinates (divisor n)."""
    xy = np.asarray(xy, float)
    d = xy - xy.mean(-2, keepdims=True)
    sd = np.sqrt((d ** 2).mean(-2, keepdims=True))
    u, v = d[..., 0] / sd[..., 0], d[..., 1] / sd[..., 1]
    r = (u * v).mean(-1, keepdims=True)
    return u * v - r * (u ** 2 + v ** 2) / 2


def q7(a, p, axis=-1):
    """Sample quantile with linear interpolation (the rule used by the demos)."""
    return np.quantile(a, p, axis=axis)


def iqr_scale(x, axis=-1):
    """(q.75 - q.25) / 1.34, the Normal-consistent scale of Exercise 3.7."""
    return (q7(x, 0.75, axis) - q7(x, 0.25, axis)) / 1.34


# ========================================================================== Section 3.1: the jackknife
def leave_one_out(x):
    """(n, n-1, ...) array whose i-th entry is the data with observation i removed."""
    x = np.asarray(x)
    n = x.shape[0]
    idx = np.array([np.r_[0:i, i + 1:n] for i in range(n)])
    return x[idx]


def jackknife(x, stat):
    """The jackknife of Section 3.1 for stat(sample) -> number, where stat accepts a stacked
    array of samples along axis 0 (as skewness, np.mean(axis=-1), corr do).

    Returns T_n, the leave-one-out values T_(-i), b_jack (3.1), T_jack, the pseudo-values
    T_i = n T_n - (n-1) T_(-i), and v_jack = s^2 / n (3.4)."""
    x = np.asarray(x, float)
    n = x.shape[0]
    T = float(stat(x))
    loo = np.asarray(stat(leave_one_out(x)), float)
    tbar = loo.mean()
    b = (n - 1) * (tbar - T)
    pseudo = n * T - (n - 1) * loo
    v = pseudo.var(ddof=1) / n
    return dict(T=T, loo=loo, b=b, Tjack=T - b, pseudo=pseudo, v=v, se=math.sqrt(v))


def jack_ell(jk):
    """l_i = (n - 1)(T_n - T_(-i)), the influence-function form of the jackknife."""
    n = len(jk["loo"])
    return (n - 1) * (jk["T"] - jk["loo"])


# ========================================================================== Sections 3.2-3.4: the bootstrap
def boot_index(n, B, rng):
    """B x n matrix of resampling indices (sampling with replacement)."""
    return rng.integers(0, n, size=(B, n))


def boot_reps(x, stat, B, rng=None, idx=None):
    """B bootstrap replications of stat (stat must accept a (B, n, ...) stack)."""
    x = np.asarray(x, float)
    if idx is None:
        idx = boot_index(x.shape[0], B, rng)
    return np.asarray(stat(x[idx]), float)


def v_boot(reps):
    """Equation (3.11): the variance of the replications with divisor B."""
    reps = np.asarray(reps, float)
    return float(((reps - reps.mean()) ** 2).mean())


def intervals(T, reps, alpha=0.05, se_star=None, se_hat=None):
    """The four 1 - alpha intervals of Section 3.4 from replications reps of T.

    normal: T -/+ z se_boot; pivotal (3.15): (2T - t*_{1-a/2}, 2T - t*_{a/2});
    percentile: (t*_{a/2}, t*_{1-a/2}); studentized (needs se_star, the se of each replication):
    (T - z*_{1-a/2} se, T - z*_{a/2} se) with Z*_b = (T*_b - T) / se*_b and se = se_hat if given,
    else se_boot (as the book writes it)."""
    reps = np.asarray(reps, float)
    z = stats.norm.ppf(1 - alpha / 2)
    se = math.sqrt(v_boot(reps))
    lo, hi = q7(reps, alpha / 2), q7(reps, 1 - alpha / 2)
    out = dict(se=se, normal=(T - z * se, T + z * se), pivotal=(2 * T - hi, 2 * T - lo),
               percentile=(lo, hi))
    if se_star is not None:
        Z = (reps - T) / np.asarray(se_star, float)
        s = se if se_hat is None else se_hat
        out["studentized"] = (T - q7(Z, 1 - alpha / 2) * s, T - q7(Z, alpha / 2) * s)
        out["Z"] = Z
    return out


def skew_with_se(xs):
    """Skewness and its delta-method standard error for each row of a (B, n) stack."""
    return skewness(xs), se_influence(skew_influence(xs))


def corr_with_se(xys):
    return corr(xys), se_influence(corr_influence(xys))


# ========================================================================== DK.rng-compatible streams
def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed) (mulberry32). Its state grows by the
    constant 0x6D2B79F5 at each call, so 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, start=0):
    """n values of DK.rng(seed).norm() after `start` uniforms (Box-Muller, cos then sin)."""
    k = (n + 1) // 2
    u = js_uniforms(seed, 2 * k, start)
    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]


def js_boot_index(seed, n, B, start=0):
    """Resampling indices as the demos draw them: floor(u * n), row by row."""
    u = js_uniforms(seed, n * B, start).reshape(B, n)
    return np.floor(u * n).astype(int)


# ========================================================================== demo 1: jackknife bias
JB_STATS = ("inv_mean", "exp_mean", "var", "corr")
JB_NS = (5, 10, 20, 40, 80)


def jb_true(stat, n):
    """theta and the exact biases of T_n and T_jack where they have closed forms (else None)."""
    if stat == "inv_mean":     # X ~ Exp(1), T = 1 / mean, theta = 1: E 1/Xbar_m = m/(m-1)
        bt = n / (n - 1) - 1
        bj = n * n / (n - 1) - (n - 1) ** 2 / (n - 2) - 1
        return 1.0, bt, bj
    if stat == "exp_mean":     # X ~ N(0,1), T = exp(mean), theta = 1: E exp(Xbar_m) = exp(1/(2m))
        bt = math.exp(0.5 / n) - 1
        bj = n * math.exp(0.5 / n) - (n - 1) * math.exp(0.5 / (n - 1)) - 1
        return 1.0, bt, bj
    if stat == "var":          # X ~ N(0,1), plug-in variance, theta = 1: T_jack = s^2 is unbiased
        return 1.0, -1.0 / n, 0.0
    return 0.5, None, None     # correlation of a bivariate Normal with rho = 0.5


def jb_data(stat, seed, n, start):
    """Data set from the stream DK.rng(seed) after `start` uniforms; returns (x, uniforms used)."""
    if stat == "inv_mean":
        u = js_uniforms(seed, n, start)
        return -np.log(u), n
    if stat in ("exp_mean", "var"):
        k = 2 * ((n + 1) // 2)
        return js_normals(seed, n, start), k
    k = 2 * n                      # pairs: z1, z2 -> (z1, rho z1 + sqrt(1 - rho^2) z2)
    z = js_normals(seed, 2 * n, start).reshape(n, 2)
    return np.column_stack([z[:, 0], 0.5 * z[:, 0] + math.sqrt(0.75) * z[:, 1]]), k


def jb_stat(stat, x):
    if stat == "inv_mean":
        return 1.0 / x.mean(-1)
    if stat == "exp_mean":
        return np.exp(x.mean(-1))
    if stat == "var":
        return x.var(-1)
    return corr(x)


def jb_demo(stat, n, R, seed):
    """Monte Carlo biases of T_n and T_jack over R data sets (data set r uses DK.rng(seed + 7919 r))."""
    T = np.empty(R)
    TJ = np.empty(R)
    for r in range(R):
        x, _ = jb_data(stat, seed + 7919 * r, n, 0)
        jk = jackknife(x, lambda s: jb_stat(stat, s))
        T[r], TJ[r] = jk["T"], jk["Tjack"]
    th = jb_true(stat, n)[0]
    return dict(bias_T=T.mean() - th, bias_J=TJ.mean() - th, se_T=T.std(ddof=1) / math.sqrt(R),
                se_J=TJ.std(ddof=1) / math.sqrt(R))


# ========================================================================== demo 2: the four intervals
def si_demo(which, B, seed, alpha=0.05):
    """The nerve / law-school bootstrap of the studentized-interval demo, with DK.rng(seed)."""
    if which == "law":
        x = law()
        f = corr_with_se
    else:
        x = nerve()
        if which == "skew":
            f = skew_with_se
        else:
            f = lambda xs: (xs.mean(-1), xs.std(-1) / math.sqrt(xs.shape[-1]))
    n = x.shape[0]
    T, seT = f(x[None])
    T, seT = float(T[0]), float(seT[0])
    idx = js_boot_index(seed, n, B)
    reps, sestar = f(x[idx])
    iv = intervals(T, reps, alpha, se_star=sestar)
    iv["T"], iv["se_delta"] = T, seT
    return iv


# ========================================================================== demo 3 / Fig 3.S4: one-sided accuracy
POP_MEAN = {"exp": 1.0, "lnorm": math.exp(0.5), "chisq1": 1.0, "unif": 0.5}


def os_draw_js(pop, seed, n):
    """One data set for the accuracy demo from DK.rng(seed); returns (x, uniforms used)."""
    if pop == "exp":
        return -np.log(js_uniforms(seed, n)), n
    if pop == "unif":
        return js_uniforms(seed, n), n
    k = 2 * ((n + 1) // 2)
    z = js_normals(seed, n)
    return (np.exp(z) if pop == "lnorm" else z * z), k


def one_sided_bounds(x, idx, alpha):
    """Lower 1 - alpha bounds for the mean of x from resamples x[idx]: Normal, pivotal, percentile,
    studentized (se = sigma_hat / sqrt(n) for the data and for each resample)."""
    n = x.shape[-1]
    T = x.mean()
    xs = x[idx]
    reps = xs.mean(-1)
    se_b = reps.std()
    se_hat = x.std() / math.sqrt(n)
    se_s = xs.std(-1) / math.sqrt(n)
    z = stats.norm.ppf(1 - alpha)
    Z = (reps - T) / se_s
    with np.errstate(divide="ignore", invalid="ignore"):
        Z = np.where(se_s > 0, Z, 0.0)
    return dict(normal=T - z * se_b, pivotal=2 * T - q7(reps, 1 - alpha),
                percentile=q7(reps, alpha), studentized=T - q7(Z, 1 - alpha) * se_hat)


def os_demo(pop, n, R, B, seed, alpha=0.05):
    """Miss rates P(mu < lower bound) as the accuracy demo computes them: data set r from
    DK.rng(seed + 7919 r), its B resamples continuing the same stream."""
    mu = POP_MEAN[pop]
    miss = {k: 0 for k in ("normal", "pivotal", "percentile", "studentized")}
    for r in range(R):
        s = seed + 7919 * r
        x, used = os_draw_js(pop, s, n)
        idx = js_boot_index(s, n, B, start=used)
        lb = one_sided_bounds(x, idx, alpha)
        for k in miss:
            miss[k] += mu < lb[k]
    return {k: v / R for k, v in miss.items()}


def edgeworth_mean(z, n, gamma):
    """One-term Edgeworth approximation (3.23) for the standardised mean: Phi(z) + a(z) phi(z)/sqrt n
    with a(z) = -gamma (z^2 - 1) / 6."""
    return stats.norm.cdf(z) - gamma * (z ** 2 - 1) / 6 * stats.norm.pdf(z) / math.sqrt(n)


def edgeworth_t(z, n, gamma):
    """One-term Edgeworth approximation for the studentized mean: a(z) = gamma (2 z^2 + 1) / 6."""
    return stats.norm.cdf(z) + gamma * (2 * z ** 2 + 1) / 6 * stats.norm.pdf(z) / math.sqrt(n)


# ========================================================================== appendix
def mallows_d2_exp(x):
    """Mallows distance d_2(F_n, F) for F = Exp(1), exactly, through the quantile coupling
    d_2^2 = int_0^1 (F_n^{-1}(u) - F^{-1}(u))^2 du."""
    xs = np.sort(np.asarray(x, float))
    n = xs.size
    u = np.arange(n + 1) / n

    def G1(v):  # int_0^v -log(1-w) dw
        w = 1 - v
        return np.where(w > 0, w * np.log(np.where(w > 0, w, 1)) + v, 1.0)

    g = np.diff(G1(u))
    d2sq = (xs ** 2).sum() / n - 2 * (xs * g).sum() + 2.0
    return math.sqrt(max(d2sq, 0.0))


def kolmogorov_boot_mean_exp(x, B, rng):
    """sup_t |H_hat_n(t) - H_n(t)| for the mean of Exp(1) data: H_n is the exact cdf of
    sqrt(n)(Xbar - 1) (a Gamma law), H_hat_n is estimated from B resamples."""
    n = x.size
    v = np.sort(math.sqrt(n) * (x[boot_index(n, B, rng)].mean(-1) - x.mean()))
    Hn = stats.gamma.cdf(1 + v / math.sqrt(n), a=n, scale=1.0 / n)
    k = np.arange(1, B + 1) / B
    return float(max(np.abs(k - Hn).max(), np.abs(k - 1.0 / B - Hn).max()))


# ========================================================================== cache helper
def cached(name, fn):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch03_" + name + ".json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    out = fn()
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# ========================================================================== numbers of the examples
def example_numbers(B=1000, seed=1):
    """Examples 3.10, 3.14, 3.17 on the nerve data (resamples from DK.rng(seed), as on the demo page)."""
    x = nerve()
    T = float(skewness(x))
    jk = jackknife(x, skewness)
    se_if = float(se_influence(skew_influence(x)))
    se_if_book = float(se_influence(skew_influence(x, book=True)))
    xs = x[js_boot_index(seed, x.size, B)]
    reps, sestar = skew_with_se(xs)
    iv = intervals(T, reps, 0.05, se_star=sestar)
    return dict(T=T, se_jack=jk["se"], b_jack=jk["b"], se_if=se_if, se_if_book=se_if_book,
                se_boot=iv["se"], normal=iv["normal"], percentile=iv["percentile"],
                pivotal=iv["pivotal"], studentized=iv["studentized"],
                normal2=(T - 2 * jk["se"], T + 2 * jk["se"]))


# ========================================================================== exercises
def ex2_numbers(B=2000, seed=2):
    """Exercise 3.2: the law school correlation, its standard errors and a studentized interval."""
    x = law()
    r = float(corr(x))
    jk = jackknife(x, corr)
    rng = np.random.default_rng(seed)
    reps, sestar = corr_with_se(x[boot_index(15, B, rng)])
    ok = sestar > 1e-12                 # a resample with all points on a line has se* = 0
    iv = intervals(r, reps[ok], 0.05, se_star=sestar[ok])
    return dict(r=r, r_printed=float(corr(law(True))), se_if=float(se_influence(corr_influence(x))),
                se_jack=jk["se"], se_boot=iv["se"], studentized=iv["studentized"], normal=iv["normal"],
                percentile=iv["percentile"], pivotal=iv["pivotal"], dropped=int((~ok).sum()))


def ex3_enumerate(x):
    """Exact ideal bootstrap variance of Xbar*^2 by enumerating all n^n resamples (small n)."""
    import itertools
    x = np.asarray(x, float)
    n = x.size
    v = np.array([np.mean(x[list(c)]) ** 2 for c in itertools.product(range(n), repeat=n)])
    return float(v.var())


def ex3_formula(x, book=False):
    x = np.asarray(x, float)
    n = x.size
    d = x - x.mean()
    a2, a3, a4 = (d ** 2).mean(), (d ** 3).mean(), (d ** 4).mean()
    if book:
        a3 = (np.abs(d) ** 3).mean()
    v = 4 * x.mean() ** 2 * a2 / n + 4 * x.mean() * a3 / n ** 2 + a4 / n ** 3
    return float(v if book else v + (2 * n - 3) * a2 ** 2 / n ** 3)


def ex5_numbers(B=2000, seed=5):
    """Exercise 3.5: parametric (lognormal) bootstrap for the nerve skewness."""
    x = nerve()
    y = np.log(x)
    mu, sig = y.mean(), y.std()
    T = float(skewness(x))
    rng = np.random.default_rng(seed)
    xs = np.exp(rng.normal(mu, sig, (B, x.size)))
    reps, sestar = skew_with_se(xs)
    iv = intervals(T, reps, 0.05, se_star=sestar)
    w = math.exp(sig ** 2)
    return dict(mu=mu, sigma=sig, T=T, skew_fitted=(w + 2) * math.sqrt(w - 1), se=iv["se"],
                mean_reps=float(reps.mean()), normal=iv["normal"], percentile=iv["percentile"],
                pivotal=iv["pivotal"], studentized=iv["studentized"])


def ex7_study(R=1000, B=500, n=25, seed=7):
    """Exercise 3.7: t_3 data, theta = (q.75 - q.25) / 1.34; coverage and median length of the
    Normal interval with jackknife se, with bootstrap se, and the percentile interval."""
    theta = 2 * stats.t.ppf(0.75, 3) / 1.34
    rng = np.random.default_rng(seed)
    z = stats.norm.ppf(0.975)
    cov = {"jack": 0, "boot": 0, "pct": 0}
    ln = {"jack": [], "boot": [], "pct": []}
    for r in range(R):
        x = rng.standard_t(3, n)
        T = float(iqr_scale(x))
        sj = jackknife(x, iqr_scale)["se"]
        reps = iqr_scale(x[boot_index(n, B, rng)])
        sb = reps.std()
        ivs = {"jack": (T - z * sj, T + z * sj), "boot": (T - z * sb, T + z * sb),
               "pct": (q7(reps, .025), q7(reps, .975))}
        for k, (lo, hi) in ivs.items():
            cov[k] += lo <= theta <= hi
            ln[k].append(hi - lo)
    return dict(theta=theta, cov={k: v / R for k, v in cov.items()},
                len={k: float(np.mean(v)) for k, v in ln.items()})


def ex12_numbers(B=4000, seed=12):
    """Exercise 3.12: 30/50 improve on placebo, 40/50 on treatment; 90% intervals for p2 - p1."""
    p1, p2, n = 0.6, 0.8, 50
    tau = p2 - p1
    se = math.sqrt(p1 * (1 - p1) / n + p2 * (1 - p2) / n)
    z = stats.norm.ppf(0.95)
    rng = np.random.default_rng(seed)
    x1 = np.r_[np.ones(30), np.zeros(20)]
    x2 = np.r_[np.ones(40), np.zeros(10)]
    reps = x2[boot_index(n, B, rng)].mean(-1) - x1[boot_index(n, B, rng)].mean(-1)
    sb = reps.std()
    return dict(tau=tau, se_delta=se, delta=(tau - z * se, tau + z * se), se_boot=sb,
                normal=(tau - z * sb, tau + z * sb), percentile=(q7(reps, .05), q7(reps, .95)))


# ========================================================================== figures
def fig_3_s1(out=None):
    """The jackknife bias correction, and l_i against the influence function (nerve data)."""
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    ns = np.array([5, 7, 10, 14, 20, 28, 40, 57, 80, 113, 160])
    a = ax[0, 0]
    bt = [jb_true("inv_mean", n)[1] for n in ns]
    bj = [abs(jb_true("inv_mean", n)[2]) for n in ns]
    a.loglog(ns, bt, color=BLUE, label=r"$|$bias$(T_n)|$, $T_n=1/\overline{X}$")
    a.loglog(ns, bj, color=RED, label=r"$|$bias$(T_{\rm jack})|$")
    a.loglog(ns, 1 / (ns * (ns - 1.0)), ":", color=GREY, lw=1.2, label=r"$b/(n(n-1))$, $b=1$")
    sim = cached("s1_sim", lambda: {str(n): jb_demo("inv_mean", n, 20000, 11) for n in (5, 7, 10, 20, 40)})
    for n, d in sim.items():
        a.plot(int(n), d["bias_T"], "o", ms=4, color=BLUE)
        if int(n) <= 10:
            a.plot(int(n), abs(d["bias_J"]), "s", ms=4, color=RED)
    a.set_xlabel("$n$")
    a.set_ylabel("absolute bias")
    a.legend(frameon=False, fontsize=7.5, loc="lower left")
    common.panel_label(a, "a", "upper right")
    b = ax[0, 1]
    x = nerve()
    jk = jackknife(x, skewness)
    ell = jack_ell(jk)
    L = skew_influence(x)
    b.plot(L, ell, ".", ms=3, color=PURPLE, alpha=.6)
    lim = [min(L.min(), ell.min()) - .5, max(L.max(), ell.max()) + .5]
    b.plot(lim, lim, "--", color=GREY, lw=1)
    b.set_xlabel(r"influence function $\hat L(X_i)$")
    b.set_ylabel(r"jackknife $\ell_i=(n-1)(T_n-T_{(-i)})$")
    b.text(0.05, 0.95, "nerve skewness\nse: jackknife %.3f\ninfluence %.3f" % (jk["se"], se_influence(L)),
           transform=b.transAxes, va="top", fontsize=8)
    common.panel_label(b, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S1", out)


def fig_3_s2(out=None):
    """The four bootstrap intervals for the nerve-data skewness (Example 3.17)."""
    x = nerve()
    T = float(skewness(x))
    # the resamples of the demonstration page (DK.rng seed 1), so the figure and the page agree
    reps, sestar = skew_with_se(x[js_boot_index(1, x.size, 1000)])
    iv = intervals(T, reps, 0.05, se_star=sestar)
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    a = ax[0, 0]
    a.hist(reps, bins=40, density=True, color=BLUE, alpha=.45)
    a.axvline(T, color="k", lw=1)
    names = [("normal", BLUE), ("percentile", GREEN), ("pivotal", ORANGE), ("studentized", RED)]
    top = a.get_ylim()[1]
    for k, (nm, c) in enumerate(names):
        lo, hi = iv[nm]
        y = top * (1.05 + 0.09 * k)
        a.plot([lo, hi], [y, y], color=c, lw=3, solid_capstyle="butt")
        a.text(hi + 0.02, y, "%s (%.2f, %.2f)" % (nm, lo, hi), va="center", fontsize=7, color=c)
    a.set_xlim(1.2, 2.95)
    a.set_ylim(0, top * 1.42)
    a.set_xlabel(r"bootstrap skewness $T^*_n$")
    a.set_ylabel("density")
    common.panel_label(a, "a")
    b = ax[0, 1]
    Z = iv["Z"]
    b.hist(Z, bins=40, density=True, color=RED, alpha=.4, label=r"$Z^*=(T^*-T_n)/\widehat{\rm se}^*$")
    b.hist((reps - T) / iv["se"], bins=40, density=True, histtype="step", color=BLUE,
           label=r"$(T^*-T_n)/\widehat{\rm se}_{\rm boot}$")
    zz = np.linspace(-4, 4, 300)
    b.plot(zz, stats.norm.pdf(zz), "--", color=GREY, lw=1.2, label=r"$N(0,1)$")
    for p in (0.025, 0.975):
        b.axvline(q7(Z, p), color=RED, lw=1, ls=":")
    b.set_xlim(-5, 4)
    b.set_xlabel("standardised replication")
    b.legend(frameon=False, fontsize=7, loc="upper left")
    common.panel_label(b, "b", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S2", out)


METHODS = ("normal", "pivotal", "percentile", "studentized")
MCOL = {"normal": BLUE, "pivotal": ORANGE, "percentile": GREEN, "studentized": RED}


def coverage_skew_lognormal(n, R, B, seed, alpha=0.05):
    """Exercise 3.6: coverage of the four intervals for the skewness of exp(N(0,1)) data;
    returns, per method, the fractions below (theta < lower), covered, above."""
    theta = (math.e + 2) * math.sqrt(math.e - 1)
    rng = np.random.default_rng(seed)
    res = {m: [0, 0, 0] for m in METHODS}
    lens = {m: [] for m in METHODS}
    for r in range(R):
        x = np.exp(rng.standard_normal(n))
        T = float(skewness(x))
        reps, sestar = skew_with_se(x[boot_index(n, B, rng)])
        iv = intervals(T, reps, alpha, se_star=sestar)
        for m in METHODS:
            lo, hi = iv[m]
            res[m][0 if theta < lo else 2 if theta > hi else 1] += 1
            lens[m].append(hi - lo)
    return dict(theta=theta, n=n, R=R, B=B,
                frac={m: [v / R for v in res[m]] for m in METHODS},
                len={m: float(np.median(lens[m])) for m in METHODS})


def fig_3_s3(out=None):
    """Coverage of the four intervals for the skewness of lognormal data (Exercise 3.6)."""
    sims = cached("s3_cov", lambda: [coverage_skew_lognormal(n, 500, 500, 100 + n) for n in (25, 50, 100, 200)])
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    a = ax[0, 0]
    ns = [s["n"] for s in sims]
    for m in METHODS:
        a.plot(ns, [s["frac"][m][1] for s in sims], "o-", color=MCOL[m], label=m, ms=4)
    a.axhline(0.95, ls="--", color=GREY, lw=1)
    a.set_xscale("log")
    a.set_xticks(ns)
    a.set_xticklabels([str(v) for v in ns])
    a.xaxis.set_minor_formatter(common.matplotlib.ticker.NullFormatter())
    a.set_ylim(0, 1)
    a.set_xlabel("$n$")
    a.set_ylabel("coverage (nominal 0.95)")
    a.legend(frameon=False, fontsize=7.5, loc="lower right")
    common.panel_label(a, "a", "upper left")
    b = ax[0, 1]
    s50 = [s for s in sims if s["n"] == 50][0]
    for k, m in enumerate(METHODS):
        lo, cov, hi = s50["frac"][m]
        b.bar(k, lo, color=GREY, alpha=.4, label="interval above $\\theta$" if k == 0 else None)
        b.bar(k, cov, bottom=lo, color=MCOL[m])
        b.bar(k, hi, bottom=lo + cov, color=GREY, label="interval below $\\theta$" if k == 0 else None)
        b.text(k, lo + cov / 2, "%.2f" % cov, ha="center", va="center", color="white", fontsize=8)
    b.set_xticks(range(4))
    b.set_xticklabels(["normal", "pivotal", "pctl", "stud."], fontsize=8)
    b.set_ylabel("fraction ($n=50$)")
    b.set_ylim(0, 1.25)
    b.legend(frameon=False, fontsize=7, loc="upper center", ncol=2)
    common.panel_label(b, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S3", out)


def accuracy_study(ns=(10, 20, 40, 80, 160), R=20000, B=400, alpha=0.05, seed=7):
    """One-sided miss rates P(mu < lower bound) for the mean of Exp(1) data, numpy generator."""
    out = {}
    for n in ns:
        rng = np.random.default_rng(seed + n)
        miss = {m: 0 for m in METHODS}
        for r in range(R):
            x = rng.exponential(size=n)
            lb = one_sided_bounds(x, boot_index(n, B, rng), alpha)
            for m in METHODS:
                miss[m] += 1.0 < lb[m]
        out[str(n)] = {m: v / R for m, v in miss.items()}
    return out


def fig_3_s4(out=None):
    """Accuracy of one-sided bootstrap bounds for a mean, and the Edgeworth expansion (3.23)."""
    acc = cached("s4_acc", accuracy_study)
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    a = ax[0, 0]
    ns = np.array([int(k) for k in acc])
    R = 20000
    for m in METHODS:
        e = np.array([acc[str(n)][m] - 0.05 for n in ns])
        a.plot(ns, np.abs(e), "o-", color=MCOL[m], ms=4, label=m)
    a.plot(ns, 0.06 / np.sqrt(ns / 10.0), ":", color=GREY, lw=1.2, label=r"slope $-1/2$")
    a.plot(ns, 0.012 / (ns / 10.0), "--", color=GREY, lw=1.2, label=r"slope $-1$")
    a.axhline(2 * math.sqrt(0.05 * 0.95 / R), color=GREY, lw=.8, alpha=.6)
    a.set_xscale("log")
    a.set_yscale("log")
    a.xaxis.set_minor_formatter(common.matplotlib.ticker.NullFormatter())
    a.set_xticks(ns)
    a.set_xticklabels([str(v) for v in ns])
    a.set_xlabel("$n$")
    a.set_ylabel(r"$|\mathbb{P}(\mu<\hat\theta_{.05})-0.05|$")
    a.legend(frameon=False, fontsize=6.8, loc="lower left", ncol=2)
    common.panel_label(a, "a", "upper right")
    b = ax[0, 1]
    z = np.linspace(-3, 3, 301)
    for n, c in ((5, BLUE), (20, RED)):
        exact = stats.gamma.cdf(1 + z / math.sqrt(n), a=n, scale=1.0 / n)
        b.plot(z, exact - stats.norm.cdf(z), color=c, label="exact, $n=%d$" % n)
        b.plot(z, edgeworth_mean(z, n, 2.0) - stats.norm.cdf(z), "--", color=c, lw=1.2,
               label="Edgeworth, $n=%d$" % n)
    b.axhline(0, color=GREY, lw=.8)
    b.set_xlabel("$z$")
    b.set_ylabel(r"$\mathbb{P}(Z_n\leq z)-\Phi(z)$")
    b.legend(frameon=False, fontsize=7, loc="lower left")
    common.panel_label(b, "b", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S4", out)


def ex10_numbers(seed=10, B=4000):
    """Exercise 3.10: theta = exp(mu), X ~ N(5, 1), n = 100."""
    rng = np.random.default_rng(seed)
    n = 100
    x = rng.normal(5, 1, n)
    th = math.exp(x.mean())
    se_delta = th / math.sqrt(n)
    par = np.exp(rng.normal(x.mean(), 1, (B, n)).mean(-1))
    nonp = np.exp(x[boot_index(n, B, rng)].mean(-1))
    z = stats.norm.ppf(0.975)
    return dict(x=x, theta_hat=th, se_delta=se_delta, delta=(th - z * se_delta, th + z * se_delta),
                par=par, nonp=nonp, se_par=par.std(), se_nonp=nonp.std(),
                par_pct=(q7(par, .025), q7(par, .975)), nonp_pct=(q7(nonp, .025), q7(nonp, .975)))


def ex11_numbers(seed=11, B=4000):
    rng = np.random.default_rng(seed)
    n = 50
    x = rng.uniform(0, 1, n)
    th = x.max()
    par = rng.uniform(0, th, (B, n)).max(-1)
    nonp = x[boot_index(n, B, rng)].max(-1)
    return dict(x=x, theta_hat=th, par=par, nonp=nonp, p_eq=float((nonp == th).mean()),
                p_theory=1 - (1 - 1 / n) ** n)


def fig_3_s5(out=None):
    """Parametric against nonparametric bootstrap: Exercises 3.10 (exp of a mean) and 3.11 (maximum)."""
    e10, e11 = ex10_numbers(), ex11_numbers()
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    a = ax[0, 0]
    bins = np.linspace(100, 230, 45)
    a.hist(e10["par"], bins=bins, density=True, color=GREEN, alpha=.4, label="parametric")
    a.hist(e10["nonp"], bins=bins, density=True, histtype="step", color=BLUE, lw=1.3, label="nonparametric")
    t = np.linspace(100, 230, 400)
    true = stats.lognorm.pdf(t, s=0.1, scale=math.exp(5))
    a.plot(t, true, color=RED, label=r"true law of $\hat\theta$")
    a.plot(t, stats.norm.pdf(t, e10["theta_hat"], e10["se_delta"]), "--", color=GREY, lw=1.2, label="delta method")
    a.set_xlabel(r"$\hat\theta=e^{\overline{X}}$ and replications")
    a.set_ylabel("density")
    a.legend(frameon=False, fontsize=6.8, loc="upper right")
    common.panel_label(a, "a", "upper left")
    b = ax[0, 1]
    th = e11["theta_hat"]
    bins = np.linspace(0.85, 1.0, 46)
    b.hist(e11["par"], bins=bins, density=True, color=GREEN, alpha=.4, label="parametric")
    b.hist(e11["nonp"], bins=bins, density=True, histtype="step", color=BLUE, lw=1.3, label="nonparametric")
    t = np.linspace(0.85, 1, 300)
    b.plot(t, 50 * t ** 49, color=RED, label=r"true: $50\,t^{49}$")
    b.axvline(th, color="k", lw=.8)
    b.set_xlabel(r"$\hat\theta=X_{\max}$ and replications")
    b.legend(frameon=False, fontsize=6.8, loc="upper left")
    b.text(0.03, 0.45, r"$\mathbb{P}_*(\hat\theta^*=\hat\theta)$" + "\n= %.3f" % e11["p_eq"],
           transform=b.transAxes, fontsize=7.5)
    common.panel_label(b, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S5", out)


def appendix_study(ns=(10, 20, 40, 80, 160, 320, 640), R=200, B=4000, seed=21):
    out = {}
    for n in ns:
        rng = np.random.default_rng(seed + n)
        d2, ks, be = [], [], []
        for r in range(R):
            x = rng.exponential(size=n)
            d2.append(mallows_d2_exp(x))
            ks.append(kolmogorov_boot_mean_exp(x, B, rng))
            s = x.std()
            be.append(33 / 4 * (np.abs(x - x.mean()) ** 3).sum() / (n ** 1.5 * s ** 3))
        out[str(n)] = dict(d2=float(np.mean(d2)), ks=float(np.mean(ks)), ks90=float(np.quantile(ks, .9)),
                           be=float(np.mean(be)))
    return out


def fig_3_s6(out=None):
    """The appendix: Mallows' distance d_2(F_n, F) and the Kolmogorov distance of the bootstrap."""
    st = cached("s6_app", appendix_study)
    ns = np.array([int(k) for k in st])
    fig, ax = common.panel_grid(1, 2, size=(3.6, 2.9))
    a = ax[0, 0]
    a.loglog(ns, [st[str(n)]["d2"] for n in ns], "o-", color=PURPLE, ms=4, label=r"mean of $d_2(\widehat F_n,F)$")
    a.loglog(ns, 0.75 * np.sqrt(np.log(ns) / ns), ":", color=GREY, label=r"$\propto\sqrt{\log n/n}$")
    a.loglog(ns, 1.1 / np.sqrt(ns), "--", color=GREY, lw=1, label=r"$\propto n^{-1/2}$")
    a.set_xlabel("$n$")
    a.set_ylabel("Mallows distance, Exp(1) data")
    a.legend(frameon=False, fontsize=7.5)
    common.panel_label(a, "a", "lower left")
    b = ax[0, 1]
    b.loglog(ns, [st[str(n)]["ks"] for n in ns], "o-", color=BLUE, ms=4, label=r"mean of $d(\widehat H_n,H_n)$")
    b.loglog(ns, [st[str(n)]["ks90"] for n in ns], "s--", color=BLUE, ms=3, lw=1, label="90% quantile")
    b.loglog(ns, [st[str(n)]["be"] for n in ns], "^-", color=ORANGE, ms=4, label="bound (3.28)")
    b.loglog(ns, 0.4 / np.sqrt(ns), ":", color=GREY, label=r"$\propto n^{-1/2}$")
    b.set_xlabel("$n$")
    b.set_ylabel("Kolmogorov distance")
    b.legend(frameon=False, fontsize=7, loc="upper right")
    common.panel_label(b, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig3-S6", out)


# ========================================================================== demo data
def write_demo_data():
    os.makedirs(DATA_DIR, exist_ok=True)
    d = dict(nerve=[float(v) for v in nerve()], lsat=[float(v) for v in LSAT], gpa=[float(v) for v in GPA])
    path = os.path.join(DATA_DIR, "ch03-bootstrap-data.json")
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


def fig_data(out=None):
    """Data for the demonstration pages (../data/ch03-bootstrap-data.json)."""
    write_demo_data()


FIGURES = {"3.S1": fig_3_s1, "3.S2": fig_3_s2, "3.S3": fig_3_s3, "3.S4": fig_3_s4,
           "3.S5": fig_3_s5, "3.S6": fig_3_s6, "data": fig_data}

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