Ghost Samples for Uniform Deviations

Why Introduce a Ghost Sample?

A uniform deviation compares an empirical average with its population counterpart across an entire function class. For a class $\mathcal{G}$, its size on a sample $X_1,\ldots,X_n$ is measured by

\sup_{g\in\mathcal{G}}\left|P_n g-Pg\right|, \qquad P_n g=\frac{1}{n}\sum_{i=1}^{n}g(X_i), \qquad Pg=E[g(X)].

The population average $Pg$ is fixed, while $P_n g$ varies with the observed sample. A ghost sample provides a useful way to represent that fixed average: condition on the observed data and average over a second, independent sample. For each fixed $g$, the ghost empirical average has conditional expectation $Pg$. This representation also gives a conditional comparison for the supremum over $g$, which is the central point here.

Definition and Conditional-Mean Identity

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed with law $P$. A ghost sample is a second sample $X_1',\ldots,X_n'$ that is independent of the original sample and whose observations are also independent and identically distributed with law $P$. Its empirical average is $P_n'g=n^{-1}\sum_{i=1}^n g(X_i')$. Write $\mathcal{A}=\sigma(X_1,\ldots,X_n)$ for the information in the original sample.

Throughout, suppose $\mathcal{G}$ is a nonempty, countable class of measurable real-valued functions and that $|g(x)|\le B$ for every $g\in\mathcal{G}$ and every $x$, for some finite constant $B$. Boundedness guarantees the expectations below exist. Countability ensures that the suprema of the measurable quantities in the argument are measurable. For uncountable classes, additional measurability or separability conditions are needed.

Proposition: For every $g\in\mathcal{G}$, $$ E[P_n'g\mid\mathcal{A}]=Pg\quad\text{almost surely}. $$

Proof. Each $X_i'$ is independent of $\mathcal{A}$, and has law $P$. Thus $E[g(X_i')\mid\mathcal{A}]=E[g(X_i')]=Pg$ almost surely. Conditional expectation is linear, so

E[P_n'g\mid\mathcal{A}] =\frac{1}{n}\sum_{i=1}^n E[g(X_i')\mid\mathcal{A}] =\frac{1}{n}\sum_{i=1}^n Pg =Pg.

This proves the identity. $\square$

The proposition says that, with the observed data held fixed, the ghost average is a random quantity whose conditional mean is the population average. It does not say that $P_n'g=Pg$ for any particular ghost sample; the equality is about a conditional expectation.

From the Identity to a Uniform Comparison

Theorem: Under the stated assumptions, $$ \sup_{g\in\mathcal{G}}|P_n g-Pg| \le E\left[\left.\sup_{g\in\mathcal{G}}|P_n g-P_n'g|\right|\mathcal{A}\right] \quad\text{almost surely}. $$

Proof. Fix $g\in\mathcal{G}$. Since $P_n g$ is determined by the original sample, it is $\mathcal{A}$-measurable. The conditional-mean identity therefore gives

P_n g-Pg =E[P_n g-P_n'g\mid\mathcal{A}].

For an integrable random variable $Z$, the conditional triangle inequality gives $|E[Z\mid\mathcal{A}]|\le E[|Z|\mid\mathcal{A}]$ almost surely. Applying it to $Z=P_n g-P_n'g$, and then noting that $|P_n g-P_n'g|$ is at most the supremum over the class, yields

|P_n g-Pg| \le E[|P_n g-P_n'g|\mid\mathcal{A}] \le E\left[\left.\sup_{h\in\mathcal{G}}|P_n h-P_n'h|\right|\mathcal{A}\right].

The right-hand side does not depend on $g$. Taking the supremum over the countable class on the left proves the result. $\square$

The order of operations matters: first form the difference for each function, then take the supremum over the class inside the conditional expectation on the right. The comparison does not claim that the supremum of the conditional expectations equals the conditional expectation of the supremum.

Worked Examples

Worked Example: A Bernoulli Mean With Two Observations

Let $X$ be Bernoulli with $P(X=1)=0.3$, and let $\mathcal{G}$ contain only $g(x)=x$. Suppose the observed data are $X_1=1$ and $X_2=0$. Calculate the uniform deviation and the conditional ghost-sample bound.

There is only one function, so the supremum is just its absolute deviation. The observed average is $P_n g=(1+0)/2=0.5$, and $Pg=0.3$. Hence

\sup_{g\in\mathcal{G}}|P_n g-Pg|=|0.5-0.3|=0.2.

Write $K=X_1'+X_2'$. Conditional on the observed data, $K$ still has a binomial distribution with parameters $2$ and $0.3$: its probabilities for $0,1,2$ are $0.49,0.42,0.09$, respectively. The ghost empirical average is $K/2$, so the conditional bound is

E\left[\left.|P_n g-P_n'g|\right|\mathcal{A}\right] =0.49|0.5-0|+0.42|0.5-0.5|+0.09|0.5-1| =0.245+0+0.045=0.29.

The computed values satisfy $0.2\le 0.29$. In this example the ghost average has conditional mean $0.3$, while its expected absolute difference from the observed average is larger.

Worked Example: A Two-Point Distribution and Two Indicators

Suppose $P(X=a)=0.75$, $P(X=b)=0.25$, and $n=1$. Let $\mathcal{G}$ consist of $g_a(x)=\mathbf{1}\{x=a\}$ and $g_b(x)=\mathbf{1}\{x=b\}$. Given the observation $X_1=a$, calculate both sides of the conditional comparison.

The empirical averages are $P_n g_a=1$ and $P_n g_b=0$, while $Pg_a=0.75$ and $Pg_b=0.25$. Thus

\sup_{g\in\mathcal{G}}|P_n g-Pg| =\max\{|1-0.75|,\ |0-0.25|\}=0.25.

If the ghost observation $X_1'$ is $a$, both indicator vectors agree with the observed ones, so $\sup_g|P_n g-P_n'g|=0$. This occurs with probability $0.75$. If $X_1'=b$, the vectors are $(1,0)$ and $(0,1)$, so the supremum is $1$. This occurs with probability $0.25$. Therefore

E\left[\left.\sup_{g\in\mathcal{G}}|P_n g-P_n'g|\right|\mathcal{A}\right] =0.75(0)+0.25(1)=0.25.

Here the conditional bound is an equality. The ghost sample replaces each population average by a conditional mean, while the supremum compares the whole pair of empirical averages.

Worked Example: Thresholds on a Three-Point Support

Let $P$ be uniform on $\{1,2,3\}$, let $n=1$, and take $\mathcal{G}=\{g_1,g_2,g_3\}$, where $g_t(x)=\mathbf{1}\{x\le t\}$. Suppose $X_1=2$. Compute the deviation and ghost bound.

The population averages are $Pg_1=1/3$, $Pg_2=2/3$, and $Pg_3=1$; the observed empirical averages are $0,1,1$. The three absolute deviations are $1/3,1/3,0$. Hence the supremum is $1/3$.

For a ghost value $X_1'=1$, the two empirical indicator vectors, in order $t=1,2,3$, are $(0,1,1)$ and $(1,1,1)$. Their largest coordinate difference is $1$. For $X_1'=2$, the vectors agree and the supremum is $0$. For $X_1'=3$, they are $(0,1,1)$ and $(0,0,1)$, again giving a supremum of $1$. Each ghost value has probability $1/3$, so

E\left[\left.\sup_{g\in\mathcal{G}}|P_n g-P_n'g|\right|\mathcal{A}\right] =\frac{1}{3}(1)+\frac{1}{3}(0)+\frac{1}{3}(1)=\frac{2}{3}.

Thus $1/3\le 2/3$. The ghost bound is larger because it allows the largest discrepancy among the thresholds to be selected separately for each ghost outcome.

What the Ghost Sample Does—and Does Not Do

The key benefit is a change in representation. The original deviation compares a sample average with a population average that is usually not directly observable. The conditional-mean identity represents the population average as an average over an independent sample. The uniform comparison then controls the original supremum by a conditional expectation of a supremum involving two empirical samples. This is the basic setup for later bounds that analyze how much two independent samples can differ.

This step alone does not provide a numerical tail bound or prove that the deviation is small. Those conclusions require further assumptions or arguments. In particular, the comparison can be loose, as the threshold example shows. Its role is to replace a fixed population quantity with a random, sample-based expression while preserving a valid upper bound.

Common Pitfall

Wrong reasoning: “For every $g$, $Pg=E[P_n'g\mid\mathcal{A}]$, so I can move the supremum through the expectation and get equality.”
Correction: The identity holds function by function. The supremum is controlled by the conditional expectation of the supremum, not generally equal to it. For each $g$, the absolute conditional mean is bounded by the conditional mean of the absolute value; that value is in turn bounded by the conditional mean of the class-wide supremum. The supremum can be attained by different functions for different ghost samples.

Key takeaway: An independent ghost sample satisfies $E[P_n'g\mid\mathcal{A}]=Pg$ for each function. Consequently, the observed uniform deviation is at most the conditional expectation of the supremum of the two-sample empirical differences.

Check Your Understanding

Use the definitions and conditional comparison to answer these questions.

What independence properties must a ghost sample satisfy?
Why is $E[P_n'g\mid\mathcal{A}]$ equal to $Pg$, even though $P_n'g$ is random?
Which measurability condition in the stated setup makes the supremum measurable?
Explain why the conditional comparison uses the supremum inside the conditional expectation.
In the Bernoulli example, what are the probabilities of $K=0,1,2$, and how do they yield the conditional bound?