Measurability of Suprema and Separable Classes

Why Measurability Needs Attention

Uniform convergence and empirical-process bounds involve a supremum over a function class. For a class $\mathcal F$ of measurable functions on a sample space $\mathcal Z$, a typical quantity is the largest discrepancy between the empirical average and its population counterpart. If $\mathcal F$ is uncountable, that supremum is an uncountable supremum of random variables. Measurability of each individual random variable does not, by itself, imply measurability of the supremum.

This is not merely a technical concern about notation. Ordinary probability $P(A)$ is defined for measurable events $A$. If the event that a supremum exceeds a threshold is not measurable, an ordinary probability bound for that event is not defined. Two standard resolutions are to establish that a countable subclass preserves the supremum, or to state the bound using outer probability.

Definition: Let $X_1,\ldots,X_n$ be observations in a measurable space $(\mathcal Z,\mathcal A)$, with common distribution $P$. For a measurable function $f$ with $P|f|<\infty$, write $Pf=E[f(X_1)]$ and $P_nf=n^{-1}\sum_{i=1}^n f(X_i)$. The empirical deviation indexed by $f$ is $Z_f=P_nf-Pf$. A supremum such as $\sup_{f\in\mathcal F}|Z_f|$ is measurable if it is a measurable random variable; equivalently, its strict upper-level events are measurable.

An Uncountable Supremum Can Fail to Be Measurable

For a countable collection of measurable random variables $Y_j$, the supremum is measurable: for every real $a$, $\{\sup_j Y_j>a\}=\bigcup_j\{Y_j>a\}$, a countable union of measurable events. This argument does not extend to an uncountable union. The following example shows the problem even when every function in the class is a simple indicator.

Worked Example: A Nonmeasurable Empirical Supremum

Let the sample space be $[0,1]$ with the completed Lebesgue sigma-algebra and the uniform distribution. Choose a nonmeasurable Vitali set $V\subset[0,1]$. For every $t\in V$, define $f_t(x)=\mathbf 1_{\{t\}}(x)$, and let $\mathcal F=\{f_t:t\in V\}$. Each singleton $\{t\}$ is measurable and has probability zero, so every $f_t$ is measurable and $Pf_t=0$.

With one observation $X$, the empirical deviation for $f_t$ is $P_1f_t-Pf_t=\mathbf 1_{\{t\}}(X)$. Taking the supremum over $t\in V$ gives

\sup_{t\in V}|P_1f_t-Pf_t| =\sup_{t\in V}\mathbf 1_{\{t\}}(X) =\mathbf 1_V(X).

The last expression is not measurable, because $V$ is not measurable. Thus all the individual deviations are measurable, but their uncountable supremum is not. The issue is the uncountable union of singleton events, not any irregularity in an individual function.

Countable Separable Classes

A useful sufficient condition for measurability is that the full class can be approximated pointwise by a countable subclass. The pointwise requirement matters: density in an average distance alone does not guarantee that function values converge at the observed sample points.

Definition: A class $\mathcal F$ of measurable functions is pointwise separable if there is a countable subclass $\mathcal F_0\subseteq\mathcal F$ such that, for every $f\in\mathcal F$, there is a sequence $f_k\in\mathcal F_0$ with $f_k(z)\to f(z)$ for every $z\in\mathcal Z$.

Here is the countable-reduction result for empirical deviations. An integrable envelope is a measurable function $G$ satisfying $|f(z)|\leq G(z)$ for all $f\in\mathcal F$ and $z\in\mathcal Z$, with $PG<\infty$. A uniform finite bound is a special case.

Theorem: Suppose $X_1,\ldots,X_n$ take values in $\mathcal Z$, every $f\in\mathcal F$ is measurable, $\mathcal F$ is pointwise separable with countable subclass $\mathcal F_0$, and $\mathcal F$ has an integrable envelope. Then, for every sample $(X_1,\ldots,X_n)$, $$ \sup_{f\in\mathcal F}|P_nf-Pf| = \sup_{f\in\mathcal F_0}|P_nf-Pf|. $$ In particular, the supremum on the left is measurable.

Proof. Fix any $f\in\mathcal F$, and choose $f_k\in\mathcal F_0$ converging pointwise to $f$. At each fixed sample, convergence at the finitely many observed points gives $P_nf_k\to P_nf$. Also, $|f_k|\leq G$ and $PG<\infty$, so the dominated convergence theorem gives $Pf_k\to Pf$. Therefore $|P_nf_k-Pf_k|\to |P_nf-Pf|$. It follows that $|P_nf-Pf|\leq\sup_{g\in\mathcal F_0}|P_ng-Pg|$. Taking the supremum over $f\in\mathcal F$ proves one inequality. Since $\mathcal F_0\subseteq\mathcal F$, the reverse inequality follows immediately. The right-hand supremum is a countable supremum of measurable random variables, and is therefore measurable. $\square$

The envelope hypothesis ensures that the population averages converge along the pointwise approximating sequence. The empirical averages require no integration limit: they are finite sums, and pointwise convergence applies directly to each observed value.

Worked Example: Threshold Functions on the Unit Interval

Let $X_1,\ldots,X_n$ be uniform on $[0,1]$, and consider $f_t(x)=\mathbf 1_{\{x\leq t\}}$ for $t\in[0,1]$. The class is bounded by $G=1$, and $Pf_t=t$. Take the countable subclass with indices in $(\mathbb Q\cap[0,1])\cup\{1\}$.

For any $t<1$, choose rationals $q_k>t$ decreasing to $t$. For each $x\leq t$, $f_{q_k}(x)=f_t(x)=1$. For each $x>t$, eventually $q_k<x$, so $f_{q_k}(x)=0=f_t(x)$. Thus $f_{q_k}(x)\to f_t(x)$ at every $x$; the endpoint $t=1$ is already in the subclass. The theorem therefore reduces the full empirical-deviation supremum to this countable set of thresholds.

For a concrete sample $X_1=1/4$, $X_2=3/4$, the empirical distribution at threshold $t$ is $0$ for $t<1/4$, $1/2$ for $1/4\leq t<3/4$, and $1$ for $3/4\leq t\leq1$. On the first interval, the deviation from $t$ is $t$, with supremum $1/4$. On the middle interval, its absolute value is $|1/2-t|$, which is at most $1/4$. On the last interval, it is $1-t$, also at most $1/4$. At $t=1/4$ or $t=3/4$, the absolute deviation equals $1/4$. Hence the full supremum is $1/4$, and the countable subclass gives the same value.

Worked Example: A Continuous Parametric Class

Let $X_1,\ldots,X_n$ be uniform on $[0,1]$, and set $f_\theta(x)=\theta x$ for $0\leq\theta\leq1$. The class is bounded by $1$, and $Pf_\theta=\theta/2$. The subclass with rational $\theta\in[0,1]$, together with $\theta=1$, is pointwise dense: for any $\theta<1$, choose rationals $\theta_k\to\theta$, and then $\theta_k x\to\theta x$ for every $x$. Thus the supremum over the full class equals the measurable supremum over that countable subclass.

For a sample $X_1=1/4$, $X_2=1/2$, the sample mean is $3/8$, so

P_nf_\theta-Pf_\theta =\theta\left(\frac{3}{8}-\frac{1}{2}\right) =-\frac{\theta}{8}.

Its absolute value is $\theta/8$, whose supremum over $0\leq\theta\leq1$ is $1/8$, attained at $\theta=1$. The rational parameters approach this value as well, so the countable supremum is exactly $1/8$.

Outer Probability When Countable Reduction Is Unavailable

Some classes do not come with a suitable countable pointwise-dense subclass. One can still give rigorous bounds without asserting that the supremum or its upper-level events are measurable. Outer probability assigns a value to every subset of the sample space by measuring it through measurable supersets.

Definition: For any subset $A$ of a probability space $(\Omega,\mathcal A,P)$, its outer probability is $$ P^*(A)=\inf\{P(B): B\in\mathcal A,\ A\subseteq B\}. $$ If $A$ is measurable, then $P^*(A)=P(A)$. For an arbitrary nonnegative function $Y$, its outer expectation is $E^*[Y]=\inf\{E[W]: W\text{ is measurable and }W\geq Y\}$, when such measurable majorants are being considered.

The basic set property needed for probability bounds is countable subadditivity.

Theorem: For arbitrary subsets $A_1,A_2,\ldots$ of a probability space, $$ P^*\left(\bigcup_{j=1}^{\infty}A_j\right) \leq \sum_{j=1}^{\infty}P^*(A_j). $$

Proof. If the sum on the right is infinite, the inequality is immediate. Otherwise, for any $\varepsilon>0$, choose measurable sets $B_j\supseteq A_j$ such that $P(B_j)\leq P^*(A_j)+\varepsilon 2^{-j}$. The measurable set $\bigcup_j B_j$ contains $\bigcup_j A_j$. By countable subadditivity of $P$, $$ P^*\left(\bigcup_j A_j\right) \leq P\left(\bigcup_j B_j\right) \leq \sum_j P(B_j) \leq \sum_j P^*(A_j)+\varepsilon. $$ Letting $\varepsilon$ decrease to zero proves the claim. $\square$

Worked Example: Stating a Bound for a Nonmeasurable Event

Return to the singleton class indexed by the Vitali set $V$. For one uniform observation, the event that its empirical supremum exceeds zero is $$ \left\{\sup_{t\in V}|P_1f_t-Pf_t|>0\right\}=V. $$ This event is not measurable, so writing its ordinary probability is not justified. The outer-probability statement $P^*(V)$ is defined. It is positive: the rational translates $V+q$, for $q\in\mathbb Q\cap[-1,1]$, are pairwise disjoint and their union covers $[0,1]$. If $P^*(V)=0$, countable subadditivity and translation invariance of Lebesgue outer measure would make this union have outer measure zero, contradicting that it contains $[0,1]$. Also $P^*(V)\leq1$, since $[0,1]$ is a measurable superset. Thus outer probability gives a valid formulation even though this event is not measurable.

In applications, a uniform deviation statement can be written with $P^*(\sup_{f\in\mathcal F}|P_nf-Pf|>\varepsilon)$ when measurability has not been established. If a countable reduction theorem applies, the supremum is measurable and outer probability agrees with ordinary probability. Outer probability is a safe way to state a bound; it does not itself prove a bound or make the underlying supremum measurable.

Common Pitfall

Wrong reasoning: “Every $f\in\mathcal F$ is measurable, so $\sup_{f\in\mathcal F}|P_nf-Pf|$ is measurable.” This treats an uncountable union as though it were a countable union. The singleton example shows the conclusion can fail. Correction: prove that a countable subclass preserves the supremum, or formulate probability statements using outer probability. Do not use an ordinary probability for an event before establishing that the event is measurable.

Key takeaway: Measurability of each indexed random variable is not enough for measurability of an uncountable supremum. Pointwise separability plus an integrable envelope gives an exact countable reduction for empirical deviations; otherwise, outer probability provides a rigorous language for bounds on potentially nonmeasurable events.

Check Your Understanding

Check that you can distinguish the two measurability strategies.

Why does a countable supremum of measurable random variables remain measurable, and what part of that argument fails for an uncountable class?
In the singleton-class example, why is each $f_t$ measurable even though the supremum is not?
State the two convergence facts used to prove countable reduction for empirical deviations.
Why does pointwise convergence of an approximating sequence imply convergence of its empirical averages for a fixed finite sample?
When is an outer-probability statement appropriate instead of an ordinary probability statement?