TCSLib

58 Communication Complexity — Finite Probability Space

58.1 Overview

This module develops the foundational infrastructure for finite probability spaces used in the proof of Newman’s theorem. It introduces the typeclasses CommunicationComplexity.FiniteMeasureSpace and CommunicationComplexity.FiniteProbabilitySpace, and establishes a library of measure-real and integral lemmas (singleton decompositions, Cauchy–Schwarz, Markov’s inequality, product-space factorisation) that are used throughout the complexity-theoretic arguments.

58.2 Declarations

Definition 58.1 Finite measurable space
#

A typeclass for a measurable space \(\Omega \) that is simultaneously finite (carries a Fintype instance) and discrete (every subset is measurable). It deliberately does not bundle a measure, so that a single type can be equipped with many different measures.

Definition 58.2 Constructor for FiniteMeasureSpace

Given a type \(\Omega \) that already carries Fintype and DiscreteMeasurableSpace instances, CommunicationComplexity.FiniteMeasureSpace.of bundles them into a FiniteMeasureSpace record without requiring any additional data.

Definition 58.3 Finite probability space

A typeclass bundling a MeasureSpace structure on \(\Omega \) together with a CommunicationComplexity.FiniteMeasureSpace witness and an IsProbabilityMeasure instance for the canonical volume measure. This makes \(\Omega \) simultaneously a finite discrete measurable space and a probability space.

Definition 58.4 Constructor from existing instances

Given a type \(\Omega \) already equipped with a MeasureSpace, Fintype, DiscreteMeasurableSpace, and IsProbabilityMeasure instance for volume, this helper packages all of those into a CommunicationComplexity.FiniteProbabilitySpace record.

Definition 58.5 Constructor from an explicit measure

Given a finite measurable space \(\Omega \) and an unbundled probability measure \(\mu \) on it, FiniteProbabilitySpace.ofMeasure promotes \(\mu \) to the canonical volume and returns a FiniteProbabilitySpace instance.

Theorem 58.6 Singleton decomposition of a finite measure

Let \(\Omega \) be a finite measurable space, \(\mu \) a finite measure on it, and \(S \subseteq \Omega \) any set. Then

\[ \mu ^{\mathbb {R}}(S) \; =\; \sum _{\omega \in \Omega } \begin{cases} \mu ^{\mathbb {R}}(\{ \omega \} ) & \text{if } \omega \in S, \\ 0 & \text{otherwise.} \end{cases} \]

In other words, a finite measure on a finite measurable space is determined by and recovers as a finite sum over its singleton masses.

Theorem 58.7 Measure of a preimage via fibers

Let \(Z : \Omega \to \alpha \) be a function from a finite measurable space to a finite type, \(\mu \) a finite measure on \(\Omega \), and \(P\) a predicate on \(\alpha \). Then

\[ \mu ^{\mathbb {R}}\{ \omega \mid P(Z(\omega ))\} \; =\; \sum _{z \in \alpha } \begin{cases} \mu ^{\mathbb {R}}(Z^{-1}\{ z\} ) & \text{if } P(z), \\ 0 & \text{otherwise.} \end{cases} \]
Theorem 58.8 Absolute continuity via singletons

On a finite measurable space, two measures satisfy \(\mu \ll \nu \) if and only if for every \(\omega \in \Omega \), \(\nu (\{ \omega \} ) = 0\) implies \(\mu (\{ \omega \} ) = 0\).

Theorem 58.9 Jensen’s inequality: square of expectation

For any probability measure \(\mu \) on a finite measurable space and any function \(f : \Omega \to \mathbb {R}\),

\[ \Bigl(\int _\Omega f\, d\mu \Bigr)^2 \; \le \; \int _\Omega f^2\, d\mu . \]
Theorem 58.10 Integral as a sum over fibers

Let \(Z : \Omega \to \alpha \) be a measurable map from a finite measurable space to a finite discrete type, \(\mu \) a finite measure on \(\Omega \), and \(f : \alpha \to \mathbb {R}\). Then

\[ \int _\Omega f(Z(\omega ))\, d\mu (\omega ) \; =\; \sum _{z \in \alpha } \mu ^{\mathbb {R}}(Z^{-1}\{ z\} ) \cdot f(z). \]
Theorem 58.11 Law of total probability over fibers

Let \(Z : \Omega \to \alpha \) be a finite-valued random variable on a finite measurable space with finite measure \(\mu \), and let \(S \subseteq \Omega \). Then

\[ \mu ^{\mathbb {R}}(S) \; =\; \sum _{z \in \alpha } \mu ^{\mathbb {R}}(Z^{-1}\{ z\} ) \cdot \mu \bigl[\, \cdot \mid Z^{-1}\{ z\} \bigr]^{\mathbb {R}}(S). \]

This is the law of total probability expressed in real-valued measure notation.

Theorem 58.12 Uniform measure of a set is its relative cardinality

Let \(\Omega \) be a nonempty finite discrete type and let \(S \subseteq \Omega \). Under the uniform probability measure on \(\Omega \),

\[ \bigl(\mathrm{uniformOn}\, \Omega \bigr)^{\mathbb {R}}(S) \; =\; \frac{\# \{ \omega \in \Omega \mid \omega \in S\} }{|\Omega |}. \]
Theorem 58.13 Uniform measure equals subtype cardinality ratio

Under the uniform measure on a nonempty finite discrete type \(\Omega \), the real-valued measure of a set \(S\) equals \(|\{ S\} | / |\Omega |\) where \(|\{ S\} |\) denotes the cardinality of the subtype \(\{ \omega : \Omega \mid \omega \in S\} \).

Theorem 58.14 A finite probability space is nonempty

Any type carrying a FiniteProbabilitySpace instance is nonempty.

Definition 58.15 Probability mass function of a finite probability space

For a finite probability space \(\Omega \), toPMF converts the canonical volume measure to a probability mass function \(\mathrm{PMF}\, \Omega \), assigning to each \(\omega \) the real weight \(\mu (\{ \omega \} )\).

Theorem 58.16 Measure of a set as a PMF sum

For a finite probability space \(\Omega \) and any set \(S \subseteq \Omega \), \(\mathrm{volume}(S) = \sum _{\omega \in S} \mathrm{toPMF}(\Omega )(\omega )\).

Theorem 58.17 Singleton masses sum to one

For any bijection \(e : \Omega \xrightarrow {\sim } \alpha \) with \(\alpha \) finite, the family \(a \mapsto \mathrm{volume}(\{ e^{-1}(a)\} )\) has sum \(1\) as an \(\mathtt{HasSum}\) statement.

Theorem 58.18 PMF of a product space factors

For finite probability spaces \(\Omega _1\) and \(\Omega _2\) and any \((x, y) \in \Omega _1 \times \Omega _2\),

\[ \mathrm{toPMF}(\Omega _1 \times \Omega _2)(x, y) \; =\; \mathrm{toPMF}(\Omega _1)(x) \cdot \mathrm{toPMF}(\Omega _2)(y). \]
Theorem 58.19 Product measure of a rectangle

For finite probability spaces \(\Omega _1\) and \(\Omega _2\) and sets \(A \subseteq \Omega _1\), \(B \subseteq \Omega _2\),

\[ \mathrm{volume}^{\mathbb {R}}(A \times B) \; =\; \mathrm{volume}^{\mathbb {R}}(A) \cdot \mathrm{volume}^{\mathbb {R}}(B). \]
Theorem 58.20 Measure of a finite disjoint union

If \((A_i)_{i \in \iota }\) is a pairwise-disjoint family of sets indexed by a finite type \(\iota \) in a finite probability space \(\Omega \), then

\[ \mathrm{volume}^{\mathbb {R}}\! \Bigl(\bigcup _{i} A_i\Bigr) \; =\; \sum _{i \in \iota } \mathrm{volume}^{\mathbb {R}}(A_i). \]
Theorem 58.21 Measure of a preimage of a finite set

For a map \(\varphi : \Xi \to \Omega \) from a finite probability space and a finite set \(T \subseteq \Omega \),

\[ \mathrm{volume}^{\mathbb {R}}(\varphi ^{-1}(T)) \; =\; \sum _{a \in T} \mathrm{volume}^{\mathbb {R}}(\varphi ^{-1}\{ a\} ). \]
Theorem 58.22 Measure of a finite set as a sum of singletons

For a finite probability space \(\Omega \) and a finset \(T \subseteq \Omega \),

\[ \mathrm{volume}^{\mathbb {R}}(T) \; =\; \sum _{a \in T} \mathrm{volume}^{\mathbb {R}}(\{ a\} ). \]
Theorem 58.23 Integral as a PMF-weighted sum

For a finite probability space \(\Omega \) and any \(f : \Omega \to \mathbb {R}\),

\[ \int _\Omega f(\omega )\, d\omega \; =\; \sum _{\omega \in \Omega } \mathrm{toPMF}(\Omega )(\omega )_{\mathbb {R}} \cdot f(\omega ). \]
Theorem 58.24 Jensen’s inequality on a finite probability space

For a finite probability space \(\Omega \) and any \(f : \Omega \to \mathbb {R}\),

\[ \Bigl(\int _\Omega f\Bigr)^2 \; \le \; \int _\Omega f^2. \]
Theorem 58.25 Integral over a coordinate of a product space

Let \(\Omega \) be a finite probability space, \(\iota \) a finite index type, and \(f : \Omega \to \mathbb {R}\). For any coordinate \(i \in \iota \), integrating \(\omega _{\bullet } \mapsto f(\omega _i)\) over the product space \((j : \iota ) \to \Omega \) (with the product measure) equals \(\int _\Omega f\).

Theorem 58.26 Measure of a cylinder set in a product space

For a finite index type \(\iota \), finite probability spaces \(\Omega _i\) for each \(i\), and sets \(s_i \subseteq \Omega _i\),

\[ \mathrm{volume}^{\mathbb {R}}\! \Bigl(\prod _{i \in \iota } s_i\Bigr) \; =\; \prod _{i \in \iota } \mathrm{volume}^{\mathbb {R}}(s_i). \]
Theorem 58.27 Measure equals integral of indicator (one-valued)

For a finite probability space \(\Omega \) and \(S \subseteq \Omega \), \(\mathrm{volume}^{\mathbb {R}}(S) = \int _\Omega \mathbf{1}_S(\omega )\, d\omega \), where \(\mathbf{1}_S\) denotes the indicator of \(S\) as an element of \(\Omega \to \mathbb {R}\).

Theorem 58.28 Measure equals integral of \(0/1\) indicator

For a finite probability space \(\Omega \) and \(S \subseteq \Omega \),

\[ \mathrm{volume}^{\mathbb {R}}(S) \; =\; \int _\Omega \bigl(\text{if } \omega \in S \text{ then } 1 \text{ else } 0\bigr)\, d\omega . \]
Theorem 58.29 PMF weights sum to one

For any finite probability space \(\Omega \), \(\sum _{\omega \in \Omega } \mathrm{toPMF}(\Omega )(\omega )_{\mathbb {R}} = 1\).

Theorem 58.30 PMF weights are nonneg

For any finite probability space \(\Omega \) and \(\omega \in \Omega \), \(0 \le \mathrm{toPMF}(\Omega )(\omega )_{\mathbb {R}}\).

Theorem 58.31 Some point has positive mass

For any finite probability space \(\Omega \), there exists \(\omega \in \Omega \) such that \(\mathrm{toPMF}(\Omega )(\omega )_{\mathbb {R}} \gt 0\).

Theorem 58.32 Integral is bounded by a pointwise bound

If \(f : \Omega \to \mathbb {R}\) satisfies \(f(\omega ) \le c\) for all \(\omega \) in a finite probability space, then \(\int _\Omega f \le c\).

Theorem 58.33 Markov’s inequality

For a nonneg function \(f : \Omega \to \mathbb {R}\) on a finite probability space and \(\varepsilon \gt 0\),

\[ \mathrm{volume}^{\mathbb {R}}\{ \omega \mid \varepsilon \le f(\omega )\} \; \le \; \frac{\int _\Omega f}{\varepsilon }. \]
Theorem 58.34 Integral exceeds a pointwise lower bound

If \(f : \Omega \to \mathbb {R}\) satisfies \(c \lt f(\omega )\) for every \(\omega \) in a finite probability space, then \(c \lt \int _\Omega f\).