89 Communication Complexity — TV Distance
89.1 Overview
This module develops the theory of total variation (TV) distance between probability measures on measurable spaces. It gives two equivalent definitions—one via the total variation norm of a signed measure and one as a supremum over measurable events—proves their equivalence, establishes the basic bound on event probability gaps, and derives a concrete half-\(\ell ^1\) formula on finite spaces, specialised further to Boolean and product distributions.
89.2 Declarations
Given two probability measures \(\mu \) and \(\nu \) on a measurable space \(\Omega \), the signed measure difference \(\mu - \nu \) is the signed measure on \(\Omega \) obtained by taking the difference of \(\mu \) and \(\nu \) as measures.
The total variation distance between two probability measures \(\mu \) and \(\nu \) on \(\Omega \) is defined as \(\tfrac {1}{2}\) times the total variation norm of the signed measure \(\mu - \nu \), i.e. \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\| \mu - \nu \| _{\mathrm{TV}}\).
The supremum definition of total variation distance between \(\mu \) and \(\nu \) is
Let \(s\) be a signed measure on a measurable space \(\Omega \), and let \(s = s^+ - s^-\) be its Jordan decomposition into a pair of (finite, mutually singular) positive measures \(s^+\) and \(s^-\). Then for every measurable set \(S \subseteq \Omega \),
where \(s^+(S)\) and \(s^-(S)\) denote the real-valued measures of \(S\) under the positive and negative parts.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) denote their signed measure difference. Then \((\mu - \nu )(\Omega ) = 0\).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) be their signed measure difference. Writing \((\mu -\nu )^{+}\) and \((\mu -\nu )^{-}\) for the positive and negative parts of the Jordan decomposition of \(\mu - \nu \), the two parts assign the same total real mass to the whole space:
Let \(s\) be a signed measure on a measurable space \(\Omega \), with Jordan decomposition \(s = s^+ - s^-\) into its positive and negative parts \(s^+\) and \(s^-\). Then the total mass of the total variation measure \(\left\lvert s\right\rvert \) of \(s\), taken as a real number, is the sum of the total masses of the two Jordan parts:
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu -\nu \) denote their signed measure difference. Writing \(\left\lvert \mu -\nu \right\rvert \) for its total variation measure and \((\mu -\nu )^{+}\) for the positive part of its Jordan decomposition, one has
where both sides are evaluated as real numbers on the whole space \(\Omega \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) denote their signed measure difference. Then for every measurable set \(S \subseteq \Omega \),
where \(\left\lvert \mu - \nu \right\rvert \) is the total variation measure of \(\mu - \nu \) and \(\left\lvert \mu - \nu \right\rvert (\Omega )\) is its total mass.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) denote their signed measure difference. Then for every measurable set \(S \subseteq \Omega \),
where \(\left\lvert \mu - \nu \right\rvert \) is the total variation measure of \(\mu - \nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) denote their signed measure difference. Then there exists a measurable set \(S \subseteq \Omega \) at which
where \(\left\lvert \mu - \nu \right\rvert \) is the total variation measure of \(\mu - \nu \); that is, some event realizes exactly half the total variation of \(\mu - \nu \) over the whole space.
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \), and let \(\mu - \nu \) denote their signed measure difference, with total variation measure \(\left\lvert \mu -\nu \right\rvert \). Then there exists a measurable set \(S \subseteq \Omega \) such that
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \). Then the total variation distance \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\lVert \mu -\nu \rVert _{\mathrm{TV}}\), defined as half the total variation norm of the signed measure \(\mu -\nu \), agrees with its supremum form over events,
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \). Then for every measurable set \(S \subseteq \Omega \),
where \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\lVert \mu - \nu \rVert _{\mathrm{TV}}\) is the total variation distance between \(\mu \) and \(\nu \).
Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \). Then their total variation distance is nonnegative, \(\mathrm{TV}(\mu ,\nu ) \ge 0\).
Let \(\alpha \) be a finite type and let \(a : \alpha \to \mathbb {R}\) be a real-valued function. For every subset \(S \subseteq \alpha \),
Let \(a\colon \alpha \to \mathbb {R}\) be a real-valued function on a finite type \(\alpha \) whose values sum to zero, that is, \(\sum _{x\in \alpha } a(x) = 0\). Then the sum of the positive parts of \(a\) equals half the sum of its absolute values:
Let \(\alpha \) be a finite type and let \(a : \alpha \to \mathbb {R}\) be a real-valued function whose entries sum to zero, \(\sum _{x \in \alpha } a(x) = 0\). Then for every subset \(S \subseteq \alpha \),
Let \(\alpha \) be a finite type and let \(a : \alpha \to \mathbb {R}\) be a family of real numbers whose total sum vanishes, \(\sum _{x} a(x) = 0\). Then
For probability measures \(\mu \) and \(\nu \) on \(\Omega \) and a point \(\omega \in \Omega \), the singleton mass difference is \(\mu (\{ \omega \} ) - \nu (\{ \omega \} ) \in \mathbb {R}\).
Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be probability measures on \(\Omega \). Then for every subset \(S \subseteq \Omega \),
where the sum ranges over all points of \(\Omega \) and each term contributes the singleton mass difference \(\mu (\{ \omega \} ) - \nu (\{ \omega \} )\) exactly when \(\omega \in S\) and \(0\) otherwise.
Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be probability measures on \(\Omega \). Then the singleton mass differences sum to zero:
Let \(\Omega \) be a finite set equipped with the discrete measurable structure, and let \(\mu \) and \(\nu \) be probability measures on \(\Omega \). Then the supremum form of total variation distance, \(\mathrm{TV}_{\sup }(\mu ,\nu ) = \sup \{ |\mu (S) - \nu (S)| : S \subseteq \Omega \} \), is exactly half the \(\ell ^1\) distance between the two measures across the individual points:
Let \(\Omega \) be a finite discrete measurable space, and let \(\mu \) and \(\nu \) be probability measures on \(\Omega \). Then the total variation distance between \(\mu \) and \(\nu \) equals half the sum, over all points \(\omega \in \Omega \), of the absolute differences of their point masses:
Let \(\mu \) and \(\nu \) be probability measures on the two-point space \(\mathrm{Bool} = \{ \mathrm{true}, \mathrm{false}\} \). Then their total variation distance is the absolute difference of the masses they assign to the single point \(\mathrm{true}\):
Let \(\alpha \) and \(\beta \) be finite discrete measurable spaces, let \(\mu _1,\nu _1\) be probability measures on \(\alpha \), and let \(\mu _2,\nu _2\) be probability measures on \(\beta \). Writing \(\mathrm{TV}\) for the total variation distance and \(\mu _1\otimes \mu _2\) for the product measure, the total variation distance between the two product measures satisfies
89.3 Additional declarations
Let \(\mu \) be a probability measure on the two-point space \(\mathrm{Bool} = \{ \mathrm{true}, \mathrm{false}\} \). Then the mass at \(\mathrm{false}\) is one minus the mass at \(\mathrm{true}\):
Let \(a, b, c, d \in \mathbb {R}\) with \(b \ge 0\) and \(c \ge 0\). Then
Let \(\alpha \) and \(\beta \) be finite types, and let \(a, c : \alpha \to \mathbb {R}\) and \(b, d : \beta \to \mathbb {R}\) be real-valued weight functions. Suppose \(b\) and \(c\) are nonnegative and each sums to one, i.e. \(b(y) \ge 0\) for all \(y\), \(c(x) \ge 0\) for all \(x\), \(\sum _{y \in \beta } b(y) = 1\) and \(\sum _{x \in \alpha } c(x) = 1\). Then the \(\ell ^1\) gap between the two product weight functions is at most the sum of the marginal \(\ell ^1\) gaps:
Let \(\mu _1\) be a measure on a measurable space \(\alpha \) and \(\mu _2\) a \(\sigma \)-finite measure on a measurable space \(\beta \). Then for every \(x \in \alpha \) and \(y \in \beta \), the real-valued mass that the product measure \(\mu _1 \otimes \mu _2\) assigns to the singleton \(\{ (x,y)\} \) is the product of the singleton masses: