Alexander Kraskov, Harald Stögbauer and Peter Grassberger (2004), “Estimating Mutual Information”, Physical Review E 69: 066138 — ARXIV-cond-mat/0305641
Key takeaways
From the reading, NOTE-938.
- Two estimators (Eqs. 8, 9). I⁽¹⁾ counts marginal points strictly inside the joint k-th-neighbour cube; I⁽²⁾ uses the hyper-rectangle of the k-th neighbour’s marginal extents. They behave almost identically; I⁽²⁾ is preferred in very high dimension.
- The trick. Estimating H(X), H(Y) and H(X,Y) separately with a fixed k uses different length scales, so the biases do not cancel. Taking the marginal neighbour counts at the joint distance makes them nearly cancel (§II B).
- The only approximation is a constant density inside each neighbourhood (Eq. 18). The bias is set by nonuniformity at the smallest resolved scale and scales, numerically, as k/N or (k − ½)/N (Eq. 32).
- Exact for independence, by numerics. The estimate vanishes up to fluctuations whenever µ(x, y) = µ(x)µ(y), for every marginal tried. Stated as a conjecture with “no proof for this very surprising result” (p. 3).
- Practice inside the paper. Use k = 2 to 4 for estimation and large k for testing independence; break ties from discretized data with noise of order 10⁻¹⁰; transform heavily skewed variables first.
Standing in the record
Filed on 2026-10-16 as the estimator behind the record’s information-flow
readings, and read the same day. NOTE-788 estimates mutual information with
scikit-learn’s kNN estimator and NOTE-320 and NOTE-828 compare against
“Kraskov”; the record now holds what that estimator assumes. It does not
estimate transfer entropy: the conditional extension is later work, not
held. Filed as THEORY-709. mathematical-statistics is for its
subject, estimation; it carries no instruction for machine-learning
practice, its applications being gene-expression data and ICA of a fetal
ECG.