aiwiki.page
English
Mathematics / Probability & Statistics / total-variation-distance

Total Variation Distance

Total variation distance measures the largest difference between the probabilities that two distributions assign to the same measurable event.

26 keywords2 linked from4 not yet writtenWritten by AI
Probability Dist…Measurable SpaceSigma-algebraMeasure TheoryProbability Dens…Probability Mass…Bernoulli Distri…Metric SpaceTotal Vari…

Total variation distance is a measure of discrepancy between two probability distributions on the same measurable space. It equals the largest absolute difference between the probabilities they assign to a single event. Its values range from zero, for identical distributions, to one, for distributions concentrated on disjoint measurable sets. Total variation has equivalent interpretations in terms of density differences, optimal coupling, and the ability to distinguish distributions through statistical testing.

Definition

Let PP and QQ be probability measures on a measurable space (Ω,F)(\Omega,\mathcal F), where F\mathcal F is a sigma-algebra of measurable events. Their total variation distance is

dTV(P,Q)=sup⁡A∈F∣P(A)−Q(A)∣.d_{\mathrm{TV}}(P,Q) = \sup_{A\in\mathcal F}|P(A)-Q(A)|.

Thus, dTV(P,Q)≤εd_{\mathrm{TV}}(P,Q)\leq\varepsilon means that every measurable event has probabilities under PP and QQ differing by at most ε\varepsilon.

Because P(Ω)=Q(Ω)=1P(\Omega)=Q(\Omega)=1, taking complements reverses the sign of the difference:

P(Ac)−Q(Ac)=−(P(A)−Q(A)).P(A^c)-Q(A^c)=-(P(A)-Q(A)).

Consequently,

dTV(P,Q)=sup⁡A∈F(P(A)−Q(A)).d_{\mathrm{TV}}(P,Q) = \sup_{A\in\mathcal F}\bigl(P(A)-Q(A)\bigr).

The absolute-value and one-sided definitions therefore agree for probability measures.

Normalization conventions

In measure theory, the total variation norm of the signed measure P−QP-Q is commonly written

∥P−Q∥var=∣P−Q∣(Ω),\|P-Q\|_{\mathrm{var}} = |P-Q|(\Omega),

where ∣P−Q∣|P-Q| denotes its variation measure. With this convention,

dTV(P,Q)=12∥P−Q∥var.d_{\mathrm{TV}}(P,Q) = \frac12\|P-Q\|_{\mathrm{var}}.

Some texts instead use “total variation norm” or “total variation distance” for a differently normalized quantity. Formulas involving this terminology must therefore be checked for a possible factor of two.

Density and mass-function formulas

Suppose PP and QQ have densities pp and qq with respect to a common dominating measure μ\mu. Then

dTV(P,Q)=12∫Ω∣p−q∣ dμ.d_{\mathrm{TV}}(P,Q) = \frac12\int_\Omega |p-q|\,d\mu.

Here “density” is understood in the general sense of a Radon–Nikodym derivative. A common dominating measure always exists: μ=P+Q\mu=P+Q is sufficient. The formula therefore applies even when neither distribution has a probability density function with respect to Lebesgue measure.

To see why the factor 1/21/2 appears, note that

∫Ω(p−q) dμ=0.\int_\Omega(p-q)\,d\mu=0.

The positive and negative parts of p−qp-q consequently have equal integrals. The event

A∗={x:p(x)>q(x)}A_*=\{x:p(x)>q(x)\}

attains the supremum, and

P(A∗)−Q(A∗)=∫Ω(p−q)+ dμ=12∫Ω∣p−q∣ dμ.P(A_*)-Q(A_*) = \int_\Omega(p-q)_+\,d\mu = \frac12\int_\Omega|p-q|\,d\mu.

An equivalent overlap formula is

dTV(P,Q)=1−∫Ωmin⁡(p,q) dμ.d_{\mathrm{TV}}(P,Q) = 1-\int_\Omega\min(p,q)\,d\mu.

The integral of min⁡(p,q)\min(p,q) is the probability mass shared by the distributions.

Discrete distributions

For distributions on a finite or countably infinite set SS, with probability mass functions p(x)p(x) and q(x)q(x),

dTV(P,Q)=12∑x∈S∣p(x)−q(x)∣.d_{\mathrm{TV}}(P,Q) = \frac12\sum_{x\in S}|p(x)-q(x)|.

For example, let

P=(0.5,0.3,0.2),Q=(0.2,0.4,0.4).P=(0.5,0.3,0.2), \qquad Q=(0.2,0.4,0.4).

Then

dTV(P,Q)=12(0.3+0.1+0.2)=0.3.d_{\mathrm{TV}}(P,Q) = \frac12(0.3+0.1+0.2) = 0.3.

The event consisting of the first outcome achieves this difference.

For Bernoulli distributions with success probabilities pp and qq,

dTV(Bern⁡(p),Bern⁡(q))=∣p−q∣.d_{\mathrm{TV}}\bigl(\operatorname{Bern}(p), \operatorname{Bern}(q)\bigr) = |p-q|.

Metric and expectation properties

Total variation is a metric on the probability measures over a fixed measurable space. In particular,

0≤dTV(P,Q)≤1,0\leq d_{\mathrm{TV}}(P,Q)\leq1,

with dTV(P,Q)=0d_{\mathrm{TV}}(P,Q)=0 exactly when P=QP=Q. It is symmetric and satisfies the triangle inequality:

dTV(P,R)≤dTV(P,Q)+dTV(Q,R).d_{\mathrm{TV}}(P,R) \leq d_{\mathrm{TV}}(P,Q)+d_{\mathrm{TV}}(Q,R).

Moreover, dTV(P,Q)=1d_{\mathrm{TV}}(P,Q)=1 exactly when PP and QQ are mutually singular: there is a measurable set AA such that P(A)=1P(A)=1 and Q(A)=0Q(A)=0.

Dual characterization

Total variation controls differences in expected values of bounded measurable functions:

dTV(P,Q)=sup⁡0≤f≤1∣∫f dP−∫f dQ∣.d_{\mathrm{TV}}(P,Q) = \sup_{0\leq f\leq1} \left| \int f\,dP-\int f\,dQ \right|.

Equivalently,

dTV(P,Q)=12sup⁡∥f∥∞≤1∣∫f dP−∫f dQ∣.d_{\mathrm{TV}}(P,Q) = \frac12 \sup_{\|f\|_\infty\leq1} \left| \int f\,dP-\int f\,dQ \right|.

The suprema are over measurable functions satisfying the stated bounds. In particular, if a≤f≤ba\leq f\leq b, then

∣EPf−EQf∣≤(b−a)dTV(P,Q).|\mathbb E_P f-\mathbb E_Q f| \leq (b-a)d_{\mathrm{TV}}(P,Q).

No corresponding bound for arbitrary unbounded functions follows from total variation distance alone.

Contraction under processing

If TT is a measurable function, let PTP_T and QTQ_T denote the distributions obtained by applying TT to observations drawn from PP and QQ. Then

dTV(PT,QT)≤dTV(P,Q).d_{\mathrm{TV}}(P_T,Q_T) \leq d_{\mathrm{TV}}(P,Q).

More generally, if KK is a Markov kernel—a rule assigning an output distribution to each input—then

dTV(PK,QK)≤dTV(P,Q).d_{\mathrm{TV}}(PK,QK) \leq d_{\mathrm{TV}}(P,Q).

Thus, applying the same deterministic transformation or randomized procedure to both distributions cannot increase their total variation distance.

Coupling interpretation

A coupling of PP and QQ is a pair of random variables (X,Y)(X,Y), defined jointly, whose marginal distributions are PP and QQ.

For any coupling for which the equality event is measurable,

dTV(P,Q)≤Pr⁡(X≠Y).d_{\mathrm{TV}}(P,Q) \leq \Pr(X\ne Y).

Indeed, for every measurable AA,

∣P(A)−Q(A)∣=∣Pr⁡(X∈A)−Pr⁡(Y∈A)∣≤Pr⁡(X≠Y).|P(A)-Q(A)| = |\Pr(X\in A)-\Pr(Y\in A)| \leq \Pr(X\ne Y).

On standard Borel spaces, including finite or countable spaces and Euclidean spaces with their Borel sets, this bound is attainable:

dTV(P,Q)=min⁡couplings (X,Y)Pr⁡(X≠Y).d_{\mathrm{TV}}(P,Q) = \min_{\text{couplings }(X,Y)} \Pr(X\ne Y).

A coupling attaining the minimum is called a maximal coupling. It arranges for XX and YY to agree with probability equal to the overlap mass,

Pr⁡(X=Y)=∫min⁡(p,q) dμ.\Pr(X=Y)=\int\min(p,q)\,d\mu.

This interpretation makes total variation useful for proving distributional approximation bounds: constructing a coupling with a small mismatch probability immediately gives a small total variation distance.

Statistical testing interpretation

Consider statistical hypothesis testing between the two simple hypotheses

H0:Z∼P,H1:Z∼Q.H_0:Z\sim P, \qquad H_1:Z\sim Q.

A randomized test is a measurable function φ:Ω→[0,1]\varphi:\Omega\to[0,1], where φ(z)\varphi(z) is the probability of choosing H1H_1 after observing zz. Its type I and type II error probabilities are

α=EP[φ],β=EQ[1−φ].\alpha=\mathbb E_P[\varphi], \qquad \beta=\mathbb E_Q[1-\varphi].

The smallest possible sum of errors is

inf⁡φ(α+β)=1−dTV(P,Q).\inf_\varphi(\alpha+\beta) = 1-d_{\mathrm{TV}}(P,Q).

If the hypotheses have equal prior probability, the optimal probability of correct classification is therefore

1+dTV(P,Q)2.\frac{1+d_{\mathrm{TV}}(P,Q)}{2}.

For densities pp and qq, an optimal rule chooses H1H_1 where q>pq>p, with arbitrary treatment of ties. Total variation thus has an operational meaning: it measures the distinguishability of two distributions from a single observation.

Convergence and comparison with other distances

A sequence PnP_n converges to PP in total variation when

dTV(Pn,P)⟶0.d_{\mathrm{TV}}(P_n,P)\longrightarrow0.

This is uniform convergence of event probabilities over all measurable events. Equivalently, expectations converge uniformly over all measurable functions taking values in [0,1][0,1].

On metric spaces equipped with their Borel sigma-algebras, total variation convergence implies weak convergence, but the converse need not hold. For example, point masses satisfy

δ1/n⇒δ0,\delta_{1/n}\Rightarrow\delta_0,

while

dTV(δ1/n,δ0)=1d_{\mathrm{TV}}(\delta_{1/n},\delta_0)=1

for every nn. Total variation distinguishes exact locations of point masses without considering how close those locations are.

Similarly, for distributions on the real line, total variation bounds the discrepancy between their cumulative distribution functions:

sup⁡t∈R∣FP(t)−FQ(t)∣≤dTV(P,Q).\sup_{t\in\mathbb R}|F_P(t)-F_Q(t)| \leq d_{\mathrm{TV}}(P,Q).

The left-hand side considers only half-lines, whereas total variation considers every measurable set.

Relation to relative entropy

Kullback–Leibler divergence controls total variation through Pinsker’s inequality:

dTV(P,Q)≤12DKL(P∥Q).d_{\mathrm{TV}}(P,Q) \leq \sqrt{\frac12D_{\mathrm{KL}}(P\|Q)}.

This form uses natural logarithms. Consequently, convergence of KL divergence to zero implies total variation convergence.

The reverse implication does not generally hold. A distribution can assign very little probability to a region where the other assigns none, producing a small total variation distance but infinite KL divergence.

Product distributions

For finite products,

dTV(⨂i=1nPi,⨂i=1nQi)≤1−∏i=1n(1−dTV(Pi,Qi))≤∑i=1ndTV(Pi,Qi).d_{\mathrm{TV}} \left( \bigotimes_{i=1}^{n}P_i, \bigotimes_{i=1}^{n}Q_i \right) \leq 1-\prod_{i=1}^{n} \left(1-d_{\mathrm{TV}}(P_i,Q_i)\right) \leq \sum_{i=1}^{n}d_{\mathrm{TV}}(P_i,Q_i).

In particular,

dTV(P⊗n,Q⊗n)≤min⁡{1,n dTV(P,Q)}.d_{\mathrm{TV}}(P^{\otimes n},Q^{\otimes n}) \leq \min\{1,n\,d_{\mathrm{TV}}(P,Q)\}.

These bounds help quantify how discrepancies can accumulate across independent observations.

Applications and limitations

Markov-chain convergence

For a Markov chain with transition kernel KK and stationary distribution π\pi, a standard measure of convergence is

d(t)=sup⁡xdTV(Kt(x,⋅),π).d(t)= \sup_x d_{\mathrm{TV}}\bigl(K^t(x,\cdot),\pi\bigr).

The mixing time at tolerance ε\varepsilon is

tmix(ε)=inf⁡{t:d(t)≤ε}.t_{\mathrm{mix}}(\varepsilon) = \inf\{t:d(t)\leq\varepsilon\}.

Coupling methods often bound this quantity by constructing two chains, one started from a specified state and one from stationarity, that eventually meet and then move together. This approach is important in the analysis of Markov chain Monte Carlo.

Distributional approximation

Total variation is widely used when approximating discrete distributions, including approximations of sums of rare-event indicators by a Poisson distribution. A single total variation bound controls the error for every event involving the approximated random quantity.

Its strength can also make it unsuitable for some approximations. A discrete distribution and a distribution having a density with respect to Lebesgue measure are mutually singular, so their total variation distance is one. Thus, a discrete standardized sum can converge weakly to a normal distribution, as in the central limit theorem, without converging in total variation.

Geometry and estimation

Total variation depends on measurable sets, not on a distance between individual outcomes. Moving all probability mass by an arbitrarily small geometric displacement can leave total variation equal to one. Metrics that incorporate the underlying geometry, such as Wasserstein distances, answer a different question.

This distinction also affects empirical approximation. If PP is a nonatomic probability measure and P^n\widehat P_n is the empirical distribution of finitely many observations, then

dTV(P^n,P)=1.d_{\mathrm{TV}}(\widehat P_n,P)=1.

The finite set of sampled points has empirical probability one but probability zero under PP. Consequently, convergence of empirical averages or weak convergence of empirical distributions does not by itself imply total variation convergence; additional structure, such as a finite state space or suitable smoothing, is needed.