"""Wasserman (2004), Chapter 14: Multivariate Models.

Computations and figures for Chapter 14 of L. Wasserman, All of Statistics: A Concise Course in
Statistical Inference (Springer, 2004), pp. 231-238, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch14-multivariate-models.html).

The chapter is short and has no figures of its own. The functions below implement every method it
describes, and the figures are supplementary (numbered 14.S1-14.S6): they illustrate the results
proved in the notes and answer the computer exercises.

* Linear algebra and Section 14.1, random vectors: sqrtm_sym (the symmetric square root of a
  positive definite matrix), sample_mean_cov (the sample mean and the matrix S of (14.4)),
  plug_in_cov (divisor n), and the linear-map rule of Theorem 14.1 (linear_map_moments).
* Section 14.2, the correlation: corr (the sample correlation (14.6), corrected as in the notes),
  fisher_z and fisher_z_inv (Fisher's transformation and its inverse), fisher_ci (the interval of
  the book), wald_ci (the delta-method interval r +- z (1 - r^2) / sqrt(n)), boot_percentile_ci (the
  bootstrap percentile interval), avar_r (the asymptotic variance of the sample correlation from
  fourth moments: the delta method of the notes, for any distribution with finite fourth moments),
  r_density (the exact density of r for normal data) and z_moments (the exact mean and variance of
  Fisher's z, by integrating r_density after the substitution r = tanh z).
* Section 14.3, the multivariate normal: mvn_draw (Exercise 4: by the Cholesky factor or by the
  symmetric square root), mvn_loglik and mvn_loglik_suff (the log-likelihood directly, and through
  the sufficient statistics as in Theorem 14.3, corrected), mvn_mle ((14.8)), conditional_normal
  (the conditional law of X given a linear combination a^T X = c), hotelling_t2 (Hotelling's T^2
  test of H0: mu = mu0, with its exact F distribution), hotelling_power (exact power, from the
  noncentral F distribution), and t_tests (separate t-tests, unadjusted and with Bonferroni's
  correction), wishart_moments.
* Section 14.4, the multinomial: multinomial_draw (Exercise 3: n categorical draws per observation,
  counted), multinomial_mle, multinomial_cov (the matrix Sigma of Theorem 14.4), multinomial_fisher
  (Exercise 2: the Fisher information in the k - 1 free parameters, and its inverse) and pearson_chi2.
* The browser demonstrations: corr_demo, hotelling_demo and cond_demo repeat, number for number,
  what the three demonstration pages compute. They draw from the seeded generator of the pages
  (mulberry32, as DK.rng in courses/demo-kit.js), reproduced here by js_uniforms; normal pairs are
  made from two uniforms by the Box-Muller transform, (u1, u2) -> sqrt(-2 log(1 - u1)) (cos, sin)
  of 2 pi u2, and the bootstrap index is floor(n u).

Figures (all supplementary; the chapter has none of its own, so nothing is skipped):
* 14.S1 Exercise 5: one sample of 100 vectors from N(mu, Sigma), with the true and estimated 95%
  ellipses and regression line, and the bootstrap distribution of the sample correlation with the
  Fisher and bootstrap intervals.
* 14.S2 Exercise 6: coverage of the Fisher, bootstrap and delta-method intervals over 1000 repeated
  samples, for normal and heavy-tailed (t) data, against n.
* 14.S3 The sampling distribution of r: its exact density, Fisher's z against its normal
  approximation, and the exact standard deviation of z compared with 1/sqrt(n - 3) and 1/sqrt(n).
* 14.S4 Hotelling's T^2 against separate t-tests: acceptance regions and power.
* 14.S5 The multinomial: the sampling distribution of the MLE for k = 3 and its normal
  approximation (Theorem 14.6), and Pearson's statistic against chi-square with k - 1 degrees of freedom.
* 14.S6 The Wishart side of Section 14.3: the null distribution of T^2 against the scaled F law
  and the chi-square approximation, and the spread of the sample eigenvalues.

Run `python3 ch14_multivariate_models.py --list`, `python3 ch14_multivariate_models.py` (all six
figures, under a minute on one CPU thread with the cache) or `python3 ch14_multivariate_models.py
--fig 14.S2`. Files go to ../img/ch14/; slow simulations are cached in cache/.
The demonstrations compute everything in the browser and need no data files.
"""
import math
import os
import pickle
import warnings

import numpy as np
from scipy import integrate, special, stats

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

CH = 14
M32 = 0xFFFFFFFF
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")

# two-sided normal critical values z_{alpha/2}, used by the pages as constants
Z_CRIT = {0.1: 1.6448536269514722, 0.05: 1.959963984540054, 0.01: 2.5758293035489004}

# Exercise 5 of the book
EX5_MU = np.array([3.0, 8.0])
EX5_SIGMA = np.array([[1.0, 1.0], [1.0, 2.0]])


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


class JSRandom:
    """The seeded uniforms of the browser demos (DK.rng(seed).u() in courses/demo-kit.js, mulberry32)."""

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

    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 js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed).u(), vectorised (mulberry32 adds a
    constant to its state 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 box_muller(u1, u2):
    """The pages' normal pair from two uniforms: radius from 1 - u1 (never 0), angle 2 pi u2."""
    r = np.sqrt(-2.0 * np.log(1.0 - u1))
    th = 2.0 * np.pi * u2
    return r * np.cos(th), r * np.sin(th)


# =========================================================================== linear algebra, 14.1
def sqrtm_sym(A):
    """The symmetric positive (semi)definite square root A^{1/2} = V diag(sqrt(lambda)) V^T."""
    lam, V = np.linalg.eigh(A)
    if lam.min() < -1e-12 * max(1.0, abs(lam).max()):
        raise ValueError("matrix is not positive semidefinite")
    return (V * np.sqrt(np.clip(lam, 0, None))) @ V.T


def sample_mean_cov(X):
    """Sample mean and the sample covariance matrix S of (14.4) (divisor n - 1); rows of X are the
    n observations."""
    X = np.asarray(X, float)
    n = X.shape[0]
    xbar = X.mean(0)
    D = X - xbar
    return xbar, D.T @ D / (n - 1)


def plug_in_cov(X):
    """The plug-in (and maximum likelihood) covariance, divisor n."""
    X = np.asarray(X, float)
    D = X - X.mean(0)
    return D.T @ D / X.shape[0]


def linear_map_moments(A, mu, Sigma):
    """Theorem 14.1: E(AX) = A mu and V(AX) = A Sigma A^T."""
    A = np.atleast_2d(A)
    return A @ mu, A @ Sigma @ A.T


# =========================================================================== 14.2 the correlation
def corr(x, y):
    """The sample correlation (14.6) with the factor 1/(n - 1) restored in the numerator (equivalently,
    divisor n throughout): centred cross-products over the root of the centred sums of squares."""
    x = np.asarray(x, float)
    y = np.asarray(y, float)
    dx, dy = x - x.mean(), y - y.mean()
    return float((dx @ dy) / math.sqrt((dx @ dx) * (dy @ dy)))


def fisher_z(r):
    """f(r) = (1/2) log((1 + r)/(1 - r)) = artanh r."""
    return np.arctanh(r)


def fisher_z_inv(z):
    """f^{-1}(z) = (e^{2z} - 1)/(e^{2z} + 1) = tanh z."""
    return np.tanh(z)


def fisher_ci(r, n, alpha=0.05):
    """The book's interval: tanh(artanh r -+ z_{alpha/2}/sqrt(n - 3))."""
    z = Z_CRIT.get(alpha, stats.norm.isf(alpha / 2))
    t = np.arctanh(r)
    h = z / math.sqrt(n - 3)
    return np.tanh(t - h), np.tanh(t + h)


def wald_ci(r, n, alpha=0.05):
    """The delta-method interval r -+ z_{alpha/2} (1 - r^2)/sqrt(n) (normal-theory standard error)."""
    z = Z_CRIT.get(alpha, stats.norm.isf(alpha / 2))
    h = z * (1 - r * r) / math.sqrt(n)
    return r - h, r + h


def quantile7(a_sorted, q):
    """Linear-interpolation quantile of a sorted sample (numpy's default, R's type 7)."""
    B = len(a_sorted)
    h = (B - 1) * q
    lo = int(math.floor(h))
    hi = min(lo + 1, B - 1)
    return a_sorted[lo] + (h - lo) * (a_sorted[hi] - a_sorted[lo])


def boot_corr(x, y, B, rng):
    """B bootstrap replicates of the sample correlation (rows resampled with replacement)."""
    n = len(x)
    idx = rng.integers(0, n, size=(B, n))
    return _corr_rows(x[idx], y[idx])


def _corr_rows(xs, ys):
    dx = xs - xs.mean(1, keepdims=True)
    dy = ys - ys.mean(1, keepdims=True)
    sxx = (dx * dx).sum(1)
    syy = (dy * dy).sum(1)
    sxy = (dx * dy).sum(1)
    den = np.sqrt(sxx * syy)
    out = np.zeros(len(sxx))
    ok = den > 0
    out[ok] = sxy[ok] / den[ok]
    return out


def boot_percentile_ci(reps, alpha=0.05):
    s = np.sort(reps)
    return quantile7(s, alpha / 2), quantile7(s, 1 - alpha / 2)


def fourth_moments_std(X):
    """Standardised mixed moments mu_ab = E[U^a V^b] (U, V the standardised coordinates) estimated
    from a sample, or a dict of exact values passed through."""
    X = np.asarray(X, float)
    U = (X - X.mean(0)) / X.std(0)
    u, v = U[:, 0], U[:, 1]
    return {"40": np.mean(u ** 4), "04": np.mean(v ** 4), "22": np.mean(u * u * v * v),
            "31": np.mean(u ** 3 * v), "13": np.mean(u * v ** 3), "rho": np.mean(u * v)}


def avar_r(m):
    """Asymptotic variance of sqrt(n)(r - rho), from the influence function
    psi = UV - (rho/2)(U^2 + V^2) of the notes: E psi^2."""
    rho = m["rho"]
    return m["22"] - rho * (m["31"] + m["13"]) + rho * rho / 4 * (m["40"] + 2 * m["22"] + m["04"])


def normal_fourth_moments(rho, kappa=0.0):
    """Exact standardised fourth moments of an elliptical law with correlation rho and kurtosis
    parameter kappa (kappa = 0: the normal; t with nu degrees of freedom: kappa = 2/(nu - 4))."""
    c = 1 + kappa
    return {"40": 3 * c, "04": 3 * c, "22": (1 + 2 * rho * rho) * c, "31": 3 * rho * c, "13": 3 * rho * c, "rho": rho}


def _hyp2f1_half(c, x, tol=1e-16, maxit=200000):
    """2F1(1/2, 1/2; c; x) by its series, 0 <= x < 1 (the pages use the same series)."""
    s, term, k = 1.0, 1.0, 0
    while k < maxit:
        term *= (0.5 + k) * (0.5 + k) / ((c + k) * (k + 1.0)) * x
        s += term
        k += 1
        if abs(term) < tol * abs(s):
            break
    return s


def r_log_const(n):
    """log of (n - 2) Gamma(n - 1) / (sqrt(2 pi) Gamma(n - 1/2))."""
    return math.log(n - 2) + math.lgamma(n - 1) - 0.5 * math.log(2 * math.pi) - math.lgamma(n - 0.5)


def r_density(r, rho, n):
    """Exact density of the sample correlation of n >= 4 normal pairs with correlation rho
    (Hotelling's 1953 form of Fisher's 1915 result):
    (n-2) Gamma(n-1) (1-rho^2)^{(n-1)/2} (1-r^2)^{(n-4)/2} / (sqrt(2 pi) Gamma(n-1/2) (1-rho r)^{n-3/2})
    * 2F1(1/2, 1/2; n - 1/2; (1 + rho r)/2)."""
    r = np.atleast_1d(np.asarray(r, float))
    lc = r_log_const(n)
    out = np.empty_like(r)
    for i, ri in enumerate(r):
        out[i] = math.exp(lc + 0.5 * (n - 1) * math.log1p(-rho * rho) + 0.5 * (n - 4) * math.log1p(-ri * ri)
                          - (n - 1.5) * math.log1p(-rho * ri)) * _hyp2f1_half(n - 0.5, (1 + rho * ri) / 2)
    return out


def z_density(z, rho, n):
    """Density of Fisher's z = artanh r: f_r(tanh z) sech^2 z, written so that 1 - r^2 = sech^2 z
    is computed without cancellation (the pages integrate the same function)."""
    z = np.atleast_1d(np.asarray(z, float))
    lc = r_log_const(n)
    out = np.empty_like(z)
    for i, zi in enumerate(z):
        lsech2 = -2 * (abs(zi) + math.log1p(math.exp(-2 * abs(zi))) - math.log(2))   # log sech^2 z
        r = math.tanh(zi)
        out[i] = math.exp(lc + 0.5 * (n - 1) * math.log1p(-rho * rho) + 0.5 * (n - 2) * lsech2
                          - (n - 1.5) * math.log1p(-rho * r)) * _hyp2f1_half(n - 0.5, (1 + rho * r) / 2)
    return out


def z_moments(rho, n, h=None):
    """Exact mean and variance of z (and of r) for normal data, by the trapezoid rule in z on
    [artanh(rho) -+ 14/sqrt(n - 3)] (the integrand is smooth and negligible at the ends)."""
    c = math.atanh(rho)
    w = 14.0 / math.sqrt(n - 3) + 0.5
    h = h or min(0.004, w / 2000)
    zz = np.arange(c - w, c + w + h / 2, h)
    f = z_density(zz, rho, n)
    tr = lambda g: h * (g.sum() - 0.5 * (g[0] + g[-1]))
    m0 = tr(f)
    mz = tr(zz * f) / m0
    vz = tr((zz - mz) ** 2 * f) / m0
    rr = np.tanh(zz)
    mr = tr(rr * f) / m0
    vr = tr((rr - mr) ** 2 * f) / m0
    return {"mass": m0, "Ez": mz, "Vz": vz, "Er": mr, "Vr": vr}


# =========================================================================== 14.3 the multivariate normal
def mvn_draw(nsim, mu, Sigma, rng, method="chol"):
    """Exercise 4: nsim draws from N(mu, Sigma) as mu + A Z with A A^T = Sigma and Z ~ N(0, I);
    A is the Cholesky factor or the symmetric square root (Theorem 14.2(1))."""
    mu = np.asarray(mu, float)
    A = np.linalg.cholesky(Sigma) if method == "chol" else sqrtm_sym(Sigma)
    Z = rng.standard_normal((nsim, len(mu)))
    return mu + Z @ A.T


def mvn_js(seed, n, mu, Sigma, start=0):
    """n draws from N(mu, Sigma) in 2-D on the pages' generator (one Box-Muller pair per draw,
    x = mu + L z with L the Cholesky factor)."""
    u = js_uniforms(seed, 2 * n, start)
    z1, z2 = box_muller(u[0::2], u[1::2])
    L = np.linalg.cholesky(Sigma)
    return np.column_stack([mu[0] + L[0, 0] * z1, mu[1] + L[1, 0] * z1 + L[1, 1] * z2])


def mvn_loglik(X, mu, Sigma):
    """sum_i log f(X_i; mu, Sigma), directly."""
    return float(common.gauss_logpdf(X, mu, Sigma).sum())


def mvn_loglik_suff(xbar, S, n, mu, Sigma):
    """The same through the sufficient statistics (Theorem 14.3 as corrected in the notes):
    -nk/2 log 2pi - n/2 log|Sigma| - (n-1)/2 tr(Sigma^{-1} S) - n/2 (xbar - mu)^T Sigma^{-1} (xbar - mu)."""
    k = len(xbar)
    Si = np.linalg.inv(Sigma)
    d = xbar - mu
    return float(-n * k / 2 * math.log(2 * math.pi) - n / 2 * np.linalg.slogdet(Sigma)[1]
                 - (n - 1) / 2 * np.trace(Si @ S) - n / 2 * d @ Si @ d)


def mvn_mle(X):
    """(14.8): mu_hat = xbar, Sigma_hat = (n - 1)/n S."""
    return X.mean(0), plug_in_cov(X)


def conditional_normal(mu, Sigma, a, c):
    """Law of X ~ N(mu, Sigma) given a^T X = c: mean mu + Sigma a (c - a^T mu)/(a^T Sigma a), covariance
    Sigma - Sigma a a^T Sigma/(a^T Sigma a) (singular: the conditional law lives on the line a^T x = c)."""
    a = np.asarray(a, float)
    Sa = Sigma @ a
    v = a @ Sa
    return mu + Sa * (c - a @ mu) / v, Sigma - np.outer(Sa, Sa) / v


def hotelling_t2(X, mu0):
    """Hotelling's T^2 = n (xbar - mu0)^T S^{-1} (xbar - mu0), F = (n - k)/(k (n - 1)) T^2 ~ F(k, n - k)
    under H0, and the p-value."""
    X = np.asarray(X, float)
    n, k = X.shape
    xbar, S = sample_mean_cov(X)
    d = xbar - mu0
    T2 = float(n * d @ np.linalg.solve(S, d))
    F = (n - k) / (k * (n - 1)) * T2
    return T2, F, float(stats.f.sf(F, k, n - k))


def hotelling_crit(n, k, alpha):
    """Critical value of T^2: k (n - 1)/(n - k) F_{k, n-k, 1-alpha}."""
    return k * (n - 1) / (n - k) * stats.f.isf(alpha, k, n - k)


def hotelling_power(n, k, delta, Sigma, alpha):
    """Exact power of the level-alpha T^2 test at mu - mu0 = delta: P(F' > F_crit) with F' noncentral
    F(k, n - k) of noncentrality n delta^T Sigma^{-1} delta."""
    lam = n * float(delta @ np.linalg.solve(Sigma, delta))
    if lam <= 0:
        return float(alpha)
    with warnings.catch_warnings():   # scipy's noncentral F warns (harmlessly) for very large lam
        warnings.simplefilter("ignore", RuntimeWarning)
        return float(stats.ncf.sf(stats.f.isf(alpha, k, n - k), k, n - k, lam))


def t_tests(X, mu0, alpha, bonferroni=True):
    """Separate two-sided t-tests of each coordinate; reject H0: mu = mu0 if any rejects, at level
    alpha/k each (Bonferroni) or alpha each."""
    X = np.asarray(X, float)
    n, k = X.shape
    xbar, S = sample_mean_cov(X)
    t = np.sqrt(n) * (xbar - mu0) / np.sqrt(np.diag(S))
    a = alpha / k if bonferroni else alpha
    return bool(np.any(np.abs(t) > stats.t.isf(a / 2, n - 1))), t


def wishart_moments(Sigma, m):
    """E W = m Sigma and Var(W_ij) = m (sigma_ij^2 + sigma_ii sigma_jj) for W ~ Wishart_k(m, Sigma)."""
    d = np.diag(Sigma)
    return m * Sigma, m * (Sigma ** 2 + np.outer(d, d))


# =========================================================================== 14.4 the multinomial
def multinomial_draw(nsim, n, p, rng):
    """Exercise 3: nsim draws from Multinomial(n, p): n categorical draws per observation by inverting
    the cumulative probabilities, then counted."""
    p = np.asarray(p, float)
    k = len(p)
    cp = np.cumsum(p)
    cp[-1] = 1.0
    U = rng.random((nsim, n))
    cat = np.searchsorted(cp, U, side="right")
    cat = np.minimum(cat, k - 1)
    out = np.zeros((nsim, k), dtype=int)
    for j in range(k):
        out[:, j] = (cat == j).sum(1)
    return out


def multinomial_mle(X):
    X = np.asarray(X, float)
    return X / X.sum(-1, keepdims=True)


def multinomial_cov(p):
    """Sigma = diag(p) - p p^T, so V(X) = n Sigma and V(p_hat) = Sigma/n (Theorem 14.4)."""
    p = np.asarray(p, float)
    return np.diag(p) - np.outer(p, p)


def multinomial_fisher(p, n=1):
    """Exercise 2: Fisher information in the free parameters (p_1, ..., p_{k-1}) (p_k = 1 - sum):
    I = n (diag(1/p_j) + 1 1^T / p_k), with inverse (diag(p_-) - p_- p_-^T)/n."""
    p = np.asarray(p, float)
    q = p[:-1]
    I = n * (np.diag(1 / q) + 1 / p[-1])
    return I, (np.diag(q) - np.outer(q, q)) / n


def pearson_chi2(X, n, p):
    X = np.asarray(X, float)
    e = n * np.asarray(p, float)
    return ((X - e) ** 2 / e).sum(-1)


def multinomial_loglik(x, p):
    x = np.asarray(x, float)
    p = np.asarray(p, float)
    m = x > 0
    return float((x[m] * np.log(p[m])).sum()) if np.all(p[m] > 0) else -math.inf


# =========================================================================== the demonstrations
T_NU = {"normal": 0, "t10": 10, "t6": 6}


def corr_demo(n=100, rho=0.7071, dist="normal", R=1000, B=500, alpha=0.05, seed=1, keep_first=True):
    """What the Fisher z demonstration computes. Replication j uses, in order: for each of the n
    observations a Box-Muller pair (z1, z2) and, for t data, nu/2 more uniforms giving a chi-square
    with nu degrees of freedom as -2 sum log(1 - u) (the scale is sqrt(nu/chi2)); then B n uniforms for
    the bootstrap indices floor(n u). The pair is (s z1, s (rho z1 + sqrt(1 - rho^2) z2))."""
    nu = T_NU[dist]
    per_obs = 2 + nu // 2
    per_rep = n * per_obs + B * n
    zc = Z_CRIT[alpha]
    out = {k: np.empty(R) for k in ("r", "fl", "fu", "wl", "wu", "bl", "bu")}
    first = None
    sq = math.sqrt(1 - rho * rho)
    for j in range(R):
        u = js_uniforms(seed, per_rep, j * per_rep)
        ud = u[: n * per_obs].reshape(n, per_obs)
        z1, z2 = box_muller(ud[:, 0], ud[:, 1])
        if nu:
            chi = -2.0 * np.log(1.0 - ud[:, 2:]).sum(1)
            s = np.sqrt(nu / chi)
        else:
            s = 1.0
        x = s * z1
        y = s * (rho * z1 + sq * z2)
        r = corr(x, y)
        out["r"][j] = r
        out["fl"][j], out["fu"][j] = fisher_ci(r, n, alpha)
        out["wl"][j], out["wu"][j] = wald_ci(r, n, alpha)
        if B > 0:
            ub = u[n * per_obs:].reshape(B, n)
            idx = np.floor(ub * n).astype(int)
            reps = _corr_rows(x[idx], y[idx])
            out["bl"][j], out["bu"][j] = boot_percentile_ci(reps, alpha)
        else:
            out["bl"][j] = out["bu"][j] = np.nan
        if j == 0 and keep_first:
            first = np.column_stack([x, y])
    res = dict(out)
    res["z"] = np.arctanh(out["r"])
    for key, (lo, hi) in {"fisher": ("fl", "fu"), "wald": ("wl", "wu"), "boot": ("bl", "bu")}.items():
        hit = (out[lo] < rho) & (rho < out[hi])
        res["cov_" + key] = float(hit.mean())
        res["len_" + key] = float((out[hi] - out[lo]).mean())
        res["hits_" + key] = int(hit.sum())
    res["first"] = first
    return res


def f2_crit(n, alpha):
    """F_{2, n-2, 1-alpha} in closed form: P(F > f) = (1 + 2f/(n - 2))^{-(n - 2)/2}."""
    d2 = n - 2
    return d2 / 2 * (alpha ** (-2.0 / d2) - 1)


def hotelling_demo(n=20, rho=0.5, theta=-45.0, c=0.5, alpha=0.05, R=2000, seed=1, ngrid=41, cmax=None):
    """What the Hotelling demonstration computes (k = 2, unit variances, correlation rho). Replication j
    uses n Box-Muller pairs; x1 = z1, x2 = rho z1 + sqrt(1 - rho^2) z2; the mean is shifted by
    delta = c (cos theta, sin theta) (theta in degrees). Returns the rejection rates of Hotelling's test
    and of the separate t-tests (unadjusted and Bonferroni) at c and along a grid of shifts, and the
    exact power of Hotelling's test."""
    sq = math.sqrt(1 - rho * rho)
    u = js_uniforms(seed, 2 * n * R).reshape(R, n, 2)
    z1, z2 = box_muller(u[:, :, 0], u[:, :, 1])
    x1 = z1
    x2 = rho * z1 + sq * z2
    m1, m2 = x1.mean(1), x2.mean(1)
    d1, d2 = x1 - m1[:, None], x2 - m2[:, None]
    s11 = (d1 * d1).sum(1) / (n - 1)
    s22 = (d2 * d2).sum(1) / (n - 1)
    s12 = (d1 * d2).sum(1) / (n - 1)
    det = s11 * s22 - s12 * s12
    th = math.radians(theta)
    ux, uy = math.cos(th), math.sin(th)
    Fc = f2_crit(n, alpha)
    T2c = 2 * (n - 1) / (n - 2) * Fc
    tc = stats.t.isf(alpha / 2, n - 1)
    tb = stats.t.isf(alpha / 4, n - 1)
    Sig = np.array([[1, rho], [rho, 1]])

    def rates(cc):
        a1, a2 = m1 + cc * ux, m2 + cc * uy
        T2 = n * (s22 * a1 * a1 - 2 * s12 * a1 * a2 + s11 * a2 * a2) / det
        t1 = math.sqrt(n) * a1 / np.sqrt(s11)
        t2 = math.sqrt(n) * a2 / np.sqrt(s22)
        tm = np.maximum(np.abs(t1), np.abs(t2))
        return {"hot": float((T2 > T2c).mean()), "unadj": float((tm > tc).mean()), "bonf": float((tm > tb).mean()),
                "T2": T2, "t1": t1, "t2": t2}

    cmax = cmax or max(1.0, 2.5 * c)
    grid = np.linspace(0, cmax, ngrid)
    curves = {"hot": [], "unadj": [], "bonf": [], "exact": []}
    for g in grid:
        rr = rates(g)
        for key in ("hot", "unadj", "bonf"):
            curves[key].append(rr[key])
        curves["exact"].append(hotelling_power(n, 2, g * np.array([ux, uy]), Sig, alpha))
    now = rates(c)
    return {"rates": {k: now[k] for k in ("hot", "unadj", "bonf")}, "T2": now["T2"], "t1": now["t1"], "t2": now["t2"],
            "exact": hotelling_power(n, 2, c * np.array([ux, uy]), Sig, alpha), "grid": grid,
            "curves": {k: np.array(v) for k, v in curves.items()}, "T2crit": T2c, "tcrit": tc, "tbonf": tb,
            "lam": n * c * c * float(np.array([ux, uy]) @ np.linalg.solve(Sig, np.array([ux, uy])))}


COND_A = {"x1": (1.0, 0.0), "x2": (0.0, 1.0), "sum": (1.0, 1.0), "diff": (1.0, -1.0)}


def strip_moments(mu, Sigma, a, b, c, h):
    """Exact mean and variance of Y = b^T X given |a^T X - c| <= h (truncated normal for W = a^T X,
    plus the conditional regression of Y on W), and the limits as h -> 0."""
    a, b = np.asarray(a, float), np.asarray(b, float)
    mw, vw = a @ mu, a @ Sigma @ a
    my, vy = b @ mu, b @ Sigma @ b
    cyw = b @ Sigma @ a
    beta = cyw / vw
    vyw = vy - cyw * cyw / vw
    sw = math.sqrt(vw)
    al, be = (c - h - mw) / sw, (c + h - mw) / sw
    Z = stats.norm.cdf(be) - stats.norm.cdf(al)
    pa, pb = stats.norm.pdf(al), stats.norm.pdf(be)
    ew = mw + sw * (pa - pb) / Z
    varw = vw * (1 + (al * pa - be * pb) / Z - ((pa - pb) / Z) ** 2)
    return {"mean": my + beta * (ew - mw), "var": vyw + beta * beta * varw, "cmean": my + beta * (c - mw), "cvar": vyw,
            "mmean": my, "mvar": vy, "pstrip": Z, "beta": beta}


def cond_demo(mu=(3.0, 8.0), s1=1.0, s2=math.sqrt(2.0), rho=1 / math.sqrt(2.0), cond="x1", c=4.0, h=0.1, N=5000, seed=1):
    """What the conditioning demonstration computes: N draws (one Box-Muller pair each,
    x1 = mu1 + s1 z1, x2 = mu2 + s2 (rho z1 + sqrt(1 - rho^2) z2)), the points in the strip
    |a^T x - c| <= h, and the displayed coordinate Y (x2 when conditioning on x1, x1 otherwise)."""
    mu = np.asarray(mu, float)
    u = js_uniforms(seed, 2 * N)
    z1, z2 = box_muller(u[0::2], u[1::2])
    x1 = mu[0] + s1 * z1
    x2 = mu[1] + s2 * (rho * z1 + math.sqrt(1 - rho * rho) * z2)
    a = COND_A[cond]
    w = a[0] * x1 + a[1] * x2
    y = x2 if cond == "x1" else x1
    inn = np.abs(w - c) <= h
    ys = y[inn]
    Sigma = np.array([[s1 * s1, rho * s1 * s2], [rho * s1 * s2, s2 * s2]])
    b = (0.0, 1.0) if cond == "x1" else (1.0, 0.0)
    ex = strip_moments(mu, Sigma, a, b, c, h)
    m = int(inn.sum())
    return {"count": m, "mean": float(ys.mean()) if m else float("nan"),
            "sd": float(ys.std(ddof=1)) if m > 1 else float("nan"), "exact": ex, "x1": x1, "x2": x2, "inside": inn}


# =========================================================================== cache
def _cached(name, fn):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch14_" + name + ".pkl")
    if os.path.exists(path):
        with open(path, "rb") as f:
            return pickle.load(f)
    val = fn()
    with open(path, "wb") as f:
        pickle.dump(val, f)
    return val


# =========================================================================== exercises
def exercise5(seed=5, B=2000):
    """Exercise 5: 100 draws from N((3, 8), [[1, 1], [1, 2]]) on the pages' generator; estimates, the
    Fisher interval and a bootstrap percentile interval for rho (B resamples, numpy generator)."""
    X = mvn_js(seed, 100, EX5_MU, EX5_SIGMA)
    xbar, S = sample_mean_cov(X)
    r = corr(X[:, 0], X[:, 1])
    rng = np.random.default_rng(1405)
    reps = boot_corr(X[:, 0], X[:, 1], B, rng)
    return {"X": X, "xbar": xbar, "S": S, "Sigma_mle": plug_in_cov(X), "r": r, "rho": 1 / math.sqrt(2),
            "fisher": fisher_ci(r, 100), "boot": boot_percentile_ci(reps), "wald": wald_ci(r, 100), "reps": reps,
            "boot_se": float(reps.std(ddof=1))}


EX6_NS = (10, 20, 30, 50, 100, 200)


def exercise6_table(dist="normal", R=1000, B=1000, seed=6):
    """Exercise 6 and its extension: coverage of the three intervals against n (pages' generator)."""
    def run():
        rows = []
        for n in EX6_NS:
            res = corr_demo(n=n, rho=1 / math.sqrt(2), dist=dist, R=R, B=B, alpha=0.05, seed=seed + n, keep_first=False)
            rows.append({k: res[k] for k in res if k.startswith("cov_") or k.startswith("len_")} | {"n": n})
        return rows
    return _cached("ex6_%s_R%d_B%d_s%d" % (dist, R, B, seed), run)


# =========================================================================== figures
def fig_14_s1(out_dir=None):
    """Figure 14.S1: Exercise 5, one sample of 100 vectors and the bootstrap distribution of r."""
    e = exercise5()
    X = e["X"]
    fig, axes = common.panel_grid(1, 2, size=(3.7, 3.2))
    ax = axes[0, 0]
    ax.plot(X[:, 0], X[:, 1], "o", ms=3, color=BLUE, alpha=0.6, mec="none")
    c95 = math.sqrt(stats.chi2.ppf(0.95, 2))
    ex, ey = common.ellipse_xy(EX5_MU, EX5_SIGMA, c95)
    ax.plot(ex, ey, color=GREEN, lw=1.6, label=r"true 95% ellipse")
    ex, ey = common.ellipse_xy(e["xbar"], e["S"], c95)
    ax.plot(ex, ey, color=RED, lw=1.4, ls="--", label=r"estimated ($\bar X$, $S$)")
    xs = np.linspace(-0.5, 6.5, 2)
    ax.plot(xs, EX5_MU[1] + (xs - EX5_MU[0]), color=GREY, lw=1, ls=":", label=r"$E(X_2\,|\,X_1)=X_1+5$")
    ax.plot(*EX5_MU, "+", color=GREEN, ms=10, mew=2)
    ax.plot(*e["xbar"], "x", color=RED, ms=8, mew=1.6)
    ax.set_xlim(-0.3, 6.3)
    ax.set_ylim(3.5, 12.5)
    ax.set_xlabel(r"$X_1$")
    ax.set_ylabel(r"$X_2$")
    ax.legend(fontsize=7, frameon=False, loc="upper left")
    common.panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    ax.hist(e["reps"], bins=40, density=True, color=BLUE, alpha=0.35, edgecolor="white", lw=0.3, label="bootstrap $r^*$")
    rr = np.linspace(0.45, 0.92, 300)
    ax.plot(rr, r_density(rr, e["r"], 100), color=PURPLE, lw=1.3, label=r"exact density, $\rho=\hat\rho$")
    yl = ax.get_ylim()[1]
    for (lo, hi), col, lab, yy in ((e["fisher"], RED, "Fisher", 1.22), (e["boot"], GREEN, "bootstrap", 1.15)):
        ax.plot([lo, hi], [yy * yl] * 2, color=col, lw=2.5, solid_capstyle="butt", label=lab + " 95%")
    ax.axvline(e["rho"], color="k", lw=1, ls="--")
    ax.axvline(e["r"], color=BLUE, lw=1)
    ax.text(e["rho"], 0.5 * yl, r" $\rho=0.707$", fontsize=8)
    ax.set_xlabel(r"sample correlation")
    ax.set_ylim(0, 1.3 * yl)
    ax.legend(fontsize=7, frameon=False, loc="upper left", bbox_to_anchor=(0.0, 0.84))
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S1", out_dir)


def fig_14_s2(out_dir=None):
    """Figure 14.S2: Exercise 6, coverage of three intervals for rho against n, normal and t data."""
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.9))
    ns = np.array(EX6_NS)
    for ax, dist, title, lab in ((axes[0, 0], "normal", "normal data", "a"), (axes[0, 1], "t10", r"$t_{10}$ data ($\kappa=1/3$)", "b"),
                                 (axes[0, 2], "t6", r"$t_{6}$ data ($\kappa=1$)", "c")):
        rows = exercise6_table(dist)
        se = math.sqrt(0.95 * 0.05 / 1000)
        ax.axhspan(0.95 - 2 * se, 0.95 + 2 * se, color=GREY, alpha=0.18, lw=0)
        ax.axhline(0.95, color="k", lw=0.8, ls="--")
        for key, col, mk, name in (("fisher", RED, "o", "Fisher"), ("boot", GREEN, "s", "bootstrap percentile"), ("wald", BLUE, "^", "delta method (Wald)")):
            ax.plot(ns, [r_["cov_" + key] for r_ in rows], marker=mk, color=col, ms=4, lw=1.2, label=name)
        if dist != "normal":
            kap = 2 / (T_NU[dist] - 4)
            lim = 2 * stats.norm.cdf(1.959963984540054 / math.sqrt(1 + kap)) - 1
            ax.axhline(lim, color=RED, lw=0.9, ls=":")
            ax.text(9.5, lim - 0.004, "Fisher's limit %.3f" % lim, color=RED, fontsize=7, va="top", ha="left")
        ax.set_xscale("log")
        ax.set_xticks(ns)
        ax.set_xticklabels([str(v) for v in ns])
        ax.set_ylim(0.70, 1.0)
        ax.set_xlabel("$n$")
        ax.set_title(title)
        common.panel_label(ax, lab, "lower right")
    axes[0, 0].set_ylabel("coverage (1000 samples)")
    axes[0, 0].legend(fontsize=7, frameon=False, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S2", out_dir)


def fig_14_s3(out_dir=None):
    """Figure 14.S3: the exact distribution of r and of Fisher's z for normal data."""
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.9))
    n = 10
    cols = (BLUE, GREEN, ORANGE, RED)
    ax = axes[0, 0]
    rr = np.linspace(-0.999, 0.999, 800)
    for rho, col in zip((0.0, 0.5, 0.8, 0.95), cols):
        ax.plot(rr, r_density(rr, rho, n), color=col, label=r"$\rho=%g$" % rho)
    ax.set_xlabel("$r$")
    ax.set_title(r"density of $r$, $n=10$")
    ax.legend(fontsize=7, frameon=False, loc="upper left")
    common.panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    zz = np.linspace(-1.5, 3.4, 600)
    for rho, col in zip((0.0, 0.5, 0.8, 0.95), cols):
        ax.plot(zz, z_density(zz, rho, n), color=col)
        ax.plot(zz, stats.norm.pdf(zz, math.atanh(rho), 1 / math.sqrt(n - 3)), color=col, ls="--", lw=1)
    ax.set_xlabel(r"$z=\tanh^{-1}r$")
    ax.set_title(r"density of $z$ (dashed: $N(\zeta,\frac{1}{n-3})$)")
    common.panel_label(ax, "b", "upper right")
    ax = axes[0, 2]
    ns = np.array([5, 6, 8, 10, 15, 20, 30, 50, 100])
    for rho, col in zip((0.0, 0.5, 0.8, 0.95), cols):
        sd = [math.sqrt(z_moments(rho, k)["Vz"] * (k - 3)) for k in ns]
        ax.plot(ns, sd, "o-", color=col, ms=3.5, lw=1.2, label=r"$\rho=%g$" % rho)
    ax.plot(ns, np.sqrt((ns - 3) / ns), color="k", lw=1, ls=":", label=r"if se were $1/\sqrt{n}$")
    ax.axhline(1, color="k", lw=0.8, ls="--")
    ax.set_xscale("log")
    ax.set_xticks([5, 10, 20, 50, 100])
    ax.set_xticklabels(["5", "10", "20", "50", "100"])
    ax.set_xlabel("$n$")
    ax.set_title(r"exact sd of $z$ times $\sqrt{n-3}$")
    ax.legend(fontsize=7, frameon=False, loc="lower right")
    common.panel_label(ax, "c", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S3", out_dir)


def fig_14_s4(out_dir=None):
    """Figure 14.S4: Hotelling's T^2 against separate t-tests (k = 2)."""
    fig, axes = common.panel_grid(1, 3, size=(3.15, 2.95))
    n, rho, alpha = 20, 0.8, 0.05
    res = hotelling_demo(n=n, rho=rho, theta=-45, c=0.0, alpha=alpha, R=2000, seed=3, ngrid=2)
    ax = axes[0, 0]
    t1, t2, T2 = res["t1"], res["t2"], res["T2"]
    rej = T2 > res["T2crit"]
    ax.plot(t1[~rej], t2[~rej], "o", ms=1.8, color=BLUE, alpha=0.45, mec="none")
    ax.plot(t1[rej], t2[rej], "o", ms=2.6, color=RED, mec="none", label=r"$T^2$ rejects")
    tb = res["tbonf"]
    ax.plot([-tb, tb, tb, -tb, -tb], [-tb, -tb, tb, tb, -tb], color=GREEN, lw=1.4, label="Bonferroni t-tests")
    P = np.array([[1, rho], [rho, 1]])
    ex, ey = common.ellipse_xy(np.zeros(2), P, math.sqrt(res["T2crit"]))
    ax.plot(ex, ey, color=RED, lw=1.2, ls="--", label=r"$t^\top P^{-1}t=$ crit.")
    ax.set_xlim(-5, 5)
    ax.set_ylim(-5, 5)
    ax.set_aspect("equal")
    ax.set_xlabel("$t_1$")
    ax.set_ylabel("$t_2$")
    ax.set_title(r"null, $n=20$, $\rho=0.8$")
    ax.legend(fontsize=6.5, frameon=False, loc="upper left")
    common.panel_label(ax, "a", "lower right")
    for ax, th, title, lab in ((axes[0, 1], -45.0, r"shift $\propto(1,-1)$: against $\rho$", "b"), (axes[0, 2], 45.0, r"shift $\propto(1,1)$: along $\rho$", "c")):
        rr = hotelling_demo(n=n, rho=rho, theta=th, c=0.0, alpha=alpha, R=2000, seed=4, ngrid=31, cmax=1.2)
        g = rr["grid"]
        ax.plot(g, rr["curves"]["exact"], color=RED, lw=1.6, label=r"$T^2$ (exact)")
        ax.plot(g, rr["curves"]["hot"], "o", color=RED, ms=2.5)
        ax.plot(g, rr["curves"]["bonf"], color=GREEN, lw=1.3, label="Bonferroni t")
        ax.plot(g, rr["curves"]["unadj"], color=ORANGE, lw=1.1, ls="--", label="unadjusted t")
        ax.axhline(alpha, color="k", lw=0.7, ls=":")
        ax.set_ylim(0, 1.02)
        ax.set_xlabel(r"shift length $\|\delta\|$ (in sd)")
        ax.set_title(title)
        common.panel_label(ax, lab, "lower right")
    axes[0, 1].set_ylabel("power")
    axes[0, 1].legend(fontsize=7, frameon=False, loc="center right")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S4", out_dir)


def fig_14_s5(out_dir=None):
    """Figure 14.S5: the multinomial MLE and Pearson's statistic (k = 3)."""
    rng = np.random.default_rng(1414)
    p = np.array([0.5, 0.3, 0.2])
    n = 50
    X = multinomial_draw(5000, n, p, rng)
    ph = multinomial_mle(X)
    fig, axes = common.panel_grid(1, 2, size=(3.7, 3.1))
    ax = axes[0, 0]
    jit = rng.uniform(-0.004, 0.004, (len(ph), 2))
    ax.plot(ph[:, 0] + jit[:, 0], ph[:, 1] + jit[:, 1], "o", ms=1.5, color=BLUE, alpha=0.25, mec="none")
    Sig = multinomial_cov(p)[:2, :2] / n
    for lev, ls in ((0.5, "-"), (0.95, "--")):
        ex, ey = common.ellipse_xy(p[:2], Sig, math.sqrt(stats.chi2.ppf(lev, 2)))
        ax.plot(ex, ey, color=RED, lw=1.3, ls=ls, label="normal approx. %d%%" % round(100 * lev))
    ax.plot([0, 1], [1, 0], color=GREY, lw=0.8)
    ax.set_xlim(0.25, 0.75)
    ax.set_ylim(0.1, 0.5)
    ax.set_xlabel(r"$\hat p_1$")
    ax.set_ylabel(r"$\hat p_2$")
    ax.set_title(r"MLE, $n=50$, $p=(0.5,0.3,0.2)$")
    ax.legend(fontsize=7, frameon=False, loc="upper right")
    common.panel_label(ax, "a", "lower left")
    ax = axes[0, 1]
    q = pearson_chi2(X, n, p)
    ax.hist(q, bins=np.arange(0, 14.5, 0.5), density=True, color=BLUE, alpha=0.35, edgecolor="white", lw=0.3, label="Pearson's statistic")
    xx = np.linspace(0.01, 14, 300)
    ax.plot(xx, stats.chi2.pdf(xx, 2), color=RED, label=r"$\chi^2_2$ density")
    ax.set_xlabel(r"$\sum_j (X_j-np_j)^2/(np_j)$")
    ax.set_title("5000 samples")
    ax.legend(fontsize=7, frameon=False)
    common.panel_label(ax, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S5", out_dir)


def t2_null_sim(n, k, R, rng):
    X = rng.standard_normal((R, n, k))
    xbar = X.mean(1)
    D = X - xbar[:, None, :]
    S = np.einsum("rni,rnj->rij", D, D) / (n - 1)
    sol = np.linalg.solve(S, xbar[:, :, None])[:, :, 0]
    return n * (xbar * sol).sum(1)


def eig_spread(k, n, R, rng):
    X = rng.standard_normal((R, n, k))
    D = X - X.mean(1, keepdims=True)
    S = np.einsum("rni,rnj->rij", D, D) / (n - 1)
    return np.linalg.eigvalsh(S)


def fig_14_s6(out_dir=None):
    """Figure 14.S6: Hotelling's T^2 null law and the spread of sample eigenvalues."""
    rng = np.random.default_rng(1416)
    fig, axes = common.panel_grid(1, 2, size=(3.7, 3.0))
    ax = axes[0, 0]
    n, k = 10, 3
    T2 = t2_null_sim(n, k, 20000, rng)
    ax.hist(T2, bins=np.arange(0, 40.5, 1), density=True, color=BLUE, alpha=0.35, edgecolor="white", lw=0.3, label=r"simulated $T^2$")
    xx = np.linspace(0.05, 40, 400)
    c = k * (n - 1) / (n - k)
    ax.plot(xx, stats.f.pdf(xx / c, k, n - k) / c, color=RED, label=r"$\frac{k(n-1)}{n-k}F_{k,n-k}$")
    ax.plot(xx, stats.chi2.pdf(xx, k), color=GREY, ls="--", label=r"$\chi^2_k$ (large $n$)")
    q95 = hotelling_crit(n, k, 0.05)
    ax.axvline(q95, color=RED, lw=0.9, ls=":")
    ax.axvline(stats.chi2.ppf(0.95, k), color=GREY, lw=0.9, ls=":")
    ax.set_xlabel(r"$T^2$, $k=3$, $n=10$")
    ax.set_xlim(0, 40)
    ax.legend(fontsize=7, frameon=False)
    common.panel_label(ax, "a", "center right")
    ax = axes[0, 1]
    k = 10
    for i, (n, col) in enumerate(((20, RED), (50, ORANGE), (200, GREEN))):
        ev = eig_spread(k, n, 400, rng)
        ax.plot(np.arange(1, k + 1) + (i - 1) * 0.18, ev.mean(0)[::-1], "o-", color=col, ms=4, lw=1.2, label="$n=%d$" % n)
        g = k / (n - 1)
        ax.axhline((1 + math.sqrt(g)) ** 2, color=col, lw=0.7, ls=":")
        ax.axhline((1 - math.sqrt(g)) ** 2, color=col, lw=0.7, ls=":")
    ax.axhline(1, color="k", lw=1, ls="--")
    ax.set_xlabel(r"rank of eigenvalue of $S$ ($k=10$, $\Sigma=I$)")
    ax.set_ylabel("mean eigenvalue")
    ax.legend(fontsize=7, frameon=False)
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig14-S6", out_dir)


FIGURES = {"14.S1": fig_14_s1, "14.S2": fig_14_s2, "14.S3": fig_14_s3, "14.S4": fig_14_s4,
           "14.S5": fig_14_s5, "14.S6": fig_14_s6}

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