C. Probability, Concentration & Information

Random variables, Gaussians, high-probability guarantees, martingales, KL divergence and risk measures

Readiness checks — a short prerequisite refresher

These checks are diagnostic, with the needed calculation explained in each answer. A gap tells you where to review; it is not a reason to skip this primer.

Book contents · Apply this chapter to a real decision · Glossary

Many guarantees in the modules are statements about a random experiment: a noisy measurement, one episode of a stochastic closed loop, a batch of training data, the random seed of a verifier. Others are deterministic and hold for every admissible state, disturbance or input, such as forward invariance or a verified network bound (Module 1 compares the types). To read a probabilistic guarantee you must be able to say what is random, which event is being measured and which average is taken. This primer builds that vocabulary from a first course in calculus and linear algebra, and then the tools the modules lean on: Gaussian conditioning (the engine of GP regression), concentration inequalities, union bounds, martingales for adaptively collected data, information measures, risk measures and distribution-free tests.

1. Random Variables, Expectation & Variance

Worked example (an excursion with an atom). Let $X\sim\mathcal U(-1,1)$ be the signed distance of the state beyond a constraint boundary (positive means violated) and $Z=\max(X,0)=X^+$ the excursion. Then $\mathbb P(Z=0)=\mathbb P(X\le0)=\tfrac12$: an atom at zero. For $0\le z\le1$, $F_Z(z)=\mathbb P(X\le z)=(1+z)/2$, so $F_Z$ jumps from $0$ to $\tfrac12$ at $z=0$ and then rises linearly to $1$ (figure). A nondegenerate Gaussian has no atoms and assigns positive probability to negative values; a degenerate Gaussian is a single point mass. Neither represents this mixed law.

Worked example. For the excursion above, $\mathbb E[Z]=0\cdot\tfrac12+\int_0^1z\cdot\tfrac12\,dz=\tfrac14$: the atom contributes nothing, the density $\tfrac12$ on $(0,1]$ the rest. Counting violations: with $c_t=\mathbf 1\{x_t\gt1\}$ and $N=\sum_{t=1}^Tc_t$, linearity gives $\mathbb E[N]=\sum_t\mathbb P(x_t\gt1)$ even though the states of one episode are dependent. If each of $T=50$ steps violates with probability $0.004$, then $\mathbb E[N]=0.2$. Since $N$ is a nonnegative integer, $\mathbf 1\{N\ge1\}\le N$, hence $\mathbb P(\text{at least one violation})\le\mathbb E[N]=0.2$ whatever the dependence. A Boolean test becomes a signed monitor by subtracting one half: $\mathbf 1\{\text{test passed}\}-\tfrac12\in\{-\tfrac12,+\tfrac12\}$ is positive exactly when the test passes.

Worked example (ensemble spread). Two ensemble members predict means $\mu_1=(1,0)$ and $\mu_2=(-1,0)$. Their average is $\bar\mu=(0,0)$ and the outer-product estimate $\hat\Sigma=\tfrac12\sum_e(\mu_e-\bar\mu)(\mu_e-\bar\mu)^\top=\begin{bmatrix}1&0\\0&0\end{bmatrix}$ is PSD but singular: the members disagree only along the first axis. With $E$ members in $\mathbb R^n$ this estimate has rank at most $E-1$, so it is singular whenever $E\le n$ and must not be inverted. A fusion rule such as $\big(\tfrac1E\sum_e\Sigma_e^{-1}\big)^{-1}$ needs every member covariance $\Sigma_e$ to be positive definite.

Almost surely, support and essential supremum

Worked example. For the excursion, $\operatorname{ess\,sup}Z=1$. Now let a disturbance $W\sim\mathcal U(0,1)$ enter through $g(W)$ with $g=0$ except $g(0.5)=10$. The worst case over all disturbances is $\sup_wg(w)=10$, but $\mathbb P(g(W)=0)=1$, so $\operatorname{ess\,sup}g(W)=0$: an almost-sure analysis never sees the spike.

Averages of many samples

Keep two objects apart: the population quantity $\mathbb E[X]$ is a fixed number, the sample average $\bar X_N$ is random and changes with the data. The empirical distribution of $N$ samples puts mass $1/N$ on each observed value (mass $1/200$ on each of $200$ simulated episodes); its mean is the sample mean. How far $\bar X_N$ typically is from $\mathbb E[X]$ at finite $N$ is the subject of Section 3 (standard errors) and Section 5 (guaranteed bounds).

Practice — Weighted averages and spread

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

2. Conditional Probability, Bayes & Conditional Expectation

Conditioning is updating on information. Once we know that an event $B$ happened, only outcomes inside $B$ remain possible, and their probabilities are rescaled so that they again sum to one.

Worked example (an alarm and the base rate). A fault occurs in $1\%$ of runs; a monitor detects a fault with probability $0.95$ and raises a false alarm on a healthy run with probability $0.05$. Given an alarm,

About five out of six alarms are false: a small false-alarm rate is swamped by the many healthy runs. The false-alarm rate $\mathbb P(\text{alarm}\mid\text{healthy})$ of a test (Section 10) and the posterior $\mathbb P(\text{fault}\mid\text{alarm})$ are different numbers, and the second needs a prior.

Transition kernels and trajectory laws. A transition kernel $P(s'\mid s,a)$ is a family of conditional laws, one distribution of the next state for each state-action pair; a stochastic policy $\pi(a\mid s)$ is a conditional law of the action. The product rule chains them into the law of a trajectory,

and total probability gives marginals, $\mathbb P(s_1=s')=\sum_{s,a}\mu(s)\,\pi(a\mid s)\,P(s'\mid s,a)$. For instance, from $\mu=\delta_{s_0}$ with two actions of probability $0.5$ each that reach an unsafe state with probabilities $0.2$ and $0.6$, $\mathbb P(s_1\text{ unsafe})=0.5\cdot0.2+0.5\cdot0.6=0.4$. Decorations such as $\mathbb P^\pi_\mu$ or $\mathbb E_{\tau\sim\pi}$ record which $\mu$, $\pi$ and $P$ generate the trajectory; change any of them and every probability changes.

Worked example (averaging over a policy). In a state $s$, action $a_1$ has expected cost $\mathbb E[X\mid a_1]=2$ and action $a_2$ has $\mathbb E[X\mid a_2]=10$. Under $\pi=(0.7,0.3)$ the tower rule gives $\mathbb E[X]=0.7\cdot2+0.3\cdot10=4.4$. Under another policy $\pi'=(0.9,0.1)$ the conditional expectations, a property of the environment, are unchanged and only the weights move: $0.9\cdot2+0.1\cdot10=2.8$. The performance-difference lemma averages the advantage of $\pi$ over the actions of $\pi'$ in exactly this way.

Worked example (small and large errors). Residuals that are $\mathcal N(0,0.5^2)$ with probability $0.8$ and $\mathcal N(0,3^2)$ with probability $0.2$ (the "80% small, 20% large" option of the Module 15 explorer) have variance $0.8\cdot0.25+0.2\cdot9=2$. Their tail is nothing like that of $\mathcal N(0,2)$: $\mathbb P(|E|\gt5)=0.8\cdot\mathbb P(|Z|\gt10)+0.2\cdot\mathbb P(|Z|\gt\tfrac53)\approx0.019$, against $0.0004$ for the Gaussian with the same variance, while near zero the mixture is more concentrated ($\mathbb P(|E|\gt1)\approx0.18$ against $0.48$). An ensemble of $E$ Gaussian predictions is an equal-weight mixture: its covariance is the average member covariance (aleatoric part) plus the covariance of the member means (epistemic part, the $\hat\Sigma$ of Section 1).

Worked example (ten runs, no failure). Let $\theta$ be the failure probability of a controller, with a uniform prior on $[0,1]$. Ten independent runs show no failure, so $L(\theta)=(1-\theta)^{10}$ and the posterior density is $11(1-\theta)^{10}$ (a Beta$(1,11)$ law, Section 10). The ML estimate is $\hat\theta=0$, "it never fails", yet the posterior mean is $1/12\approx0.083$ and $\mathbb P(\theta\gt0.2\mid\mathcal D)=\int_{0.2}^111(1-\theta)^{10}d\theta=0.8^{11}\approx0.086$. For Gaussian models the posterior and the marginal likelihood are available in closed form (Section 4); non-Gaussian likelihoods, such as binary safe/unsafe labels or censored measurements, need approximations (Laplace, expectation propagation, sampling). Preference data give another likelihood: in the Bradley–Terry model an item with score $r_a$ beats one with score $r_b$ with probability $1/(1+e^{-(r_a-r_b)})$, and the negative log-likelihood of an observed preference is the logistic loss $\log(1+e^{-(r_a-r_b)})$.

Worked example (nested probabilities). A controller is stable with probability at least $1-\epsilon=0.95$ under a posterior truncated to a region $A$ of mass $c=0.99$. Under the untruncated posterior, $\mathbb P(\text{stable})\ge\mathbb P(\text{stable}\cap A)=\mathbb P(\text{stable}\mid A)\,\mathbb P(A)\ge0.95\cdot0.99=0.9405$. The same product rule composes a hyperparameter statement with a function statement: if the true hyperparameter lies in a box with probability at least $1-\delta_1$ and, given that, a confidence band holds with probability at least $1-\delta_2$, both hold with probability at least $(1-\delta_1)(1-\delta_2)\ge1-\delta_1-\delta_2$. If the result is afterwards validated on random test samples, the validation confidence is a third, frequentist probability over those samples (Section 6); keep it apart from posterior mass. The tower rule also explains conformal coverage (Section 10): conditional on the calibration data the coverage is a random variable $C$, and its average $\mathbb E[C]$ is the marginal coverage probability.

Practice — Condition on the information you actually have

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

3. Markov Chains, Stationary Distributions & Monte Carlo

Worked example. Let $P=\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}$ (state 1 nominal, state 2 degraded). $\pi=\pi P$ gives $\pi_2=0.1\pi_1+0.5\pi_2$, so $\pi_2=\pi_1/5$ and $\pi=(5/6,1/6)$. From state 2: $p_1=(0.5,0.5)$, $p_2=(0.7,0.3)$, $p_3=(0.78,0.22)$, $p_4=(0.812,0.188)$; the gap to $\pi$ shrinks by the factor $0.4$ per step, the second eigenvalue of $P$ ($\operatorname{tr}P-1$). The chain never stops jumping; only its distribution settles, and the approach phase is the transient. If every state can reach every other (irreducible), $\pi$ is unique and positive; if moreover the chain is aperiodic (the possible return times to a state have greatest common divisor $1$; for an irreducible chain one self-loop $P_{ii}\gt0$, as here, suffices), $p_t\to\pi$ from any start. Periodicity does block convergence: $P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ has the unique $\pi=(\tfrac12,\tfrac12)$, yet started in state 1 its law alternates $(1,0),(0,1),(1,0),\dots$ for ever. A chain with one closed recurrent class plus transient states (unichain) also has a unique $\pi$.

Worked example. $Q=\begin{bmatrix}0.5&0.3\\0.2&0.4\end{bmatrix}$: $\det(I-Q)=0.5\cdot0.6-0.3\cdot0.2=0.24$ and $N=\tfrac1{0.24}\begin{bmatrix}0.6&0.3\\0.2&0.5\end{bmatrix}=\begin{bmatrix}2.5&1.25\\0.833&2.083\end{bmatrix}$. From state 1 the chain spends on average $2.5+1.25=3.75$ steps before absorption. (For $V\ge0$, the drift condition $\mathbb E[V(X_{t+1})\mid X_t=x]\le V(x)-1$ for all $x$ outside a set $C$ is the probabilistic Lyapunov (Foster) criterion: from $x$ the chain reaches $C$ after at most $V(x)$ steps on average.)

Worked example. $a=0.9$, $\sigma=0.1$: $v_\infty=0.01/0.19=0.0526$, a stationary standard deviation of $0.229$, $2.3$ times the per-step noise, because noise accumulates. In Module 1's loop $x_{t+1}=x_t-k(x_t-0.8)+w_t$ the error $e_t=x_t-0.8$ has $a=1-k$ and $v_\infty=\sigma^2/(k(2-k))$. Three different notions: the deterministic equilibrium ($\sigma=0$, $e=0$); stability of the recursion ($|a|\lt1$); the stationary distribution ($\sigma\gt0$: the state keeps moving, its law no longer changes).

Random functions over time. The recursion $f_t=\sqrt{1-\varepsilon}\,f_{t-1}+\sqrt{\varepsilon}\,g_t$ with $\varepsilon\in[0,1]$, centred independent innovations $g_t$ of variance $s^2$, independent of the centred $f_0$ with $\operatorname{Var}f_0=s^2$ keeps $\operatorname{Var}f_t=(1-\varepsilon)s^2+\varepsilon s^2=s^2$ for every $t$, while $\operatorname{Cov}(f_t,f_{t-k})=(1-\varepsilon)^{k/2}s^2$ decays: memory fades and the process reverts to its mean ($\varepsilon=0$ frozen, $\varepsilon=1$ fresh each step). With $a=1$ and i.i.d. centred increments of variance $\sigma^2\gt0$ independent of $x_0$, the random walk $x_t=x_0+\sum_{s\lt t}w_s$ has variance growing like $t\sigma^2$: no stationary law and no mean reversion. Sped up to $n$ steps per unit of time and with each step divided by $\sigma\sqrt n$, $W_n(t)=\frac1{\sigma\sqrt n}\sum_{s\lt\lfloor nt\rfloor}w_s$ has $\operatorname{Var}W_n(t)=\lfloor nt\rfloor/n\to t$, and as $n\to\infty$ it converges in distribution (Donsker's theorem) to the Wiener process $W$: $W(0)=0$, continuous paths and independent increments $W(t)-W(s)\sim\mathcal N(0,t-s)$, hence for $s\le t$, $\operatorname{Cov}(W(s),W(t))=\operatorname{Cov}\big(W(s),W(s)+(W(t)-W(s))\big)=\operatorname{Var}W(s)=s=\min(s,t)$.

Worked example (200 episodes). $40$ of $N=200$ episodes violate: $\hat p=0.2$, $\mathrm{SE}=\sqrt{0.2\cdot0.8/200}=0.028$, and the normal-approximation 95% interval is $0.2\pm1.96\cdot0.028=[0.145,\,0.255]$ ($1.96$ is the $97.5\%$ quantile of the standard normal, Section 4). With zero violations the formula gives $\mathrm{SE}=0$, which is meaningless. The exact statement: if the true rate were $p$, all $200$ runs are clean with probability $(1-p)^{200}$, which is below $0.05$ once $p\gt1-0.05^{1/200}=0.0149\approx3/200$ (the "rule of three"). Truncation bias: estimating $\mathbb E\sum_{t\ge0}\gamma^tc_t$ with $c_t\in[0,1]$ from episodes cut at horizon $H$ underestimates by at most $\gamma^H/(1-\gamma)$, which is $0.657$ for $\gamma=0.99$, $H=500$.

Practice — Transitions, long-run laws and Monte Carlo

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

4. The Multivariate Gaussian & Gaussian Conditioning

Worked example (one-sided safety probability). If the posterior of $f(x)$ is $\mathcal N(\mu,\sigma^2)$, then $\mathbb P(f(x)\ge\mu+\beta\sigma)=1-\Phi(\beta)=\Phi(-\beta)$. Requiring this to be at least $\alpha$ means $\Phi(\beta)\le1-\alpha$; for $\alpha=0.9$ that is $\beta\le-1.2816$. A safety probability above one half therefore forces a negative multiplier, i.e. a lower confidence bound; an optimistic $\beta\ge0$ certifies at most probability $\tfrac12$. Numerics: $Q(10)=7.6\cdot10^{-24}$, but $1-\Phi(10)$ evaluated in double precision is exactly $0$ because $\Phi(10)$ rounds to $1$ (cancellation). Tail probabilities should be computed from $\operatorname{erfc}$ directly; the formula is exact, the subtraction is not.

Worked example (Gaussian chance constraint). Let $x\sim\mathcal N(m,\Sigma)$ with $m=(0.5,0.5)$, $\Sigma=\begin{bmatrix}0.04&0.01\\0.01&0.09\end{bmatrix}$ and $h=(1,1)$. Then $h^\top x\sim\mathcal N(1,\,0.04+0.09+2\cdot0.01)=\mathcal N(1,0.15)$ and $\mathbb P(h^\top x\le2)=\Phi(1/0.387)=\Phi(2.58)=0.995$. In general $\mathbb P(h^\top x\le b)\ge p\iff h^\top m+\Phi^{-1}(p)\sqrt{h^\top\Sigma h}\le b$: a deterministic, tightened constraint (here $1+1.645\cdot0.387=1.64\le2$ for $p=0.95$). The equivalence is exact only if $x$ really is Gaussian.

Worked example (repeated measurements). Let $y_1,\dots,y_m$ be i.i.d. $\mathcal N(f,\sigma^2)$. Then $\bar y\sim\mathcal N(f,\sigma^2/m)$, and since $\sum_i(y_i-f)^2=\sum_i(y_i-\bar y)^2+m(\bar y-f)^2$ (the cross term $2(\bar y-f)\sum_i(y_i-\bar y)$ vanishes), the likelihood of $f$ is $e^{-m(\bar y-f)^2/(2\sigma^2)}$ times a factor free of $f$: the mean with noise variance $\sigma^2/m$ carries all the information about $f$.

Precision addition. For a scalar prior $f\sim\mathcal N(m_0,s_0^2)$ and one observation $y=f+\varepsilon$ with noise $\varepsilon\sim\mathcal N(0,\sigma^2)$ independent of $f$ ($s_0,\sigma\gt0$), the theorem with $\Sigma_{xx}=\Sigma_{xy}=s_0^2$, $\Sigma_{yy}=s_0^2+\sigma^2$ gives posterior variance $s^2=s_0^2\sigma^2/(s_0^2+\sigma^2)$, i.e.

precisions (inverse variances) add and the mean is a precision-weighted average; $m$ repeated observations enter through $\bar y$ with precision $m/\sigma^2$. Conditioning independent parts on their sum works the same way: for independent $X_1\sim\mathcal N(0,a)$, $X_2\sim\mathcal N(0,b)$ and $S=X_1+X_2$, $\mathbb E[X_1\mid S]=\frac{a}{a+b}S$ and $\operatorname{Var}(X_1\mid S)=\frac{ab}{a+b}$ (a simulator part and a residual part of an objective, say).

A truncated Gaussian on $[a_{\rm lo},a_{\rm hi}]$ has density $\varphi\big(\tfrac{a-m}{s}\big)\big/\big(s\,[\Phi(\tfrac{a_{\rm hi}-m}{s})-\Phi(\tfrac{a_{\rm lo}-m}{s})]\big)$ on the interval (Section 2's renormalisation), and seeded Gaussian draws are the standard way to generate random test networks, weights and noise; they sample, they do not cover.

Practice — Standardise and condition Gaussian laws

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

5. Concentration: Markov, Chebyshev, Hoeffding & Sub-Gaussian Noise

A standard error says how far an average typically lands from its mean. A safety argument needs a bound on the probability of a large deviation that holds for every $N$, with no normal approximation. Each inequality below buys a faster-decaying tail with a stronger assumption.

Worked example (standardised prediction errors). If, given the history, $f(x_t)\sim\mathcal N(\mu_t,\sigma_t^2)$ and the query $x_t$ was chosen from past data (so it is fixed once we condition on the history), then $\mathbb P\big(|f(x_t)-\mu_t|\gt\sqrt\rho\,\sigma_t\mid\text{history}\big)\le e^{-\rho/2}$. Choosing $\rho=2\ln(1/\delta)$ makes this $\delta$: for $\delta=0.05$, $\sqrt\rho=2.45$, slightly conservative against the exact two-sided $1.96$.

Worked example (how many runs?). Outcomes in $[0,1]$, accuracy $t=0.05$, failure probability $\delta=0.05$. Chebyshev with $\operatorname{Var}\le\tfrac14$: $N\ge1/(4\delta t^2)=2000$. Hoeffding: $N\ge\ln(40)/(2\cdot0.0025)=737.8$, so $738$. The central-limit approximation $(1.96\cdot0.5/0.05)^2\approx385$ is smaller but is not a guarantee. For rare events Hoeffding is loose; the Chernoff–KL bound $\mathbb P(\mathrm{Bin}(N,p)\ge Nq)\le e^{-N\,\mathrm{kl}(q\|p)}$ for $q\gt p$ (and the mirror image for $q\lt p$), with the KL divergence between Bernoulli laws $\mathrm{kl}(q\|p)=q\ln\frac qp+(1-q)\ln\frac{1-q}{1-p}$ (Section 8), is much sharper: for $p=0.01$, $q=0.03$, $N=1000$ it gives $1.9\cdot10^{-6}$ where Hoeffding gives $0.45$ (the exact value is $2\cdot10^{-7}$).

Heavy and uneven noise. A Student-$t$ variable with $\nu\in\{1,2,\dots\}$ degrees of freedom is $T=Z/\sqrt{V/\nu}$, where $Z,Z_1,\dots,Z_\nu$ are independent standard normals and $V=\sum_{j=1}^\nu Z_j^2$. Its density decays only polynomially, like $|t|^{-(\nu+1)}$, so the absolute moments $\mathbb E|T|^k$ of order $k\ge\nu$ are infinite and $\mathbb Ee^{\lambda T}=\infty$ for every $\lambda\ne0$: no sub-Gaussian parameter exists. For $\nu=3$ (variance $3$), $\mathbb P(|T|\gt5)=0.015$ against $0.004$ for $\mathcal N(0,3)$, and $\mathbb P(|T|\gt10)=0.002$ against $8\cdot10^{-9}$. Heteroscedastic noise $\varepsilon_t=s(x_t)\xi_t$ with $\xi_t\sim\mathcal N(0,1)$ independent of the past and $|s(x)|\le R$ everywhere is conditionally $R$-sub-Gaussian: one envelope $R$ covers every input.

Practice — Choose a bound whose assumptions hold

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

6. “With Probability at Least $1-\delta$”: Union Bounds & Confidence Statements

Worked example (what joint coverage costs). A two-sided Gaussian band at one point with $\delta=0.05$ needs $\beta=1.96$. For $T=100$ rounds at $\delta/T$ each it needs $\Phi^{-1}(1-0.00025)=3.48$; for $T=10^4$, $4.56$: the price grows only like $\sqrt{\log T}$. If the per-step failures were independent with probability $0.001$, joint success over $100$ steps would be exactly $0.999^{100}=0.905$ against the union bound's $0.9$: barely conservative, and the union bound stays valid under dependence, where the product formula does not. The same logic turns per-step chance constraints into a joint one: $\mathbb P(x_t\notin C)\le\delta$ for each $t$ does not give $\mathbb P(\exists t\le T:\ x_t\notin C)\le\delta$, but $\mathbb P(x_t\notin C)\le\delta/T$ for each $t$ does.

Anytime budgets. To cover all $t=1,2,\dots$ at once, spend a summable sequence: $\delta_t=\frac{\delta}{t(t+1)}$ gives $\sum_{t\ge1}\delta_t=\delta\sum_{t\ge1}\big(\frac1t-\frac1{t+1}\big)=\delta$ by telescoping; $\delta_t=\delta/\pi_t$ with $\pi_t=\pi^2t^2/6$, so that $\sum_t\pi_t^{-1}=1$, does the same via $\sum_t1/t^2=\pi^2/6$. For $\delta=0.05$ and $\delta_t=\delta/(t(t+1))$, a two-sided Gaussian band needs $\beta_t=\Phi^{-1}(1-\delta_t/2)=2.24,\ 3.51,\ 4.57,\ 5.45$ at $t=1,10,100,1000$.

Uniform over inputs. On a finite domain a union bound over the $|D|$ points only adds $\log|D|$ under the square root: with the Gaussian tail of Section 5 the multiplier becomes $\beta_t=\sqrt{2\log(|D|\pi_t/\delta)}$. On a continuum there are infinitely many points: one needs a discretisation plus a Lipschitz argument, or a self-normalised martingale bound (Section 7) that controls the whole function at once. Nested (PAC) statements. When a bound is itself calibrated from random data, two probabilities appear: $\mathbb P_{\mathcal Z}\big\{\mathbb P(\text{good}\mid\mathcal Z)\ge1-\gamma\big\}\ge1-\kappa$, "probably ($1-\kappa$, over the calibration sample $\mathcal Z$) approximately ($1-\gamma$, over fresh draws) correct". Example: let $B$ be the maximum of $m$ i.i.d. samples of a continuous quantity with CDF $F$. $F(B)$ is the fraction of fresh draws that $B$ covers, and $\mathbb P\{F(B)\lt1-\gamma\}=(1-\gamma)^m$ because all $m$ samples must fall below the $(1-\gamma)$-quantile. For $\gamma=0.05$ and $\kappa=0.01$, $m\ge\ln0.01/\ln0.95=89.8$: $90$ samples.

Practice — Budget failure probability explicitly

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

7. Adaptive Data, Filtrations & Martingales

A safe-exploration algorithm chooses its next query $x_t$ from everything it has seen. The data $(x_1,y_1),(x_2,y_2),\dots$ are then neither independent nor identically distributed: $x_t$ depends on past noise, and so may the spread of the next measurement. What survives is a "fresh noise" property, and martingales are its language.

Why "zero-mean given the past" and not just "zero-mean". Let $\varepsilon_1=\pm1$ with probability $\tfrac12$ each and $\varepsilon_2=\varepsilon_1$ (the sensor repeats its error). Both have mean zero, but $\mathbb E[\varepsilon_2\mid\varepsilon_1]=\varepsilon_1\ne0$ and $\operatorname{Var}(\varepsilon_1+\varepsilon_2)=4$ instead of $2$: averaging does not cancel the error. Conversely, heteroscedastic noise $\varepsilon_t=s(x_t)\xi_t$ with fresh standard normal $\xi_t$ and adaptively chosen $x_t$ is not i.i.d., yet $\mathbb E[\varepsilon_t\mid\mathcal F_{t-1}]=s(x_t)\,\mathbb E[\xi_t]=0$ (take out what is known). For such sequences, and $s\lt t$, $\mathbb E[\varepsilon_s\varepsilon_t]=\mathbb E\big[\varepsilon_s\,\mathbb E[\varepsilon_t\mid\mathcal F_{t-1}]\big]=0$, so $\operatorname{Var}\sum_t\varepsilon_t=\sum_t\mathbb E\varepsilon_t^2$ exactly as for independent noise.

The method of mixtures: one bound for all times. Ville applied to $M^\lambda$ is time-uniform, but each fixed $\lambda$ is tuned to one scale of $S_t$. The remedy is to average over $\lambda$, since a nonnegative mixture of supermartingales is again one. With $R=1$ and $\lambda\sim\mathcal N(0,1/v)$, completing the square gives

Ville with $c=1/\delta$: with probability at least $1-\delta$, simultaneously for all $t$, $|S_t|\lt\sqrt{2(v+t)\big[\ln(1/\delta)+\tfrac12\ln(1+t/v)\big]}$, a sum self-normalised by its accumulated variance $v+t$. For $v=1$, $\delta=0.05$, $t=100$: $|S_t|\lt32.7$, against $27.2$ from Hoeffding valid at $t=100$ only, and $50.8$ from a union bound with $\delta_t=\delta/(t(t+1))$. Module 3 does the same in feature space: $v+t$ becomes the matrix $V+\sum_sX_sX_s^\top$ and $\sqrt{v/(v+t)}$ a determinant ratio, whose logarithm is, up to sign, the information gain of Section 8. Martingale noise also drives stochastic approximation: updates $\theta_{t+1}=\theta_t+\eta_t(h(\theta_t)+\varepsilon_t)$ with $\sum_t\eta_t=\infty$, $\sum_t\eta_t^2\lt\infty$ (Robbins–Monro), with martingale-difference noise of bounded conditional second moment, make the weighted noise series converge; together with stability and regularity assumptions they average out the noise $\sum_t\eta_t\varepsilon_t$ and, under further conditions, converge almost surely to stable zeros of $h$; primal-dual methods run two such recursions with step sizes decaying at different rates (two timescales).

Practice — Use only information available before the draw

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

8. Entropy, KL Divergence, Total Variation & Mutual Information

Worked example. The policy $(0.7,0.2,0.1)$ has $H=0.7\ln\frac1{0.7}+0.2\ln5+0.1\ln10=0.802$ nats ($1.157$ bits), below $\ln3=1.099$; a fair coin has $\ln2=0.693$; $\mathcal U(0,\tfrac12)$ has $h=\ln\tfrac12=-0.693\lt0$. An entropy bonus with a temperature rewards spread-out policies. The expected entropy reduction of a measurement $Y$ about $X$, $H(X)-\mathbb E_y[H(X\mid Y=y)]$, is the mutual information below. A model with low predictive entropy is confident, which is not the same as accurate.

Worked example (direction matters). $p=(0.5,0.5)$, $q=(0.9,0.1)$: $\mathrm{KL}(p\|q)=0.5\ln\frac{0.5}{0.9}+0.5\ln5=0.511$ but $\mathrm{KL}(q\|p)=0.9\ln1.8+0.1\ln0.2=0.368$. If $q=(1,0)$ excludes the second action, $\mathrm{KL}(p\|q)=\infty$ while $\mathrm{KL}(q\|p)=\ln2$: a new policy that tries an action the old one never takes is infinitely far in $\mathrm{KL}(\text{new}\|\text{old})$. From a uniform $q$ over $|\mathcal A|$ actions, $\mathrm{KL}(p\|q)=\log|\mathcal A|-H(p)\le\log|\mathcal A|$, the usual bound on an initial divergence.

Maximum likelihood is forward KL: $\mathbb E_{x\sim p^\ast}[\log q_\theta(x)]=-H(p^\ast)-\mathrm{KL}(p^\ast\|q_\theta)$, and $H(p^\ast)$ does not depend on $\theta$, so maximising the expected log-likelihood minimises $\mathrm{KL}(p^\ast\|q_\theta)$; a weighted likelihood $\sum_iw_i\log\pi_\theta(a_i\mid s_i)$ fits $\pi_\theta$ to the reweighted target in the same forward direction.

Variational inference and EM rest on the identity $\log p_\theta(x)=\mathbb E_{z\sim q}\big[\log\frac{p_\theta(x,z)}{q(z)}\big]+\mathrm{KL}\big(q\,\|\,p_\theta(z\mid x)\big)$ for any law $q$ of a latent $z$ with $\mathrm{KL}\big(q\,\|\,p_\theta(z\mid x)\big)\lt\infty$ (in particular, $q$ puts no mass where the posterior has none): the first term (the ELBO) is a lower bound on the log-likelihood, tight when $q$ is the posterior. (For other $q$ the ELBO is $-\infty$: the bound still holds, the identity would read $-\infty+\infty$.) EM alternates an E-step (set $q$ to the posterior, or fit it) and an M-step (maximise the ELBO over $\theta$).

Worked example. For $p=(0.5,0.5)$, $q=(0.9,0.1)$: $d_{\rm TV}=\tfrac12(0.4+0.4)=0.4$, and Pinsker gives $0.4\le\sqrt{0.511/2}=0.505$ and $0.4\le\sqrt{0.368/2}=0.429$. A trust region $\mathrm{KL}\le\epsilon$ therefore caps every event probability change at $\sqrt{\epsilon/2}$. If two laws of a whole data sequence are within $d_{\rm TV}=\epsilon$, then every event, such as "the test point is covered", changes probability by at most $\epsilon$; this compares laws, not the realised samples.

$f$-divergences generalise both: for convex $f$ with $f(1)=0$, $D_f(p\|q)=\sum_iq_if(p_i/q_i)=\mathbb E_q[f(p/q)]\ge0$ (Jensen), defined when $p_i=0$ wherever $q_i=0$. $f(w)=w\log w$ gives KL, $f(w)=\tfrac12|w-1|$ gives $d_{\rm TV}$, and $f(w)=\tfrac12(w-1)^2$ gives half the Pearson $\chi^2$ divergence $\sum_i(p_i-q_i)^2/q_i$ (for the example above, $\chi^2=0.4^2/0.9+0.4^2/0.1=1.78$). The Wasserstein-1 distance for laws on $\mathbb R$ with finite first absolute moments is $W_1(p,q)=\inf\mathbb E|X-Y|$ over couplings $=\sup\{\mathbb E_pg-\mathbb E_qg:\ g\ \text{1-Lipschitz}\}$ measures how far mass must move: for point masses at $0$ and $\epsilon\gt0$, $d_{\rm TV}=1$ and $\mathrm{KL}=\infty$, but $W_1=\epsilon$. Its 1-Lipschitz "critics" are why Lipschitz networks appear in Wasserstein GANs.

Worked example. Unit prior variances, $\sigma^2=0.25$ (so $\sigma^{-2}K=4K$). Two uncorrelated points: $\tfrac12\ln\det(5I)=\tfrac12\ln25=1.609$ nats. Correlation $0.5$: $\det\begin{bmatrix}5&2\\2&5\end{bmatrix}=21$, $\tfrac12\ln21=1.522$: correlated measurements tell us less. The same point twice: $\det\begin{bmatrix}5&4\\4&5\end{bmatrix}=9$, $\tfrac12\ln9=\tfrac12\ln(1+2\cdot4)=1.099$, exactly one measurement with noise variance $\sigma^2/2$. On a one-point domain $\gamma_T=\tfrac12\ln(1+4T)$: $0.80$, $1.86$, $3.00$ nats for $T=1,10,100$. Such slow growth is best seen on a logarithmic axis, where equal vertical steps mean equal ratios.

Practice — Compare distributions, not individual samples

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

9. Quantiles, Value-at-Risk & CVaR

Worked example (splitting an atom). Let $Z\in\{0,1,5\}$ with probabilities $0.7,0.2,0.1$. Then $F^{-1}(u)=0$ on $(0,0.7]$, $1$ on $(0.7,0.9]$ and $5$ on $(0.9,1)$ (figure), and $\mathbb E[Z]=\int_0^1F^{-1}=0.2+0.5=0.7$. At $\alpha=0.85$: $\operatorname{VaR}_{0.85}=1$ and $\operatorname{CVaR}_{0.85}=\frac{0.05\cdot1+0.1\cdot5}{0.15}=3.67$. The atom at $1$ occupies $u\in(0.7,0.9]$ and only its top $0.05$ lies in the tail: it is included fractionally. The naive $\mathbb E[Z\mid Z\ge\operatorname{VaR}]=0.7/0.3=2.33$ is wrong here; it equals CVaR when $F$ is continuous at the quantile.

Gaussian CVaR. For $Z\sim\mathcal N(\mu,\sigma^2)$, $\operatorname{VaR}_\alpha=\mu+\sigma\Phi^{-1}(\alpha)$ and, from $\mathbb E[Z\mid Z\ge q]=\mu+\sigma\varphi(z_q)/(1-\Phi(z_q))$ with $z_q=(q-\mu)/\sigma$, $\operatorname{CVaR}_\alpha=\mu+\sigma\,\varphi(\Phi^{-1}(\alpha))/(1-\alpha)$; at $\alpha=0.95$ this is $\mu+2.063\,\sigma$. Papers that write $\alpha$ for the tail fraction print $\mu+\sigma\varphi(\Phi^{-1}(\alpha))/\alpha$, the same quantity since $\varphi$ is even. In a Gaussian cost critic written $\mathcal N(Q_c^\pi,V_c^\pi)$ the second argument $V_c^\pi$ is a variance (take its square root), not the cost value function.

Chance, expectation and CVaR constraints. For an episode cost $Z$: $\mathbb E[Z]\le d$ constrains the average, $\mathbb P(Z\gt0)\le\delta$ (equivalently $\operatorname{VaR}_{1-\delta}(Z)\le0$) the frequency of failure, and $\operatorname{CVaR}_\alpha(Z)\le d$ frequency and magnitude together. If $Z=100$ with probability $0.01$ and $0$ otherwise: $\mathbb E[Z]=1$, $\mathbb P(Z\gt0)=0.01$ and $\operatorname{CVaR}_{0.95}(Z)=\frac{0.01\cdot100}{0.05}=20$: with budget $d=2$ and level $\delta=0.05$ the mean and chance constraints hold, and only the CVaR constraint ($20\gt2$) sees the rare catastrophe. A finite-horizon chance constraint $\mathbb P(\forall t\in\{1,\dots,T\}:\ s_t\in\mathcal S)\ge1-\delta$, with $T\ge1$ and $s_0\in\mathcal S$ almost surely, concerns the whole trajectory; it is implied by per-step levels $\delta/T$ (Section 6) and by an expected number of violations $\mathbb E[N]\le\delta$ (Section 1).

Empirical quantiles, robust summaries and expectiles. Sorting $N$ observed values gives empirical quantiles (median, quartiles). The interquartile mean averages the middle $50\%$ and is robust to outlying runs; a bootstrap interval resamples the $N$ runs with replacement many times and reads off percentiles of the recomputed statistic. These describe one random experiment; they are not bounds on the next network or seed. Quantiles minimise an asymmetric absolute loss: for integrable $Z$, $\operatorname{VaR}_\tau\in\arg\min_m\mathbb E[(\tau-\mathbf 1\{Z\lt m\})(Z-m)]$, where the minimisers form an interval of $\tau$-quantiles whose smallest point is $F^{-1}(\tau)$ (for $Z\in\{0,1\}$ with probabilities $\tfrac12,\tfrac12$ and $\tau=\tfrac12$ every $m\in[0,1]$ minimises). For $\mathbb E[Z^2]\lt\infty$ the $\tau$-expectile minimises the asymmetric squared loss $\mathbb E[|\tau-\mathbf 1\{Z\lt m\}|(Z-m)^2]$. $\tau=\tfrac12$ gives the mean, and as $\tau\to1$ ($\tau\to0$) the expectile tends to the essential supremum (infimum), which is how offline RL approximates a maximum (minimum) over actions seen in the data.

Practice — Read a tail with discrete atoms

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

10. Binomial Tails, Hypothesis Tests & Exchangeability

Worked example (binomial tails and the scenario bound). For $n=20$, $p=0.1$: $\mathbb P(K=0)=0.9^{20}=0.122$ and $\mathbb P(K\le1)=0.122+20\cdot0.1\cdot0.9^{19}=0.392$. For the scenario bound, let $\theta_N^\ast$ solve a convex program in $d$ decision variables whose $N$ constraints are sampled i.i.d. from $P$, and let $V(\theta)$ be the probability that the constraint of a fresh sample is violated by $\theta$. If every such program is feasible (with nonempty interior) and has a unique solution (or a fixed tie-break rule), the scenario theorem (Module 15) gives $P^N\{V(\theta_N^\ast)\gt\epsilon\}\le\sum_{i=0}^{d-1}\binom Ni\epsilon^i(1-\epsilon)^{N-i}$, exactly the lower tail $\mathbb P(\mathrm{Bin}(N,\epsilon)\le d-1)$: for $d=2$, $\epsilon=0.05$ it is $0.037$ at $N=100$, and $N=181$ is the first sample size that brings it below $10^{-3}$. The scalar case $d=1$ is the max-of-samples bound of Section 6; keeping the $(r+1)$-th largest of $m$ samples instead of the maximum changes the failure probability to $\mathbb P(\mathrm{Bin}(m,\gamma)\le r)$.

Worked example. $95$ successes in $100$ at $\alpha=0.05$: $p_L=0.898$, whereas the normal approximation $0.95-1.645\cdot0.0218=0.914$ is over-optimistic. $100$ successes in $100$ at $\alpha=0.001$: $p_L=0.001^{1/100}=0.933$; with $n=10^4$ it is $0.99931$, approaching $1$ only like $1-\ln(1/\alpha)/n$. In randomized smoothing the certified radius is $\sigma\Phi^{-1}(p_L)$, e.g. $0.5\cdot\Phi^{-1}(0.933)=0.75$.

Worked example (an event trigger). Under the null model the standardised residual $r_t=(y_t-\mu_{t-1}(x_t))/\sqrt{\sigma_{t-1}^2(x_t)+\sigma^2}$ is $\mathcal N(0,1)$. Triggering a reset when $|r_t|\gt3$ gives false-alarm probability $0.0027$ per step, i.e. $2.7$ expected false alarms in $1000$ unchanged steps. To keep the probability of any false alarm over $1000$ steps below $0.05$ (union bound), test each step at $5\cdot10^{-5}$: $|r_t|\gt\Phi^{-1}(1-2.5\cdot10^{-5})=4.06$.

Beta laws, the probability integral transform and conditional coverage. For $a,b\gt0$, the Beta$(a,b)$ law on $[0,1]$ has density proportional to $x^{a-1}(1-x)^{b-1}$, mean $\frac a{a+b}$ and variance $\frac{ab}{(a+b)^2(a+b+1)}$ (Beta$(1,11)$ was the posterior in Section 2).

If $S$ has a continuous CDF $F$, then $F(S)\sim\mathcal U(0,1)$ (the probability integral transform), and the $k$-th smallest of $n$ i.i.d. uniforms is Beta$(k,n+1-k)$. So if the calibration and test scores are i.i.d. with a continuous CDF $F$ (the score function fixed beforehand, e.g. fitted on separate data) and $1\le k\le n$, the coverage of one fixed calibration set, $C=\mathbb P(S_{n+1}\le S_{(k)}\mid S_1,\dots,S_n)=F(S_{(k)})$, is Beta$(k,n+1-k)$ whatever $F$ is.

Exchangeability with almost surely distinct scores fixes only its mean $\mathbb E[C]=\frac k{n+1}$ (with $S_2=1-S_1$, $S_1\sim\mathcal U(0,1)$, the pair is exchangeable, but for $n=k=1$ the coverage is $\mathbf 1\{S_1\ge\tfrac12\}$, not uniform).

For $n=19$, $k=18$: mean $0.9$, standard deviation $0.065$, and $\mathbb P(C\lt0.8)=19\cdot0.8^{18}\cdot0.2+0.8^{19}=0.083$. Testing on $m=2000$ fresh points adds binomial noise; by total variance (Section 2) the measured coverage has variance $\operatorname{Var}C+\mathbb E[C(1-C)]/m=0.00429+0.00004$, which equals $p(1-p)\frac{n+1+m}{m(n+2)}$ with $p=\frac k{n+1}$: the calibration set, not the test set, dominates the spread.

Practice — Separate a test outcome from its coverage

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

Interactive: Concentration & Gaussian Conditioning

Part A draws 2000 independent samples of size up to $400$ from a law on $[0,1]$ (seeded, so results reproduce) and compares the observed frequency of a deviation $|\bar X_N-m|\ge t$ with Chebyshev, Hoeffding and the normal approximation. Part B conditions a 2-D Gaussian with standard deviations $\sigma_x,\sigma_y$ and correlation $\rho$ (Section 1) on $y=y_0$ with the Schur complement and checks the formula against the samples that fall in a thin slab around $y_0$.

What to look for. (A) The true deviation probability stays below both bounds, for every law: they are guarantees for anything with values in $[0,1]$. The observed frequency only estimates it from $2000$ runs, so where a bound drops below about $10^{-3}$ one or two deviating runs can lift the observed frequency above it (seed 1, Bernoulli$(0.5)$, $N=215$, $t=0.15$: $1/2000$ against Hoeffding's $1.3\cdot10^{-4}$). Chebyshev decays like $1/N$ and Hoeffding exponentially; at $t=0.1$ Chebyshev is still the tighter one up to $N\approx191$ for the uniform law (whose variance $1/12$ is far below the worst case $1/4$ that Hoeffding implicitly assumes), after which Hoeffding wins. The normal approximation follows the dots for smooth laws but is not a bound: for Bernoulli$(0.1)$ at $N=10$ the true deviation probability is $0.61$ while the approximation says $0.29$.

Gaussian conditioning panel. Dragging $y_0$ moves the conditional mean along the purple line but leaves the conditional variance $\sigma_x^2(1-\rho^2)$ unchanged; at $\rho=0$ the observation changes nothing, and as $|\rho|\to1$ it pins $x$ down. The slab statistics agree with the formula up to sampling error plus a small bias, because a slab of finite width is not the line $y=y_0$ (at the default settings the exact slab mean is $0.997$ instead of $1$, far inside the sampling error of about $0.06$); far in the tail the slab empties, and only the formula still works.

Exercises

These cumulative problems connect several ideas. If a step feels too large, return to the section practice route, where each topic has an Easy, Medium and Hard problem with a separate hint, worked solution and prerequisite review link.

Further Reading

Flashcards