"""Wasserman (2006), Chapter 1: Introduction.

Companion code for Chapter 1 of L. Wasserman, All of Nonparametric Statistics (Springer, 2006),
pp. 1-11, written from scratch with numpy, scipy and matplotlib, to be read next to the lecture notes
(../ch01-introduction.html):

* Section 1.3, confidence sets for a proportion (Example 1.17): wald_halfwidth, hoeffding_eps,
  coverage_exact and expected_length (exact sums over the Binomial law), inf_coverage (the worst
  coverage over a grid of p), n_delta (the sample size after which the coverage stays within delta of
  the nominal level: finite for every p, unbounded over p).
* Section 1.4, inequalities: tail_bounds_binomial (Markov, Chebyshev, Hoeffding (1.24), Bernstein (1.29)
  and its moment version (1.30) against the exact Binomial tail), gauss_tail_bounds (Mill's
  inequalities (1.25)-(1.27) and the Chernoff bound), berry_esseen_distance (the exact Kolmogorov
  distance of a standardised Binomial or Gamma sum from the Normal, for the Berry-Esseen bound (1.28)),
  bernstein_halfwidth and hoeffding_halfwidth (finite-sample intervals for a bounded mean).
* Exercise 1.5, the mean under contamination: three_point_coverage computes exactly the coverage of the
  interval Xbar +- z se, of Hoeffding's interval and of Bernstein's interval when the data come from
  G = (1 - eps) Bernoulli(q) + eps delta_a.

Figures. The chapter has no figures (only Table 1.1, a table of notation), so nothing is skipped. Five
supplementary figures illustrate the gaps filled in the notes and the exercises:
  1.S1 Exercise 1.2: coverage and length of the Wald and Hoeffding intervals for p = 0.2;
  1.S2 pointwise against uniform coverage: the Wald coverage as a function of p, and n(delta);
  1.S3 the tail inequalities of Section 1.4 against exact tails;
  1.S4 the Berry-Esseen bound (1.28) against the exact distance;
  1.S5 Exercise 1.5: the plug-in interval under contamination, and Bernstein against Hoeffding.
Run `python3 ch01_introduction.py --list`, `python3 ch01_introduction.py` (all five figures, well under
a minute on one CPU thread) or `python3 ch01_introduction.py --fig 1.S2`. Files go to ../img/ch01/;
the curves the browser demonstrations show are written to ../data/ch01-*.json by export_json().
"""
import json
import math
import os

import numpy as np
from scipy import stats
from scipy.special import gammaln

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

CH = 1
DATA_OUT = os.path.normpath(os.path.join(common.HERE, "..", "data"))
plt = common.plt


# --------------------------------------------------------------------------- Example 1.17
def z_alpha(alpha):
    """z_{alpha/2} = Phi^{-1}(1 - alpha/2)."""
    return stats.norm.ppf(1 - alpha / 2)


def hoeffding_eps(n, alpha):
    """Half-width of the finite-sample interval (1.19): sqrt(log(2/alpha) / (2n))."""
    return np.sqrt(np.log(2 / alpha) / (2 * np.asarray(n, float)))


def wald_halfwidth(k, n, alpha):
    """Half-width of the Wald interval (1.18) when k successes are seen in n trials."""
    ph = np.asarray(k, float) / n
    return z_alpha(alpha) * np.sqrt(ph * (1 - ph) / n)


def _pmf(n, p):
    return stats.binom.pmf(np.arange(n + 1), n, p)


def covers(method, k, n, p, alpha):
    """Does the interval computed from k successes contain p? (closed intervals)"""
    k = np.asarray(k)
    h = wald_halfwidth(k, n, alpha) if method == "wald" else hoeffding_eps(n, alpha) + 0 * k
    return np.abs(k / n - p) <= h + 1e-13


def coverage_exact(n, p, alpha, method):
    """P_p(p in C_n), summed over the Binomial(n, p) law."""
    k = np.arange(n + 1)
    return float(np.sum(_pmf(n, p) * covers(method, k, n, p, alpha)))


def expected_length(n, p, alpha, method):
    """E_p(length of C_n) with the interval truncated to [0, 1]."""
    k = np.arange(n + 1)
    ph = k / n
    h = wald_halfwidth(k, n, alpha) if method == "wald" else hoeffding_eps(n, alpha)
    L = np.minimum(1, ph + h) - np.maximum(0, ph - h)
    return float(np.sum(_pmf(n, p) * L))


P_GRID = np.concatenate([np.linspace(0.001, 0.009, 9), np.linspace(0.01, 0.99, 99), np.linspace(0.991, 0.999, 9)])


def inf_coverage(n, alpha, method, grid=P_GRID):
    """min over the p grid of the exact coverage, and the p where it is attained."""
    c = np.array([coverage_exact(n, p, alpha, method) for p in grid])
    i = int(np.argmin(c))
    return float(c[i]), float(grid[i])


def n_delta(p, alpha=0.05, delta=0.01, nmax=3000, method="wald"):
    """Smallest N such that coverage(n) >= 1 - alpha - delta for every N <= n <= nmax."""
    cov = np.array([coverage_exact(n, p, alpha, method) for n in range(1, nmax + 1)])
    bad = np.nonzero(cov < 1 - alpha - delta)[0]
    return 1 if bad.size == 0 else int(bad[-1] + 2)


# --------------------------------------------------------------------------- Section 1.4
def tail_bounds_binomial(n, p, eps):
    """Bounds on P(|Xbar - p| >= eps) for Bernoulli(p) data, and the exact value.

    Returns a dict of arrays (one entry per eps). Chebyshev: p(1-p)/(n eps^2); Hoeffding (1.24):
    2 exp(-2 n eps^2); Bernstein (1.29) with M = max(p, 1-p), v = n p(1-p); Bernstein (1.30), moment
    version, with the same M and v_i = p(1-p); Markov applied to |Xbar - p|.
    """
    eps = np.atleast_1d(np.asarray(eps, float))
    k = np.arange(n + 1)
    f = _pmf(n, p)
    dev = np.abs(k / n - p)
    exact = np.array([f[dev >= e - 1e-12].sum() for e in eps])
    s2 = p * (1 - p)
    M = max(p, 1 - p)
    t = n * eps
    out = {
        "exact": exact,
        "markov": np.minimum(1, (f * dev).sum() / eps),
        "chebyshev": np.minimum(1, s2 / (n * eps ** 2)),
        "hoeffding": np.minimum(1, 2 * np.exp(-2 * n * eps ** 2)),
        "bernstein": np.minimum(1, 2 * np.exp(-0.5 * t ** 2 / (n * s2 + M * t / 3))),
        "bernstein_moment": np.minimum(1, 2 * np.exp(-0.5 * t ** 2 / (n * s2 + M * t))),
    }
    return out


def gauss_tail_bounds(t):
    """P(Z > t) and the bounds (1.26) lower/upper, (1.27) and the Chernoff bound exp(-t^2/2)."""
    t = np.asarray(t, float)
    phi = stats.norm.pdf(t)
    return {"exact": stats.norm.sf(t), "mills_low": (1 / t - 1 / t ** 3) * phi, "mills_up": phi / t,
            "half_exp": 0.5 * np.exp(-t ** 2 / 2), "chernoff": np.exp(-t ** 2 / 2)}


def rho3_bernoulli(p):
    """E|X - p|^3 for X ~ Bernoulli(p)."""
    return p * (1 - p) * (p ** 2 + (1 - p) ** 2)


RHO3_EXP = 12 / math.e - 2      # E|X - 1|^3 for X ~ Exp(1)


def berry_esseen_distance(n, dist="bernoulli", p=0.2):
    """sup_z |P(Z_n <= z) - Phi(z)| for the standardised mean of n draws, computed exactly."""
    if dist == "bernoulli":
        k = np.arange(n + 1)
        z = (k - n * p) / np.sqrt(n * p * (1 - p))
        F = stats.binom.cdf(k, n, p)
        Fm = F - stats.binom.pmf(k, n, p)
        Ph = stats.norm.cdf(z)
        return float(max(np.max(np.abs(F - Ph)), np.max(np.abs(Fm - Ph))))
    # Exp(1): the sum is Gamma(n, 1); a fine grid plus the location of the maximum
    z = np.linspace(-6, 6, 24001)
    d = np.abs(stats.gamma.cdf(n + np.sqrt(n) * z, n) - stats.norm.cdf(z))
    return float(d.max())


def berry_esseen_bound(n, rho3, sigma, C=33 / 4):
    return C * rho3 / (np.sqrt(n) * sigma ** 3)


def hoeffding_halfwidth(n, R, alpha):
    """Finite-sample half-width for the mean of n variables with range R: R sqrt(log(2/alpha)/(2n))."""
    return R * np.sqrt(np.log(2 / alpha) / (2 * np.asarray(n, float)))


def bernstein_halfwidth(n, M, sigma2, alpha):
    """Half-width from Bernstein (1.29) with |X_i - mu| <= M and V(X_i) <= sigma2.

    Solves 2 exp(-t^2 / (2 (v + M t / 3))) = alpha for t, v = n sigma2, and returns t / n.
    """
    n = np.asarray(n, float)
    L = np.log(2 / alpha)
    t = L * M / 3 + np.sqrt((L * M / 3) ** 2 + 2 * L * n * sigma2)
    return t / n


# --------------------------------------------------------------------------- Exercise 1.5
def three_point_coverage(n, q, eps, a, alpha=0.05, oracle=False):
    """Exact coverage of three intervals for mu = E_G(X), G = (1-eps) Bernoulli(q) + eps delta_a.

    The data take the values 0, 1 and a with probabilities (1-eps)(1-q), (1-eps)q and eps. With j ones
    and k values a, Xbar = (j + k a)/n and S^2 = (j + k a^2)/n - Xbar^2 (divisor n, as in Exercise 1.5).
    Returns dict(mu, wald, hoeff, bern, p_clean): coverage of Xbar +- z S/sqrt(n), of Hoeffding's interval
    with range B = max(1, a), of Bernstein's interval with M = B and sigma^2 <= B^2/4 (or the true
    variance when oracle=True), and the probability that no value a is drawn.
    """
    z = z_alpha(alpha)
    B = max(1.0, a)
    mu = (1 - eps) * q + eps * a
    var = (1 - eps) * q + eps * a * a - mu * mu
    p0, p1, p2 = (1 - eps) * (1 - q), (1 - eps) * q, eps
    j = np.arange(n + 1)[:, None]
    k = np.arange(n + 1)[None, :]
    ok = j + k <= n
    jj, kk = np.where(ok, j, 0), np.where(ok, k, 0)
    with np.errstate(divide="ignore", invalid="ignore"):
        lp = (gammaln(n + 1) - gammaln(jj + 1) - gammaln(kk + 1) - gammaln(n - jj - kk + 1)
              + (jj * np.log(p1) if p1 > 0 else np.where(jj > 0, -np.inf, 0))
              + (kk * np.log(p2) if p2 > 0 else np.where(kk > 0, -np.inf, 0))
              + ((n - jj - kk) * np.log(p0) if p0 > 0 else np.where(n - jj - kk > 0, -np.inf, 0)))
    w = np.where(ok, np.exp(lp), 0.0)
    xb = (jj + kk * a) / n
    s2 = np.maximum((jj + kk * a * a) / n - xb ** 2, 0)
    dev = np.abs(xb - mu)
    hw = hoeffding_halfwidth(n, B, alpha)
    bw = bernstein_halfwidth(n, B, var if oracle else B * B / 4, alpha)
    return {"mu": mu, "var": var,
            "wald": float((w * (dev <= z * np.sqrt(s2 / n) + 1e-12)).sum()),
            "hoeff": float((w * (dev <= hw + 1e-12)).sum()),
            "bern": float((w * (dev <= bw + 1e-12)).sum()),
            "p_clean": float((1 - eps) ** n), "hw": float(hw), "bw": float(bw)}


# --------------------------------------------------------------------------- figures
def fig_1_s1(out=None):
    """Exercise 1.2: coverage and expected length of (1.18) and (1.19), p = 0.2, alpha = 0.05."""
    ns = np.unique(np.round(np.logspace(0, 3.3, 260)).astype(int))
    cw = [coverage_exact(n, 0.2, 0.05, "wald") for n in ns]
    ch = [coverage_exact(n, 0.2, 0.05, "hoeff") for n in ns]
    lw = [expected_length(n, 0.2, 0.05, "wald") for n in ns]
    lh = [2 * hoeffding_eps(n, 0.05) for n in ns]
    fig, ax = common.panel_grid(1, 2, size=(3.9, 2.9))
    a = ax[0, 0]
    a.plot(ns, cw, color=ORANGE, lw=1.1, label="Wald (1.18)")
    a.plot(ns, ch, color=BLUE, label="Hoeffding (1.19)")
    a.axhline(0.95, color="k", ls="--", lw=0.8)
    a.axhspan(0.94, 0.96, color=GREY, alpha=0.15, lw=0)
    a.set_xscale("log"); a.set_ylim(0.5, 1.01); a.set_xlabel("n"); a.set_ylabel("exact coverage")
    a.legend(loc="lower right"); common.panel_label(a, "a")
    b = ax[0, 1]
    lw = np.array(lw); m = lw > 0
    b.plot(ns[m], np.array(lh)[m] / lw[m], color=PURPLE)
    b.axhline(np.sqrt(np.log(40) / 2) / (z_alpha(0.05) * 0.4), color=GREY, ls=":", lw=1)
    b.set_xscale("log"); b.set_xlabel("n"); b.set_ylabel("length ratio Hoeffding / Wald"); b.set_ylim(0.8, 3)
    common.panel_label(b, "b")
    return savefig(fig, CH, "fig1-S1", out)


def fig_1_s2(out=None):
    """Pointwise against uniform: the Wald coverage as a function of p, and n(delta) against p."""
    ps = np.linspace(0.001, 0.999, 999)
    fig, ax = common.panel_grid(1, 2, size=(3.9, 2.9))
    a = ax[0, 0]
    for n, c in ((20, ORANGE), (100, MAGENTA), (1000, BLUE)):
        a.plot(ps, [coverage_exact(n, p, 0.05, "wald") for p in ps], color=c, lw=0.8, label="n = %d" % n)
    a.axhline(0.95, color="k", ls="--", lw=0.8)
    a.set_xlabel("p"); a.set_ylabel("exact coverage of (1.18)"); a.set_ylim(0, 1.02); a.legend(loc="lower center")
    common.panel_label(a, "a", "upper right")
    b = ax[0, 1]
    pp, nd = n_delta_curve()
    b.plot(pp, nd, "o-", color=MAGENTA, ms=3)
    b.axhline(3000, color=GREY, ls=":", lw=1, label="search limit 3000")
    b.set_xscale("log"); b.set_yscale("log"); b.set_xlabel("p"); b.set_ylabel(r"$n(\delta)$, $\delta=0.01$")
    b.legend(loc="upper right"); common.panel_label(b, "b", "lower left")
    return savefig(fig, CH, "fig1-S2", out)


ND_P = np.array([0.01, 0.015, 0.02, 0.03, 0.05, 0.075, 0.1, 0.15, 0.2, 0.3, 0.5])


def n_delta_curve(nmax=3000):
    cache = os.path.join(common.HERE, "cache", "ch01_ndelta.json")
    if os.path.exists(cache):
        d = json.load(open(cache))
        return np.array(d["p"]), np.array(d["n"])
    nd = [n_delta(p, nmax=nmax) for p in ND_P]
    os.makedirs(os.path.dirname(cache), exist_ok=True)
    json.dump({"p": ND_P.tolist(), "n": nd}, open(cache, "w"))
    return ND_P, np.array(nd)


def fig_1_s3(out=None):
    """The inequalities of Section 1.4 against exact tails (Binomial n = 100, and the Normal)."""
    fig, ax = common.panel_grid(1, 3, size=(3.0, 2.8))
    eps = np.linspace(0.01, 0.4, 200)
    style = [("markov", "Markov", GREY, ":"), ("chebyshev", "Chebyshev", GREEN, "--"),
             ("hoeffding", "Hoeffding (1.24)", BLUE, "-"), ("bernstein", "Bernstein (1.29)", RED, "-"),
             ("bernstein_moment", "Bernstein (1.30)", ORANGE, "--")]
    for c, p in enumerate((0.5, 0.05)):
        a = ax[0, c]
        tb = tail_bounds_binomial(100, p, eps)
        a.semilogy(eps, tb["exact"], color="k", lw=2, label="exact")
        for key, lab, col, ls in style:
            a.semilogy(eps, tb[key], color=col, ls=ls, lw=1.2, label=lab)
        a.set_ylim(1e-12, 2); a.set_xlabel(r"$\epsilon$")
        if c == 0:
            a.set_ylabel(r"$P(|\bar X_n-p|\geq\epsilon)$")
        a.set_title(r"Binomial mean, $n=100$, $p=%g$" % p)
        common.panel_label(a, "ab"[c], "lower left")
    ax[0, 0].legend(loc="upper right", fontsize=7)
    a = ax[0, 2]
    t = np.linspace(0.3, 6, 300)
    g = gauss_tail_bounds(t)
    a.semilogy(t, g["exact"], color="k", lw=2, label="P(Z > t)")
    a.semilogy(t, g["mills_up"], color=BLUE, label=r"$\phi(t)/t$")
    a.semilogy(t[t > 1], g["mills_low"][t > 1], color=BLUE, ls="--", label=r"$(1/t-1/t^3)\phi(t)$")
    a.semilogy(t, g["half_exp"], color=RED, label=r"$\frac{1}{2}e^{-t^2/2}$ (1.27)")
    a.semilogy(t, g["chernoff"], color=GREY, ls=":", label=r"$e^{-t^2/2}$")
    a.set_ylim(1e-10, 2); a.set_xlabel("t"); a.set_title("Normal tail, Mill's inequality")
    a.legend(loc="lower left", fontsize=7); common.panel_label(a, "c", "upper right")
    return savefig(fig, CH, "fig1-S3", out)


def fig_1_s4(out=None):
    """The Berry-Esseen bound (1.28) against the exact Kolmogorov distance."""
    ns = np.unique(np.round(np.logspace(0.5, 3.5, 40)).astype(int))
    fig, ax = common.panel_grid(1, 2, size=(3.9, 2.9))
    for c, (dist, lab) in enumerate((("bernoulli", "Bernoulli(0.2)"), ("exp", "Exponential(1)"))):
        a = ax[0, c]
        d = [berry_esseen_distance(n, dist) for n in ns]
        if dist == "bernoulli":
            r3, s = rho3_bernoulli(0.2), math.sqrt(0.16)
        else:
            r3, s = RHO3_EXP, 1.0
        a.loglog(ns, d, "o", color="k", ms=3, label="exact distance")
        a.loglog(ns, berry_esseen_bound(ns, r3, s), color=RED, label="(1.28), C = 33/4")
        a.loglog(ns, berry_esseen_bound(ns, r3, s, 0.4748), color=BLUE, label="C = 0.4748")
        a.set_xlabel("n"); a.set_title(lab); common.panel_label(a, "ab"[c], "lower left")
    ax[0, 0].set_ylabel(r"$\sup_z|P(Z_n\leq z)-\Phi(z)|$")
    ax[0, 0].legend(loc="upper right", fontsize=8)
    return savefig(fig, CH, "fig1-S4", out)


def seq_contam(n):
    """The sequence of Exercise 1.5(b): eps_n = n^(-3/2), a_n = n^2."""
    return n ** -1.5, float(n) ** 2


def fig_1_s5(out=None):
    """Exercise 1.5: the plug-in interval under contamination; Bernstein against Hoeffding."""
    ns = np.unique(np.round(np.logspace(1, 2.6, 25)).astype(int))
    fixed = [three_point_coverage(n, 0.3, 0.0, 1.0)["wald"] for n in ns]
    seq = [three_point_coverage(n, 0.3, *seq_contam(n)) for n in ns]
    fig, ax = common.panel_grid(1, 2, size=(3.9, 2.9))
    a = ax[0, 0]
    a.plot(ns, fixed, "o-", ms=3, color=BLUE, label="F = Bernoulli(0.3)")
    a.plot(ns, [s["wald"] for s in seq], "s-", ms=3, color=RED, label=r"$G_n$, $\epsilon_n=n^{-3/2}$, $a_n=n^2$")
    a.plot(ns, [1 - s["p_clean"] for s in seq], color=GREY, ls=":", label=r"$P$(some $X_i=a_n$)")
    a.plot(ns, [s["bern"] for s in seq], "^-", ms=3, color=GREEN, label=r"Bernstein, $G_n$")
    a.axhline(0.95, color="k", ls="--", lw=0.8)
    a.set_xscale("log"); a.set_xlabel("n"); a.set_ylabel("exact coverage"); a.set_ylim(0, 1.03)
    a.legend(loc="center left", fontsize=7.5); common.panel_label(a, "a", "lower left")
    b = ax[0, 1]
    n2 = np.logspace(1, 4, 100)
    b.loglog(n2, hoeffding_halfwidth(n2, 2.0, 0.05), color=BLUE, label="Hoeffding, range 2B")
    b.loglog(n2, bernstein_halfwidth(n2, 2.0, 1.0, 0.05), color=RED, label=r"Bernstein, $\sigma^2\leq B^2$")
    b.loglog(n2, bernstein_halfwidth(n2, 2.0, 0.05, 0.05), color=RED, ls="--", label=r"Bernstein, $\sigma^2\leq0.05$")
    b.loglog(n2, z_alpha(0.05) * np.sqrt(0.05 / n2), color=GREY, ls=":", label=r"$z_{\alpha/2}\sigma/\sqrt{n}$, $\sigma^2=0.05$")
    b.set_xlabel("n"); b.set_ylabel("half-width, B = 1"); b.legend(loc="lower left", fontsize=7.5)
    common.panel_label(b, "b", "upper right")
    return savefig(fig, CH, "fig1-S5", out)


# --------------------------------------------------------------------------- JSON for the demos
def export_json():
    """Reference curves for the coverage demo: n(delta) against p."""
    pp, nd = n_delta_curve()
    os.makedirs(DATA_OUT, exist_ok=True)
    with open(os.path.join(DATA_OUT, "ch01-ndelta.json"), "w") as f:
        json.dump({"alpha": 0.05, "delta": 0.01, "nmax": 3000, "p": pp.tolist(), "n": [int(x) for x in nd]},
                  f, separators=(",", ":"))


def exercise_2_table(alpha=0.05, p=0.2):
    """Coverage and length of both intervals at a few n, and the n after which Wald stays within 1%."""
    rows = []
    for n in (10, 20, 50, 100, 200, 500, 1000):
        rows.append((n, coverage_exact(n, p, alpha, "wald"), coverage_exact(n, p, alpha, "hoeff"),
                     expected_length(n, p, alpha, "wald"), 2 * float(hoeffding_eps(n, alpha))))
    return rows, n_delta(p, alpha, 0.01, 3000)


FIGURES = {"1.S1": fig_1_s1, "1.S2": fig_1_s2, "1.S3": fig_1_s3, "1.S4": fig_1_s4, "1.S5": fig_1_s5}

if __name__ == "__main__":
    import sys
    common.run(FIGURES, CH)
    if len(sys.argv) == 1:
        export_json()
        rows, nd = exercise_2_table()
        for r in rows:
            print("n=%5d  cov wald %.4f  hoeff %.4f  len wald %.4f  hoeff %.4f" % r)
        print("Wald within 1%% of 0.95 for all n >= %d (up to 3000)" % nd)
