Probability Symmetrization with a Ghost Sample

From an Empirical Deviation to a Two-Sample Event

A uniform deviation is a statement about the largest discrepancy between empirical averages and their population expectations across a function class. Its probability can be difficult to analyze directly because every empirical average is compared with a fixed, possibly unknown expectation. A ghost sample provides a useful alternative: it is an independent sample from the same distribution, whose empirical average can stand in for that expectation with high probability.

The key step is conditional. If the observed sample has a function whose empirical average is far from its expectation, then, with sufficiently high conditional probability, the ghost empirical average is close to that same expectation. The two empirical averages must then be far apart. Markov’s inequality supplies the probability guarantee, but only when the deviation threshold is large enough relative to the sample size and the function variances.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed observations with common distribution $P$, and let $X'_1,\ldots,X'_n$ be an independent sample with that same distribution. For an integrable function $f$, write $Pf=E[f(X_1)]$, $P_n f=n^{-1}\sum_{i=1}^n f(X_i)$, and $P'_n f=n^{-1}\sum_{i=1}^n f(X'_i)$. For a class $\mathcal F$, the one-sample uniform deviation is $\sup_{f\in\mathcal F}|P_n f-Pf|$, and the two-sample deviation is $\sup_{f\in\mathcal F}|P_n f-P'_n f|$.

For the statements below, assume that $\mathcal F$ is countable and that $f(X_1)$ is integrable with finite variance for every $f\in\mathcal F$. Countability ensures the suprema are measurable; it also allows us to choose a measurable witness by taking the first qualifying function in a fixed enumeration. Suppose further that $ \operatorname{Var}(f(X_1))\leq v $ for every $f\in\mathcal F$, where $v$ is finite.

The Probability Symmetrization Bound

Theorem: Under the conditions above, for every $\varepsilon>0$ satisfying $n\varepsilon^2\geq 8v$, $$ P\!\left(\sup_{f\in\mathcal F}|P_n f-Pf|>\varepsilon\right) \leq 2P\!\left(\sup_{f\in\mathcal F}|P_n f-P'_n f|>\frac{\varepsilon}{2}\right). $$ The probability on the right is over both independent samples. If $v=0$, the stated threshold condition is automatic.

The factor $2$ comes from ensuring that the ghost average is within $\varepsilon/2$ of the population expectation with conditional probability at least $1/2$. The threshold $n\varepsilon^2\geq8v$ is exactly what makes that guarantee follow from Markov’s inequality applied to a squared deviation.

Find a witness in the observed sample.
On the event that the one-sample supremum exceeds $\varepsilon$, select a function whose empirical deviation exceeds $\varepsilon$.

Control the ghost average conditionally.
For that fixed witness, the ghost average has variance at most $v/n$. Markov’s inequality bounds the chance that it is at least $\varepsilon/2$ from its expectation.

Compare the two averages.
When the ghost average is close to the expectation, the triangle inequality forces the witness’s two-sample deviation to exceed $\varepsilon/2$.

Here is the full argument. For a fixed function $f$, independence of the ghost observations gives $ \operatorname{Var}(P'_n f)=\operatorname{Var}(f(X_1))/n\leq v/n $. Markov’s inequality applied to the nonnegative squared deviation therefore gives

P\!\left(|P'_n f-Pf|\geq \frac{\varepsilon}{2}\right) \leq \frac{E[(P'_n f-Pf)^2]}{(\varepsilon/2)^2} \leq \frac{4v}{n\varepsilon^2} \leq \frac{1}{2}.

Let $E$ denote the event $\sup_{f\in\mathcal F}|P_n f-Pf|>\varepsilon$. For each observed sample in $E$, choose the first function $f$ in the enumeration for which $|P_n f-Pf|>\varepsilon$. This choice depends only on the observed sample. Conditional on that sample, the bound just established applies to the selected function, so the ghost sample satisfies $|P'_n f-Pf|<\varepsilon/2$ with probability at least $1/2$. On this event, the reverse triangle inequality yields

|P_n f-P'_n f| \geq |P_n f-Pf|-|P'_n f-Pf| > \varepsilon-\frac{\varepsilon}{2} =\frac{\varepsilon}{2}.

Thus, conditional on every observed sample in $E$, the probability that the two-sample supremum exceeds $\varepsilon/2$ is at least $1/2$. Integrating over the observed sample gives $P(\sup_{f\in\mathcal F}|P_n f-P'_n f|>\varepsilon/2)\geq P(E)/2$, which proves the theorem. $\square$

Bounded Functions and the Threshold

A common way to verify the variance condition is to bound the range of every function. If $a\leq f(X_1)\leq b$ almost surely, then $\operatorname{Var}(f(X_1))\leq(b-a)^2/4$. To see this, put $Y=f(X_1)$. Since $(Y-a)(b-Y)\geq0$, taking expectations and rearranging gives $E[Y^2]\leq(a+b)E[Y]-ab$. Consequently,

\operatorname{Var}(Y) =E[Y^2]-(E[Y])^2 \leq (b-E[Y])(E[Y]-a) \leq \frac{(b-a)^2}{4}.

The final inequality follows because the two nonnegative factors have sum $b-a$, and their product is at most one quarter of the squared sum. Substituting $v=(b-a)^2/4$ into the theorem gives this useful form:

Corollary: If every $f\in\mathcal F$ takes values in the same interval $[a,b]$ almost surely, then, whenever $n\varepsilon^2\geq2(b-a)^2$, $$ P\!\left(\sup_{f\in\mathcal F}|P_n f-Pf|>\varepsilon\right) \leq 2P\!\left(\sup_{f\in\mathcal F}|P_n f-P'_n f|>\frac{\varepsilon}{2}\right). $$

Worked Example: A Single Bernoulli Indicator

Let $X_i\sim\operatorname{Bernoulli}(1/2)$, and take the singleton class $\mathcal F=\{f\}$, where $f(x)=x$. The values lie in $[0,1]$, so the variance bound is $v=1/4$. Set $n=50$ and $\varepsilon=0.2$. The threshold calculation is $n\varepsilon^2=50(0.2)^2=50(0.04)=2$, while $8v=8(1/4)=2$. The condition holds exactly, so

P\!\left(\left|\frac{1}{50}\sum_{i=1}^{50}X_i-\frac12\right|>0.2\right) \leq 2P\!\left(\left|\frac{1}{50}\sum_{i=1}^{50}X_i -\frac{1}{50}\sum_{i=1}^{50}X'_i\right|>0.1\right).

The right-hand event compares two sample proportions, and the population mean $1/2$ no longer appears. This example verifies that equality at the threshold is sufficient; the theorem requires $n\varepsilon^2\geq8v$, not a strict inequality.

Worked Example: A Finite Class of Category Indicators

Suppose each observation has one of three categories, $A,B,$ or $C$, and let $\mathcal F=\{f_A,f_B\}$, where $f_A(x)=\mathbf{1}\{x=A\}$ and $f_B(x)=\mathbf{1}\{x=B\}$. Both functions take values in $[0,1]$. For $n=200$ and $\varepsilon=0.1$, the bounded-range threshold is $n\varepsilon^2=200(0.01)=2$, exactly the required $2(1-0)^2=2$. Therefore,

P\!\left( \max\{|P_n f_A-Pf_A|,\ |P_n f_B-Pf_B|\}>0.1 \right) \leq 2P\!\left( \max\{|P_n f_A-P'_n f_A|,\ |P_n f_B-P'_n f_B|\}>0.05 \right).

The supremum is a maximum over two functions, so it is measurable without any additional selection issue. The argument does not require the category probabilities to be equal: the same conclusion holds for any distribution on $A,B,C$, since the variance bound used only the range of the indicators.

Worked Example: Checking a Variance-Based Threshold

Suppose every function in a countable class takes values in $[2,5]$, and its variance is therefore at most $v=(5-2)^2/4=9/4=2.25$. Take $n=200$ and $\varepsilon=0.3$. The general variance threshold is $8v=8(2.25)=18$, and $n\varepsilon^2=200(0.09)=18$. Hence the probability symmetrization inequality applies:

P\!\left(\sup_{f\in\mathcal F}|P_n f-Pf|>0.3\right) \leq 2P\!\left(\sup_{f\in\mathcal F}|P_n f-P'_n f|>0.15\right).

The same conclusion follows directly from the bounded-range threshold $2(b-a)^2=2(3)^2=18$. If instead $n=199$, then $n\varepsilon^2=17.91<18$, so this variance-based theorem does not justify the displayed inequality at that sample size and threshold. A different argument or a larger threshold would be needed.

Common Pitfall: Using the Bound Below Its Threshold

A tempting but incomplete argument is: “On a large-deviation sample, the ghost average is close to its expectation with probability at least one half, so the two-sample event is at least half as likely.” The missing step is the guarantee that the ghost average is close with probability at least one half. Markov’s inequality only supplies $P(|P'_n f-Pf|\geq\varepsilon/2)\leq4v/(n\varepsilon^2)$. If $n\varepsilon^2<8v$, this upper bound can exceed one half and gives no such guarantee. One cannot then infer the factor $2$ from this proof.

The correction is to state and check the threshold before applying the inequality. For a range-$[0,1]$ class, the condition is $n\varepsilon^2\geq2$; for a general class with variance bound $v$, it is $n\varepsilon^2\geq8v$. The condition is a sufficient hypothesis for this symmetrization argument, not a claim that the inequality must fail whenever the condition is absent.

Key takeaway: A ghost sample turns a one-sample uniform deviation into a two-sample deviation probability only after the ghost average has been shown to approximate the population expectation with conditional probability at least one half. The variance bound and threshold condition are what make that step valid.

Check Your Understanding

Use the variance-based theorem and its bounded-range corollary to answer the following.

If $\operatorname{Var}(f(X_1))\leq 3$ for every function in a countable class, what condition on $n$ and $\varepsilon$ ensures the theorem applies?
For functions valued in $[-1,1]$, what is the largest variance bound obtained from the range, and what threshold condition follows?
Why is the function witnessing a large deviation allowed to depend on the observed sample but not on the ghost sample in the proof?
In the category-indicator example, why does the proof not require the categories to have equal probabilities?
Does failure of the stated threshold condition prove that probability symmetrization is false? Explain what the condition establishes.

Probability Symmetrization with a Ghost Sample

What You'll Learn