TCSLib

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

Definition 89.1 Signed measure difference
✓
#

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.

Definition 89.2 Total variation distance
✓
#

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}}\).

Definition 89.3 Total variation distance via event supremum
✓
#

The supremum definition of total variation distance between \(\mu \) and \(\nu \) is

\[ \mathrm{TV}_{\sup }(\mu ,\nu ) \; =\; \sup \bigl\{ |\mu (S) - \nu (S)| : S \subseteq \Omega \text{ measurable}\bigr\} . \]
Lemma 89.4 Signed measure via Jordan decomposition
✓

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 \),

\[ s(S) = s^+(S) - s^-(S), \]

where \(s^+(S)\) and \(s^-(S)\) denote the real-valued measures of \(S\) under the positive and negative parts.

Lemma 89.5 Signed measure difference vanishes on the whole space
✓

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\).

Lemma 89.6 Jordan parts of a probability-measure difference have equal total mass
✓

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:

\[ (\mu -\nu )^{+}(\Omega ) = (\mu -\nu )^{-}(\Omega ). \]
Lemma 89.7 Total variation mass as the sum of Jordan parts
✓

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:

\[ \left\lvert s\right\rvert (\Omega ) = s^+(\Omega ) + s^-(\Omega ). \]
Lemma 89.8 Half the total variation equals the positive Jordan part
✓

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

\[ \tfrac {1}{2}\, \left\lvert \mu -\nu \right\rvert (\Omega ) = (\mu -\nu )^{+}(\Omega ), \]

where both sides are evaluated as real numbers on the whole space \(\Omega \).

Lemma 89.9 Event probability gap bounded by half the total variation
✓

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 \),

\[ \left\lvert (\mu - \nu )(S)\right\rvert \; \le \; \tfrac {1}{2}\, \left\lvert \mu - \nu \right\rvert (\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.

Lemma 89.10 Probability gap bounded by half total variation
✓

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 \),

\[ \left\lvert \mu (S) - \nu (S)\right\rvert \le \tfrac {1}{2}\, \left\lvert \mu - \nu \right\rvert (\Omega ), \]

where \(\left\lvert \mu - \nu \right\rvert \) is the total variation measure of \(\mu - \nu \).

Lemma 89.11 Attainment of half the total variation by a single event
✓

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

\[ \left\lvert (\mu - \nu )(S)\right\rvert = \tfrac {1}{2}\, \left\lvert \mu - \nu \right\rvert (\Omega ), \]

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.

Lemma 89.12 Attainment of the total-variation distance
✓

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

\[ \left\lvert \mu (S) - \nu (S)\right\rvert = \tfrac {1}{2}\, \left\lvert \mu -\nu \right\rvert (\Omega ). \]
Theorem 89.13 Equivalence of the two definitions of total variation distance
✓

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,

\[ \mathrm{TV}(\mu ,\nu ) \; =\; \sup \bigl\{ \, \left\lvert \mu (S)-\nu (S)\right\rvert : S \subseteq \Omega \text{ measurable}\, \bigr\} . \]
Theorem 89.14 Events differ by at most the total variation distance
✓

Let \(\mu \) and \(\nu \) be probability measures on a measurable space \(\Omega \). Then for every measurable set \(S \subseteq \Omega \),

\[ \left\lvert \mu (S) - \nu (S)\right\rvert \le \mathrm{TV}(\mu ,\nu ), \]

where \(\mathrm{TV}(\mu ,\nu ) = \tfrac {1}{2}\lVert \mu - \nu \rVert _{\mathrm{TV}}\) is the total variation distance between \(\mu \) and \(\nu \).

Theorem 89.15 Nonnegativity of total variation distance
✓

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\).

Lemma 89.16 Indicator sum bounded by the positive-part sum
✓

Let \(\alpha \) be a finite type and let \(a : \alpha \to \mathbb {R}\) be a real-valued function. For every subset \(S \subseteq \alpha \),

\[ \sum _{x \in S} a(x) \; \le \; \sum _{x \in \alpha } \max \bigl(a(x),\, 0\bigr). \]
Lemma 89.17 Positive part sum equals half the \(\ell ^1\) norm
✓

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:

\[ \sum _{x\in \alpha } \max \bigl(a(x),\, 0\bigr) \; =\; \frac{1}{2}\sum _{x\in \alpha } \left\lvert a(x)\right\rvert . \]
Lemma 89.18 Half-total-variation bound for a zero-sum indicator sum
✓

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 \),

\[ \Bigl|\sum _{x \in S} a(x)\Bigr| \; \le \; \tfrac {1}{2} \sum _{x \in \alpha } \left\lvert a(x)\right\rvert . \]
Lemma 89.19 Positive part of a zero-sum family equals half its total variation
✓

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

\[ \Bigl|\sum _{x} \max (a(x), 0)\Bigr| = \tfrac {1}{2} \sum _{x} \left\lvert a(x)\right\rvert . \]
Definition 89.20 Singleton mass difference
✓

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}\).

Lemma 89.21 Probability gap as a sum of singleton mass differences
✓

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 \),

\[ \mu (S) - \nu (S) = \sum _{\omega \in \Omega } \mathbf{1}[\omega \in S]\, \bigl(\mu (\{ \omega \} ) - \nu (\{ \omega \} )\bigr), \]

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.

Lemma 89.22 Singleton mass differences sum to zero
✓

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:

\[ \sum _{\omega \in \Omega } \bigl(\mu (\{ \omega \} ) - \nu (\{ \omega \} )\bigr) = 0. \]
Theorem 89.23 Total variation distance as half the \(\ell ^1\) distance
✓

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:

\[ \mathrm{TV}_{\sup }(\mu ,\nu ) \; =\; \frac{1}{2}\sum _{\omega \in \Omega } \bigl|\mu (\{ \omega \} ) - \nu (\{ \omega \} )\bigr|. \]
Theorem 89.24 Total variation distance as half the \(\ell ^1\) distance
✓

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:

\[ \mathrm{TV}(\mu ,\nu ) \; =\; \frac{1}{2}\sum _{\omega \in \Omega } \left\lvert \mu (\{ \omega \} ) - \nu (\{ \omega \} )\right\rvert . \]
Theorem 89.25 Total variation distance on the two-point space
✓

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}\):

\[ \mathrm{TV}(\mu ,\nu ) = \left\lvert \mu (\{ \mathrm{true}\} ) - \nu (\{ \mathrm{true}\} )\right\rvert . \]
Theorem 89.26 Subadditivity of total variation distance under products
✓

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

\[ \mathrm{TV}(\mu _1\otimes \mu _2,\ \nu _1\otimes \nu _2)\ \le \mathrm{TV}(\mu _1,\nu _1)+\mathrm{TV}(\mu _2,\nu _2). \]

89.3 Additional declarations

Lemma 89.27 Mass at false on the two-point space
✓

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}\):

\[ \mu (\{ \mathrm{false}\} ) = 1 - \mu (\{ \mathrm{true}\} ). \]
Lemma 89.28 Pointwise triangle bound for a product gap
✓

Let \(a, b, c, d \in \mathbb {R}\) with \(b \ge 0\) and \(c \ge 0\). Then

\[ \left\lvert ab - cd\right\rvert \; \le \; \left\lvert a - c\right\rvert \, b + c\, \left\lvert b - d\right\rvert . \]
Lemma 89.29 \(\ell ^1\) gap of product weights bounded by marginal gaps
✓

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:

\[ \sum _{(x,y) \in \alpha \times \beta } \left\lvert a(x)\, b(y) - c(x)\, d(y)\right\rvert \; \le \; \sum _{x \in \alpha } \left\lvert a(x) - c(x)\right\rvert + \sum _{y \in \beta } \left\lvert b(y) - d(y)\right\rvert . \]
Lemma 89.30 Singleton mass of a product measure
✓

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:

\[ (\mu _1 \otimes \mu _2)(\{ (x,y)\} ) = \mu _1(\{ x\} )\, \mu _2(\{ y\} ). \]