"""Murphy (2023), Chapter 11: Monte Carlo methods.

Companion code for Chapter 11 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 483-498, written from scratch with numpy and scipy
(scipy is used only for the kernel density estimate, the Sobol generator and to confirm my own
implementations), to be read next to the lecture notes (../ch11-monte-carlo.html).

Methods
* 11.2 Monte Carlo integration: estimate_pi, standard error and the sample-size rule (Figures 11.1, 11.2).
* 11.3 inverse-cdf sampling and the polar Box-Muller method (inverse_cdf_expon, box_muller_polar; Figure 11.3).
* 11.4 rejection sampling (gamma example, gamma_rejection) and adaptive rejection sampling
  (ars_sample); acceptance rate in high dimension (Figures 11.4b, 11.5 and own Figure 11.9a).
* 11.5 importance sampling: direct and self-normalised estimators and the effective sample size
  (snis, ess); annealed importance sampling for a normalising constant (ais; own Figures 11.8, 11.9b).
* 11.6 variance reduction: control variates, antithetic sampling, quasi-Monte Carlo and randomised
  QMC (Figure 11.7 and own Figure 11.10).

Skipped figures, with reasons: Figure 11.4a (a hand-drawn schematic of rejection sampling) and
Figure 11.6 (a schematic of a rare-event proposal) contain nothing computed.

Data: simulated (seeds fixed in the code). Figure numbers 11.8 to 11.10 are my own extra figures.
"""
import json
import os
import sys

import numpy as np
from scipy import special, stats
from scipy.stats import qmc

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig, run  # noqa: E402

CH = 11
DATA_OUT = os.path.normpath(os.path.join(os.path.dirname(os.path.abspath(__file__)), "..", "data"))


# ------------------------------------------------------------------ 11.2 Monte Carlo integration
def estimate_pi(n=5000, r=2.0, seed=0):
    """Estimate pi by MC integration of the indicator of the disc of radius r inside the square [-r, r]^2.

    Returns (x, y, inside, pi_hat, se_pi, se_area) where area_hat = 4 r^2 mean(inside)."""
    rng = np.random.default_rng(seed)
    x = rng.uniform(-r, r, n)
    y = rng.uniform(-r, r, n)
    inside = x ** 2 + y ** 2 <= r ** 2
    f = 4 * r ** 2 * inside                        # 4r^2 f(x,y), unbiased for the area I = pi r^2
    area = f.mean()
    se_area = np.sqrt(f.var() / n)
    return x, y, inside, area / r ** 2, se_area / r ** 2, se_area


def mc_mean_se(fx):
    """MC estimate and numerical standard error, equations (11.2), (11.9) (with the unbiased 1/(N-1))."""
    fx = np.asarray(fx, float)
    return fx.mean(), fx.std(ddof=1) / np.sqrt(len(fx))


# ------------------------------------------------------------------ 11.3 simple distributions
def inverse_cdf_expon(u, lam):
    """Exponential sample by the inverse cdf (11.15): F^{-1}(u) = -ln(1-u)/lam."""
    return -np.log1p(-np.asarray(u)) / lam


def box_muller_polar(n, rng):
    """n standard normal draws by the polar method of Section 11.3.2 (rejection from the unit disc)."""
    out = []
    got = 0
    while got < n:
        m = max(16, int((n - got) * 1.4) + 8)
        z = rng.uniform(-1, 1, (m, 2))
        r2 = (z ** 2).sum(1)
        ok = (r2 <= 1) & (r2 > 0)
        z, r2 = z[ok], r2[ok]
        x = z * np.sqrt(-2 * np.log(r2) / r2)[:, None]
        out.append(x.ravel())
        got += x.size
    return np.concatenate(out)[:n]


def mvn_sample(mu, Sigma, n, rng):
    """y = L x + mu with Sigma = L L^T and x ~ N(0, I) from the polar method (equation 11.18)."""
    L = np.linalg.cholesky(Sigma)
    X = box_muller_polar(n * len(mu), rng).reshape(n, len(mu))
    return X @ L.T + mu


# ------------------------------------------------------------------ 11.4 rejection sampling
def gamma_rejection_const(alpha, lam, k=None, rate_q=None):
    """Envelope constant C for sampling Ga(alpha, rate lam) from Ga(k, rate rate_q), equation (11.28).

    Default (the book): k = floor(alpha), rate_q = lam - 1. Returns (C, x_star) with x_star = (alpha-k)/(lam-rate_q)."""
    k = int(np.floor(alpha)) if k is None else k
    rate_q = lam - 1.0 if rate_q is None else rate_q
    if abs(alpha - k) < 1e-12:                    # integer shape: the ratio is monotone, maximal at x = 0 (or constant)
        return (1.0 if abs(lam - rate_q) < 1e-12 else float((lam / rate_q) ** k)), 0.0
    xs = (alpha - k) / (lam - rate_q)
    C = np.exp(stats.gamma.logpdf(xs, alpha, scale=1 / lam) - stats.gamma.logpdf(xs, k, scale=1 / rate_q))
    return C, xs


def gamma_rejection(alpha, lam, n_prop, rng, k=None, rate_q=None):
    """Rejection sampler for Ga(alpha, lam) with a Ga(k, rate_q) proposal (integer k: a sum of k exponentials).

    Returns (accepted samples, C)."""
    k = int(np.floor(alpha)) if k is None else k
    rate_q = lam - 1.0 if rate_q is None else rate_q
    C, _ = gamma_rejection_const(alpha, lam, k, rate_q)
    x = rng.exponential(1 / rate_q, (n_prop, k)).sum(1)
    u = rng.uniform(0, 1, n_prop)
    ratio = np.exp(stats.gamma.logpdf(x, alpha, scale=1 / lam) - stats.gamma.logpdf(x, k, scale=1 / rate_q)) / C
    return x[u <= ratio], C


class ARS:
    """Adaptive rejection sampling (Gilks and Wild 1992) for a log-concave density on (lo, hi).

    The upper envelope is the lower envelope of the tangent lines of h = log f at the abscissae, a
    piecewise exponential function (equation 11.29); a rejected point becomes a new abscissa."""

    def __init__(self, h, dh, xs, lo=-np.inf, hi=np.inf):
        self.h, self.dh, self.lo, self.hi = h, dh, lo, hi
        self.xs = sorted(xs)
        self.n_eval = 0
        self._build()

    def _build(self):
        xs = np.array(self.xs)
        hv, dv = np.array([self.h(x) for x in xs]), np.array([self.dh(x) for x in xs])
        self.n_eval += len(xs) if not hasattr(self, "_h") else 0
        self._h, self._d, self._x = hv, dv, xs
        z = (hv[1:] - hv[:-1] - xs[1:] * dv[1:] + xs[:-1] * dv[:-1]) / (dv[:-1] - dv[1:])
        self.brk = np.concatenate([[self.lo], z, [self.hi]])
        a, b = self.brk[:-1], self.brk[1:]
        line = lambda j, x: hv[j] + dv[j] * (x - xs[j])
        mass = np.empty(len(xs))
        for j in range(len(xs)):
            ha, hb = line(j, a[j]), line(j, b[j])
            if abs(dv[j]) < 1e-12:
                mass[j] = np.exp(ha) * (b[j] - a[j])
            else:
                mass[j] = (np.exp(hb) - np.exp(ha)) / dv[j]
        self.mass = mass

    def env_logpdf(self, x):
        """log of the (unnormalised) upper envelope at x (min over the tangent lines)."""
        x = np.atleast_1d(x)
        return np.min(self._h[:, None] + self._d[:, None] * (x[None, :] - self._x[:, None]), axis=0)

    def _draw_envelope(self, rng):
        j = rng.choice(len(self.mass), p=self.mass / self.mass.sum())
        a, b, d = self.brk[j], self.brk[j + 1], self._d[j]
        ha = self._h[j] + d * (a - self._x[j])
        hb = self._h[j] + d * (b - self._x[j])
        u = rng.uniform()
        if abs(d) < 1e-12:
            return a + u * (b - a)
        if np.isinf(a):                                     # d > 0 on the left-unbounded piece
            return b + np.log(u * self.mass[j] * d * np.exp(-hb)) / d
        return a + np.log(1 + u * self.mass[j] * d * np.exp(-ha)) / d

    def sample(self, n, rng):
        out, tries = [], 0
        while len(out) < n:
            x = self._draw_envelope(rng)
            u = rng.uniform()
            tries += 1
            lf, lu = self.h(x), self.env_logpdf(x)[0]
            if np.log(u) <= lf - lu:
                out.append(x)
            else:                                           # refine the envelope with the rejected point
                self.xs = sorted(self.xs + [x])
                self._build()
        self.acceptance = n / tries
        return np.array(out)


# ------------------------------------------------------------------ 11.5 importance sampling
def snis(phi_x, logw_unnorm):
    """Self-normalised IS estimate (11.38), normalised weights W (11.41) and the estimate of Z, (11.43)."""
    m = np.max(logw_unnorm)
    w = np.exp(logw_unnorm - m)
    W = w / w.sum()
    Zhat = np.exp(m) * w.mean()
    return float(np.sum(W * phi_x)), W, float(Zhat)


def ess(W):
    """Effective sample size 1 / sum W^2 of normalised weights."""
    W = np.asarray(W)
    return 1.0 / np.sum(W ** 2)


def log_target_mix(x, w=(0.4, 0.6), mu=(-2.0, 1.5), sd=(0.7, 1.0), Z=2.0):
    """Unnormalised bimodal target gamma(x) = Z * sum_k w_k N(x | mu_k, sd_k^2); normalising constant Z."""
    x = np.asarray(x, float)
    lp = [np.log(wk) + stats.norm.logpdf(x, m, s) for wk, m, s in zip(w, mu, sd)]
    return np.log(Z) + special.logsumexp(lp, axis=0)


def ais(logf0, logfn, sample_n, betas, n_chains, rng, n_mh=5, step=0.5):
    """Annealed importance sampling in 1-D (Section 11.5.4), written in Neal's order.

    Target f0 (unnormalised), easy distribution f_n (normalised, sampled by sample_n). betas decrease
    from 1 to 0, f_j = f0^beta_j fn^(1-beta_j). Returns (x, logw) where logw estimates log(Z0/Zn)."""
    x = sample_n(n_chains, rng)
    logw = np.zeros(n_chains)
    b = np.asarray(betas, float)[::-1]                      # from beta=0 (easy) up to beta=1 (target)
    logf = lambda x, bj: bj * logf0(x) + (1 - bj) * logfn(x)
    for j in range(1, len(b)):
        logw += logf(x, b[j]) - logf(x, b[j - 1])           # weight at the current point, before moving
        for _ in range(n_mh):                               # random-walk MH leaving f_j invariant
            prop = x + step * rng.standard_normal(n_chains)
            acc = np.log(rng.uniform(size=n_chains)) < logf(prop, b[j]) - logf(x, b[j])
            x = np.where(acc, prop, x)
    return x, logw


# ------------------------------------------------------------------ 11.6 variance reduction
def f_cv(x):
    """The integrand 1/(1+x) of Section 11.6.3.1 (X ~ Unif(0,1)); exact mean ln 2."""
    return 1.0 / (1.0 + x)


def vr_estimators(S, rng):
    """One replication of the three estimators of Sections 11.6.3 and 11.6.4 with budget S function evaluations:
    plain MC with S draws, control variate b(x) = 1 + x with c estimated from the same draws, and antithetic
    pairs (x, 1-x) from S/2 base draws."""
    x = rng.uniform(size=S)
    fx, bx = f_cv(x), 1 + x
    C = np.cov(fx, bx)
    c = -C[0, 1] / C[1, 1]
    mc = fx.mean()
    cv = mc + c * (bx.mean() - 1.5)
    u = rng.uniform(size=S // 2)
    anti = 0.5 * (f_cv(u) + f_cv(1 - u)).mean()
    return mc, cv, anti, c


def vr_exact(S):
    """Exact standard errors for the three estimators with S function evaluations (closed forms)."""
    mu = np.log(2)
    var_f = 0.5 - mu ** 2                                   # E[f^2] = 1/2
    cov_fb = 1.0 - 1.5 * mu                                 # E[f b] = 1
    var_b = 1 / 12
    cstar = -cov_fb / var_b
    var_cv = var_f - cov_fb ** 2 / var_b
    cov_anti = 2 * mu / 3 - mu ** 2                         # Cov(f(U), f(1-U))
    var_pair = (var_f + cov_anti) / 2
    return dict(mu=mu, var_f=var_f, cstar=cstar, se_mc=np.sqrt(var_f / S), se_cv=np.sqrt(var_cv / S),
                se_anti=np.sqrt(var_pair / (S // 2)), rho2=cov_fb ** 2 / (var_b * var_f), cov_anti=cov_anti)


def van_der_corput(n, base=2):
    """First n points of the van der Corput sequence (the 1-D Halton sequence)."""
    out = np.zeros(n)
    for i in range(n):
        f, k, v = 1.0, i + 1, 0.0
        while k > 0:
            f /= base
            v += f * (k % base)
            k //= base
        out[i] = v
    return out


def rqmc_1d(n, rng):
    """Randomised QMC (11.64): a shifted van der Corput point set y_i = x_i + u mod 1."""
    return (van_der_corput(n) + rng.uniform()) % 1.0


# ------------------------------------------------------------------ figures
def fig_11_1(out=None):
    """Estimating pi by Monte Carlo integration with 5000 samples."""
    x, y, inside, pi_hat, se_pi, se_area = estimate_pi(5000, 2.0, seed=0)
    fig, ax = plt.subplots(figsize=(3.6, 3.6))
    ax.plot(x[inside], y[inside], "o", color=BLUE, ms=2.2, mew=0)
    ax.plot(x[~inside], y[~inside], "D", color=RED, ms=2.2, mew=0)
    ax.set_aspect("equal"); ax.set_xlim(-2, 2); ax.set_ylim(-2, 2)
    ax.set_title("pi estimate %.3f (se %.3f)" % (pi_hat, se_pi))
    savefig(fig, CH, "fig11-1", out)


def fig_11_2(out=None):
    """10 and 100 samples from N(1.5, 0.25) with a kernel density estimate."""
    mu, sd = 1.5, 0.5
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 2.7), sharey=True)
    grid = np.linspace(-0.5, 3.5, 400)
    for ax, n, lab in zip(axes, (10, 100), "ab"):
        s = np.random.default_rng(n).normal(mu, sd, n)
        ax.hist(s, bins=np.linspace(0, 3, 16), density=True, color="#9cb8e6", edgecolor="white")
        ax.plot(grid, stats.norm.pdf(grid, mu, sd), color=BLUE, label="true pdf")
        ax.plot(grid, stats.gaussian_kde(s)(grid), color=RED, ls=":", lw=2, label="estimated pdf")
        ax.set_xlim(0, 3); ax.set_ylim(0, 2.1); ax.set_xlabel("n samples = %d" % n)
        ax.legend(loc="upper left", fontsize=8)
    savefig(fig, CH, "fig11-2", out)


def fig_11_3(out=None):
    """Sampling from N(3, 1) with the inverse cdf."""
    rng = np.random.default_rng(3)
    u = rng.uniform(size=400)
    x = stats.norm.ppf(u, 3, 1)
    xs = np.linspace(0, 7, 400)
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    ax.plot(xs, stats.norm.cdf(xs, 3, 1), color=BLUE, label="cdf N(3, 1)")
    ax.plot(xs, stats.norm.pdf(xs, 3, 1), color=GREEN, label="pdf N(3, 1)")
    for ui, xi in zip(u[:6], x[:6]):
        ax.plot([0, xi, xi], [ui, ui, 0], color=GREY, ls="--", lw=0.9)
    ax.plot(np.zeros(120), u[:120], ".", color=RED, ms=3, label="samples Unif(0, 1)")
    ax.plot(x[:120], np.zeros(120), ".", color=ORANGE, ms=3, label="samples N(3, 1)")
    ax.set_xlim(-0.2, 7); ax.set_ylim(-0.03, 1.05); ax.set_xlabel("x (N(3, 1))"); ax.set_ylabel("u (Unif(0, 1))")
    ax.legend(loc="center left", fontsize=8)
    savefig(fig, CH, "fig11-3", out)


def fig_11_4(out=None):
    """Rejection sampling from Ga(5.7, 2) with the envelope M Ga(5, rate 1)."""
    alpha, lam = 5.7, 2.0
    rng = np.random.default_rng(4)
    samp, C = gamma_rejection(alpha, lam, 20000, rng)
    xs = np.linspace(0, 10, 500)
    fig, ax = plt.subplots(figsize=(4.8, 3.2))
    ax.hist(samp, bins=np.linspace(0, 10, 41), density=True, color="#cfdcf3", edgecolor="white",
            label="accepted samples (own)")
    ax.plot(xs, stats.gamma.pdf(xs, alpha, scale=1 / lam), color=BLUE, label="target p(x)")
    ax.plot(xs, C * stats.gamma.pdf(xs, 5, scale=1.0), color=RED, ls=":", lw=2, label="comparison function Mq(x)")
    ax.axvline(0.7, color=GREY, lw=0.8, ls="--")
    ax.set_xlabel("x"); ax.set_xlim(0, 10); ax.set_ylim(0, 1.05)
    ax.set_title("C = %.3f, acceptance %.3f" % (C, 1 / C))
    ax.legend(fontsize=8)
    savefig(fig, CH, "fig11-4", out)


def fig_11_5(out=None):
    """Adaptive rejection sampling: the tangent envelope (a) and ARS for a half Gaussian (b, c)."""
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 2.7))
    ax = axes[0]
    h = lambda x: -0.5 * x ** 2
    dh = lambda x: -x
    xs = np.linspace(-3.2, 3.2, 400)
    ab = np.array([-1.6, 0.1, 1.5])
    ax.plot(xs, h(xs), color=BLUE, lw=2.4, label="log f")
    for a in ab:
        ax.plot(xs, h(a) + dh(a) * (xs - a), color=RED, lw=1, alpha=0.9)
    zs = [(h(ab[i + 1]) - h(ab[i]) - ab[i + 1] * dh(ab[i + 1]) + ab[i] * dh(ab[i])) / (dh(ab[i]) - dh(ab[i + 1])) for i in range(2)]
    for z in zs:
        ax.axvline(z, color=RED, ls="--", lw=0.8)
    ch = np.interp(xs, ab, h(ab))
    ax.plot(ab, h(ab), "o", color=GREEN, ms=4)
    ax.plot(ab, h(ab), color=GREEN, lw=1.1, ls="--", label="chords (squeeze)")
    ax.set_ylim(-3.2, 0.6); ax.set_xlim(-3.2, 3.2); ax.set_xlabel("x"); ax.set_ylabel("log f(x)")
    ax.legend(fontsize=8, loc="lower center")
    ax = axes[1]
    xx = np.linspace(-5, 5, 400)
    ax.plot(xx[xx <= 0], np.exp(-0.5 * xx[xx <= 0] ** 2), color=BLUE)
    ax.set_xlabel("x"); ax.set_ylabel("f(x)"); ax.set_title("f(x) half-Gaussian"); ax.set_ylim(0, 1.05)
    rng = np.random.default_rng(5)
    a = ARS(lambda x: -0.5 * x ** 2, lambda x: -x, [-3.0, -1.0, -0.3], lo=-np.inf, hi=0.0)
    s = a.sample(10000, rng)
    ax = axes[2]
    ax.hist(s, bins=np.linspace(-5, 5, 101), color="#7aa6dd", edgecolor="none")
    ax.set_xlim(-5, 5); ax.set_xlabel("x"); ax.set_ylabel("samples")
    ax.set_title("ARS: %d abscissae, %.1f%% accepted" % (len(a.xs), 100 * a.acceptance), fontsize=9.5)
    fig.subplots_adjust(wspace=0.38)
    savefig(fig, CH, "fig11-5", out)


def fig_11_7(out=None):
    """512 points in the unit square: MC, Sobol QMC and scrambled (randomised) QMC."""
    n = 512
    rng = np.random.default_rng(7)
    pts = [rng.uniform(size=(n, 2)),
           qmc.Sobol(2, scramble=False).random(n),
           qmc.Sobol(2, scramble=True, seed=7).random(n)]
    names = ["MC", "QMC (Sobol)", "RQMC (scrambled Sobol)"]
    fig, axes = plt.subplots(1, 3, figsize=(9.0, 3.1))
    for ax, p, nm in zip(axes, pts, names):
        ax.plot(p[:, 0], p[:, 1], ".", color=BLUE, ms=2.6)
        ax.set_aspect("equal"); ax.set_xlim(0, 1); ax.set_ylim(0, 1); ax.set_xticks([0, 1]); ax.set_yticks([0, 1])
        ax.set_title("%d %s" % (n, nm), fontsize=9.5)
    savefig(fig, CH, "fig11-7", out)


# ------------------------------------------------------------------ own figures
AIS_TARGET = dict(w=(0.4, 0.6), mu=(-2.5, 2.5), sd=(0.4, 0.4), Z=2.0)


def ais_experiment(Ks=(1, 10, 50, 200), n_chains=100, reps=40, seed=8):
    """log Z-hat for the bimodal target (Z = 2, two narrow modes) with the broad easy distribution N(0, 4^2)."""
    mu_s = 4.0
    logf0 = lambda x: log_target_mix(x, **AIS_TARGET)
    logfn = lambda x: stats.norm.logpdf(x, 0, mu_s)
    sample_n = lambda n, rng: rng.normal(0, mu_s, n)
    rng = np.random.default_rng(seed)
    res = {}
    for K in Ks:
        betas = np.linspace(1, 0, K + 1)
        est = []
        for _ in range(reps):
            _, lw = ais(logf0, logfn, sample_n, betas, n_chains, rng)
            est.append(special.logsumexp(lw) - np.log(len(lw)))
        res[K] = np.array(est)
    return res


def fig_11_8(out=None):
    """(own) Annealed importance sampling: weighted samples and the estimate of log Z against the number of temperatures."""
    mu_s = 4.0
    logf0 = lambda x: log_target_mix(x, **AIS_TARGET)
    logfn = lambda x: stats.norm.logpdf(x, 0, mu_s)
    sample_n = lambda n, rng: rng.normal(0, mu_s, n)
    rng = np.random.default_rng(9)
    x, lw = ais(logf0, logfn, sample_n, np.linspace(1, 0, 201), 4000, rng)
    W = np.exp(lw - lw.max()); W /= W.sum()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 2.9))
    ax = axes[0]
    g = np.linspace(-6, 6, 500)
    ax.hist(x, bins=np.linspace(-6, 6, 61), weights=W, density=True, color="#cfdcf3", edgecolor="white", label="AIS (200 temperature steps)")
    ax.plot(g, np.exp(log_target_mix(g, **AIS_TARGET)) / 2.0, color=BLUE, label="target")
    ax.plot(g, stats.norm.pdf(g, 0, mu_s), color=GREY, ls=":", label="easy distribution")
    ax.set_xlabel("x"); ax.legend(fontsize=7.5, loc="upper center")
    ax.set_ylim(0, 1.0)
    ax = axes[1]
    Ks = (1, 10, 50, 200)
    res = ais_experiment(Ks)
    for i, K in enumerate(Ks):
        ax.plot(np.full(len(res[K]), i) + np.random.default_rng(i).uniform(-0.12, 0.12, len(res[K])), res[K], ".", color=BLUE, ms=3, alpha=0.6)
        ax.plot([i - 0.25, i + 0.25], [res[K].mean()] * 2, color=RED, lw=2)
    ax.axhline(np.log(2.0), color=GREEN, ls="--", label="true log Z = ln 2")
    ax.set_xticks(range(len(Ks))); ax.set_xticklabels([str(k) for k in Ks])
    ax.set_xlabel("temperature steps K (K = 1: plain IS)"); ax.set_ylabel("log Z-hat (100 chains per run)")
    ax.legend(fontsize=8)
    savefig(fig, CH, "fig11-8", out)


def fig_11_9(out=None):
    """(own) (a) rejection-sampling acceptance against dimension; (b) effective sample size of IS against proposal scale."""
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 2.9))
    ax = axes[0]
    D = np.arange(1, 101)
    for ratio, col in ((1.01, GREEN), (1.05, BLUE), (1.1, RED)):
        ax.semilogy(D, ratio ** (-D.astype(float)), color=col, label="sigma_q / sigma_p = %.2f" % ratio)
    rng = np.random.default_rng(10)
    Ds = [1, 5, 10, 20, 30, 40]
    emp = []
    for d in Ds:
        x = rng.normal(0, 1.1, (200000, d))
        logr = stats.norm.logpdf(x, 0, 1).sum(1) - stats.norm.logpdf(x, 0, 1.1).sum(1)
        C = 1.1 ** d
        emp.append(np.mean(np.log(rng.uniform(size=len(x))) <= logr - np.log(C)))
    ax.plot(Ds, emp, "ko", ms=4, label="simulation (ratio 1.10)")
    ax.set_xlabel("dimension D"); ax.set_ylabel("acceptance rate 1/C"); ax.set_ylim(1e-5, 1.2); ax.legend(fontsize=8)
    ax = axes[1]
    s = np.linspace(0.45, 3.0, 60)
    g = np.empty_like(s); e = np.empty_like(s)
    rng = np.random.default_rng(11)
    N = 20000
    for i, si in enumerate(s):
        x = rng.normal(0, si, N)
        logw = stats.norm.logpdf(x, 0, 1) - stats.norm.logpdf(x, 0, si)
        W = np.exp(logw - logw.max()); W /= W.sum()
        e[i] = ess(W) / N
        g[i] = ess_theory(si)
    ax.plot(s, g, color=BLUE, label="theory: 1 / E_q[w^2]")
    ax.plot(s, e, ".", color=RED, ms=4, label="simulation (N = 20000)")
    ax.axvline(1 / np.sqrt(2), color=GREY, ls=":")
    ax.set_xlabel("proposal standard deviation (target N(0, 1))"); ax.set_ylabel("ESS / N"); ax.set_ylim(0, 1.05)
    ax.legend(fontsize=8)
    fig.subplots_adjust(wspace=0.3)
    savefig(fig, CH, "fig11-9", out)


def ess_theory(s):
    """ESS/N = 1 / E_q[w^2] for target N(0,1) and proposal N(0, s^2); infinite variance (ESS/N -> 0) for s^2 <= 1/2."""
    if s * s <= 0.5:
        return 0.0
    return float(np.sqrt(2 - 1 / s ** 2) / s)


def fig_11_10(out=None):
    """(own) Variance reduction: error against the number of evaluations for 1/(1+x) and for a 5-D integrand."""
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 2.9))
    # (a) histograms of the three estimators with S = 1500 and 2000 replications
    rng = np.random.default_rng(12)
    R = np.array([vr_estimators(1500, rng)[:3] for _ in range(2000)])
    ax = axes[0]
    bins = np.linspace(0.675, 0.712, 60)
    for k, (nm, col) in enumerate((("plain MC", GREY), ("control variate", BLUE), ("antithetic", RED))):
        ax.hist(R[:, k], bins=bins, histtype="stepfilled", alpha=0.45, color=col, label="%s (sd %.4f)" % (nm, R[:, k].std()))
    ax.axvline(np.log(2), color="k", lw=0.8, ls="--")
    ax.set_xlabel("estimate of ln 2 (S = 1500)"); ax.set_yticks([]); ax.legend(fontsize=7.5, loc="upper left"); ax.set_ylim(0, ax.get_ylim()[1] * 1.6)
    # (b) error against N for the 1-D integrand
    Ns = 2 ** np.arange(4, 13)
    rng = np.random.default_rng(13)
    reps = 200
    mu = np.log(2)
    err = {k: [] for k in ("MC", "antithetic", "control variate", "QMC (vdC)", "RQMC")}
    for N in Ns:
        a = {k: [] for k in err}
        for _ in range(reps):
            mc, cv, an, _c = vr_estimators(int(N), rng)
            a["MC"].append(mc - mu); a["control variate"].append(cv - mu); a["antithetic"].append(an - mu)
            a["RQMC"].append(f_cv(rqmc_1d(int(N), rng)).mean() - mu)
        a["QMC (vdC)"] = [f_cv(van_der_corput(int(N))).mean() - mu]
        for k in err:
            err[k].append(np.sqrt(np.mean(np.square(a[k]))))
    ax = axes[1]
    for (k, v), col in zip(err.items(), (GREY, BLUE, RED, GREEN, MAGENTA)):
        ax.loglog(Ns, v, "o-", ms=3, color=col, label=k)
    ax.set_xlabel("N"); ax.set_ylabel("RMS error"); ax.set_title("f(x) = 1/(1+x), D = 1", fontsize=9.5); ax.legend(fontsize=7.5)
    # (c) 5-D smooth integrand
    ax = axes[2]
    D, a_ = 5, 1.0
    exact = ((np.exp(a_) - 1) / a_) ** D
    g = lambda X: np.exp(a_ * X.sum(1))
    rng = np.random.default_rng(14)
    e_mc, e_q, e_r = [], [], []
    for N in Ns:
        em = [g(rng.uniform(size=(N, D))).mean() - exact for _ in range(60)]
        eq = [g(qmc.Sobol(D, scramble=True, seed=int(rng.integers(1 << 30))).random(N)).mean() - exact for _ in range(60)]
        e_mc.append(np.sqrt(np.mean(np.square(em)))); e_r.append(np.sqrt(np.mean(np.square(eq))))
        e_q.append(abs(g(qmc.Sobol(D, scramble=False).random(N)).mean() - exact))
    ax.loglog(Ns, e_mc, "o-", ms=3, color=GREY, label="MC")
    ax.loglog(Ns, e_q, "o-", ms=3, color=GREEN, label="QMC (Sobol)")
    ax.loglog(Ns, e_r, "o-", ms=3, color=MAGENTA, label="RQMC (scrambled Sobol)")
    ax.loglog(Ns, 0.5 * e_mc[0] * (Ns / Ns[0]) ** -0.5, color="k", lw=0.7, ls=":")
    ax.set_xlabel("N"); ax.set_ylabel("RMS error"); ax.set_title("f(x) = exp(sum x_i), D = 5", fontsize=9.5); ax.legend(fontsize=7.5)
    fig.subplots_adjust(wspace=0.4)
    savefig(fig, CH, "fig11-10", out)


# ------------------------------------------------------------------ data export
def export_reference():
    """Reference numbers the demos reproduce (written to ../data/ch11-reference.json)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    ex = vr_exact(1500)
    C1, xs1 = gamma_rejection_const(5.7, 2.0)
    C2, _ = gamma_rejection_const(5.7, 2.0, k=5, rate_q=5 * 2.0 / 5.7)
    ref = dict(vr_S1500={k: float(v) for k, v in ex.items()},
               rejection_gamma=dict(alpha=5.7, lam=2.0, C_book=float(C1), x_star=float(xs1), C_opt=float(C2), rate_opt=float(5 * 2.0 / 5.7)),
               is_target=dict(w=[0.4, 0.6], mu=[-2.0, 1.5], sd=[0.7, 1.0], Z=2.0, mean=0.1))
    with open(os.path.join(DATA_OUT, "ch11-reference.json"), "w") as f:
        json.dump(ref, f, indent=1)
    print("wrote data/ch11-reference.json")


def fig_export(out=None):
    """Export the JSON reference data."""
    export_reference()


FIGURES = {"11.1": fig_11_1, "11.2": fig_11_2, "11.3": fig_11_3, "11.4": fig_11_4, "11.5": fig_11_5,
           "11.7": fig_11_7, "11.8": fig_11_8, "11.9": fig_11_9, "11.10": fig_11_10, "data": fig_export}

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