"""Wasserman (2004), Chapter 23: Probability Redux: Stochastic Processes.

Companion code for Chapter 23 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 381-401, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch23-stochastic-processes.html):

* Section 23.2, Markov chains: n_step and marginal (the Chapman-Kolmogorov equations and
  mu_n = mu_0 P^n), stationary (solve pi P = pi), reach and communicating_classes (the classes of
  Theorem 23.12, with the convention p_ii(0) = 1), period (the gcd of the cycle lengths of a class,
  from breadth-first levels), classify (closed classes are recurrent, the others transient: Theorems
  23.16 and 23.17 for a finite chain), first_passage (the first-passage probabilities f_ij(n) of
  (23.12)-(23.13)), absorption (where a chain started in a transient state ends up), tv (total
  variation distance), coupling_times (the coupling behind the convergence theorem 23.25),
  simulate_chain, mle_transition (the maximum likelihood estimator n_ij / n_i and Theorem 23.31),
  hardy_weinberg (Example 23.29) and the random-walk Metropolis chain of Example 23.30.
* Example 23.18 and Polya's theorem: rw_u (exact return probabilities u_{2n} of the simple random walk
  in one, two and three dimensions, and of the biased walk in one dimension), first_return (the
  first-return probabilities, from the renewal equation u = f * u), watson_constant (the expected
  number of visits to the origin in three dimensions, in closed form).
* Section 23.3, Poisson processes: hpp_gaps (exponential gaps), hpp_uniform (a Poisson count, then
  sorted uniform times: the order-statistics property), ipp_thinning (an inhomogeneous process by
  thinning), chisq_homogeneity (the goodness-of-fit test of Example 23.36, with its likelihood ratio
  version) and web_hits (the simulated stand-in for the web server data of Figure 23.3).
* Exercises 23.1-23.16: branching_cdf (Exercise 23.5), two_state_power (Exercise 23.3) and the
  matrices of the exercises.
* JSRandom: the seeded generator of the browser demonstrations (DK.rng in courses/demo-kit.js), and
  Python twins of the three demonstrations (demo_markov, demo_rw, demo_pp), so that every number the
  pages show is reproduced here.

Figures. Figure 23.1 (a fictitious stock price) and Figure 23.2 (a chain that settles down and one
that does not) are simulated, as in the book; the series are new simulations, so they agree with the
book in kind, not point by point. Figure 23.3 shows hits on a web server; the book does not
distribute those data, so the figure is reproduced with a simulated inhomogeneous Poisson process of
the same size (about 1000 events in about 22 minutes) and the analysis of Example 23.36 is repeated on
it. Nothing is skipped. Five supplementary figures illustrate gaps filled in the notes:
  23.S1 convergence to the stationary distribution, two counterexamples, and the coupling inequality;
  23.S2 recurrence and transience of random walks in one, two and three dimensions (Polya);
  23.S3 the Poisson process: exponential gaps, uniform order statistics, thinning;
  23.S4 the sampling distribution of the transition-probability MLE (Theorem 23.31);
  23.S5 Exercises 23.4 (running proportions) and 23.5 (extinction of a branching process).
Run `python3 ch23_stochastic_processes.py --list`, `python3 ch23_stochastic_processes.py` (all eight
figures, about half a minute on one CPU thread) or `python3 ch23_stochastic_processes.py --fig 23.2`.
Files go to ../img/ch23/; the simulated web hits used by the Poisson process demo are written to
../data/ch23-hits.json by export_json() (run with the figures).
"""
import json
import math
import os

import numpy as np
from scipy import special, stats

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

CH = 23
M32 = 0xFFFFFFFF


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


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32, pos() a uniform in (0, 1), exp(mean) an exponential variable by inversion, and norm()
    the Box-Muller transform that keeps r sin(t) for the next call, exactly as in JavaScript."""

    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 pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def exp(self, mean):
        return -mean * math.log(self.pos())

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self.pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


def js_cumrows(P):
    """Row-wise cumulative sums, accumulated left to right as the demos do."""
    out = []
    for row in np.asarray(P, float):
        s, c = 0.0, []
        for v in row:
            s = s + float(v)
            c.append(s)
        out.append(c)
    return out


def js_draw(cum, u):
    """The demos' inverse-cdf draw: the first j with u < cum[j] (the last state if rounding leaves none)."""
    for j, c in enumerate(cum):
        if u < c:
            return j
    return len(cum) - 1


# =========================================================================== 23.2 the book's chains
WEATHER = np.array([[0.4, 0.6], [0.8, 0.2]])                                    # Example 23.8
CYCLE3 = np.array([[0, 1, 0], [0, 0, 1], [1, 0, 0]], float)                      # p. 390 and Example 23.27
EX13 = np.array([[1/3, 2/3, 0, 0], [2/3, 1/3, 0, 0], [1/4, 1/4, 1/4, 1/4], [0, 0, 0, 1]])   # Example 23.13
EX28 = np.array([[1/2, 1/2, 0, 0, 0, 0], [1/4, 3/4, 0, 0, 0, 0], [1/4, 1/4, 1/4, 1/4, 0, 0],
                 [1/4, 0, 1/4, 1/4, 0, 1/4], [0, 0, 0, 0, 1/2, 1/2], [0, 0, 0, 0, 1/2, 1/2]])  # Example 23.28
EX1 = np.array([[0.1, 0.2, 0.7], [0.9, 0.1, 0.0], [0.1, 0.8, 0.1]])               # Exercise 23.1
EX6 = np.array([[0.40, 0.50, 0.10], [0.05, 0.70, 0.25], [0.05, 0.50, 0.45]])      # Exercise 23.6
EX8 = np.array([[1/3, 0, 1/3, 0, 0, 1/3], [1/2, 1/4, 1/4, 0, 0, 0], [0, 0, 0, 0, 1, 0],
                [1/4, 1/4, 1/4, 0, 0, 1/4], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1]])           # Exercise 23.8


def random_walk_absorbing(N, p):
    """Example 23.7: the walk on {1, ..., N} that steps right with probability p, left with q = 1 - p,
    and stays at the two end points."""
    P = np.zeros((N, N))
    P[0, 0] = P[-1, -1] = 1.0
    for i in range(1, N - 1):
        P[i, i + 1], P[i, i - 1] = p, 1 - p
    return P


def ex2_matrix(py=(0.1, 0.3, 0.2, 0.4)):
    """Exercise 23.2: X_n = max(Y_1, ..., Y_n) with X_0 = 0; from i, stay with P(Y <= i), else jump to j > i
    with P(Y = j)."""
    py = np.asarray(py, float)
    K = len(py)
    P = np.zeros((K, K))
    for i in range(K):
        P[i, i] = py[: i + 1].sum()
        P[i, i + 1:] = py[i + 1:]
    return P


def ex10_matrix(p):
    """Exercise 23.10: from state k move to k + 1 with probability p, back to state 1 with q; state 5
    returns to 1."""
    q = 1 - p
    P = np.zeros((5, 5))
    for i in range(4):
        P[i, 0], P[i, i + 1] = q, p
    P[4, 0] = 1.0
    return P


def hardy_weinberg(Pa):
    """Example 23.29: genotype of successive descendants (AA, Aa, aa) when each child has one parent from
    the line and one random mate whose transmitted gene is A with probability Pa."""
    Qa = 1 - Pa
    return np.array([[Pa, Qa, 0.0], [Pa / 2, 0.5, Qa / 2], [0.0, Pa, Qa]])


def lazy(P, eps):
    """The lazy chain eps I + (1 - eps) P: same stationary distributions, every state aperiodic if eps > 0."""
    return eps * np.eye(len(P)) + (1 - eps) * np.asarray(P, float)


# =========================================================================== 23.2 basic computations
def check_stochastic(P, tol=1e-12):
    P = np.asarray(P, float)
    return bool(np.all(P >= -tol) and np.allclose(P.sum(1), 1.0, atol=tol))


def n_step(P, n):
    """The n-step transition matrix P_n = P^n (Chapman-Kolmogorov, (23.6)-(23.7))."""
    return np.linalg.matrix_power(np.asarray(P, float), n)


def marginal(mu0, P, n):
    """mu_n = mu_0 P^n (Lemma 23.10)."""
    return np.asarray(mu0, float) @ n_step(P, n)


def stationary(P):
    """A stationary distribution: solve pi (P - I) = 0 with sum(pi) = 1 (unique when the chain has one
    closed class). The last balance equation is replaced by the normalisation."""
    P = np.asarray(P, float)
    K = len(P)
    A = (P - np.eye(K)).T.copy()
    A[-1, :] = 1.0
    b = np.zeros(K)
    b[-1] = 1.0
    return np.linalg.solve(A, b)


def reach(P):
    """R[i, j] = True when i -> j, i.e. p_ij(n) > 0 for some n >= 0 (so R[i, i] is always True)."""
    R = (np.asarray(P) > 0) | np.eye(len(P), dtype=bool)
    for k in range(len(P)):                                  # Warshall's transitive closure
        R = R | (R[:, [k]] & R[[k], :])
    return R


def communicating_classes(P):
    """The equivalence classes of i <-> j (Theorem 23.12), each sorted, in order of their first state."""
    R = reach(P)
    C = R & R.T
    seen, out = set(), []
    for i in range(len(P)):
        if i not in seen:
            cls = [j for j in range(len(P)) if C[i, j]]
            seen.update(cls)
            out.append(cls)
    return out


def is_closed(P, cls):
    P = np.asarray(P)
    out = [j for j in range(len(P)) if j not in cls]
    return bool(np.all(P[np.ix_(cls, out)] == 0)) if out else True


def period(P, cls):
    """The period of a communicating class: gcd of level(u) + 1 - level(v) over the edges u -> v inside
    the class, with breadth-first levels from its first state. (Every closed walk has a length that is
    a sum of such terms, and the terms are themselves differences of walk lengths.)"""
    P = np.asarray(P)
    cls = list(cls)
    level = {cls[0]: 0}
    frontier = [cls[0]]
    while frontier:
        nxt = []
        for u in frontier:
            for v in cls:
                if P[u, v] > 0 and v not in level:
                    level[v] = level[u] + 1
                    nxt.append(v)
        frontier = nxt
    g = 0
    for u in cls:
        for v in cls:
            if P[u, v] > 0:
                g = math.gcd(g, abs(level[u] + 1 - level[v]))
    return g


def period_bruteforce(P, i, nmax=60):
    """gcd{n <= nmax : p_ii(n) > 0}, straight from the definition (for checking period())."""
    Q = (np.asarray(P) > 0).astype(int)
    M = np.eye(len(P), dtype=int)
    g = 0
    for n in range(1, nmax + 1):
        M = np.minimum(M @ Q, 1)
        if M[i, i]:
            g = math.gcd(g, n)
    return g


def classify(P):
    """For a finite chain: each communicating class, whether it is closed (then recurrent and positive,
    Theorem 23.16(3)-(4) and Lemma 23.20) or not (then transient), and its period."""
    out = []
    for c in communicating_classes(P):
        closed = is_closed(P, c)
        d = period(P, c)                      # 0: the class is a single state that can never return (no period)
        out.append({"states": c, "closed": closed, "recurrent": closed, "period": d if d > 0 else None})
    return out


def first_passage(P, i, j, nmax):
    """f_ij(n) = P(X_1 != j, ..., X_{n-1} != j, X_n = j | X_0 = i), n = 1..nmax: kill the chain on entering
    j (taboo matrix Q with column j set to 0) and read the probability of stepping into j."""
    P = np.asarray(P, float)
    Q = P.copy()
    Q[:, j] = 0.0
    v = np.zeros(len(P))
    v[i] = 1.0
    f = np.empty(nmax)
    for n in range(nmax):
        f[n] = v @ P[:, j]
        v = v @ Q
    return f


def expected_visits(P, i, nmax):
    """sum_{n=0}^{nmax} p_ii(n), the expected number of visits to i (counting time 0) up to time nmax."""
    P = np.asarray(P, float)
    v = np.zeros(len(P))
    v[i] = 1.0
    s = 0.0
    for _ in range(nmax + 1):
        s += v[i]
        v = v @ P
    return s


def absorption(P, mu0, n=4000):
    """The limit of mu_n for an aperiodic finite chain (mu_0 P^n for large n)."""
    return marginal(mu0, P, n)


def tv(mu, nu):
    """Total variation distance max_A |mu(A) - nu(A)| = (1/2) sum |mu - nu|."""
    return 0.5 * float(np.abs(np.asarray(mu, float) - np.asarray(nu, float)).sum())


def tv_curve(P, mu0, target, N):
    """d_n = TV(mu_0 P^n, target) for n = 0..N."""
    mu = np.asarray(mu0, float).copy()
    out = []
    for _ in range(N + 1):
        out.append(tv(mu, target))
        mu = mu @ P
    return np.array(out)


def simulate_chain(P, x0, n, rng):
    """X_0 = x0, X_1, ..., X_n by inverse-cdf draws from the rows of P (numpy generator)."""
    cum = np.cumsum(np.asarray(P, float), axis=1)
    x = np.empty(n + 1, dtype=int)
    x[0] = x0
    u = rng.random(n)
    for t in range(n):
        x[t + 1] = min(int(np.searchsorted(cum[x[t]], u[t], side="right")), len(P) - 1)
    return x


def simulate_chains(P, x0, n, R, rng):
    """R independent chains of length n + 1 at once (array R x (n + 1))."""
    cum = np.cumsum(np.asarray(P, float), axis=1)
    X = np.empty((R, n + 1), dtype=int)
    X[:, 0] = x0
    for t in range(n):
        u = rng.random(R)
        X[:, t + 1] = np.minimum((u[:, None] >= cum[X[:, t]]).sum(1), len(P) - 1)
    return X


def coupling_times_np(P, x0, target, N, R, rng):
    """Independent coupling: X from x0 and Y from target move independently until they meet (then
    together). Returns the meeting times (np.inf if not met by N)."""
    cum = np.cumsum(np.asarray(P, float), axis=1)
    K = len(P)
    x = np.full(R, x0)
    y = np.minimum((rng.random(R)[:, None] >= np.cumsum(target)).sum(1), K - 1)
    T = np.where(x == y, 0.0, np.inf)
    for t in range(1, N + 1):
        live = ~np.isfinite(T)
        if not live.any():
            break
        ux, uy = rng.random(R), rng.random(R)
        x = np.where(live, np.minimum((ux[:, None] >= cum[x]).sum(1), K - 1), x)
        y = np.where(live, np.minimum((uy[:, None] >= cum[y]).sum(1), K - 1), y)
        T[live & (x == y)] = t
    return T


def mle_transition(x, K):
    """Counts n_ij of the observed transitions and the MLE p_ij = n_ij / n_i (rows with n_i = 0 set to 0,
    the book's convention)."""
    x = np.asarray(x)
    n = np.zeros((K, K))
    np.add.at(n, (x[:-1], x[1:]), 1)
    ni = n.sum(1, keepdims=True)
    with np.errstate(invalid="ignore", divide="ignore"):
        ph = np.where(ni > 0, n / np.where(ni > 0, ni, 1), 0.0)
    return n, ph


def loglik_transition(P, x):
    x = np.asarray(x)
    return float(np.log(np.asarray(P)[x[:-1], x[1:]]).sum())


def metropolis_rw(logg, x0, b, n, rng):
    """Example 23.30: the random-walk Metropolis chain with proposal N(x, b^2) and acceptance min(g(W)/g(x), 1)."""
    x = np.empty(n + 1)
    x[0] = x0
    acc = 0
    for i in range(n):
        w = x[i] + b * rng.standard_normal()
        if math.log(rng.random()) < logg(w) - logg(x[i]):
            x[i + 1] = w
            acc += 1
        else:
            x[i + 1] = x[i]
    return x, acc / n


def two_state_power(a, b, n):
    """Exercise 23.3: P^n = (1/(a+b)) [[b, a], [b, a]] + (1-a-b)^n/(a+b) [[a, -a], [-b, b]]."""
    s = a + b
    return (np.array([[b, a], [b, a]]) + (1 - s) ** n * np.array([[a, -a], [-b, b]])) / s


# =========================================================================== random walks (Example 23.18, Polya)
def rw_u(d, K, p=0.5):
    """u[k] = P(S_{2k} = 0 | S_0 = 0), k = 0..K, for the simple random walk on Z^d (d = 1, 2, 3), or for
    the walk on Z that steps +1 with probability p (d = 1)."""
    k = np.arange(K + 1)
    if d == 1:
        # C(2k, k) (pq)^k through logs
        return np.exp(special.gammaln(2 * k + 1) - 2 * special.gammaln(k + 1) + k * math.log(p * (1 - p)))
    if d == 2:
        return np.exp(2 * (special.gammaln(2 * k + 1) - 2 * special.gammaln(k + 1) - k * math.log(4.0)))
    if d == 3:
        # closed walks of length 2n on Z^3: C(2n, n) sum_j C(n, j)^2 C(2j, j); divide by 6^(2n)
        out = np.empty(K + 1)
        for n in range(K + 1):
            j = np.arange(n + 1)
            lt = 2 * (special.gammaln(n + 1) - special.gammaln(j + 1) - special.gammaln(n - j + 1)) \
                + special.gammaln(2 * j + 1) - 2 * special.gammaln(j + 1)
            m = lt.max()
            out[n] = math.exp(special.gammaln(2 * n + 1) - 2 * special.gammaln(n + 1) - 2 * n * math.log(6.0)
                              + m + math.log(np.exp(lt - m).sum()))
        return out
    raise ValueError("d must be 1, 2 or 3")


def rw_u_bruteforce(d, K):
    """u[k] for small K by propagating the exact distribution of the walk on a grid (for checking rw_u)."""
    size = 2 * (2 * K) + 1
    c = 2 * K
    shape = (size,) * d
    prob = np.zeros(shape)
    prob[(c,) * d] = 1.0
    out = [1.0]
    for step in range(1, 2 * K + 1):
        new = np.zeros(shape)
        for ax in range(d):
            new += (np.roll(prob, 1, axis=ax) + np.roll(prob, -1, axis=ax)) / (2 * d)
        prob = new
        if step % 2 == 0:
            out.append(prob[(c,) * d])
    return np.array(out)


def first_return(u):
    """First-return probabilities f[k] = P(first return to 0 at time 2k), from the renewal equation
    u_k = sum_{m=1}^{k} f_m u_{k-m} (k >= 1). f[0] = 0."""
    K = len(u) - 1
    f = np.zeros(K + 1)
    for k in range(1, K + 1):
        f[k] = u[k] - np.dot(f[1:k], u[k - 1:0:-1])
    return f


def watson_constant():
    """sum_n P(S_n = 0) for the simple random walk on Z^3 (Watson 1939):
    sqrt(6)/(32 pi^3) Gamma(1/24) Gamma(5/24) Gamma(7/24) Gamma(11/24) = 1.516386..."""
    g = special.gamma
    return math.sqrt(6) / (32 * math.pi ** 3) * g(1 / 24) * g(5 / 24) * g(7 / 24) * g(11 / 24)


# =========================================================================== 23.3 Poisson processes
def hpp_gaps(lam, T, rng):
    """Homogeneous Poisson process on [0, T]: add exponential gaps of mean 1/lam until T is passed."""
    out, t = [], 0.0
    while True:
        t += rng.exponential(1.0 / lam)
        if t > T:
            return np.array(out)
        out.append(t)


def hpp_uniform(lam, T, rng):
    """The same law built the other way: N(T) ~ Poisson(lam T), then N sorted Uniform(0, T) times."""
    n = rng.poisson(lam * T)
    return np.sort(rng.uniform(0, T, n))


def ipp_thinning(lam_fun, lam_max, T, rng):
    """Inhomogeneous Poisson process with intensity lam_fun <= lam_max on [0, T], by thinning a
    homogeneous process of rate lam_max (keep a point at t with probability lam_fun(t)/lam_max)."""
    cand = hpp_gaps(lam_max, T, rng)
    keep = rng.random(len(cand)) < lam_fun(cand) / lam_max
    return cand[keep]


def chisq_homogeneity(times, T, k=4):
    """Example 23.36: given N events on [0, T], a homogeneous process puts each in any of k equal bins
    with probability 1/k. Returns observed and expected counts, Pearson's statistic, its chi^2_{k-1}
    p-value, the likelihood ratio statistic G^2 and its p-value."""
    times = np.asarray(times, float)
    O = np.histogram(times, bins=np.linspace(0, T, k + 1))[0].astype(float)
    n = O.sum()
    E = np.full(k, n / k)
    X2 = float(((O - E) ** 2 / E).sum())
    G2 = float(2 * np.sum(np.where(O > 0, O * np.log(np.where(O > 0, O, 1) / E), 0.0)))
    return {"O": O, "E": E, "n": int(n), "X2": X2, "p": float(stats.chi2.sf(X2, k - 1)),
            "G2": G2, "pG2": float(stats.chi2.sf(G2, k - 1)), "df": k - 1}


# the simulated web server: about 1000 hits in 1300 seconds, with a lull in the middle (rates per second)
WEB_T = 1300.0


def web_intensity(t):
    t = np.asarray(t, float)
    return 0.05 + 1.6 * np.exp(-((t - 230.0) / 210.0) ** 2) + 1.25 * np.exp(-((t - 1130.0) / 175.0) ** 2) \
        + 0.45 * np.exp(-((t - 870.0) / 50.0) ** 2)


WEB_MAX = 1.7


def web_hits(seed=2343):
    """The simulated stand-in for the web hits of Figure 23.3 (times in seconds, rounded to 0.01 s)."""
    rng = np.random.default_rng(seed)
    x = ipp_thinning(web_intensity, WEB_MAX, WEB_T, rng)
    return np.round(x, 2)


def branching_cdf(pk, nmax):
    """Exercise 23.5(d): F(n) = P(extinct by generation n) = G(F(n-1)), G the offspring pgf, F(0) = 0."""
    pk = np.asarray(pk, float)
    F = [0.0]
    for _ in range(nmax):
        F.append(float(np.polyval(pk[::-1], F[-1])))
    return np.array(F)


# =========================================================================== Python twins of the demos
DEMO_CHAINS = {"weather": WEATHER, "ex6": EX6, "cycle": CYCLE3, "ex13": EX13, "ex28": EX28,
               "hw": hardy_weinberg(0.7)}


def demo_markov(chain="weather", eps=0.0, start=0, N=30, M=2000, seed=1):
    """The Markov-convergence demo: classes, target distribution, d_n = TV(mu_n, target) for n = 0..N,
    and the coupling estimate of P(T > n), with the demo's generator and draw order."""
    P = lazy(DEMO_CHAINS[chain], eps)
    K = len(P)
    cl = classify(P)
    closed = [c for c in cl if c["closed"]]
    mu0 = np.zeros(K)
    mu0[start] = 1.0
    if len(closed) == 1:
        target = stationary(P)
    else:
        target = js_power_limit(P, mu0)
    d = tv_curve(P, mu0, target, N)
    cumP, cumT = js_cumrows(P), js_cumrows([target])[0]
    rng = JSRandom(seed)
    Ts = []
    for _ in range(M):
        x = start
        y = js_draw(cumT, rng.u())
        t = 0
        while x != y and t < N:
            x = js_draw(cumP[x], rng.u())
            y = js_draw(cumP[y], rng.u())
            t += 1
        Ts.append(t if x == y else math.inf)
    Ts = np.array(Ts)
    PT = np.array([(Ts > n).mean() for n in range(N + 1)])
    met = np.isfinite(Ts)
    return {"P": P, "classes": cl, "target": target, "d": d, "PT": PT, "fracMet": float(met.mean()),
            "meanT": float(Ts[met].mean()) if met.any() else float("nan")}


def js_power_limit(P, mu0, n=5000):
    """The demo's limit for chains with several closed classes: mu_0 P^n by repeated vector products."""
    mu = np.asarray(mu0, float).copy()
    for _ in range(n):
        mu = mu @ P
    return mu


RW_LIMITS = {1: 1.0, 2: 1.0}


def demo_rw(d=1, p=0.5, T=1000, M=500, seed=1):
    """The random-walk demo: exact expected returns and P(returned by t) at even t, and the demo's Monte
    Carlo (one uniform per step; d = 1: +1 if u < p; d = 2, 3: axis floor(2 d u) // 2, minus sign when it is odd)."""
    K = T // 2
    u = rw_u(d, K, p)
    f = first_return(u)
    exact_ret = np.cumsum(u[1:])                # expected returns by time 2k, k = 1..K
    exact_hit = np.cumsum(f[1:])                # P(returned by 2k)
    rng = JSRandom(seed)
    at0 = np.zeros(T + 1)
    first = np.zeros(T + 1)
    for _ in range(M):
        pos = [0] * d
        returned = False
        for t in range(1, T + 1):
            r = rng.u()
            if d == 1:
                pos[0] += 1 if r < p else -1
            else:
                kk = int(math.floor(r * 2 * d))
                pos[kk >> 1] += -1 if (kk & 1) else 1
            if not any(pos):
                at0[t] += 1
                if not returned:
                    returned = True
                    first[t] += 1
    mc_ret = np.cumsum(at0) / M
    mc_hit = np.cumsum(first) / M
    return {"u": u, "f": f, "exact_ret": exact_ret, "exact_hit": exact_hit, "mc_ret": mc_ret, "mc_hit": mc_hit}


def js_rpois(m, rng):
    """The demo's Poisson sampler: a sum of Poisson(c) draws with c <= 20, each by sequential inversion."""
    n = 0
    while m > 0:
        c = min(m, 20.0)
        m -= c
        u = rng.u()
        k = 0
        pk = math.exp(-c)
        cdf = pk
        while u > cdf and k < 1000:
            k += 1
            pk *= c / k
            cdf += pk
        n += k
    return n


def js_pp_once(mode, o, rng):
    """One realisation in the Poisson demo: returns (times, labels) with labels 0 or 1."""
    T = o["T"]
    if mode in ("gaps", "split", "data"):
        lam = o["lam"]
        times, t = [], 0.0
        while True:
            t += rng.exp(1.0 / lam)
            if t > T:
                break
            times.append(t)
        if mode == "split":
            lab = [0 if rng.u() < o["p"] else 1 for _ in times]
            return times, lab
        return times, [0] * len(times)
    if mode == "uniform":
        n = js_rpois(o["lam"] * T, rng)
        times = sorted(T * rng.u() for _ in range(n))
        return times, [0] * n
    if mode == "inhom":
        lam, a = o["lam"], o["a"]
        lmax = lam * (1 + a)
        times, t = [], 0.0
        while True:
            t += rng.exp(1.0 / lmax)
            if t > T:
                break
            if rng.u() < (1 + a * math.sin(2 * math.pi * t / T)) / (1 + a):
                times.append(t)
        return times, [0] * len(times)
    if mode == "super":
        out = []
        for lab, lam in ((0, o["lam"]), (1, o["nu"])):
            t = 0.0
            while True:
                t += rng.exp(1.0 / lam)
                if t > T:
                    break
                out.append((t, lab))
        out.sort()
        return [a for a, _ in out], [b for _, b in out]
    raise ValueError(mode)


def demo_pp(mode="gaps", lam=0.5, T=100.0, p=0.3, nu=0.5, a=0.8, k=4, R=500, seed=1, data=None):
    """The Poisson-process demo: replicate 0 is shown (or the data, for mode 'data', whose replicates are
    simulated from the fitted homogeneous model); summaries over the R replicates: counts (and the two
    colours), gaps (of the kept points when thinning), the chi-squared test of homogeneity with k bins and
    its rejection rate at the 5% level."""
    o = {"lam": lam, "T": T, "p": p, "nu": nu, "a": a}
    rng = JSRandom(seed)
    if mode == "data":
        o["lam"] = len(data) / T
    reps = [js_pp_once(mode, o, rng) for _ in range(R)]
    shown = (list(data), [0] * len(data)) if mode == "data" else reps[0]
    counts = np.array([len(r[0]) for r in reps], float)
    nA = np.array([sum(1 for l in r[1] if l == 0) for r in reps], float)
    nB = counts - nA
    gsrc = [[t for t, l in zip(*r) if l == 0] for r in reps] if mode == "split" else [r[0] for r in reps]
    if mode == "data":                        # the gap summaries describe the data themselves
        gsrc = [list(data)]
    gaps = np.concatenate([np.diff(np.r_[0.0, g]) for g in gsrc])
    rej = np.mean([chisq_homogeneity(r[0], T, k)["p"] < 0.05 for r in reps if len(r[0]) > 0])
    test = chisq_homogeneity(shown[0], T, k)
    corr = float(np.corrcoef(nA, nB)[0, 1]) if nB.std() > 0 and nA.std() > 0 else float("nan")
    return {"shown": shown, "counts": counts, "nA": nA, "nB": nB, "gaps": gaps, "rej": float(rej), "test": test,
            "meanN": float(counts.mean()), "varN": float(counts.var(ddof=1)), "meanA": float(nA.mean()),
            "meanB": float(nB.mean()), "corrAB": corr, "meanGap": float(gaps.mean()), "sdGap": float(gaps.std(ddof=1))}


# =========================================================================== figures
def fig_23_1(out_dir=None):
    """Figure 23.1: a fictitious stock price over ten weeks (simulated)."""
    rng = np.random.default_rng(231)
    n = 10 * 5 * 78                                    # ten weeks of five trading days, 78 five-minute prices a day
    t = np.arange(n) / (5 * 78)                        # time in weeks
    slow = np.cumsum(rng.normal(0, 0.035, n))          # a slowly drifting level (a random walk)
    fast = np.zeros(n)
    z = rng.normal(0, 0.9, n)
    for i in range(1, n):                              # fast mean-reverting fluctuations: AR(1)
        fast[i] = 0.55 * fast[i - 1] + z[i]
    price = 40 + slow + fast
    fig, ax = common.plt.subplots(figsize=(6.2, 2.9))
    ax.plot(t, price, color="k", lw=0.45)
    ax.set_xlabel("time (weeks)")
    ax.set_ylabel("price")
    ax.set_xlim(0, 10)
    ax.set_title("A fictitious stock price, recorded every five trading minutes", fontsize=9.5)
    return savefig(fig, CH, "fig23-1", out_dir)


def fig_23_2(out_dir=None):
    """Figure 23.2: a random walk (no equilibrium) and an AR(1) chain (settles down)."""
    rng = np.random.default_rng(232)
    n = 1000
    z1, z2 = rng.normal(size=n), rng.normal(size=n)
    rw = np.concatenate([[0.0], np.cumsum(z1)])
    ar = np.empty(n + 1)
    ar[0] = 25.0
    for i in range(n):
        ar[i + 1] = 0.5 * ar[i] + z2[i]
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.3))
    for j, (x, nm) in enumerate(((rw, "random walk  $X_n=X_{n-1}+Z_n$"), (ar, "AR(1)  $X_n=0.5X_{n-1}+Z_n$, $X_0=25$"))):
        ax = axes[0, j]
        ax.plot(np.arange(n + 1), x, color="k", lw=0.6)
        ax.set_title(nm, fontsize=9)
        ax.set_xlabel("time $n$")
        common.panel_label(ax, "abcd"[j], loc="lower right" if j == 0 else "upper right")
        ax2 = axes[1, j]
        h1, h2 = x[1:501], x[501:]
        lo, hi = min(x[50:].min(), -4) - 0.5, max(x[50:].max(), 4) + 0.5
        bins = np.linspace(lo, hi, 40)
        ax2.hist(h1, bins=bins, density=True, color=BLUE, alpha=0.5, label="$n=1..500$")
        ax2.hist(h2, bins=bins, density=True, color=RED, alpha=0.5, label="$n=501..1000$")
        if j == 1:
            g = np.linspace(-5, 5, 300)
            ax2.plot(g, stats.norm.pdf(g, 0, math.sqrt(4 / 3)), color="k", lw=1.3, label=r"$\pi=N(0,4/3)$")
            ax2.set_xlim(-5.5, 5.5)
        ax2.legend(fontsize=7, frameon=False, loc="upper left")
        ax2.set_xlabel("$x$")
        ax2.set_yticks([])
        common.panel_label(ax2, "abcd"[j + 2], loc="upper right")
    axes[1, 0].set_title("histograms of the two halves differ", fontsize=9)
    axes[1, 1].set_title("histograms agree with $\\pi$", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig23-2", out_dir)


def fig_23_3(out_dir=None):
    """Figure 23.3: hits on a web server (simulated inhomogeneous Poisson process) and the test of Example 23.36."""
    x = web_hits()
    res = chisq_homogeneity(x, WEB_T, 4)
    fig, (ax, ax2) = common.plt.subplots(2, 1, figsize=(6.4, 3.4), gridspec_kw={"height_ratios": [1.0, 1.2]}, sharex=True)
    ax.vlines(x, 0, 1, color="k", lw=0.35)
    ax.set_yticks([])
    ax.set_ylim(0, 1)
    ax.set_title("%d simulated hits in %.0f s;  $\\hat\\lambda=N/T=%.2f$ per minute" % (len(x), WEB_T, 60 * len(x) / WEB_T),
                 fontsize=9)
    edges = np.linspace(0, WEB_T, 5)
    for i in range(4):
        ax2.bar((edges[i] + edges[i + 1]) / 2, res["O"][i] / (WEB_T / 4) * 60, width=WEB_T / 4 * 0.96, color=BLUE,
                alpha=0.35, edgecolor=BLUE)
        ax2.text((edges[i] + edges[i + 1]) / 2, 5, "$O_%d=%d$" % (i + 1, res["O"][i]), ha="center", fontsize=8)
    g = np.linspace(0, WEB_T, 600)
    ax2.plot(g, 60 * web_intensity(g), color=RED, lw=1.4, label=r"true intensity $\lambda(t)$")
    ax2.axhline(60 * len(x) / WEB_T, color="k", ls="--", lw=1, label=r"fitted constant $\hat\lambda$")
    ax2.set_ylabel("hits per minute")
    ax2.set_xlabel("time (seconds)")
    ax2.set_xlim(0, WEB_T)
    ax2.legend(fontsize=7.5, frameon=False, loc="upper center", ncol=2)
    ax2.set_ylim(0, 125)
    mant, ex = ("%.1e" % res["p"]).split("e")
    ax2.set_title("four equal bins: $\\chi^2=%.0f$ on 3 df, $p=%s\\times10^{%d}$" % (res["X2"], mant, int(ex)), fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig23-3", out_dir)


def fig_23_s1(out_dir=None):
    """Figure 23.S1: convergence to pi, two counterexamples, and the coupling inequality."""
    fig, axes = common.panel_grid(1, 3, size=(3.1, 2.7))
    ax = axes[0, 0]
    N = 40
    for P, nm, col in ((WEATHER, "weather (Ex. 23.8)", BLUE), (EX6, "Exercise 23.6", GREEN),
                       (lazy(CYCLE3, 0.2), "3-cycle, laziness 0.2", ORANGE), (hardy_weinberg(0.7), "Hardy-Weinberg, $P=0.7$", PURPLE)):
        d = tv_curve(P, np.eye(len(P))[0], stationary(P), N)
        keep = d > 1e-15
        ax.semilogy(np.arange(N + 1)[keep], d[keep], "o-", ms=2.2, lw=1, color=col, label=nm)
    d = tv_curve(CYCLE3, [1, 0, 0], np.ones(3) / 3, N)
    ax.semilogy(np.arange(N + 1), d, "-", lw=1.2, color=RED, label="3-cycle (periodic)")
    ax.set_ylim(1e-15, 2)
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"$\|\mu_n-\pi\|_{TV}$")
    ax.legend(fontsize=6.4, frameon=False, loc="lower left")
    common.panel_label(ax, "a", loc="upper right")
    ax = axes[0, 1]
    n = np.arange(31)
    mu1 = np.array([marginal([1, 0, 0], CYCLE3, k)[0] for k in n])
    ax.plot(n, mu1, "o", ms=2.5, color=RED, label=r"3-cycle: $\mu_n(1)$")
    ax.plot(n, np.cumsum(mu1) / (n + 1), "-", color=RED, lw=1, label=r"3-cycle: Cesaro average")
    m28 = np.array([marginal(np.eye(6)[2], EX28, k) for k in n])
    ax.plot(n, m28[:, :2].sum(1), "-", color=BLUE, lw=1.4, label=r"Ex. 23.28 from 3: $\mu_n\{1,2\}$")
    ax.plot(n, m28[:, 4:].sum(1), "--", color=BLUE, lw=1.4, label=r"Ex. 23.28 from 3: $\mu_n\{5,6\}$")
    ax.set_ylim(-0.05, 1.75)
    ax.set_xlabel("$n$")
    ax.legend(fontsize=6.2, frameon=False, loc="upper right", ncol=1)
    common.panel_label(ax, "b", loc="upper left")
    ax = axes[0, 2]
    rng = np.random.default_rng(2301)
    for P, nm, col in ((EX6, "Exercise 23.6", GREEN), (lazy(CYCLE3, 0.2), "lazy 3-cycle", ORANGE)):
        pi = stationary(P)
        T = coupling_times_np(P, 0, pi, 40, 20000, rng)
        nn = np.arange(41)
        ax.step(nn, [(T > k).mean() for k in nn], where="post", color=col, lw=1.2, label=r"$P(T>n)$, " + nm)
        ax.plot(nn, tv_curve(P, np.eye(3)[0], pi, 40), "o", ms=2.2, color=col, label=r"$d_n$, " + nm)
    ax.set_yscale("log")
    ax.set_ylim(1e-4, 60)
    ax.set_xlabel("$n$")
    ax.legend(fontsize=6.2, frameon=False, loc="upper right", ncol=1)
    common.panel_label(ax, "c", loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig23-S1", out_dir)


def fig_23_s2(out_dir=None):
    """Figure 23.S2: expected returns and return probabilities of random walks (Polya's theorem)."""
    K = 5000
    cases = [(1, 0.5, "$d=1$", BLUE), (2, 0.5, "$d=2$", GREEN), (3, 0.5, "$d=3$", RED), (1, 0.6, "$d=1$, $p=0.6$", ORANGE)]
    fig, axes = common.panel_grid(1, 2, size=(3.6, 2.8))
    t = 2 * np.arange(1, K + 1)
    for d, p, nm, col in cases:
        u = rw_u(d, K, p)
        f = first_return(u)
        axes[0, 0].loglog(t, np.cumsum(u[1:]), color=col, lw=1.4, label=nm)
        axes[0, 1].semilogx(t, np.cumsum(f[1:]), color=col, lw=1.4, label=nm)
    w = watson_constant()
    axes[0, 0].axhline(w - 1, color=RED, ls=":", lw=1)
    axes[0, 0].axhline(4.0, color=ORANGE, ls=":", lw=1)
    axes[0, 0].set_xlabel("time $t$")
    axes[0, 0].set_title("expected number of returns by time $t$", fontsize=9)
    axes[0, 0].legend(fontsize=7, frameon=False, loc="upper left")
    axes[0, 1].axhline(1 - 1 / w, color=RED, ls=":", lw=1)
    axes[0, 1].axhline(0.8, color=ORANGE, ls=":", lw=1)
    axes[0, 1].axhline(1.0, color=GREY, ls=":", lw=1)
    axes[0, 1].set_ylim(0, 1.05)
    axes[0, 1].set_xlabel("time $t$")
    axes[0, 1].set_title("$P$(back at the origin by time $t$)", fontsize=9)
    axes[0, 1].legend(fontsize=7, frameon=False, loc="upper left", ncol=2)
    axes[0, 1].set_ylim(0, 1.18)
    common.panel_label(axes[0, 0], "a", loc="lower right")
    common.panel_label(axes[0, 1], "b", loc="lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig23-S2", out_dir)


def fig_23_s3(out_dir=None):
    """Figure 23.S3: the Poisson process: a path, exponential gaps, uniform order statistics, thinning."""
    rng = np.random.default_rng(2303)
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.5))
    ax = axes[0, 0]
    lam, T = 1.0, 20.0
    w = hpp_gaps(lam, T, rng)
    ax.step(np.r_[0, w, T], np.r_[0, np.arange(1, len(w) + 1), len(w)], where="post", color="k", lw=1.2, label="$X(t)$")
    ax.plot([0, T], [0, lam * T], "--", color=RED, lw=1, label=r"$m(t)=\lambda t$")
    ax.vlines(w, -1.6, -0.4, color=BLUE, lw=0.8)
    ax.set_ylim(-2, len(w) + 3)
    ax.set_xlabel("$t$")
    ax.legend(fontsize=7, frameon=False, loc="lower right", bbox_to_anchor=(1.0, 0.08))
    common.panel_label(ax, "a", loc="upper left")
    ax = axes[0, 1]
    gaps = np.concatenate([np.diff(np.r_[0, hpp_gaps(lam, 200.0, rng)]) for _ in range(50)])
    ax.hist(gaps, bins=np.linspace(0, 6, 31), density=True, color=BLUE, alpha=0.5, label="gaps (%d)" % len(gaps))
    g = np.linspace(0, 6, 200)
    ax.plot(g, lam * np.exp(-lam * g), color=RED, lw=1.4, label=r"$\lambda e^{-\lambda s}$")
    ax.set_xlabel("interarrival time $s$")
    ax.legend(fontsize=7, frameon=False, loc="center right")
    common.panel_label(ax, "b", loc="upper right")
    ax = axes[1, 0]
    # given N(10) = 5, the 3rd arrival time is 10 x Beta(3, 3)
    w3 = []
    while len(w3) < 4000:
        x = hpp_gaps(0.5, 10.0, rng)
        if len(x) == 5:
            w3.append(x[2])
    ax.hist(w3, bins=np.linspace(0, 10, 26), density=True, color=GREEN, alpha=0.5, label=r"$W_3$ given $X(10)=5$")
    g = np.linspace(0, 10, 200)
    ax.plot(g, stats.beta.pdf(g / 10, 3, 3) / 10, color="k", lw=1.4, label=r"$10\,\mathrm{Beta}(3,3)$")
    ax.set_xlabel("$t$")
    ax.legend(fontsize=7, frameon=False, loc="upper right")
    ax.set_ylim(0, 0.27)
    common.panel_label(ax, "c", loc="upper left")
    ax = axes[1, 1]
    lam, p, T = 2.0, 0.3, 10.0
    NA, NB = [], []
    for _ in range(3000):
        x = hpp_gaps(lam, T, rng)
        a = rng.random(len(x)) < p
        NA.append(a.sum())
        NB.append((~a).sum())
    NA, NB = np.array(NA), np.array(NB)
    jit = rng.uniform(-0.25, 0.25, (2, len(NA)))
    ax.plot(NA + jit[0], NB + jit[1], ".", ms=1.2, color=PURPLE, alpha=0.5)
    ax.set_xlabel(r"kept, $\sim$ Poisson$(\lambda pT=%g)$" % (lam * p * T))
    ax.set_ylabel(r"discarded, $\sim$ Poisson$(%g)$" % (lam * (1 - p) * T))
    ax.set_title("thinning: correlation %.3f" % np.corrcoef(NA, NB)[0, 1], fontsize=8.5)
    common.panel_label(ax, "d", loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig23-S3", out_dir)


def mle_sampling(a=0.1, b=0.3, n=500, R=4000, seed=2304):
    """Replicates of the MLE of p_12 = a in the two-state chain (start in state 1): returns p-hat and N_1."""
    rng = np.random.default_rng(seed)
    X = simulate_chains(np.array([[1 - a, a], [b, 1 - b]]), 0, n, R, rng)
    prev, nxt = X[:, :-1], X[:, 1:]
    N1 = (prev == 0).sum(1)
    n12 = ((prev == 0) & (nxt == 1)).sum(1)
    return n12 / np.maximum(N1, 1), N1


def fig_23_s4(out_dir=None):
    """Figure 23.S4: Theorem 23.31 for the chain of Exercise 23.4 (p_12 = 0.1)."""
    a, b = 0.1, 0.3
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.7))
    ph, N1 = mle_sampling(a, b, 500, 4000)
    z = np.sqrt(N1) * (ph - a) / math.sqrt(a * (1 - a))
    ax = axes[0, 0]
    ax.hist(z, bins=np.linspace(-4, 4, 33), density=True, color=BLUE, alpha=0.5, label=r"$\sqrt{N_1}(\hat p_{12}-p_{12})/\sqrt{p_{12}(1-p_{12})}$")
    g = np.linspace(-4, 4, 200)
    ax.plot(g, stats.norm.pdf(g), color=RED, lw=1.4, label="$N(0,1)$")
    ax.set_title("$n=500$, 4000 replicates", fontsize=9)
    ax.legend(fontsize=6.5, frameon=False, loc="upper left")
    ax.set_ylim(0, 0.62)
    common.panel_label(ax, "a", loc="upper right")
    ax = axes[0, 1]
    ns = [50, 100, 200, 500, 1000, 2000]
    covN, covn = [], []
    for nn in ns:
        ph, N1 = mle_sampling(a, b, nn, 4000, seed=2305 + nn)
        se = np.sqrt(ph * (1 - ph) / np.maximum(N1, 1))
        covN.append(np.mean(np.abs(ph - a) <= 1.96 * se))
        se2 = np.sqrt(ph * (1 - ph) / nn)
        covn.append(np.mean(np.abs(ph - a) <= 1.96 * se2))
    ax.semilogx(ns, covN, "o-", color=BLUE, lw=1.2, label=r"$\hat p\pm1.96\sqrt{\hat p(1-\hat p)/N_1}$")
    ax.semilogx(ns, covn, "s--", color=ORANGE, lw=1.2, label=r"wrong: $n$ in place of $N_1$")
    ax.axhline(0.95, color="k", lw=0.8, ls=":")
    ax.set_ylim(0.8, 1.0)
    ax.set_xlabel("chain length $n$")
    ax.set_ylabel("coverage")
    ax.legend(fontsize=6.5, frameon=False, loc="lower right")
    common.panel_label(ax, "b", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig23-S4", out_dir)


def fig_23_s5(out_dir=None):
    """Figure 23.S5: Exercise 23.4 (running proportions) and Exercise 23.5(e) (extinction cdf)."""
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.7))
    rng = np.random.default_rng(2345)
    a, b = 0.1, 0.3
    x = simulate_chain(np.array([[1 - a, a], [b, 1 - b]]), 0, 20000, rng)[1:]
    n = np.arange(1, len(x) + 1)
    p1 = np.cumsum(x == 0) / n
    ax = axes[0, 0]
    ax.semilogx(n, p1, color=BLUE, lw=1.1, label=r"$\hat p_n(1)$")
    ax.semilogx(n, 1 - p1, color=RED, lw=1.1, label=r"$\hat p_n(2)$")
    ax.axhline(b / (a + b), color=BLUE, ls=":", lw=1)
    ax.axhline(a / (a + b), color=RED, ls=":", lw=1)
    ax.set_ylim(-0.02, 1.02)
    ax.set_xlabel("$n$")
    ax.legend(fontsize=7, frameon=False, loc="center right")
    ax.set_title("Exercise 23.4: $a=0.1$, $b=0.3$", fontsize=9)
    common.panel_label(ax, "a", loc="lower left")
    ax = axes[0, 1]
    F = branching_cdf([0.25, 0.5, 0.25], 60)
    X = np.ones(20000, dtype=np.int64)
    ext = [0.0]
    for _ in range(60):
        X = rng.binomial(2 * X, 0.5)                   # sum of X iid Binomial(2, 1/2) offspring counts
        ext.append(float((X == 0).mean()))
    nn = np.arange(61)
    ax.plot(nn, F, color="k", lw=1.4, label="$F(n)$ from the recursion")
    ax.plot(nn, ext, "o", ms=2.2, color=GREEN, label="simulated, 20000 lines")
    ax.plot(nn[4:], 1 - 4 / nn[4:], ":", color=GREY, lw=1, label="$1-4/n$")
    ax.set_xlabel("generation $n$")
    ax.set_ylim(0, 1.02)
    ax.legend(fontsize=7, frameon=False, loc="lower right")
    ax.set_title("Exercise 23.5(e): $P(N\\leq n)$", fontsize=9)
    common.panel_label(ax, "b", loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig23-S5", out_dir)


# =========================================================================== data for the demos
def export_json(path=None):
    """Write the simulated web hits of Figure 23.3 for the Poisson process demo."""
    x = web_hits()
    out = {"source": "simulated inhomogeneous Poisson process standing in for the web hits of Wasserman (2004), "
                     "Figure 23.3 (times in seconds)", "T": WEB_T, "times": [float(v) for v in x]}
    path = path or os.path.join(common.HERE, "..", "data", "ch23-hits.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    return path


FIGURES = {"23.1": fig_23_1, "23.2": fig_23_2, "23.3": fig_23_3, "23.S1": fig_23_s1, "23.S2": fig_23_s2,
           "23.S3": fig_23_s3, "23.S4": fig_23_s4, "23.S5": fig_23_s5}

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