Engineering / Mathematics — Discrete Probability
Statistical Distance
Statistical distance between distributions, its properties, and its use in proving that a sampler is close to uniform.
Executive summary
Statistical distance measures how distinguishable two distributions are by any test whatever. It is the natural currency for arguing that an efficiently generated distribution is close enough to an ideal one.
Its two key properties — the operational interpretation and non-increase under processing — are what make it usable in proofs.
Learning objectives
- Define statistical distance and its equivalent forms.
- State the distinguishing interpretation.
- Apply the data processing and triangle inequalities.
01Definition and equivalent forms
Statistical distance
For distributions X, Y on a finite set S:
Δ(X, Y) = (1/2) Σ_{s∈S} |P(X = s) − P(Y = s)|.
Equivalently Δ(X, Y) = max_{A ⊆ S} |P(X ∈ A) − P(Y ∈ A)|.
The second form is the operational one: statistical distance is exactly the maximum advantage any test can achieve in distinguishing the two distributions, over all possible tests including computationally unbounded ones.
Δ(X,Y) ≤ ε ⇒ no test distinguishes X from Y with advantage exceeding ε02Properties
| Property | Statement |
|---|---|
| Range | 0 ≤ Δ(X,Y) ≤ 1 |
| Identity | Δ(X,Y) = 0 iff X and Y are the same distribution |
| Symmetry | Δ(X,Y) = Δ(Y,X) |
| Triangle inequality | Δ(X,Z) ≤ Δ(X,Y) + Δ(Y,Z) |
| Data processing | Δ(f(X), f(Y)) ≤ Δ(X,Y) for any function f |
The data processing inequality is the workhorse. It says no post-processing can increase distinguishability, so once a source is shown close to uniform, anything computed from it inherits the closeness.
03Application to sampling
An algorithm generating a random number from an interval by reduction modulo the interval length produces a slightly non-uniform distribution. Statistical distance quantifies exactly how much.
Drawing a uniform k-bit value and reducing modulo n gives a distribution whose statistical distance from uniform on [0, n) is at most n/2^k. Choosing k comfortably above len(n) — typically by 64 or 128 bits — drives the distance below any threshold of concern.
04Frequently asked questions
Why the factor of one half?
It normalises the range to [0,1] and makes the definition agree with the maximum-advantage form. Without it the sum would reach 2 for disjointly supported distributions.
Is statistical distance the right measure for cryptography?
For information-theoretic arguments, yes. For computational security a weaker notion is used — indistinguishability by efficient tests — since many secure constructions have statistical distance close to one while remaining computationally indistinguishable.
How is a small statistical distance interpreted operationally?
As a bound on how much any process can be affected by the substitution. If a system behaves correctly with the ideal distribution and the real one is within ε, the real system's behaviour differs by at most ε in probability.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 130-136.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.