"""Wasserman (2004), Chapter 4: Inequalities.

Computations and figures for Chapter 4 of L. Wasserman, All of Statistics: A Concise Course in
Statistical Inference (Springer, 2004), pp. 63-69, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch04-inequalities.html).

The chapter is short and has no figures of its own: everything it states is an inequality. The
functions below compute each bound and the exact quantity it bounds, so that the bounds can be
compared, and the figures are supplementary (numbered 4.S1-4.S7) or answer the chapter's computer
exercises.

* Section 4.1, probability inequalities: markov_bound (4.1), chebyshev_bound (4.2), cantelli_bound
  (the one-sided version), hoeffding_bound ((4.3) optimised over t, and (4.4)), chernoff_bound (the
  Chernoff bound for a binomial proportion, with the Bernoulli Kullback-Leibler divergence kl_bern
  as exponent), the exact binomial tails binom_tail (written out from the probability mass
  function, and compared with scipy), the Hoeffding lemma function hoeffding_g and its second
  derivative, and the bounds tail_bounds() shown in the tail-bounds demonstration.
* Hoeffding's confidence interval for a proportion: hoeffding_eps, hoeffding_ci, wald_ci, the exact
  coverage and expected length of both intervals by summing over the binomial distribution
  (coverage_exact, expected_length), their coverage by simulation (coverage_sim, which uses the
  same seeded generator as the browser demonstrations), and sample_size_for_length.
* Mill's inequality: normal_tail2 (the exact P(|Z| > t)), mills_bound and the matching lower bound
  mills_lower, the absolute normal moments abs_normal_moment, and the moment (Markov) bounds of
  Exercise 6.
* Section 4.2, inequalities for expectations: jensen_summary (E g(X), g(E X), the gap and the slope
  of a supporting line) for the functions in JENSEN_G, on two-point distributions and on the nerve
  data of the book (nerve.dat, 799 waiting times between nerve pulses), and kl_hist_exponential
  (the Kullback-Leibler divergence between the histogram of the nerve data and a discretised
  exponential model, written as a Jensen gap). gauss_max_mc illustrates the maximal inequality
  E max Z_i <= sqrt(2 log n), proved in the notes with Jensen's inequality.

Figures (all supplementary; the chapter has none of its own):
* 4.S1 Markov, Chebyshev, Hoeffding, Chernoff and the exact tail of a binomial proportion
  (Examples 4.3 and 4.6, Exercise 3).
* 4.S2 Exercise 4(b) and (c): coverage and length of the Hoeffding interval against n, with the
  normal-approximation (Wald) interval for comparison.
* 4.S3 Exercise 6: P(|Z| > t), the moment bounds E|Z|^k / t^k for k = 1, ..., 5, and Mill's bound.
* 4.S4 Hoeffding's lemma: the exact log moment generating function of a centred bounded variable,
  the function g(u) of the proof and the bound u^2 / 8, and g''(u) <= 1/4.
* 4.S5 Jensen's inequality on the nerve data for g(x) = x^2, 1/x and -log x.
* 4.S6 Exercises 1 and 7: the exponential distribution against Chebyshev, and the mean of normals
  against Chebyshev and Mill.
* 4.S7 The maximum of n standard normals against sqrt(2 log n) and the union bound.

Figures not reproduced: none (the chapter has no figures).

Run `python3 ch04_inequalities.py --list`, `python3 ch04_inequalities.py` (all figures, about
half a minute) or `python3 ch04_inequalities.py --fig 4.S2`. Files go to ../img/ch04/; the data of
the browser demonstrations go to ../data/ (export_demo_data).
"""
import json
import math
import os

import numpy as np
from scipy import special

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

CH = 4
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
M32 = 0xFFFFFFFF
TOL = 1e-9          # tolerance used when comparing k - n p with n eps (the same rule as the demos)


# =========================================================================== seeded generator
def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of the mulberry32 generator DK.rng(seed) of the
    demonstrations: its state grows by 0x6D2B79F5 at each call, so the j-th output is a hash of
    seed + j * 0x6D2B79F5 (mod 2^32) and can be computed for all j at once."""
    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


# =========================================================================== Section 4.1: the bounds
def markov_bound(mean, t):
    """Markov's inequality (4.1): P(X >= t) <= E(X) / t for X >= 0 and t > 0 (capped at 1)."""
    return np.minimum(1.0, np.asarray(mean, float) / np.asarray(t, float))


def chebyshev_bound(var, t):
    """Chebyshev's inequality (4.2): P(|X - mu| >= t) <= sigma^2 / t^2 (capped at 1)."""
    return np.minimum(1.0, np.asarray(var, float) / np.asarray(t, float) ** 2)


def cantelli_bound(var, t):
    """One-sided Chebyshev (Cantelli) inequality: P(X - mu >= t) <= sigma^2 / (sigma^2 + t^2), t > 0."""
    var = np.asarray(var, float)
    return var / (var + np.asarray(t, float) ** 2)


def hoeffding_bound(n, eps, width=1.0, two_sided=True):
    """Hoeffding's inequality for the mean of n independent variables with values in an interval of
    length `width`: P(Xbar - mu >= eps) <= exp(-2 n eps^2 / width^2), which is (4.3) with the best
    t = 4 n eps / width^2; with two_sided, the factor 2 of (4.4). Capped at 1."""
    b = np.exp(-2.0 * np.asarray(n, float) * np.asarray(eps, float) ** 2 / width ** 2)
    return np.minimum(1.0, 2.0 * b if two_sided else b)


def hoeffding_rhs(t, eps, widths):
    """The right side of (4.3) for a given t > 0: exp(-t eps) prod_i exp(t^2 (b_i - a_i)^2 / 8)."""
    widths = np.asarray(widths, float)
    return np.exp(-t * eps + t ** 2 * np.sum(widths ** 2) / 8.0)


def kl_bern(q, p):
    """Kullback-Leibler divergence between Bernoulli(q) and Bernoulli(p), with 0 log 0 = 0."""
    q, p = np.asarray(q, float), np.asarray(p, float)
    with np.errstate(divide="ignore", invalid="ignore"):
        a = np.where(q > 0, q * np.log(q / p), 0.0)
        b = np.where(q < 1, (1 - q) * np.log((1 - q) / (1 - p)), 0.0)
    return a + b


def chernoff_bound(n, p, eps, two_sided=True):
    """Chernoff's bound for a binomial proportion: P(Xbar - p >= eps) <= exp(-n kl(p + eps, p))
    (0 if p + eps > 1), and the same for the lower tail with p - eps."""
    n, p, eps = float(n), float(p), float(eps)
    up = 0.0 if p + eps > 1 else float(np.exp(-n * kl_bern(p + eps, p)))
    if not two_sided:
        return min(1.0, up)
    lo = 0.0 if p - eps < 0 else float(np.exp(-n * kl_bern(p - eps, p)))
    return min(1.0, up + lo)


def binom_pmf(n, p):
    """The Binomial(n, p) probabilities, from log Gamma (the formula the demonstrations use)."""
    k = np.arange(n + 1)
    if p <= 0 or p >= 1:
        out = np.zeros(n + 1)
        out[0 if p <= 0 else n] = 1.0
        return out
    lg = special.gammaln(n + 1) - special.gammaln(k + 1) - special.gammaln(n - k + 1)
    return np.exp(lg + k * np.log(p) + (n - k) * np.log1p(-p))


def binom_tail(n, p, eps, two_sided=True):
    """Exact P(|Xbar - p| > eps) (two_sided) or P(Xbar - p >= eps) (one-sided, upper) for the
    mean Xbar = S / n of n Bernoulli(p) variables, by summing the probability mass function."""
    k = np.arange(n + 1)
    f = binom_pmf(n, p)
    if two_sided:
        sel = np.abs(k - n * p) > n * eps + TOL
    else:
        sel = (k - n * p) >= n * eps - TOL
    return float(f[sel].sum())


def tail_bounds(n, p, eps, two_sided=True):
    """Every bound of the chapter for the tail of a binomial proportion, and the exact value.
    Markov's inequality applies to the upper tail only: P(Xbar >= p + eps) <= p / (p + eps).
    Values are not capped at 1 here (the demonstration shows the raw bound)."""
    var = p * (1 - p) / n
    out = dict(exact=binom_tail(n, p, eps, two_sided),
               chebyshev=var / eps ** 2,
               hoeffding=(2.0 if two_sided else 1.0) * math.exp(-2 * n * eps ** 2),
               chernoff=chernoff_bound(n, p, eps, two_sided))
    if two_sided:
        out["markov"] = float("nan")
    else:
        out["markov"] = p / (p + eps)
        out["cantelli"] = var / (var + eps ** 2)
    return out


def hoeffding_g(u, gamma):
    """g(u) = -gamma u + log(1 - gamma + gamma e^u), the log of the convexity bound (4.9) on the moment
    generating function, with u = t (b - a) and gamma = -a / (b - a) in [0, 1]."""
    u = np.asarray(u, float)
    return -gamma * u + np.log1p(gamma * np.expm1(u))


def hoeffding_g2(u, gamma):
    """g''(u) = rho (1 - rho) with rho = gamma e^u / (1 - gamma + gamma e^u): at most 1/4."""
    u = np.asarray(u, float)
    rho = gamma * np.exp(u) / (1 - gamma + gamma * np.exp(u))
    return rho * (1 - rho)


# =========================================================================== the confidence interval
def hoeffding_eps(n, alpha):
    """eps_n = sqrt(log(2 / alpha) / (2 n)): the half-width of Hoeffding's interval."""
    return np.sqrt(np.log(2.0 / alpha) / (2.0 * np.asarray(n, float)))


def z_quantile(alpha):
    """The upper alpha/2 point z_{alpha/2} of N(0, 1)."""
    return float(-special.ndtri(alpha / 2.0))


def hoeffding_ci(xbar, n, alpha, truncate=True):
    e = hoeffding_eps(n, alpha)
    lo, hi = xbar - e, xbar + e
    return (np.maximum(lo, 0.0), np.minimum(hi, 1.0)) if truncate else (lo, hi)


def wald_ci(xbar, n, alpha, truncate=True):
    """The normal-approximation (Wald) interval Xbar +- z_{alpha/2} sqrt(Xbar (1 - Xbar) / n)."""
    h = z_quantile(alpha) * np.sqrt(xbar * (1 - xbar) / n)
    lo, hi = xbar - h, xbar + h
    return (np.maximum(lo, 0.0), np.minimum(hi, 1.0)) if truncate else (lo, hi)


def _covers(method, k, n, p, alpha):
    xbar = k / n
    if method == "hoeffding":
        h = hoeffding_eps(n, alpha)
    else:
        h = z_quantile(alpha) * np.sqrt(xbar * (1 - xbar) / n)
    return np.abs(xbar - p) < h


def coverage_exact(n, p, alpha, method="hoeffding"):
    """Exact P(p in C) for the open interval C = (Xbar - h, Xbar + h), by summing the binomial
    probabilities of the outcomes k whose interval contains p. Truncation to [0, 1] does not change
    the coverage of a p in (0, 1)."""
    k = np.arange(n + 1)
    return float(binom_pmf(n, p)[_covers(method, k, n, p, alpha)].sum())


def expected_length(n, p, alpha, method="hoeffding", truncate=True):
    """Exact expected length of the (truncated) interval."""
    k = np.arange(n + 1)
    f = binom_pmf(n, p)
    lo, hi = (hoeffding_ci if method == "hoeffding" else wald_ci)(k / n, n, alpha, truncate)
    return float(np.sum(f * (hi - lo)))


def coverage_sim(n, p, alpha, reps, seed, method="hoeffding"):
    """Coverage by simulation, as in Exercise 4(b): reps data sets of n Bernoulli(p) draws, the
    i-th made of uniforms i n + 1, ..., (i + 1) n of DK.rng(seed) (X_j = 1 when u_j < p)."""
    hits = 0
    S = np.empty(reps, dtype=np.int64)
    chunk = max(1, 2_000_000 // n)
    for r0 in range(0, reps, chunk):
        r1 = min(reps, r0 + chunk)
        u = js_uniforms(seed, (r1 - r0) * n, start=r0 * n).reshape(r1 - r0, n)
        S[r0:r1] = (u < p).sum(1)
    hits = _covers(method, S, n, p, alpha)
    return float(np.mean(hits)), S


def sample_size_for_length(L, alpha):
    """Smallest n with 2 eps_n <= L, i.e. n >= 2 log(2 / alpha) / L^2."""
    return int(math.ceil(2.0 * math.log(2.0 / alpha) / L ** 2 - 1e-12))


def n_grid(nmax=10000):
    """Sample sizes of the coverage curves (the same in the demonstration): 1, ..., 100 and then
    100 points equally spaced on the log scale up to nmax, rounded."""
    out = list(range(1, 101))
    for i in range(1, 101):
        v = int(math.floor(10 ** (2 + i * (math.log10(nmax) - 2) / 100) + 0.5))
        if v > out[-1]:
            out.append(v)
    return np.array(out)


# =========================================================================== Mill's inequality
def normal_tail2(t):
    """Exact P(|Z| > t) = erfc(t / sqrt 2)."""
    return special.erfc(np.asarray(t, float) / math.sqrt(2.0))


def mills_bound(t):
    """Mill's inequality: P(|Z| > t) <= sqrt(2 / pi) exp(-t^2 / 2) / t."""
    t = np.asarray(t, float)
    return math.sqrt(2.0 / math.pi) * np.exp(-t ** 2 / 2) / t


def mills_lower(t):
    """The matching lower bound P(|Z| > t) >= sqrt(2 / pi) t / (1 + t^2) exp(-t^2 / 2)."""
    t = np.asarray(t, float)
    return math.sqrt(2.0 / math.pi) * t / (1 + t ** 2) * np.exp(-t ** 2 / 2)


def abs_normal_moment(k):
    """E|Z|^k = 2^{k/2} Gamma((k + 1) / 2) / sqrt(pi) for k > -1."""
    return 2 ** (k / 2) * special.gamma((k + 1) / 2) / math.sqrt(math.pi)


def moment_bound(t, k):
    """Markov's inequality applied to |Z|^k: P(|Z| > t) <= E|Z|^k / t^k."""
    return abs_normal_moment(k) / np.asarray(t, float) ** k


def best_moment_order(t):
    """The real k > 0 minimising E|Z|^k / t^k (it is close to t^2 for large t)."""
    from scipy.optimize import minimize_scalar
    r = minimize_scalar(lambda k: math.log(abs_normal_moment(k)) - k * math.log(t), bounds=(1e-6, 200), method="bounded",
                        options=dict(xatol=1e-10))
    return float(r.x), float(math.exp(r.fun))


# =========================================================================== Section 4.2: Jensen
# Each entry: value, derivative (a supporting slope; for |x - c| the slope 0 is used at the kink),
# whether the function is convex (True) or concave (False), and the domain (lower bound).
JENSEN_G = {
    "x^2": (lambda x: x ** 2, lambda x: 2 * x, True, -np.inf),
    "exp": (np.exp, np.exp, True, -np.inf),
    "1/x": (lambda x: 1 / x, lambda x: -1 / x ** 2, True, 0.0),
    "-log": (lambda x: -np.log(x), lambda x: -1 / x, True, 0.0),
    "abs": (np.abs, lambda x: np.sign(x) * (np.abs(x) > 1e-12), True, -np.inf),
    "xlogx": (lambda x: x * np.log(x), lambda x: np.log(x) + 1, True, 0.0),
}


def nerve():
    """The nerve data of the book (nerve.dat): 799 waiting times (seconds) between successive pulses
    along a nerve fibre. The file is a whitespace-separated table with a ragged last row."""
    with open(common.aos_file("nerve.dat")) as f:
        return np.array(f.read().split(), float)


def jensen_summary(gname, x, w=None):
    """E g(X), g(E X), the Jensen gap E g(X) - g(E X) >= 0 and the supporting slope g'(E X), for X
    taking the values x with probabilities w (uniform if w is None)."""
    g, dg, _, _ = JENSEN_G[gname]
    x = np.asarray(x, float)
    w = np.full(x.size, 1.0 / x.size) if w is None else np.asarray(w, float)
    mu = float(np.sum(w * x))
    Eg = float(np.sum(w * g(x)))
    return dict(mu=mu, Eg=Eg, gmu=float(g(mu)), gap=Eg - float(g(mu)), slope=float(dg(mu)))


NERVE_BINS = np.round(np.arange(0.0, 1.45 + 1e-9, 0.05), 10)   # 29 bins of width 0.05 on [0, 1.45]


def kl_hist_exponential(x, mean, edges=NERVE_BINS):
    """KL(p || q) between the histogram p of x on the bins `edges` and the exponential model with the
    given mean, discretised on the same bins (the last bin is open to the right, so q sums to one).
    Returned with the pieces of the Jensen argument: E_p[Y] = sum_{p_j > 0} q_j <= 1 for Y = q / p,
    and the gap KL - (-log E_p Y) >= 0."""
    cnt = np.histogram(x, bins=edges)[0]
    p = cnt / cnt.sum()
    cdf = 1 - np.exp(-edges / mean)
    q = np.diff(cdf)
    q[-1] = math.exp(-edges[-2] / mean)          # last bin: [edges[-2], infinity)
    s = p > 0
    kl = float(np.sum(p[s] * np.log(p[s] / q[s])))
    EY = float(np.sum(q[s]))
    return dict(p=p, q=q, kl=kl, EY=EY, lower=-math.log(EY), gap=kl + math.log(EY))


def gauss_max_mc(ns, reps=2000, seed=4):
    """Monte Carlo mean of max_i Z_i and of max_i |Z_i| over n standard normals."""
    rng = np.random.default_rng(seed)
    out_max, out_abs = [], []
    for n in ns:
        Z = rng.standard_normal((reps, n))
        out_max.append(Z.max(1).mean())
        out_abs.append(np.abs(Z).max(1).mean())
    return np.array(out_max), np.array(out_abs)


# =========================================================================== figures
def _logax(ax):
    ax.set_yscale("log")
    ax.grid(True, which="major", color="#e6e6e6", lw=0.6)


def fig_4_s1(out_dir=None):
    """Figure 4.S1: Markov, Chebyshev, Hoeffding, Chernoff and the exact tail of a binomial proportion."""
    fig, axes = common.panel_grid(1, 3, size=(3.3, 2.9))
    n, p = 100, 0.5
    eps = np.linspace(0.005, 0.5, 400)
    # (a) upper tail against eps at n = 100, p = 1/2
    ax = axes[0, 0]
    T = [tail_bounds(n, p, e, two_sided=False) for e in eps]
    ax.plot(eps, [min(1, t["markov"]) for t in T], color=GREY, label="Markov")
    ax.plot(eps, [t["cantelli"] for t in T], color=ORANGE, label="Chebyshev (one-sided)")
    ax.plot(eps, [min(1, t["hoeffding"]) for t in T], color=BLUE, label="Hoeffding")
    ax.plot(eps, [t["chernoff"] for t in T], color=GREEN, label="Chernoff (KL)")
    ax.step(eps, [t["exact"] for t in T], where="post", color=RED, label="exact")
    _logax(ax)
    ax.set_ylim(1e-14, 2)
    ax.set_xlabel(r"$\epsilon$")
    ax.set_title(r"$P(\bar X_n-p\geq\epsilon)$, $n=100$, $p=\frac{1}{2}$")
    ax.legend(loc="lower left", fontsize=7.5, frameon=False)
    common.panel_label(ax, "a", "upper right")
    # (b) two-sided tail against n at eps = 0.2 (Examples 4.3 and 4.6)
    ax = axes[0, 1]
    ns = np.arange(1, 201)
    ax.plot(ns, chebyshev_bound(p * (1 - p) / ns, 0.2), color=ORANGE, label="Chebyshev")
    ax.plot(ns, hoeffding_bound(ns, 0.2), color=BLUE, label="Hoeffding")
    ax.plot(ns, [chernoff_bound(k, p, 0.2) for k in ns], color=GREEN, label="Chernoff (KL)")
    ax.plot(ns, [binom_tail(k, p, 0.2) for k in ns], color=RED, lw=1.1, label="exact")
    ax.plot([100, 100], [0.0625, 2 * math.exp(-8)], "o", color="k", ms=3.5)
    ax.annotate("0.0625", (100, 0.0625), (115, 0.12), fontsize=8)
    ax.annotate("0.00067", (100, 2 * math.exp(-8)), (115, 2.5e-3), fontsize=8)
    _logax(ax)
    ax.set_ylim(1e-12, 2)
    ax.set_xlabel(r"$n$")
    ax.set_title(r"$P(|\bar X_n-p|>0.2)$, $p=\frac{1}{2}$")
    ax.legend(loc="lower left", fontsize=7.5, frameon=False)
    common.panel_label(ax, "b", "upper right")
    # (c) the same with a small p: the variance matters, and Chebyshev can beat Hoeffding
    ax = axes[0, 2]
    p2, e2 = 0.05, 0.05
    ns = np.arange(1, 801)
    ax.plot(ns, chebyshev_bound(p2 * (1 - p2) / ns, e2), color=ORANGE, label="Chebyshev")
    ax.plot(ns, hoeffding_bound(ns, e2), color=BLUE, label="Hoeffding")
    ax.plot(ns, [chernoff_bound(k, p2, e2) for k in ns], color=GREEN, label="Chernoff (KL)")
    ax.plot(ns, [binom_tail(k, p2, e2) for k in ns], color=RED, lw=1.0, label="exact")
    _logax(ax)
    ax.set_ylim(1e-8, 2)
    ax.set_xlabel(r"$n$")
    ax.set_title(r"$P(|\bar X_n-p|>0.05)$, $p=0.05$")
    ax.legend(loc="lower left", fontsize=7.5, frameon=False)
    common.panel_label(ax, "c", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s1", out_dir)


def fig_4_s2(out_dir=None):
    """Figure 4.S2: Exercise 4(b), (c): coverage and length of the Hoeffding interval against n."""
    p, alpha = 0.4, 0.05
    ns = n_grid()
    covH = np.array([coverage_exact(n, p, alpha, "hoeffding") for n in ns])
    covW = np.array([coverage_exact(n, p, alpha, "wald") for n in ns])
    sim_n = np.array([1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000])
    simH = np.array([coverage_sim(n, p, alpha, 1000, 4000 + i)[0] for i, n in enumerate(sim_n)])
    fig, axes = common.panel_grid(1, 2, size=(3.6, 2.9))
    ax = axes[0, 0]
    ax.plot(ns, covH, color=BLUE, label="Hoeffding, exact")
    ax.plot(sim_n, simH, "o", color=BLUE, mfc="white", ms=4, label="Hoeffding, 1000 simulations")
    ax.plot(ns, covW, color=ORANGE, lw=1.0, label="Wald (normal), exact")
    ax.axhline(1 - alpha, color="k", ls="--", lw=0.8)
    ax.set_xscale("log")
    ax.set_ylim(0.0, 1.02)
    ax.set_xlabel(r"$n$")
    ax.set_ylabel("coverage")
    ax.set_title(r"coverage, $p=0.4$, $\alpha=0.05$")
    ax.legend(loc="center right", fontsize=7.5, frameon=False)
    common.panel_label(ax, "b", "lower right")
    ax = axes[0, 1]
    nn = np.unique(np.concatenate([np.arange(1, 101), np.geomspace(100, 10000, 300).astype(int)]))
    ax.plot(nn, 2 * hoeffding_eps(nn, alpha), color=BLUE, label=r"Hoeffding, $2\epsilon_n$")
    ax.plot(ns, [expected_length(n, p, alpha, "hoeffding") for n in ns], color=BLUE, ls=":", label="Hoeffding, truncated (mean)")
    ax.plot(ns, [expected_length(n, p, alpha, "wald") for n in ns], color=ORANGE, lw=1.0, label="Wald (mean)")
    n05 = sample_size_for_length(0.05, alpha)
    ax.axhline(0.05, color="k", ls="--", lw=0.8)
    ax.axvline(n05, color=GREY, ls=":", lw=0.8)
    ax.annotate("n = %d" % n05, (n05, 0.05), (60, 0.022), fontsize=8, arrowprops=dict(arrowstyle="->", lw=0.6))
    ax.set_xscale("log")
    ax.set_yscale("log")
    ax.set_xlabel(r"$n$")
    ax.set_ylabel("length")
    ax.set_title("length of the interval")
    ax.legend(loc="upper right", fontsize=7.5, frameon=False)
    common.panel_label(ax, "c", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s2", out_dir)


def fig_4_s3(out_dir=None):
    """Figure 4.S3: Exercise 6: P(|Z| > t) against the moment bounds and Mill's inequality."""
    t = np.linspace(0.05, 5, 500)
    fig, ax = plt.subplots(figsize=(4.6, 3.3))
    cols = [GREY, ORANGE, PURPLE, CYAN, MAGENTA]
    for k, c in zip(range(1, 6), cols):
        ax.plot(t, moment_bound(t, k), color=c, lw=1.1, label=r"$E|Z|^{%d}/t^{%d}$" % (k, k))
    ax.plot(t, mills_bound(t), color=BLUE, lw=1.6, label="Mill")
    ax.plot(t, normal_tail2(t), color=RED, lw=2, label=r"exact $P(|Z|>t)$")
    _logax(ax)
    ax.set_ylim(1e-7, 2)
    ax.set_xlim(0, 5)
    ax.set_xlabel(r"$t$")
    ax.set_title(r"bounds on $P(|Z|>t)$, $Z\sim N(0,1)$")
    ax.legend(loc="lower left", fontsize=8, frameon=False, ncol=2)
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s3", out_dir)


def fig_4_s4(out_dir=None):
    """Figure 4.S4: Hoeffding's lemma, g(u) <= u^2/8 and g''(u) <= 1/4."""
    u = np.linspace(0, 6, 400)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.8))
    ax = axes[0, 0]
    for gam, c in zip((0.5, 0.2, 0.05), (BLUE, GREEN, ORANGE)):
        ax.plot(u, hoeffding_g(u, gam), color=c, label=r"$g(u)$, $\gamma=%.2g$" % gam)
    ax.plot(u, u ** 2 / 8, color="k", ls="--", lw=1, label=r"$u^2/8$")
    ax.set_xlabel(r"$u=t(b-a)$")
    ax.set_title(r"$\log E\,e^{tY}$ for a two-point $Y$")
    ax.legend(loc="upper left", fontsize=7.5, frameon=False)
    ax = axes[0, 1]
    for gam, c in zip((0.5, 0.2, 0.05), (BLUE, GREEN, ORANGE)):
        ax.plot(u, hoeffding_g2(u, gam), color=c, label=r"$\gamma=%.2g$" % gam)
    ax.axhline(0.25, color="k", ls="--", lw=1)
    ax.set_ylim(0, 0.28)
    ax.set_xlabel(r"$u$")
    ax.set_title(r"$g''(u)=\rho(1-\rho)\leq 1/4$")
    ax.legend(loc="lower right", fontsize=7.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s4", out_dir)


def fig_4_s5(out_dir=None):
    """Figure 4.S5: Jensen's inequality on the nerve data for g(x) = x^2, 1/x and -log x."""
    x = nerve()
    fig, axes = common.panel_grid(1, 3, size=(3.0, 2.7))
    specs = [("x^2", r"$g(x)=x^2$", (0, 1.4)), ("1/x", r"$g(x)=1/x$", (0.005, 1.4)), ("-log", r"$g(x)=-\log x$", (0.005, 1.4))]
    for ax, (gname, title, (a, b)) in zip(axes[0], specs):
        g, dg, _, _ = JENSEN_G[gname]
        J = jensen_summary(gname, x)
        xs = np.linspace(a, b, 600)
        ax.plot(xs, g(xs), color="k", lw=1.2)
        ax.plot(x, g(x), "o", color=BLUE, ms=2.5, alpha=0.25)
        ax.plot(xs, J["gmu"] + J["slope"] * (xs - J["mu"]), color=GREEN, lw=1, ls="--")
        ax.plot([J["mu"]], [J["gmu"]], "o", color=GREEN, ms=5)
        ax.plot([J["mu"]], [J["Eg"]], "o", color=RED, ms=5)
        ax.vlines(J["mu"], J["gmu"], J["Eg"], color=RED, lw=1.5)
        ax.set_title(title)
        ax.set_xlabel(r"$x$ (seconds)")
        lo = min(g(xs).min(), J["gmu"]) if gname != "1/x" else 0
        hi = {"x^2": 2.0, "1/x": 30.0, "-log": 5.0}[gname]
        ax.set_ylim(lo - 0.05 * (hi - lo), hi)
        ax.text(0.97, 0.95, r"$Eg(X)=%.3f$" "\n" r"$g(EX)=%.3f$" % (J["Eg"], J["gmu"]), transform=ax.transAxes,
                ha="right", va="top", fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s5", out_dir)


def fig_4_s6(out_dir=None):
    """Figure 4.S6: Exercises 1 and 7 (Chebyshev against the truth, and against Mill)."""
    fig, axes = common.panel_grid(1, 2, size=(3.5, 2.9))
    ax = axes[0, 0]
    k = np.linspace(0.05, 5, 400)
    exact = np.where(k > 1, np.exp(-(1 + k)), np.exp(-(1 + k)) + 1 - np.exp(-(1 - np.minimum(k, 1))))
    ax.plot(k, np.minimum(1, 1 / k ** 2), color=ORANGE, label=r"Chebyshev $1/k^2$")
    ax.plot(k, exact, color=RED, label="exact")
    _logax(ax)
    ax.set_xlabel(r"$k$")
    ax.set_title(r"Exponential: $P(|X-\mu|\geq k\sigma)$")
    ax.legend(loc="lower left", fontsize=8, frameon=False)
    ax = axes[0, 1]
    n = 10
    t = np.linspace(0.02, 1.5, 400)
    ax.plot(t, np.minimum(1, 1 / (n * t ** 2)), color=ORANGE, label=r"Chebyshev $1/(nt^2)$")
    ax.plot(t, np.minimum(1, mills_bound(np.sqrt(n) * t)), color=BLUE, label="Mill")
    ax.plot(t, normal_tail2(np.sqrt(n) * t), color=RED, label="exact")
    _logax(ax)
    ax.set_ylim(1e-6, 2)
    ax.set_xlabel(r"$t$")
    ax.set_title(r"$P(|\bar X_n|>t)$, $N(0,1)$ data, $n=10$")
    ax.legend(loc="lower left", fontsize=8, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s6", out_dir)


def fig_4_s7(out_dir=None):
    """Figure 4.S7: the maximum of n standard normals against sqrt(2 log n)."""
    ns = np.unique(np.geomspace(2, 5000, 25).astype(int))
    mx, mabs = gauss_max_mc(ns)
    fig, axes = common.panel_grid(1, 2, size=(3.5, 2.9))
    ax = axes[0, 0]
    ax.plot(ns, mx, "o", color=RED, ms=3.5, label=r"$E\,\mathrm{max}_i\,Z_i$ (simulated)")
    ax.plot(ns, mabs, "s", color=BLUE, ms=3, mfc="white", label=r"$E\,\mathrm{max}_i\,|Z_i|$ (simulated)")
    ax.plot(ns, np.sqrt(2 * np.log(ns)), color="k", lw=1.2, label=r"$\sqrt{2\log n}$")
    ax.plot(ns, np.sqrt(2 * np.log(2 * ns)), color="k", lw=1, ls="--", label=r"$\sqrt{2\log 2n}$")
    ax.set_xscale("log")
    ax.set_xlabel(r"$n$")
    ax.set_title("expected maximum")
    ax.legend(loc="upper left", fontsize=7.5, frameon=False)
    ax = axes[0, 1]
    t = np.linspace(0.5, 6, 300)
    n = 100
    exact = 1 - (1 - normal_tail2(t)) ** n
    ax.plot(t, exact, color=RED, label=r"exact $P(\mathrm{max}_i\,|Z_i|>t)$")
    ax.plot(t, np.minimum(1, n * mills_bound(t)), color=BLUE, label="union bound + Mill")
    _logax(ax)
    ax.set_ylim(1e-6, 2)
    ax.set_xlabel(r"$t$")
    ax.set_title(r"$n=100$")
    ax.legend(loc="lower left", fontsize=7.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig4-s7", out_dir)


# =========================================================================== demo data
def export_demo_data():
    """The nerve data for the Jensen demonstration."""
    os.makedirs(DATA_OUT, exist_ok=True)
    x = nerve()
    out = dict(note="Nerve data of Wasserman (2004), file nerve.dat on the book's website: 799 waiting times "
                    "(seconds) between successive pulses along a nerve fibre.",
               x=[float(v) for v in x], bins=[float(v) for v in NERVE_BINS])
    path = os.path.join(DATA_OUT, "ch04-nerve.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


FIGURES = {"4.S1": fig_4_s1, "4.S2": fig_4_s2, "4.S3": fig_4_s3, "4.S4": fig_4_s4, "4.S5": fig_4_s5,
           "4.S6": fig_4_s6, "4.S7": fig_4_s7}

if __name__ == "__main__":
    import sys
    common.run(FIGURES, CH)
    if "--list" not in sys.argv:
        export_demo_data()
