Proof of Symmetrization by Conditional Jensen

Why Introduce a Second Sample?

A uniform deviation compares empirical averages with population averages across a whole function class. The population average is not observed, so it can be difficult to analyze directly. An independent sample from the same distribution offers a useful replacement: conditional on the observed data, its empirical average has expectation equal to the population average. Conditional Jensen’s inequality then bounds the original deviation by a deviation between two empirical averages.

The key point is that the argument works for the supremum over functions, not only for one fixed function. We will make the measurability and integrability conditions explicit and prove that step before using the inequality in examples.

Setup and Definitions

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed observations with distribution $P$ on a measurable space $(\mathcal X,\mathcal A)$. For a measurable, integrable function $f:\mathcal X\to\mathbb R$, write $Pf=E[f(X_1)]$ for its population average and $P_n f=n^{-1}\sum_{i=1}^n f(X_i)$ for its empirical average. Let $X_1',\ldots,X_n'$ be an independent sample with the same distribution, and write $P_n'f=n^{-1}\sum_{i=1}^n f(X_i')$.

The independent sample $X_1',\ldots,X_n'$ is called a ghost sample. It is introduced for the proof, not because the population distribution is known or observed. Throughout this tutorial, $\mathcal F$ is a nonempty, countable class of measurable functions and there is a finite constant $M$ such that $|f(x)|\le M$ for every $f\in\mathcal F$ and $x\in\mathcal X$. Countability ensures the suprema below are measurable; boundedness makes them integrable.

Theorem: Under these assumptions, $$ E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le E\left[\sup_{f\in\mathcal F}|P_n f-P_n'f|\right]. $$

This is the expected symmetrization inequality. Its right-hand side compares two empirical averages based on identically distributed samples. No independence between the different functions’ values is required; what matters is that the ghost sample is independent of the observed sample and has the same distribution.

Proof by Conditional Jensen

Let $\mathcal G=\sigma(X_1,\ldots,X_n)$, the information in the observed sample. For any fixed $f\in\mathcal F$, the observed average $P_n f$ is $\mathcal G$-measurable. Independence and identical distribution give

E[P_n'f\mid\mathcal G] =\frac1n\sum_{i=1}^n E[f(X_i')\mid\mathcal G] =\frac1n\sum_{i=1}^n Pf =Pf.

Consequently, $P_n f-Pf=E[P_n f-P_n'f\mid\mathcal G]$. Conditional Jensen first bounds the absolute value of this conditional expectation. We then take the supremum and bound it by the conditional expectation of the supremum:

\begin{aligned} \sup_{f\in\mathcal F}|P_n f-Pf| &=\sup_{f\in\mathcal F} \left|E[P_n f-P_n'f\mid\mathcal G]\right|\\ &\le \sup_{f\in\mathcal F}E[|P_n f-P_n'f|\mid\mathcal G]\\ &\le E\left[\sup_{f\in\mathcal F}|P_n f-P_n'f|\mid\mathcal G\right]. \end{aligned}

The first inequality is the conditional form of $|E[Y\mid\mathcal G]|\le E[|Y|\mid\mathcal G]$. For the second, each term $|P_n f-P_n'f|$ is bounded above by the same random variable $\sup_{g\in\mathcal F}|P_n g-P_n'g|$. Taking conditional expectations preserves that inequality, and then taking the supremum over $f$ proves the displayed step. Countability allows these inequalities to hold simultaneously for all $f$, outside one null set.

Taking expectations of both sides and using the defining property of conditional expectation yields

E\left[\sup_{f\in\mathcal F}|P_n f-Pf|\right] \le E\left[ E\left[\sup_{f\in\mathcal F}|P_n f-P_n'f|\mid\mathcal G\right] \right] = E\left[\sup_{f\in\mathcal F}|P_n f-P_n'f|\right].

All quantities are finite: each empirical average lies in $[-M,M]$, so each absolute difference in the right-hand supremum is at most $2M$. This proves the inequality. $\square$

The proof uses two separate ideas. Conditional Jensen handles each function’s difference from its mean; the supremum is then bounded by the conditional expectation of the supremum. Reversing or skipping that order is not justified by the argument.

Worked Examples

Worked Example: A Single Bernoulli Indicator

Let $X_i\sim\operatorname{Bernoulli}(0.3)$, let $n=1$, and take $\mathcal F=\{f\}$ with $f(x)=x$. Then $Pf=0.3$. The observed value is 1 with probability 0.3 and 0 with probability 0.7, so

$$ E|P_1f-Pf| =0.3|1-0.3|+0.7|0-0.3| =0.3(0.7)+0.7(0.3) =0.42. $$

For the ghost-sample difference, the two Bernoulli observations disagree with probability $0.3(0.7)+0.7(0.3)=0.42$. Their absolute difference is 1 when they disagree and 0 otherwise. Therefore

$$ E|P_1f-P_1'f|=0.42(1)+0.58(0)=0.42. $$

Here the two sides are equal. Replacing the population average by a ghost average has not loosened the bound in this particular case.

Worked Example: A Class with Two Complementary Functions

Again let $X_i\sim\operatorname{Bernoulli}(0.25)$ and $n=1$, but now take $\mathcal F=\{f_1,f_2\}$, where $f_1(x)=x$ and $f_2(x)=1-x$. The population averages are $Pf_1=0.25$ and $Pf_2=0.75$. If $X_1=1$, both absolute deviations are $0.75$; if $X_1=0$, both are $0.25$. Thus

E\left[\sup_{f\in\mathcal F}|P_1f-Pf|\right] =0.25(0.75)+0.75(0.25)=0.375.

For the ghost-sample side, if $X_1=X_1'$, both functions have empirical difference zero. If $X_1\ne X_1'$, each function has absolute difference 1, so the supremum is 1. The probability of disagreement is $0.25(0.75)+0.75(0.25)=0.375$. Therefore

E\left[\sup_{f\in\mathcal F}|P_1f-P_1'f|\right] =0.375(1)+0.625(0)=0.375.

This example shows why the supremum belongs inside each expectation: on each realized sample, the function giving the largest deviation can depend on the observed value.

Worked Example: A Strict Inequality with Two Observations

Let $X_i\sim\operatorname{Bernoulli}(0.25)$, $n=2$, and $\mathcal F=\{f\}$ with $f(x)=x$. If $K=X_1+X_2$, then $P_2f=K/2$, and $K$ has probabilities $P(K=0)=9/16$, $P(K=1)=6/16$, and $P(K=2)=1/16$. Since $Pf=0.25$, the absolute deviations for $K=0,1,2$ are $0.25,0.25,0.75$. Hence

E|P_2f-Pf| =\frac9{16}(0.25)+\frac6{16}(0.25)+\frac1{16}(0.75) =0.28125=\frac{36}{128}.

Let $K'$ be the corresponding count in the independent ghost sample. It has the same probabilities as $K$. The probability that $|K-K'|=1$ is $2[(9/16)(6/16)+(6/16)(1/16)]=120/256$. The probability that $|K-K'|=2$ is $2(9/16)(1/16)=18/256$. Since $|P_2f-P_2'f|=|K-K'|/2$,

E|P_2f-P_2'f| =\frac12\left(\frac{120}{256}+2\frac{18}{256}\right) =\frac{39}{128} =0.3046875.

Thus $36/128\le39/128$, strictly. The ghost-sample comparison can be more variable than the original deviation, which is consistent with its role as an upper bound.

Why the Supremum Step Matters

For a single function, conditional Jensen immediately gives $E|P_n f-Pf|\le E|P_n f-P_n'f|$. The uniform statement is not obtained by simply choosing one function in advance: the largest deviation can be attained by different functions on different samples. The proof instead establishes a pointwise conditional bound that holds for every function, then uses the fact that the conditional expectation of a pointwise supremum dominates each conditional expectation.

The countability assumption is a convenient way to ensure that the supremum is a random variable and that all conditional inequalities can be treated on a common probability-one set. For an uncountable class, measurability of the supremum cannot be presumed. One needs additional measurability conditions, such as a suitable countable subclass determining the same supremum, before using this proof with ordinary expectations.

Common Mistake

Pitfall: It is not enough to write “the ghost average has mean $Pf$, so the supremum of the original deviations is bounded by the supremum of the ghost deviations.” The mean identity alone gives no inequality between those suprema. The correction is to condition on the observed sample, express each deviation as a conditional expectation of a ghost-sample difference, apply conditional Jensen, and only then bound the supremum by the conditional expectation of the supremum.

A second error is to assume that the ghost sample is independent after conditioning without stating why. It is independent by construction: the entire ghost sample is independent of $\mathcal G=\sigma(X_1,\ldots,X_n)$. This is what makes each conditional mean $E[f(X_i')\mid\mathcal G]$ equal to $Pf$.

Check Your Understanding

Use the conditioning argument and the examples to answer these questions.

Why does $E[P_n'f\mid\mathcal G]=Pf$ hold for a fixed $f$?
Which inequality in the proof requires countability or another condition ensuring measurable suprema?
For a single function, what does conditional Jensen bound before expectations are taken?
In the two-function Bernoulli example, why can the function giving the largest deviation depend on the observed sample?
What additional issue must be addressed before applying the proof to an uncountable function class?