Rademacher Signs from Pairwise Swapping

Why Pairwise Swapping Produces Signs

A ghost sample turns a deviation from the population mean into a comparison between two samples. For independent observations \(X_1,\ldots,X_n\) and an independent copy \(X_1',\ldots,X_n'\), that comparison involves the differences \(f(X_i')-f(X_i)\). These paired differences have a useful symmetry: exchanging the two observations in any pair changes only the sign of that pair's contribution. Because the two observations are identically distributed, the exchange does not change the joint distribution of the data.

This symmetry is the precise reason independent random signs can be introduced. It is not a claim that a realized two-sample difference is unchanged when signs are added. Rather, the signed and unsigned processes have the same distribution when the data pairs are random. That distinction matters when using probability symmetrization: the signs are a representation of the randomness in the paired sample differences, not extra randomization that preserves a fixed dataset.

Definition: A Rademacher sign is a random variable \(\varepsilon\) with \(P(\varepsilon=1)=P(\varepsilon=-1)=1/2\). Independent Rademacher signs \(\varepsilon_1,\ldots,\varepsilon_n\) are mutually independent and, unless stated otherwise, independent of both samples.

Let \(X_1,\ldots,X_n\) be independent and identically distributed with distribution \(F\), and let \(X_1',\ldots,X_n'\) be an independent sample from the same distribution. For a measurable function \(f\), write \(P f=E[f(X)]\), \(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')\). The two-sample difference is therefore

P_n'f-P_nf=\frac{1}{n}\sum_{i=1}^n\bigl(f(X_i')-f(X_i)\bigr).

For this tutorial, the basic identity is stated first for a finite class \(\mathcal F\) of measurable functions. This makes all suprema measurable. The same conclusions apply to a countable class, or to a class for which the relevant suprema are measurable. Assume the functions are bounded by a common finite constant so that the expectations of the suprema below exist.

The Pairwise-Swapping Identity

Theorem: Under the conditions above, the random vectors indexed by \(f\in\mathcal F\), \[ \left(\frac{1}{n}\sum_{i=1}^n[f(X_i')-f(X_i)]\right)_{f\in\mathcal F} \quad\text{and}\quad \left(\frac{1}{n}\sum_{i=1}^n\varepsilon_i[f(X_i')-f(X_i)]\right)_{f\in\mathcal F} \] have the same distribution. Consequently, any measurable function of the whole vector has the same distribution under the two expressions. In particular, their suprema of absolute values have the same distribution and the same expectation.

The equality is joint across \(f\), not just a separate equality for each individual function. That allows the identity to be used for a supremum over a function class.

Encode each sign as a swap decision.
For each \(i\), leave the pair \((X_i,X_i')\) in place when \(\varepsilon_i=1\), and exchange its two entries when \(\varepsilon_i=-1\).

Check the transformed pair law.
Each original pair consists of two independent observations with the same distribution. Its joint law is unchanged by exchanging the entries, so the transformed pair has the same law as the original pair.

Relate the transformed difference to the signed difference.
For a pair left in place, the difference is \(f(X_i')-f(X_i)\). For a swapped pair, it is \(f(X_i)-f(X_i')\), the negative of that difference.

Here is the complete distributional argument. Let \((\widetilde X_i,\widetilde X_i')=(X_i,X_i')\) if \(\varepsilon_i=1\), and \((\widetilde X_i,\widetilde X_i')=(X_i',X_i)\) if \(\varepsilon_i=-1\). Conditional on any fixed vector of signs, each pair has the same joint distribution as \((X_i,X_i')\), because its entries are identically distributed and independent. The transformed pairs remain independent across \(i\), so their joint distribution is the same as that of the original pairs. Also, for every \(i\) and \(f\),

f(\widetilde X_i')-f(\widetilde X_i) =\varepsilon_i\bigl(f(X_i')-f(X_i)\bigr).

Thus the signed vector is the vector of two-sample differences computed from the transformed pairs. Since the transformed pairs have the original joint distribution, the two vectors have the same distribution. This proves the theorem. Boundedness and finiteness of \(\mathcal F\) ensure that the stated supremum is measurable and integrable, so equality in distribution also gives equality of its expectation. \(\square\)

For example, applying the theorem to the supremum of absolute values gives, for every \(t\),

P\left(\sup_{f\in\mathcal F}|P_n'f-P_nf|>t\right) = P\left(\sup_{f\in\mathcal F} \left|\frac{1}{n}\sum_{i=1}^n\varepsilon_i[f(X_i')-f(X_i)]\right|>t\right).

This is an exact identity for the two-sample difference. It does not itself bound either probability; it gives a signed representation of the same distribution.

Worked Example: A One-Observation Bernoulli Difference

Let \(n=1\), let \(X\) and \(X'\) be independent Bernoulli random variables with success probability \(0.3\), and take \(f(x)=x\). The unsigned difference is \(D=X'-X\). Its probabilities follow by considering the four possible pairs:

\(P(D=1)=P(X'=1,X=0)=0.3(0.7)=0.21\). Similarly, \(P(D=-1)=P(X'=0,X=1)=0.7(0.3)=0.21\). The remaining probability is \(P(D=0)=0.7^2+0.3^2=0.58\).

Now take an independent Rademacher sign \(\varepsilon\). If \(D=0\), then \(\varepsilon D=0\). If \(D=1\) or \(D=-1\), multiplication by the independent fair sign makes the result equally likely to be \(1\) or \(-1\). Therefore \(P(\varepsilon D=1)=0.21\), \(P(\varepsilon D=-1)=0.21\), and \(P(\varepsilon D=0)=0.58\). The two distributions agree, as the swapping identity predicts.

The Signed Empirical Process

The signed two-sample empirical process is the function-indexed random quantity

\frac{1}{n}\sum_{i=1}^n\varepsilon_i[f(X_i')-f(X_i)], \qquad f\in\mathcal F.

It can also be written as the difference of two signed sample averages:

\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(X_i') - \frac{1}{n}\sum_{i=1}^n\varepsilon_i f(X_i).

This algebraic form is often convenient when analyzing each sample contribution separately. The same signs appear in both averages; one should not assume these two terms are independent. Their useful role here is simply to express the signed paired difference exactly.

Worked Example: Computing the Signed Process for a Finite Class

Let \(n=2\), with paired values \((X_1,X_1')=(0,1)\) and \((X_2,X_2')=(1,0)\), and let \(\mathcal F=\{f_0,f_1\}\), where \(f_0(x)=0\) and \(f_1(x)=x\). For \(f_0\), every paired difference is zero, so the signed process is zero for every choice of signs.

For \(f_1\), the two paired differences are \(1-0=1\) and \(0-1=-1\). The signed process is therefore

\(\frac{1}{2}[\varepsilon_1(1)+\varepsilon_2(-1)]=(\varepsilon_1-\varepsilon_2)/2\).

The four equally likely sign pairs give values \(0\) for \((1,1)\), \(1\) for \((1,-1)\), \(-1\) for \((-1,1)\), and \(0\) for \((-1,-1)\). Thus the supremum of the absolute process over \(\mathcal F\) equals \(1\) with probability \(1/2\) and \(0\) with probability \(1/2\). This calculation is conditional on the displayed numerical pairs; the theorem concerns the distribution when the sample pairs themselves are random.

Worked Example: Separating the Two Signed Averages

Consider a single function \(f(x)=x\) and two fixed pairs \((X_1,X_1')=(2,1)\) and \((X_2,X_2')=(0,3)\). The paired differences are \(-1\) and \(3\), so the signed process is

\(\frac{1}{2}[-\varepsilon_1+3\varepsilon_2]\).

Using the difference-of-averages expression gives the same result:

\(\frac{1}{2}[\varepsilon_1 f(1)+\varepsilon_2 f(3)]-\frac{1}{2}[\varepsilon_1 f(2)+\varepsilon_2 f(0)] =\frac{1}{2}[\varepsilon_1+3\varepsilon_2-2\varepsilon_1-0] =\frac{1}{2}[-\varepsilon_1+3\varepsilon_2]\).

For signs \((1,1),(1,-1),(-1,1),(-1,-1)\), the values are \(1,-2,2,-1\), respectively. Each has probability \(1/4\), so the expectation of the absolute value is \((1+2+2+1)/4=1.5\).

Why the Identity Matters—and a Common Pitfall

Probability symmetrization with a ghost sample first replaces a population-centered deviation by a two-sample difference. Pairwise swapping then gives that difference a signed representation. This makes Rademacher signs a natural tool for studying the behavior of empirical processes. The identity is a starting point: deriving bounds from the signed process requires additional arguments, which are distinct from the equality proved here.

Common mistake: treating the identity as conditional on the observed pairs. For fixed pairs, multiplying their differences by random signs generally changes their distribution. In the second worked example, the unsigned average of the paired differences is \((1-1)/2=0\) for those fixed pairs, while the signed average takes values \(-1,0,1\). There is no conditional equality in that calculation. The correction is to keep track of the randomness over which the theorem averages: the pairs are random, and their exchangeability makes the signed and unsigned processes equal in distribution unconditionally.

Key takeaway: Swapping the entries of each independent, identically distributed observation pair independently preserves the joint sample law. Since each swap reverses that pair's difference, independent Rademacher signs can be inserted into a two-sample empirical process without changing its distribution.

Check Your Understanding

Use the pairwise-swapping argument to answer the following.

What property of each observation pair allows its entries to be exchanged without changing its joint distribution?
For a single pair, write the difference after swapping in terms of the original difference.
Why does the theorem establish a joint identity over a finite function class rather than only a separate identity for each function?
Write the signed two-sample process as a difference of two signed sample averages.
Why does the pairwise-swapping identity not imply that adding signs preserves the distribution conditional on fixed observed pairs?

Rademacher Signs from Pairwise Swapping

What You'll Learn