"""Chapter 7 of Wasserman (2006), All of Nonparametric Statistics: Normal Means and Minimax Theory.

Reproduces the figure of the chapter that is computed from a model, and the simulation table:

* Figure 7.2  the radii rho_S of Baraud's confidence ball for nested subspaces, n = 100, four values of gamma;
* Table 7.1   coverage and mean radius of the chi-square, Baraud and pivotal confidence balls (Example 7.69).

Skipped figure:

* Figure 7.1 is a schematic of the one-way layout X_ij = theta_i + noise (a table of symbols, nothing computed).

Supplementary figures (numbered 7.S1, 7.S2, ... in the notes) illustrate results the book states without a
picture:

* 7.S1  regression turned into a Normal means problem: the coefficients Z_j of a noisy curve (Section 7.3);
* 7.S2  the exact risk functions of soft and hard thresholding, and SURE against the true risk (Exercises 5, 7);
* 7.S3  the exact risk of the James-Stein estimator against the oracle and the bound (7.43) (Theorem 7.42);
* 7.S4  Pinsker's linear minimax estimator on a Sobolev ellipsoid and the Pinsker constant (Theorems 7.32, 7.36);
* 7.S5  the Donoho-Johnstone oracle inequality for the universal threshold (Theorem 7.90);
* 7.S6  Exercise 1: the risk of bZ against b, and the simulated James-Stein shrinkage factors;
* 7.S7  Exercise 8: the radii of the three confidence balls for theta_i = 1/i;
* 7.S8  adaptive estimation: blockwise James-Stein against the Pinsker estimator (Theorem 7.50).

Everything the chapter is about (SURE, soft and hard thresholding, the James-Stein estimator and its exact risk,
Pinsker's linear minimax estimator, the block James-Stein estimator, and the three confidence balls) is
implemented here from scratch; noncentral chi-square probabilities come from scipy and are cross-checked by a
Poisson-mixture formula.

Usage: python ch07_normal_means_minimax.py [--fig 7.2 7.S3 ...] [--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, savefig, run

CH = 7
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


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


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

    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)

    def normals(self, n):
        return np.array([self.norm() for _ in range(n)])


def demo_seed(seed, r):
    """Seed of replicate r in the demos: seed + 7919 r."""
    return (seed + 7919 * r) & M32


# =========================================================================== estimators and SURE
def soft(z, lam):
    """Soft threshold sign(z)(|z| - lam)_+, equation (7.21)."""
    return np.sign(z) * np.maximum(np.abs(z) - lam, 0.0)


def hard(z, lam):
    """Hard threshold z I(|z| > lam), equation (7.23)."""
    return np.where(np.abs(z) > lam, z, 0.0)


def sure_soft(z, lam, sigma):
    """SURE (7.22) of the soft-threshold estimator at threshold lam."""
    z = np.asarray(z, float)
    return float(np.sum(sigma ** 2 - 2 * sigma ** 2 * (np.abs(z) <= lam) + np.minimum(z ** 2, lam ** 2)))


def sure_soft_curve(z, lams, sigma):
    return np.array([sure_soft(z, l, sigma) for l in lams])


def sure_soft_min(z, sigma):
    """Minimiser of SURE over lam >= 0. Between consecutive |z|'s SURE increases in lam and it drops by
    2 sigma^2 at each |z_i|, so the minimum is at 0 or at one of the |z_i|."""
    cand = np.concatenate([[0.0], np.sort(np.abs(z))])
    vals = sure_soft_curve(z, cand, sigma)
    k = int(np.argmin(vals))
    return float(cand[k]), float(vals[k])


def sure_generic(z, est, sigma, h=1e-6):
    """SURE (7.19) for any weakly differentiable estimator est(z) (vector -> vector), with the divergence
    computed by central differences (used to cross-check the closed forms)."""
    z = np.asarray(z, float)
    n = len(z)
    g = est(z) - z
    div = 0.0
    for i in range(n):
        e = np.zeros(n)
        e[i] = h
        div += (est(z + e)[i] - est(z - e)[i]) / (2 * h) - 1.0
    return float(n * sigma ** 2 + 2 * sigma ** 2 * div + np.sum(g ** 2))


def risk_soft(theta, lam, sigma=1.0):
    """Exact risk E(soft(Z, lam) - theta)^2 for Z ~ N(theta, sigma^2) (one coordinate; vectorised)."""
    t = np.asarray(theta, float) / sigma
    l = lam / sigma
    Phi, phi = stats.norm.cdf, stats.norm.pdf
    r = (1 + l ** 2 + (t ** 2 - l ** 2 - 1) * (Phi(l - t) - Phi(-l - t))
         - (l - t) * phi(l + t) - (l + t) * phi(l - t))
    return sigma ** 2 * r


def risk_hard(theta, lam, sigma=1.0):
    """Exact risk E(hard(Z, lam) - theta)^2 for Z ~ N(theta, sigma^2)."""
    t = np.asarray(theta, float) / sigma
    l = lam / sigma
    Phi, phi = stats.norm.cdf, stats.norm.pdf
    inside = Phi(l - t) - Phi(-l - t)
    r = t ** 2 * inside + (1 - inside) + (l - t) * phi(l - t) + (l + t) * phi(l + t)
    return sigma ** 2 * r


def js(z, sigma):
    """James-Stein estimator (7.41)."""
    n = len(z)
    return (1 - (n - 2) * sigma ** 2 / np.sum(z ** 2)) * z


def js_plus(z, sigma):
    """Modified (positive-part) James-Stein estimator (7.46)."""
    n = len(z)
    return max(0.0, 1 - n * sigma ** 2 / np.sum(z ** 2)) * z


def inv_noncentral_mean(n, delta):
    """E[1/(n - 2 + 2K)], K ~ Poisson(delta/2): equals sigma^2 E(1 / sum Z_i^2) (proof of Theorem 7.42)."""
    lam = delta / 2.0
    kmax = int(lam + 12 * math.sqrt(lam + 1) + 60)
    k = np.arange(kmax + 1)
    logp = -lam + k * math.log(lam) - np.array([math.lgamma(i + 1) for i in k]) if lam > 0 else np.where(k == 0, 0.0, -np.inf)
    return float(np.sum(np.exp(logp) / (n - 2 + 2 * k)))


def js_risk(n, sigma, norm2):
    """Exact risk (7.44) of the James-Stein estimator, as a function of ||theta||^2."""
    return n * sigma ** 2 - (n - 2) ** 2 * sigma ** 2 * inv_noncentral_mean(n, norm2 / sigma ** 2)


def js_bound(n, sigma, norm2):
    """The first bound of (7.43)."""
    return 2 * sigma ** 2 + (n - 2) * sigma ** 2 * norm2 / ((n - 2) * sigma ** 2 + norm2)


def oracle_linear(n, sigma, norm2):
    """Risk (7.38) of the ideal linear estimator b* Z."""
    return n * sigma ** 2 * norm2 / (n * sigma ** 2 + norm2)


def linear_risk(b, n, sigma, norm2):
    """Risk (7.37) of bZ."""
    return (1 - b) ** 2 * norm2 + n * b ** 2 * sigma ** 2


# =========================================================================== Pinsker
def sobolev_a(J, m):
    """a_j of Theorem 7.11 for the Fourier basis, j = 1..J: a_1 = 0, a_j = (pi j)^m for even j and
    (pi (j - 1))^m for odd j >= 3."""
    j = np.arange(1, J + 1)
    base = np.where(j % 2 == 0, j, j - 1).astype(float)
    return (math.pi * base) ** m


def pinsker_linear(a, sigma_n, c):
    """Linear minimax estimator over the ellipsoid {sum a_j^2 theta_j^2 <= c^2} (Theorem 7.36 with the
    constraint written as in (7.9)). Returns mu, the weights w_j = (1 - a_j/mu)_+, the minimax linear risk
    sigma_n^2 sum w_j and the prior variances tau_j^2 = sigma_n^2 (mu/a_j - 1)_+."""
    a = np.asarray(a, float)

    def eq(mu):
        return sigma_n ** 2 * np.sum(a * np.maximum(mu - a, 0.0)) - c ** 2

    lo, hi = 1e-12, max(1.0, a[a > 0].min())
    while eq(hi) < 0:
        hi *= 2.0
        if hi > a.max():
            raise ValueError("ellipsoid truncated too early: increase the number of coefficients")
    mu = optimize.brentq(eq, lo, hi, xtol=1e-14, rtol=1e-14, maxiter=500)
    w = np.maximum(1 - a / mu, 0.0)
    with np.errstate(divide="ignore"):
        tau2 = np.where(a > 0, sigma_n ** 2 * np.maximum(mu / np.where(a > 0, a, 1) - 1, 0.0), np.inf)
    return mu, w, float(sigma_n ** 2 * np.sum(w)), tau2


def linear_max_risk(w, a, sigma_n, c):
    """sup over the ellipsoid of the risk of the linear estimator w*Z: sigma_n^2 sum w^2 +
    c^2 max_j (1 - w_j)^2 / a_j^2 (the max is infinite if some a_j = 0 has w_j < 1)."""
    a = np.asarray(a, float)
    bias = np.where(a > 0, (1 - w) ** 2 / np.where(a > 0, a, 1) ** 2, np.where(w < 1, np.inf, 0.0))
    return float(sigma_n ** 2 * np.sum(w ** 2) + c ** 2 * np.max(bias))


def pinsker_constant(m):
    """P_m of (7.35)."""
    return (m / (m + 1.0)) ** (2 * m / (2 * m + 1.0)) * (2 * m + 1.0) ** (1 / (2 * m + 1.0))


def pinsker_limit(m, sigma, c):
    """The limit of n^{2m/(2m+1)} R_n, with (sigma^2/pi) in place of the book's (sigma/pi) in (7.34)."""
    return (sigma ** 2 / math.pi) ** (2 * m / (2 * m + 1.0)) * c ** (2 / (2 * m + 1.0)) * pinsker_constant(m)


def pinsker_n_risk(n, m, sigma, c, J=None):
    """Minimax linear risk over Theta(m, c) with sigma_n^2 = sigma^2/n."""
    J = J or max(400, int(8 * (n * c ** 2 / sigma ** 2) ** (1 / (2 * m + 1)) + 50))
    a = sobolev_a(J, m)
    mu, w, R, _ = pinsker_linear(a, sigma / math.sqrt(n), c)
    return R


# =========================================================================== block James-Stein (Theorem 7.50)
def clz_blocks(n):
    """Blocks of Cai, Low and Zhao (2000) as described before Theorem 7.50 (indices are 1-based, returned
    as 0-based Python slices). b = 1 + 1/log n; B_0 = {1..[b^K0]}, B_k = {[b^(k-1)] < i <= [b^k]}, and the
    estimate is 0 beyond [b^K1], K1 = [log_b n] - 1."""
    b = 1 + 1 / math.log(n)
    K1 = int(math.floor(math.log(n) / math.log(b))) - 1
    K0 = 1
    while True:
        ok = math.floor(b ** K0) >= 3 and all(math.floor(b ** k) - math.floor(b ** (k - 1)) >= 3
                                               for k in range(K0 + 1, K1 + 1))
        if ok:
            break
        K0 += 1
    edges = [0, int(math.floor(b ** K0))]
    for k in range(K0 + 1, K1 + 1):
        edges.append(int(math.floor(b ** k)))
    return [(edges[i], edges[i + 1]) for i in range(len(edges) - 1)], edges[-1]


def block_js(z, sigma_n, blocks, last):
    """Positive-part James-Stein within each block (the (n_k - 2) version), zero beyond `last`."""
    out = np.zeros_like(z)
    for lo, hi in blocks:
        zb = z[lo:hi]
        d = hi - lo
        s = np.sum(zb ** 2)
        out[lo:hi] = max(0.0, 1 - (d - 2) * sigma_n ** 2 / s) * zb if s > 0 else 0.0
    out[last:] = 0.0
    return out


# =========================================================================== confidence balls
def ncx2_cdf(x, df, nc):
    """P(chi^2_{nc, df} <= x); nc = 0 gives the central chi-square."""
    if df == 0:
        return float(nc <= x)
    if nc <= 0:
        return float(stats.chi2.cdf(x, df))
    return float(stats.ncx2.cdf(x, df, nc))


def q_upper(df, alpha):
    """q_{0,df}(alpha) = upper alpha quantile of chi^2_df, -inf for alpha >= 1."""
    if alpha >= 1:
        return -np.inf
    return float(stats.chi2.isf(alpha, df))


def baraud_kappa(n, d, alpha_S, gamma):
    """rho_S^2 / sigma_n^2 of (7.57) for a subspace of dimension d in R^n."""
    e = n - d
    if d == n:
        return q_upper(n, alpha_S)
    if d == 0:
        c0 = q_upper(n, gamma)
        f = lambda z: ncx2_cdf(c0, n, z) - alpha_S
        hi = 1.0
        while f(hi) > 0:
            hi *= 2
        return optimize.brentq(f, 0.0, hi, xtol=1e-10)
    cS = q_upper(e, gamma)
    G = lambda z: ncx2_cdf(cS, e, z)
    # z_max: G(z_max) = alpha_S (beyond it the quantile is -inf)
    hi = 1.0
    while G(hi) > alpha_S:
        hi *= 2
    zmax = optimize.brentq(lambda z: G(z) - alpha_S, 0.0, hi, xtol=1e-10)
    h = lambda z: -(z + q_upper(d, alpha_S / G(z)))
    zs = np.linspace(0.0, zmax * (1 - 1e-9), 201)
    vals = np.array([-h(z) for z in zs])
    k = int(np.argmax(vals))
    a, b = zs[max(k - 1, 0)], zs[min(k + 1, len(zs) - 1)]
    if b > a:
        r = optimize.minimize_scalar(h, bounds=(a, b), method="bounded", options={"xatol": 1e-9})
        return max(float(-r.fun), float(vals[k]))
    return float(vals[k])


def baraud_table(n, alpha=0.05, gamma=0.5, cache=True):
    """kappa_d = rho_{S_d}^2 / sigma_n^2 for the nested subspaces S_0, ..., S_n, alpha_S = alpha/(n+1)."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    p = os.path.join(CACHE_DIR, "ch07-baraud-n%d-a%g-g%g.npy" % (n, alpha, gamma))
    if cache and os.path.exists(p):
        return np.load(p)
    aS = alpha / (n + 1)
    k = np.array([baraud_kappa(n, d, aS, gamma) for d in range(n + 1)])
    np.save(p, k)
    return k


def baraud_accept_c(n, gamma):
    """c(S_d) = q_{0,n-d}(gamma) for d = 0..n (c(S_n) = 0, always accepted)."""
    return np.array([q_upper(n - d, gamma) if d < n else 0.0 for d in range(n + 1)])


def balls(z, sigma_n, kappa, cS, alpha=0.05):
    """The three confidence balls of Section 7.8 for nested subspaces.
    Returns dict with (centre, radius^2) for the chi-square ball, Baraud's ball and the pivotal ball."""
    n = len(z)
    s2 = sigma_n ** 2
    tail = np.concatenate([np.cumsum((z ** 2)[::-1])[::-1], [0.0]])     # tail[d] = sum_{j > d} Z_j^2
    # chi-square ball
    r2_chi = s2 * q_upper(n, alpha)
    # Baraud: accepted subspaces, smallest radius
    acc = tail / s2 <= cS + 1e-12
    acc[n] = True
    rho2 = s2 * kappa
    d_b = int(np.argmin(np.where(acc, rho2, np.inf)))
    cen_b = np.concatenate([z[:d_b], np.zeros(n - d_b)])
    # pivotal (Beran-Dumbgen): R_m = m s2 + sum_{j>m}(Z_j^2 - s2)
    m = np.arange(n + 1)
    Rm = m * s2 + tail - (n - m) * s2
    mh = int(np.argmin(Rm))
    pos = max(tail[mh] - (n - mh) * s2, 0.0)
    Rh = mh * s2 + pos
    tau2 = 2 * n * s2 * (n * s2 + 2 * pos)
    r2_piv = Rh + math.sqrt(tau2) * stats.norm.isf(alpha) / math.sqrt(n)
    cen_p = np.concatenate([z[:mh], np.zeros(n - mh)])
    return {"chi2": (z, r2_chi), "baraud": (cen_b, rho2[d_b], d_b), "pivotal": (cen_p, r2_piv, mh)}


def ball_simulation(theta, sigma_n, gammas=(0.90, 0.50, 0.15, 0.05), alpha=0.05, reps=1000, seed=1):
    """Coverage and mean radius of the three balls; replicate r draws Z with DK.rng(seed + 7919 r)."""
    n = len(theta)
    tabs = {g: (baraud_table(n, alpha, g), baraud_accept_c(n, g)) for g in gammas}
    out = {"chi2": [], "pivotal": []}
    for g in gammas:
        out["baraud%g" % g] = []
    rad = {k: [] for k in out}
    for r in range(reps):
        z = theta + sigma_n * JSRandom(demo_seed(seed, r)).normals(n)
        for gi, g in enumerate(gammas):
            b = balls(z, sigma_n, *tabs[g], alpha=alpha)
            cen, r2, _ = b["baraud"]
            out["baraud%g" % g].append(np.sum((cen - theta) ** 2) <= r2)
            rad["baraud%g" % g].append(math.sqrt(r2))
            if gi == 0:
                for k in ("chi2", "pivotal"):
                    cen, r2 = b[k][0], b[k][1]
                    out[k].append(np.sum((cen - theta) ** 2) <= r2)
                    rad[k].append(math.sqrt(max(r2, 0.0)))
    return {k: (float(np.mean(out[k])), float(np.mean(rad[k])), np.array(rad[k])) for k in out}


def table_7_1(reps=1000, seed=1):
    n = 100
    theta = np.zeros(n)
    theta[:5] = 10.0
    p = os.path.join(CACHE_DIR, "ch07-table71-%d-%d.json" % (reps, seed))
    if os.path.exists(p):
        with open(p) as f:
            return json.load(f)
    res = ball_simulation(theta, 1 / math.sqrt(n), reps=reps, seed=seed)
    d = {k: [v[0], v[1]] for k, v in res.items()}
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(p, "w") as f:
        json.dump(d, f)
    return d


# =========================================================================== regression -> Normal means
def doppler(x):
    return np.sqrt(x * (1 - x)) * np.sin(2.1 * np.pi / (x + 0.05))


def cosine_basis(x, J):
    """phi_1 = 1, phi_j = sqrt(2) cos((j - 1) pi x), j = 2..J (the basis of Chapter 8)."""
    j = np.arange(J)
    B = np.sqrt(2) * np.cos(np.pi * np.outer(x, j))
    B[:, 0] = 1.0
    return B


def regression_coefficients(f, n=512, sigma=0.5, seed=7):
    """Y_i = f(x_i) + sigma eps_i on the midpoint grid x_i = (i - 1/2)/n, Z_j = n^{-1} sum Y_i phi_j(x_i)
    (equation (7.14)); on this grid the cosine vectors are exactly orthogonal, so the Z_j are independent
    N(E Z_j, sigma^2/n). Returns x, y, Z, the exact means E Z_j and the true coefficients theta_j."""
    x = (np.arange(1, n + 1) - 0.5) / n
    rng = np.random.default_rng(seed)
    y = f(x) + sigma * rng.standard_normal(n)
    B = cosine_basis(x, n)
    Z = B.T @ y / n
    EZ = B.T @ f(x) / n
    # true coefficients by fine quadrature
    xf = (np.arange(1, 200001) - 0.5) / 200000
    th = np.array([np.mean(f(xf) * (np.sqrt(2) * np.cos(np.pi * j * xf) if j else 1.0)) for j in range(n)])
    return x, y, Z, EZ, th


# =========================================================================== exercises
def ex1(n=1000, reps=1000, seed=1):
    """Exercise 1: theta_i = 1/i^2, sigma_n = 1."""
    theta = 1.0 / np.arange(1, n + 1) ** 2
    t2 = float(np.sum(theta ** 2))
    bstar = t2 / (n + t2)
    rng = np.random.default_rng(seed)
    bs, loss_js, loss_mle = [], [], []
    for _ in range(reps):
        z = theta + rng.standard_normal(n)
        b = max(0.0, 1 - n / np.sum(z ** 2))
        bs.append(b)
        loss_js.append(np.sum((b * z - theta) ** 2))
        loss_mle.append(np.sum((z - theta) ** 2))
    return {"theta2": t2, "bstar": bstar, "oracle": oracle_linear(n, 1.0, t2), "mle": float(n),
            "b": np.array(bs), "js_risk": float(np.mean(loss_js)), "js_se": float(np.std(loss_js) / math.sqrt(reps)),
            "mle_sim": float(np.mean(loss_mle)), "pinsker": n * t2 / (n + t2)}


def curved_soft(z, lam):
    """Exercise 2: sign(z) (|z| - lam)_+^2."""
    return np.sign(z) * np.maximum(np.abs(z) - lam, 0.0) ** 2


def sure_curved(z, lam, sigma=1.0):
    """SURE (7.19) for the curved soft threshold: D_i = 2(|z_i| - lam)_+ - 1."""
    g = curved_soft(z, lam) - z
    D = 2 * np.maximum(np.abs(z) - lam, 0.0) - 1
    return float(len(z) * sigma ** 2 + 2 * sigma ** 2 * np.sum(D) + np.sum(g ** 2))


def risk_curved(theta, lam, sigma=1.0):
    """Exact one-coordinate risk of the curved soft threshold, by Gauss-Hermite-free quadrature."""
    from scipy.integrate import quad
    out = []
    for t in np.atleast_1d(theta):
        f = lambda e: (curved_soft(np.array([t + sigma * e]), lam)[0] - t) ** 2 * stats.norm.pdf(e)
        pts = [(-lam - t) / sigma, (lam - t) / sigma]
        v = quad(f, -12, 12, points=sorted(pts), limit=200)[0]
        out.append(v)
    return np.array(out)


def ex2(reps=200, seed=2):
    """Exercise 2(b): curved soft threshold with SURE-chosen lambda, against James-Stein, for theta_i = 1/i^2
    and for ten 10's followed by 990 zeros (n = 1000, sigma = 1)."""
    rng = np.random.default_rng(seed)
    out = {}
    for name, theta in (("decay", 1.0 / np.arange(1, 1001) ** 2), ("spikes", np.r_[10.0 * np.ones(10), np.zeros(990)])):
        lc, lj, ls = [], [], []
        grid = np.linspace(0, 12, 481)
        for _ in range(reps):
            z = theta + rng.standard_normal(1000)
            s = [sure_curved(z, l) for l in grid]
            lam = grid[int(np.argmin(s))]
            lc.append(np.sum((curved_soft(z, lam) - theta) ** 2))
            lj.append(np.sum((js_plus(z, 1.0) - theta) ** 2))
            lam_s, _ = sure_soft_min(z, 1.0)
            ls.append(np.sum((soft(z, lam_s) - theta) ** 2))
        out[name] = {"curved": float(np.mean(lc)), "js": float(np.mean(lj)), "soft_sure": float(np.mean(ls))}
    return out


def ex8(reps=1000, seed=8):
    """Exercise 8: theta_i = 1/i, Z_i ~ N(theta_i, 1), n = 100, gamma = 0.5 for Baraud."""
    theta = 1.0 / np.arange(1, 101)
    return ball_simulation(theta, 1.0, gammas=(0.5,), reps=reps, seed=seed)


def ex9(n, alpha=0.05, sigma=1.0):
    """Exercise 9: the exact sup-norm ball ||theta - Z||_inf <= c_n with sigma_n = sigma/sqrt(n)."""
    sn = sigma / math.sqrt(n)
    c = sn * stats.norm.ppf((1 + (1 - alpha) ** (1.0 / n)) / 2)
    return c, 2 * c


def ex10(n=100, reps=4000, seed=10):
    """Exercise 10 at theta = 0, sigma_n = 1: E max_S |hat R_S - R(hat theta_S, theta)| for (i) one model
    (S empty), (ii) the n + 1 nested models, (iii) all 2^n subsets. With W_i = Z_i^2 - 1 the error of model S
    is sum_{i not in S} W_i."""
    rng = np.random.default_rng(seed)
    W = rng.standard_normal((reps, n)) ** 2 - 1
    single = np.abs(W.sum(1))
    tails = np.cumsum(W[:, ::-1], axis=1)
    nested = np.max(np.abs(tails), axis=1)
    allsub = np.maximum(np.sum(np.maximum(W, 0), 1), np.sum(np.maximum(-W, 0), 1))
    return float(single.mean()), float(nested.mean()), float(allsub.mean())


def ex11(n=1000, k=10, size=5.0, reps=500, seed=11):
    """Exercise 11: BIC keeps Z_i^2 > sigma^2 log n, SURE/C_p keeps Z_i^2 > 2 sigma^2 (sigma_n = 1).
    Returns, for each rule, (risk, probability of selecting exactly the true model, mean number of
    wrongly classified coordinates)."""
    rng = np.random.default_rng(seed)
    theta = np.r_[size * np.ones(k), np.zeros(n - k)]
    true = theta != 0
    res = {"bic": [0.0, 0.0, 0.0], "sure": [0.0, 0.0, 0.0]}
    for _ in range(reps):
        z = theta + rng.standard_normal(n)
        for name, thr in (("bic", math.log(n)), ("sure", 2.0)):
            keep = z ** 2 > thr
            res[name][0] += np.sum((np.where(keep, z, 0) - theta) ** 2) / reps
            res[name][1] += float(np.array_equal(keep, true)) / reps
            res[name][2] += float(np.sum(keep != true)) / reps
    return {k2: tuple(v) for k2, v in res.items()}


def ex11_table():
    return {(n, size): ex11(n=n, size=size) for n in (100, 1000) for size in (2.0, 5.0)}


# =========================================================================== figures
def fig_7_2(out=None):
    """Figure 7.2: Baraud's radii rho_S against the dimension of S (n = 100, sigma_n = 1/sqrt(n))."""
    n = 100
    sn = 1 / math.sqrt(n)
    fig, ax = common.plt.subplots(figsize=(5.6, 3.6))
    cols = {0.05: RED, 0.15: ORANGE, 0.50: GREEN, 0.90: BLUE}
    d = np.arange(n + 1)
    for g, col in cols.items():
        k = baraud_table(n, 0.05, g)
        ax.plot(d, sn * np.sqrt(k), color=col, label=r"$\gamma=%.2f$" % g)
    ax.axhline(sn * math.sqrt(q_upper(n, 0.05)), color=GREY, ls=":", lw=1.4, label=r"$\chi^2$ ball")
    ax.set_xlabel("dimension of the subspace $S$")
    ax.set_ylabel(r"$\rho_S$")
    ax.set_xlim(0, n)
    ax.legend(frameon=False, loc="lower right", fontsize=8.5)
    savefig(fig, CH, "fig7-2", out)


def fig_7_S1(out=None):
    """Figure 7.S1: a regression problem becomes a Normal means problem (Section 7.3)."""
    x, y, Z, EZ, th = regression_coefficients(doppler)
    n = len(x)
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.3))
    axs[0].plot(x, y, ".", ms=2.5, color=GREY)
    axs[0].plot(x, doppler(x), color=BLUE)
    axs[0].set_title("(a) $Y_i=f(x_i)+\\sigma\\epsilon_i$, $n=512$, $\\sigma=0.5$")
    axs[0].set_xlabel("$x$")
    j = np.arange(1, 129)
    axs[1].plot(j, Z[:128], ".", ms=4, color=RED, label="$Z_j$ (data)")
    axs[1].plot(j, th[:128], color=BLUE, lw=1.2, label=r"$\theta_j=\int f\phi_j$")
    axs[1].axhspan(-2 * 0.5 / math.sqrt(n), 2 * 0.5 / math.sqrt(n), color=GREY, alpha=0.18, lw=0,
                   label=r"$\pm2\sigma/\sqrt{n}$")
    axs[1].set_xlabel("$j$")
    axs[1].set_title("(b) cosine coefficients, first 128")
    axs[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S1", out)


def fig_7_S2(out=None):
    """Figure 7.S2: exact risk of soft and hard thresholding, and SURE against the true risk."""
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.4))
    t = np.linspace(0, 6, 400)
    for lam, ls in ((1.0, "-"), (2.0, "--")):
        axs[0].plot(t, risk_soft(t, lam), color=RED, ls=ls, label="soft, $\\lambda=%g$" % lam)
        axs[0].plot(t, risk_hard(t, lam), color=BLUE, ls=ls, label="hard, $\\lambda=%g$" % lam)
    axs[0].plot(t, np.minimum(t ** 2, 1), color=GREY, lw=1, label=r"oracle $\min(\theta^2,1)$")
    axs[0].axhline(1, color=GREY, ls=":", lw=1)
    axs[0].set_xlabel(r"$\theta$ ($\sigma=1$)")
    axs[0].set_ylabel("risk")
    axs[0].set_title("(a) risk of one coordinate")
    axs[0].legend(frameon=False, fontsize=7.5, ncol=2)
    n = 200
    theta = np.r_[np.linspace(4, 1, 20), np.zeros(n - 20)]
    z = theta + JSRandom(3).normals(n)
    lams = np.linspace(0, 4, 401)
    axs[1].plot(lams, sure_soft_curve(z, lams, 1.0), color=RED, lw=1.2, label="SURE (7.22), one data set")
    axs[1].plot(lams, [np.sum(risk_soft(theta, l)) for l in lams], color=BLUE, label="true risk")
    ls_, _ = sure_soft_min(z, 1.0)
    axs[1].axvline(ls_, color=RED, ls="--", lw=1)
    axs[1].axvline(math.sqrt(2 * math.log(n)), color=GREEN, ls=":", lw=1.4, label=r"$\sqrt{2\log n}$")
    axs[1].set_xlabel(r"$\lambda$")
    axs[1].set_title("(b) soft threshold, $n=200$, 20 nonzero means")
    axs[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S2", out)


def fig_7_S3(out=None):
    """Figure 7.S3: exact James-Stein risk, the bound (7.43) and the linear oracle."""
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.4))
    for ax, n in zip(axs, (10, 100)):
        s = 1.0
        u = np.linspace(0, 3 * n, 300)
        ax.plot(u, [js_risk(n, s, v) for v in u], color=RED, label="James-Stein (exact)")
        ax.plot(u, [js_bound(n, s, v) for v in u], color=ORANGE, ls="--", label="bound (7.43)")
        ax.plot(u, [oracle_linear(n, s, v) for v in u], color=BLUE, label="linear oracle (7.38)")
        ax.axhline(n, color=GREY, ls=":", label="MLE")
        ax.set_xlabel(r"$\|\theta\|^2$ ($\sigma_n=1$)")
        ax.set_title("(%s) $n=%d$" % ("a" if n == 10 else "b", n))
        ax.set_ylim(0, n * 1.08)
    axs[0].set_ylabel("risk")
    axs[0].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S3", out)


def fig_7_S4(out=None):
    """Figure 7.S4: Pinsker's weights on a Sobolev ellipsoid and convergence to the Pinsker constant."""
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.4))
    sigma, c = 1.0, 5.0
    for n, col in ((100, BLUE), (1000, GREEN), (10000, RED)):
        a = sobolev_a(400, 1)
        mu, w, R, _ = pinsker_linear(a, sigma / math.sqrt(n), c)
        axs[0].step(np.arange(1, 81), w[:80], where="mid", color=col, label="$n=%d$" % n)
    axs[0].set_xlabel("$j$")
    axs[0].set_ylabel("weight $w_j$")
    axs[0].set_title(r"(a) linear minimax weights, $m=1$, $c=5$, $\sigma=1$")
    axs[0].legend(frameon=False, fontsize=8)
    ns = np.unique(np.round(np.logspace(1, 6, 26)).astype(int))
    for m, col in ((1, BLUE), (2, RED)):
        sc = [n ** (2 * m / (2 * m + 1)) * pinsker_n_risk(n, m, 2.0, c) for n in ns]
        axs[1].semilogx(ns, sc, "o-", ms=3, color=col, label="$m=%d$" % m)
        axs[1].axhline(pinsker_limit(m, 2.0, c), color=col, ls="--", lw=1)
    axs[1].set_xlabel("$n$")
    axs[1].set_ylabel(r"$n^{2m/(2m+1)}R_n^L$")
    axs[1].set_title(r"(b) $\sigma=2$, $c=1$: dashed = limit with $\sigma^2/\pi$")
    axs[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S4", out)


def dj_ratio(n, tmax=8.0):
    """sup over theta of r_soft(lambda_n, theta) / (1/n + min(theta^2, 1)), lambda_n = sqrt(2 log n)."""
    lam = math.sqrt(2 * math.log(n))
    t = np.linspace(0, tmax + lam, 4001)
    return float(np.max(risk_soft(t, lam) / (1.0 / n + np.minimum(t ** 2, 1))))


def fig_7_S5(out=None):
    """Figure 7.S5: the Donoho-Johnstone oracle inequality."""
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.4))
    ns = np.unique(np.round(np.logspace(0.5, 6, 30)).astype(int))
    axs[0].semilogx(ns, [dj_ratio(n) for n in ns], "o-", ms=3, color=RED, label="worst-case ratio, soft threshold")
    axs[0].semilogx(ns, 2 * np.log(ns) + 1, color=GREY, ls="--", label=r"$2\log n+1$")
    axs[0].semilogx(ns, 2 * np.log(ns), color=GREY, ls=":", label=r"$2\log n$")
    axs[0].set_xlabel("$n$")
    axs[0].set_title(r"(a) $\sup_\theta\, \mathrm{risk}/(\sigma_n^2+R_{\rm oracle})$")
    axs[0].legend(frameon=False, fontsize=8)
    n = 1000
    lam = math.sqrt(2 * math.log(n))
    ks = np.arange(0, 101, 4)
    for size, col in ((5.0, RED), (2.0, BLUE)):
        rs, ro = [], []
        for k in ks:
            theta = np.r_[size * np.ones(k), np.zeros(n - k)]
            rs.append(np.sum(risk_soft(theta, lam)))
            ro.append(np.sum(np.minimum(theta ** 2, 1)))
        axs[1].plot(ks, rs, color=col, label="soft, $\\theta_i=%g$" % size)
        axs[1].plot(ks, ro, color=col, ls=":", label="oracle, $\\theta_i=%g$" % size)
        axs[1].plot(ks, [js_risk(n, 1.0, k * size ** 2) for k in ks], color=col, ls="--", lw=1, label="James-Stein, $\\theta_i=%g$" % size)
    axs[1].set_xlabel("number $k$ of nonzero means ($n=1000$, $\\sigma_n=1$)")
    axs[1].set_title(r"(b) universal threshold $\sqrt{2\log n}$")
    axs[1].legend(frameon=False, fontsize=7, ncol=2)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S5", out)


def fig_7_S6(out=None):
    """Figure 7.S6: Exercise 1."""
    r = ex1()
    n, t2 = 1000, r["theta2"]
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.3))
    b = np.linspace(0, 0.02, 400)
    axs[0].plot(b, linear_risk(b, n, 1.0, t2), color=BLUE)
    axs[0].axvline(r["bstar"], color=RED, ls="--", lw=1, label="$b^*=%.5f$" % r["bstar"])
    axs[0].set_xlabel("$b$")
    axs[0].set_ylabel("risk of $bZ$")
    axs[0].set_title(r"(a) $\theta_i=1/i^2$, $n=1000$")
    axs[0].legend(frameon=False, fontsize=8)
    axs[1].hist(r["b"], bins=40, color=BLUE, alpha=0.75)
    axs[1].axvline(r["bstar"], color=RED, ls="--", lw=1, label="$b^*$")
    axs[1].set_xlabel("James-Stein factor $(1-n/\\sum Z_i^2)_+$")
    axs[1].set_title("(b) 1000 simulations: %.0f%% are exactly 0" % (100 * np.mean(r["b"] == 0)))
    axs[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S6", out)


def fig_7_S7(out=None):
    """Figure 7.S7: Exercise 8, radii of the three balls."""
    res = ex8()
    fig, ax = common.plt.subplots(figsize=(5.8, 3.4))
    bins = np.linspace(4, 13, 61)
    for k, col, lab in (("chi2", GREY, "$\\chi^2$"), ("baraud0.5", BLUE, "Baraud, $\\gamma=0.5$"), ("pivotal", RED, "pivotal")):
        cov, mr, rad = res[k]
        ax.hist(rad, bins=bins, color=col, alpha=0.6, label="%s: coverage %.3f, mean %.2f" % (lab, cov, mr))
    ax.set_xlabel("radius")
    ax.set_title(r"Exercise 8: $\theta_i=1/i$, $n=100$, $\sigma_n=1$, 1000 data sets")
    ax.legend(frameon=False, fontsize=8)
    savefig(fig, CH, "fig7-S7", out)


def block_js_study(m=1.0, c=1.0, sigma=1.0, ns=(100, 1000, 10000, 100000, 1000000), reps=20, seed=5):
    """Risk of blockwise James-Stein (no knowledge of m, c), of Pinsker's linear minimax estimator and of a
    single James-Stein estimator, at the least favourable theta of the ellipsoid Theta(m, c):
    theta_j^2 = tau_j^2 (the prior variances of Theorem 7.36 (4)), where Pinsker's risk equals R_n^L."""
    p = os.path.join(CACHE_DIR, "ch07-blockjs-%g-%g-%d.json" % (m, c, reps))
    if os.path.exists(p):
        with open(p) as f:
            return json.load(f)
    rng = np.random.default_rng(seed)
    out = []
    for n in ns:
        J = n
        a = sobolev_a(J, m)
        sn = sigma / math.sqrt(n)
        mu, w, RL, tau2 = pinsker_linear(a, sn, c)
        tau2 = np.where(np.isfinite(tau2), tau2, 0.0)
        th = np.sqrt(tau2)
        th[0] = 0.0                       # a_1 = 0: the constant coefficient is unconstrained; take it 0
        th *= c / math.sqrt(np.sum((a * th) ** 2))
        blocks, last = clz_blocks(n)
        risk_p = float(np.sum((1 - w) ** 2 * th ** 2 + w ** 2 * sn ** 2))
        lb, lj = [], []
        for _ in range(reps):
            z = th + sn * rng.standard_normal(J)
            lb.append(np.sum((block_js(z, sn, blocks, last) - th) ** 2))
            lj.append(np.sum((js_plus(z, sn) - th) ** 2))
        out.append({"n": n, "block": float(np.mean(lb)), "pinsker_at_theta": risk_p, "pinsker_minimax": RL,
                    "js": float(np.mean(lj))})
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(p, "w") as f:
        json.dump(out, f)
    return out


def fig_7_S8(out=None):
    """Figure 7.S8: adaptive estimation with blockwise James-Stein (Theorem 7.50)."""
    fig, axs = common.plt.subplots(1, 2, figsize=(9.2, 3.4))
    for ax, m in zip(axs, (1.0, 2.0)):
        res = block_js_study(m=m, c=10.0)
        ns = [r["n"] for r in res]
        RL = np.array([r["pinsker_minimax"] for r in res])
        ax.semilogx(ns, np.array([r["block"] for r in res]) / RL, "o-", color=RED, ms=3, label="block James-Stein (no $m$, $c$)")
        ax.semilogx(ns, np.array([r["pinsker_at_theta"] for r in res]) / RL, "s--", color=BLUE, ms=3, label="Pinsker estimator (knows $m$, $c$)")
        ax.semilogx(ns, np.array([r["js"] for r in res]) / RL, "^-", color=GREEN, ms=3, lw=1, label="one James-Stein")
        ax.axhline(1, color=GREY, ls=":", lw=1)
        ax.set_xlabel("$n$")
        ax.set_yscale("log")
        ax.set_title("(%s) $m=%g$, $c=10$, $\\sigma=1$" % ("a" if m == 1 else "b", m))
    axs[0].set_ylabel(r"risk / minimax linear risk $R_n^L$")
    axs[0].legend(frameon=False, fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S8", out)


# =========================================================================== data for the demos
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    n = 100
    d = {"n": n, "alpha": 0.05, "gammas": [0.05, 0.15, 0.5, 0.9],
         "kappa": {("%g" % g): [round(float(v), 6) for v in baraud_table(n, 0.05, g)] for g in (0.05, 0.15, 0.5, 0.9)},
         "c": {("%g" % g): [round(float(v), 6) for v in baraud_accept_c(n, g)] for g in (0.05, 0.15, 0.5, 0.9)},
         "q_chi": q_upper(n, 0.05)}
    p = os.path.join(DATA_OUT, "ch07-baraud.json")
    with open(p, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", p)


FIGURES = {"7.2": fig_7_2, "7.S1": fig_7_S1, "7.S2": fig_7_S2, "7.S3": fig_7_S3, "7.S4": fig_7_S4,
           "7.S5": fig_7_S5, "7.S6": fig_7_S6, "7.S7": fig_7_S7, "7.S8": fig_7_S8}

if __name__ == "__main__":
    import sys
    if "--json" in sys.argv:
        export_json()
    else:
        run(FIGURES, CH)
        export_json()
        t = table_7_1()
        print("Table 7.1:", {k: (round(v[0], 3), round(v[1], 3)) for k, v in t.items()})
