The Book

Inspired by Paul Erdős’ description of beautiful proofs, this website highlights deep and elegant insights that, in my humble opinion, deserve their own pages in The Book. I planned, AI drafted, and I edited: the decide-execute-deliver sandwich.

The Even–Odd Decomposition

Shapley Values

Variance Reduction

Sampling

The Shapley value is blind to half of every game, and paired sampling is the estimator that never looks at that half.

Exponential Minimum Sampling

Sampling

Language Models

Divide independent Exp(1) draws by the token probabilities and keep the argmin: the result is an exact sample, and if a verifier holds the same draws, every sample is also a distortion-free watermark.

Tilting at Rare Events

Sampling

Variance Reduction

Language Models

Naive and exponentially tilted estimators show how proposal sampling makes rare events common without changing the probability being estimated.

Aliasing on Purpose

Shapley Values

When a set function has no interactions above order three, fewer than \(4d\) evaluations recover its exact Shapley-distribution mean by merging pairwise interactions that carry the same weight.

The Infinite Gaussian Vector

Probability

Numerical Linear Algebra

A Gaussian process is one Gaussian vector stretched over every input you might ask about; conditioning it on data is the textbook Gaussian-conditioning formula, and fitting its kernel is maximizing a likelihood.

Why Sums Become Gaussian

Probability

A geometric proof that independent Gaussians sum to a Gaussian, and a cumulant view of why standardized sums approach one.

Hutch++ and the Split Spectrum

Numerical Linear Algebra

Variance Reduction

Deflate the heavy top of the spectrum and run Hutchinson on the flat rest: the error falls like \(1/m\) instead of \(1/\sqrt{m}\), and no algorithm does better.

Implicit Control Variate

Sampling

Variance Reduction

Fix the sample size and the best constant baseline subtracts itself.

Iterative Hessian Mixing

Differential Privacy

Numerical Linear Algebra

Both moving parts of the iterative Hessian sketch were privacy mechanisms all along, and the better conditioned the data, the less noise the sketch needs.

Three Faces of Leverage Scores

Numerical Linear Algebra

Sampling

One number per row of a matrix (self-influence, minimum energy, effective resistance), and it is exactly the right rate to sample the row at.

A Determinant Counts Spanning Trees

Numerical Linear Algebra

Cauchy–Binet expands a reduced graph Laplacian over edge sets, and its incidence minors keep exactly the spanning trees.

One Data Shapley Vector Is Not Enough

Shapley Values

Optimization

Shapley linearity gives one Data Shapley vector per validation point, and averaging those vectors discards the distinctions data selection needs.

Three Noises for the Argmax

Sampling

Differential Privacy

One integral explains why Gumbel gives a softmax, exponential noise gives permute-and-flip, and Laplace behaves differently from both.

Shapley Values for Piecewise-Constant Games

Shapley Values

When a game takes the same value on whole blocks of coalitions, the Shapley sum collapses to one term per block: exact Shapley values in time linear in the number of distinct values, not the number of coalitions. Trees and causal models are two instances.

Prune and Clone

Sampling

Variance Reduction

Language Models

Run rollouts as a population: prune the hopeless, clone the promising, and give every clone a weight of one over its chance of being picked. The estimate stays unbiased no matter how bad the guide is.

Rotate, Round, and Debias

Numerical Linear Algebra

Variance Reduction

Language Models

Random rotation turns directional quantization error into a concentrated scalar problem; alignment correction and residual control variates then recover unbiased inner products.

A PSA on Shapley Values

Shapley Values

The game and the value are different objects. Most modern SHAP estimators fit a surrogate game, then compute that surrogate’s exact Shapley values.

Speculative Decoding Is a Maximal Coupling

Language Models

Sampling

The accept/reject rule of speculative decoding is a maximal coupling of draft and target, so the output is exactly the big model’s distribution, and no exact scheme can accept more often.

The Greedy \(1-1/e\) Guarantee

Optimization

Repeatedly take the largest marginal gain and you land within \(1-1/e\) of the best possible set, for any monotone submodular objective, and no efficient algorithm does better.

The Tournament Is a Distribution Update

Language Models

Sampling

SynthID-Text’s enormous knockout bracket can be integrated out exactly: propagate the winner’s distribution through each keyed round, then sample once.

Volume Sampling Keeps Leverage and Rejects Redundancy

Numerical Linear Algebra

Sampling

A determinant preserves each row’s leverage score while preventing parallel rows from filling the sample.