The Expected Symmetrization Inequality

Why Compare Two Empirical Averages?

A uniform deviation asks how far empirical averages can be from their population averages, with the worst case taken over a class of functions. The population averages are not observed, so directly bounding that worst-case error can be difficult. A useful move is to introduce an independent copy of the data and compare the two empirical averages instead. This copy is called a ghost sample: it is a mathematical device, not additional observed data.

The expected symmetrization inequality formalizes this move. It says that the expected worst-case deviation from the population is no greater than the expected worst-case difference between the original sample and an independent sample of the same size. The inequality is about expectations of suprema, not about a pointwise ordering for each pair of samples.

Definitions and the Inequality

Definition: Let \(X_1,\ldots,X_n\) be independent and identically distributed random variables with distribution \(P\). For a measurable, integrable function \(f\), define its population average \(Pf=E[f(X_1)]\) and empirical average \(P_n f=n^{-1}\sum_{i=1}^n f(X_i)\). Let \(X_1',\ldots,X_n'\) be an independent sample with the same distribution, and define \(P_n'f=n^{-1}\sum_{i=1}^n f(X_i')\). The primed sample is the ghost sample.

Let \(\mathcal F\) be a nonempty, countable class of measurable functions such that \(E|f(X_1)|<\infty\) for each \(f\in\mathcal F\). Countability ensures that the suprema below are measurable. A simple sufficient condition for all the quantities to be integrable is a common bound \(|f(x)|\le M\) for every \(f\in\mathcal F\) and every \(x\).

Theorem (Expected symmetrization inequality): Under these conditions,

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].

The expectation on the right is over both independent samples. For an uncountable class, the same statement requires suitable measurability and integrability conditions on the suprema; the countable-class formulation avoids those additional technical issues.

The right side is still a uniform deviation: it takes a supremum over the same class. Its advantage is that it compares two empirical averages, so it does not involve the unknown population average \(Pf\). The bound is an expectation-level statement; it does not assert that the ghost-sample difference is larger for every realized pair of samples.

Worked Examples

Worked Example: A Bernoulli Observation and One Function

Let \(X_1\sim\operatorname{Bernoulli}(1/4)\), take \(n=1\), and let \(\mathcal F\) contain just \(f(x)=x\). Then \(Pf=1/4\), and the left side is \(E|X_1-1/4|\). If \(X_1=1\), the absolute deviation is \(3/4\); if \(X_1=0\), it is \(1/4\). Therefore

E|X_1-1/4| =\frac14\cdot\frac34+\frac34\cdot\frac14 =\frac{3}{16}+\frac{3}{16} =\frac38.

For the ghost sample \(X_1'\), the right side is \(E|X_1-X_1'|\). The absolute difference is one exactly when the two Bernoulli variables disagree. The disagreement probability is

P(X_1\ne X_1') =P(X_1=1,X_1'=0)+P(X_1=0,X_1'=1) =\frac14\cdot\frac34+\frac34\cdot\frac14 =\frac38.

Thus both sides equal \(3/8\) in this example. Equality here is not a general feature of the inequality.

Worked Example: A Finite Class of Indicators

Let \(X_i\) take values \(1,2,3\) with equal probability, take \(n=1\), and set \(\mathcal F=\{f_1,f_2\}\), where \(f_1(x)=\mathbf 1\{x=1\}\) and \(f_2(x)=\mathbf 1\{x=2\}\). Each population average is \(1/3\).

If \(X_1=1\), the two deviations are \(2/3\) and \(1/3\), so their maximum absolute value is \(2/3\). If \(X_1=2\), it is again \(2/3\). If \(X_1=3\), both deviations have absolute value \(1/3\). Hence

E\!\left[\sup_{f\in\mathcal F}|P_1f-Pf|\right] =\frac13\cdot\frac23+\frac13\cdot\frac23+\frac13\cdot\frac13 =\frac59.

For the ghost-sample side, \(P_1f-P_1'f=f(X_1)-f(X_1')\). If \(X_1=X_1'\), the supremum is zero. If the two values differ, at least one of the indicators distinguishes them, so the supremum of the absolute differences is one. The independent draws differ with probability \(1-3(1/3)^2=2/3\). Therefore

E\!\left[\sup_{f\in\mathcal F}|P_1f-P_1'f|\right] =\frac23 \ge \frac59.

The two sides need not match: the ghost-sample comparison can give a looser bound.

Worked Example: Two Observations from a Bernoulli Distribution

Let \(X_i\sim\operatorname{Bernoulli}(1/2)\), take \(n=2\), and again use the singleton class \(f(x)=x\). Write \(K=X_1+X_2\), so \(P_2f=K/2\). The values \(K=0,1,2\) have probabilities \(1/4,1/2,1/4\), and the absolute deviations from \(Pf=1/2\) are \(1/2,0,1/2\). Thus

E|P_2f-Pf| =\frac14\cdot\frac12+\frac12\cdot0+\frac14\cdot\frac12 =\frac14.

For the ghost sample, let \(K'=X_1'+X_2'\), which is independent of \(K\) and has the same probabilities. The empirical-average difference is \(|K-K'|/2\). The probability that \(|K-K'|=1\) is \(1/2\): the four ordered pairs \((0,1),(1,0),(1,2),(2,1)\) each have probability \(1/8\). The probability that \(|K-K'|=2\) is \(1/8\), from \((0,2)\) and \((2,0)\), each of probability \(1/16\). Consequently,

E|P_2f-P_2'f| =\frac12\left(1\cdot\frac12+2\cdot\frac18\right) =\frac38 \ge\frac14.

This calculation illustrates that the ghost sample adds variation: it compares two random empirical averages rather than comparing one average to a fixed population value.

What the Ghost-Sample Difference Looks Like

Even when a full uniform deviation is being studied, the difference for any single fixed function has a simple second-moment calculation. Write \(\sigma_f^2=\operatorname{Var}(f(X_1))\), and assume this variance is finite.

Result: For a fixed \(f\) with finite variance,

E[P_n f-P_n'f]=0, \qquad \operatorname{Var}(P_n f-P_n'f)=\frac{2\sigma_f^2}{n}, \qquad E|P_n f-P_n'f|\le \sqrt{\frac{2\sigma_f^2}{n}}.

To verify the first identity, both empirical averages have expectation \(Pf\), so their difference has expectation \(Pf-Pf=0\). For the variance, the two empirical averages are independent, each has variance \(\sigma_f^2/n\), and independent random variables have covariance zero. Therefore

\operatorname{Var}(P_n f-P_n'f) =\operatorname{Var}(P_n f)+\operatorname{Var}(P_n'f) =\frac{\sigma_f^2}{n}+\frac{\sigma_f^2}{n} =\frac{2\sigma_f^2}{n}.

Finally, for any square-integrable random variable \(Y\), Cauchy–Schwarz gives \(E|Y|\le\sqrt{E[Y^2]}\). Applying this to \(Y=P_n f-P_n'f\), whose mean is zero, yields

E|P_n f-P_n'f| \le \sqrt{E[(P_n f-P_n'f)^2]} =\sqrt{\operatorname{Var}(P_n f-P_n'f)} =\sqrt{\frac{2\sigma_f^2}{n}}.

This result concerns one function. Taking a supremum over a class changes the problem: the function attaining the largest difference can vary with the observed samples. The expected symmetrization inequality handles that uniform comparison, but a single-function variance calculation alone does not control the supremum.

Using the Bound Carefully

The theorem is useful because the population average disappears from the expression on its right. This can make the right side more amenable to analysis, especially when the class has structure that allows its empirical differences to be bounded. The inequality itself does not say how small that right side is; that requires further information about the class and the distribution.

A common mistake is to argue that, for every \(f\), the difference between two sample averages must be at least the deviation of the first from the population average. That is false: the two sample averages can happen to be close even when both are far from the population average. The theorem instead compares expected suprema. The independent ghost sample has the same distribution as the original sample, and averaging over it gives the stated expectation bound; this is not a pointwise comparison.

Another mistake is to treat the ghost sample as fixed or dependent on the original sample. Its independence and identical distribution are part of the setup. Without them, the expectation on the right need not represent the comparison in the theorem. Finally, keep the order of operations clear: the theorem bounds the expectation of a supremum, not the supremum of separate expectations.

Key takeaway: For a countable integrable function class and an independent sample from the same distribution, expected uniform deviation from the population is bounded by the expected uniform difference between two empirical averages. It is a comparison in expectation, not a sample-by-sample inequality.

Check Your Understanding

Try these questions before moving on.

In the expected symmetrization inequality, what distribution must the ghost sample have, and how must it relate to the original sample?
Why does countability of the function class make the supremum measurable?
For a fixed function with variance \(\sigma_f^2\), what is the variance of \(P_n f-P_n'f\), and which assumptions are used to compute it?
Why does the theorem not imply that the ghost-sample difference exceeds the population deviation for every realized sample pair?
In the three-category indicator example, why is the supremum of the ghost-sample differences one whenever the two sampled categories differ?