92 Communication Complexity — TV Distance
92.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.
92.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
For any signed measure \(s\) on \(\Omega \) and any measurable set \(S\), the value \(s(S)\) equals the difference of its Jordan positive and negative parts: \(s(S) = s^+(S) - s^-(S)\).
For any two probability measures \(\mu \) and \(\nu \), the signed difference satisfies \((\mu - \nu )(\Omega ) = 0\).
For probability measures \(\mu \) and \(\nu \), the Jordan positive part and the Jordan negative part of \(\mu - \nu \) assign equal real mass to \(\Omega \): \(((\mu -\nu )^+)(\Omega ) = ((\mu -\nu )^-)(\Omega )\).
For any signed measure \(s\), the real-valued total variation mass of \(\Omega \) equals the sum of the Jordan positive and negative part masses: \(\| s\| _{\mathrm{TV}}(\Omega ) = s^+(\Omega ) + s^-(\Omega )\).
For probability measures \(\mu \) and \(\nu \), \(\tfrac {1}{2}\| \mu -\nu \| _{\mathrm{TV}}(\Omega ) = ((\mu -\nu )^+)(\Omega )\).
For every measurable set \(S \subseteq \Omega \), \(|(\mu -\nu )(S)| \le \tfrac {1}{2}\| \mu -\nu \| _{\mathrm{TV}}(\Omega )\).
For every measurable set \(S \subseteq \Omega \), \(|\mu (S) - \nu (S)| \le \tfrac {1}{2}\| \mu -\nu \| _{\mathrm{TV}}(\Omega )\).
There exists a measurable set \(S \subseteq \Omega \) for which the bound is tight: \(|(\mu -\nu )(S)| = \tfrac {1}{2}\| \mu -\nu \| _{\mathrm{TV}}(\Omega )\).
There exists a measurable set \(S \subseteq \Omega \) such that \(|\mu (S) - \nu (S)| = \tfrac {1}{2}\| \mu -\nu \| _{\mathrm{TV}}(\Omega )\).
The total-variation-mass definition and the supremum-over-events definition coincide: \(\mathrm{TV}(\mu ,\nu ) = \mathrm{TV}_{\sup }(\mu ,\nu )\).
For every measurable set \(S \subseteq \Omega \), \(|\mu (S) - \nu (S)| \le \mathrm{TV}(\mu ,\nu )\).
For any two probability measures \(\mu \) and \(\nu \), \(\mathrm{TV}(\mu ,\nu ) \ge 0\).
For any function \(a : \alpha \to \mathbb {R}\) on a finite type \(\alpha \) and any set \(S \subseteq \alpha \), \(\sum _{x \in S} a(x) \le \sum _{x : \alpha } \max (a(x), 0)\).
Let \(a : \alpha \to \mathbb {R}\) be a function on a finite type with \(\sum _x a(x) = 0\). Then \(\sum _x \max (a(x), 0) = \tfrac {1}{2}\sum _x |a(x)|\).
If \(a : \alpha \to \mathbb {R}\) satisfies \(\sum _x a(x) = 0\), then for every \(S \subseteq \alpha \), \(\bigl|\sum _{x \in S} a(x)\bigr| \le \tfrac {1}{2}\sum _x |a(x)|\).
If \(a : \alpha \to \mathbb {R}\) satisfies \(\sum _x a(x) = 0\), then \(\bigl|\sum _x \max (a(x),0)\bigr| = \tfrac {1}{2}\sum _x |a(x)|\).
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}\).
On a finite measurable space, for any measurable set \(S\), \(\mu (S) - \nu (S) = \sum _{\omega \in S} (\mu (\{ \omega \} ) - \nu (\{ \omega \} ))\).
On a finite measurable space, the singleton mass differences sum to zero: \(\sum _{\omega : \Omega } (\mu (\{ \omega \} ) - \nu (\{ \omega \} )) = 0\).
On a finite measurable space \(\Omega \), the supremum form of total variation distance satisfies
On a finite measurable space \(\Omega \),
For probability measures \(\mu \) and \(\nu \) on \(\mathrm{Bool}\), \(\mathrm{TV}(\mu ,\nu ) = |\mu (\{ \mathrm{true}\} ) - \nu (\{ \mathrm{true}\} )|\).
For probability measures \(\mu _1, \nu _1\) on \(\alpha \) and \(\mu _2, \nu _2\) on \(\beta \) (both finite measurable spaces),