Tutorials › Probability Theory (Graduate) › Exchangeable Pairs for Normal Approximation

Home  /  Tutorials  /  Coupling and Stein Methods

Coupling and Stein Methods · Tutorial 912 of 946

Exchangeable Pairs for Normal Approximation

Learn how exchangeable pairs turn a small, symmetric perturbation into an identity that reveals the key terms in Gaussian approximation.

Advanced 10 min read

What You'll Learn

  • Define exchangeability for a pair of random variables and identify its symmetry under swapping coordinates.
  • Prove the antisymmetry identity for an exchangeable pair.
  • Express the identity using the increment between the paired variables.
  • Expand the increment’s contribution using Taylor’s theorem and control the remainder.
  • Relate the resulting terms to the Gaussian Stein equation.
  • Analyze exchangeable pairs arising from Gaussian variables and a coordinate-replacement construction.

Why Pair a Variable with a Perturbed Copy?

Normal approximation can be approached by comparing a random variable with a Gaussian law through the Gaussian Stein equation. Exchangeable pairs provide a way to make that comparison using a joint construction: rather than studying a variable \(W\) alone, we construct another variable \(W'\) on the same probability space, with a joint distribution that is unchanged when the two coordinates are swapped.

The difference between the two variables is the increment \(\Delta=W'-W\). The key feature is not merely that this increment is small. Exchangeability makes its contribution to expectations obey an exact symmetry identity. When that identity is combined with a Taylor expansion, the first-order change in a test function is weighted by \(\Delta^2\). This is how the increment exposes the terms that need to resemble those in the Gaussian Stein equation.

Exchangeability and the Increment

Definition: A pair of real-valued random variables \((W,W')\) is exchangeable if its joint distribution is the same as the joint distribution of \((W',W)\). Equivalently, for every pair of Borel sets \(A,B\subseteq\mathbb R\), $$ \mathbb P(W\in A,\ W'\in B)=\mathbb P(W'\in A,\ W\in B). $$ The increment of the pair is the random variable $$ \Delta=W'-W. $$

Exchangeability implies that \(W\) and \(W'\) have the same marginal distribution, but it says more: it constrains how the two variables occur together. Under swapping the coordinates, the increment changes sign, since \(W-W'=-\Delta\). This sign change is the source of the identities below.

For example, if \((W,W')\) is exchangeable and the relevant expectations exist, then \(\mathbb E W=\mathbb E W'\), so \(\mathbb E\Delta=0\). This conclusion alone is not the main tool. The more useful fact is an identity involving the increment multiplied by a function of both coordinates.

The Antisymmetry Identity

Theorem: If \((W,W')\) is exchangeable and \(F:\mathbb R^2\to\mathbb R\) is measurable with \(\mathbb E|\Delta F(W,W')|<\infty\), then $$ \mathbb E[\Delta F(W,W')] = \frac12\mathbb E\!\left[\Delta\bigl(F(W,W')-F(W',W)\bigr)\right]. $$ In particular, if \(F\) is symmetric, meaning \(F(w,w')=F(w',w)\), then $$ \mathbb E[\Delta F(W,W')]=0. $$
Proof. By exchangeability, evaluating the integrable function \((w,w')\mapsto (w'-w)F(w',w)\) at \((W,W')\) has the same expectation as evaluating it at \((W',W)\). Therefore $$ \mathbb E[\Delta F(W',W)] = \mathbb E[(W-W')F(W,W')] = -\mathbb E[\Delta F(W,W')]. $$ Subtracting this equality from \(\mathbb E[\Delta F(W,W')]\) gives $$ 2\mathbb E[\Delta F(W,W')] = \mathbb E\!\left[\Delta\bigl(F(W,W')-F(W',W)\bigr)\right], $$ which proves the stated identity. If \(F\) is symmetric, the difference inside the expectation is zero, so the special case follows. \(\square\)

Choose \(F(w,w')=f(w)\), where \(f\) is a measurable function for which the expectations are finite. The general identity gives the particularly useful relation $$ \mathbb E[\Delta f(W)] = \frac12\mathbb E[\Delta(f(W)-f(W'))]. $$ Equivalently, $$ \mathbb E[\Delta f(W)] = -\frac12\mathbb E[\Delta(f(W')-f(W))]. $$ The negative sign matters: if \(f\) increases along a positive increment, the product \(\Delta(f(W')-f(W))\) is nonnegative, and the corresponding expectation of \(\Delta f(W)\) is nonpositive.

Worked Example: Independent Rademacher Variables

Worked Example: Independent Rademacher Variables

Let \(W\) and \(W'\) be independent, with each taking the values \(-1\) and \(1\) with probability \(1/2\). The joint probabilities of the four possible pairs are all \(1/4\). Swapping the coordinates leaves these probabilities unchanged, so the pair is exchangeable.

Take \(f(w)=w\). Then \(\Delta=W'-W\), and direct calculation gives $$ \mathbb E[\Delta f(W)] =\mathbb E[(W'-W)W] =\mathbb E[W'W]-\mathbb E[W^2] =0-1=-1. $$ The product \(W'W\) has expectation zero because independence gives \(\mathbb E[W'W]=\mathbb E[W']\mathbb E[W]=0\).

The identity’s other side gives the same answer. Since \(f(W')-f(W)=\Delta\), $$ -\frac12\mathbb E[\Delta(f(W')-f(W))] =-\frac12\mathbb E[\Delta^2]. $$ Here \(\Delta=0\) when \(W'=W\), which has probability \(1/2\), and \(\Delta^2=4\) when \(W'\ne W\), also with probability \(1/2\). Hence \(\mathbb E[\Delta^2]=2\), and the expression equals \(-1\).

This verifies the identity explicitly. It also illustrates a limitation: exchangeability itself does not make \(W\) approximately Gaussian. The pair supplies a useful identity, but the size and behavior of its increment still determine whether that identity yields a good approximation.

From the Increment to a Derivative

The identity becomes especially informative when \(f(W')-f(W)\) can be approximated by its first-order change. Suppose \(f\) is differentiable and \(f'\) is Lipschitz with constant \(L\), so that \(|f'(x)-f'(y)|\le L|x-y|\) for all real \(x,y\). Taylor’s theorem with an integral remainder gives $$ f(W')-f(W)=\Delta f'(W)+R, \qquad |R|\le \frac{L}{2}\Delta^2. $$ Multiplying by \(\Delta\) yields a term involving \(\Delta^2 f'(W)\), with an error controlled by the third absolute moment of the increment.

Theorem: Under the exchangeability assumption, if \(f'\) is Lipschitz with constant \(L\) and \(\mathbb E|\Delta|^3<\infty\), then $$ \mathbb E[\Delta f(W)] = -\frac12\mathbb E[\Delta^2 f'(W)]+\eta, \qquad |\eta|\le \frac{L}{4}\mathbb E|\Delta|^3, $$ provided the expectations in the identity are finite.
Proof. The Taylor remainder satisfies $$ \left|f(W')-f(W)-\Delta f'(W)\right| \le \frac{L}{2}\Delta^2. $$ Thus, after multiplying by \(\Delta\), the difference between \(\Delta(f(W')-f(W))\) and \(\Delta^2 f'(W)\) has absolute value at most \(L|\Delta|^3/2\). Taking expectations gives $$ \mathbb E[\Delta(f(W')-f(W))] = \mathbb E[\Delta^2 f'(W)]+r, \qquad |r|\le \frac{L}{2}\mathbb E|\Delta|^3. $$ The exchangeability identity says that \(\mathbb E[\Delta f(W)]\) is minus one half of the expectation on the left. Setting \(\eta=-r/2\) proves the result and its stated bound. \(\square\)

This calculation explains the two main roles of the increment. The quantity \(\Delta^2\) weights the derivative \(f'(W)\), while \(\mathbb E|\Delta|^3\) controls the error from replacing a finite change in \(f\) by a first-order change. A small increment can make the Taylor error small, but smallness alone is not enough: the size and variation of the squared increment also matter.

How the Gaussian Stein Equation Enters

Let \(Z\) have the standard normal distribution. For a suitable test function \(h\), the normal Stein equation is $$ f'(w)-wf(w)=h(w)-\mathbb E h(Z). $$ When \(W\) has mean zero and variance one, taking expectations gives $$ \mathbb E h(W)-\mathbb E h(Z) = \mathbb E[f'(W)-Wf(W)]. $$ The earlier material on the normal Stein equation explains the choice of \(f\) and the derivative bounds available for common classes of test functions. The exchangeable-pair identity addresses the term involving \(Wf(W)\).

To see the algebra without imposing any special behavior on the pair, define \(m(W)=\mathbb E[\Delta\mid W]\). For a positive constant \(\lambda\), write $$ m(W)=-\lambda W+r(W), $$ where \(r(W)=m(W)+\lambda W\) is simply the difference between the conditional mean increment and \(-\lambda W\). By conditional expectation, $$ \mathbb E[\Delta f(W)]=\mathbb E[m(W)f(W)] =-\lambda\mathbb E[Wf(W)]+\mathbb E[r(W)f(W)]. $$ Rearranging this equality, then applying the exchangeability identity, gives the exact decomposition $$ \mathbb E[f'(W)-Wf(W)] = \mathbb E[f'(W)] -\frac{1}{2\lambda}\mathbb E[\Delta(f(W')-f(W))] -\frac{1}{\lambda}\mathbb E[r(W)f(W)]. $$ If \(f'\) is Lipschitz, the Taylor calculation turns the middle term into a contribution involving \(\Delta^2 f'(W)\), plus a remainder. Thus the Gaussian comparison is related to how the increment’s average direction, squared size, and Taylor error behave. This identity is algebraic; it does not assert that the residual \(r(W)\) is small or that a Gaussian approximation follows.

This distinction is useful in practice. Exchangeability guarantees the symmetry identity, but additional information about a particular construction is needed to control the terms in the decomposition. The identity tells us what to investigate: how the increment tends to move the current value, how large its square is, and how often it is large enough for the Taylor remainder to matter.

Worked Example: A Correlated Gaussian Pair

Worked Example: A Correlated Gaussian Pair

Let \(X\) and \(Y\) be jointly Gaussian, each with mean zero and variance one, and with correlation \(\rho\), where \(-1\le \rho\le 1\). Their joint covariance matrix is $$ \begin{pmatrix} 1 & \rho\\ \rho & 1 \end{pmatrix}. $$ This matrix is unchanged when the coordinates are swapped. Since a centered Gaussian distribution is determined by its covariance matrix, \((X,Y)\) and \((Y,X)\) have the same joint distribution. The pair is exchangeable.

Set \(W=X\), \(W'=Y\), and \(\Delta=Y-X\). Then $$ \mathbb E[\Delta^2] =\mathbb E[Y^2]+\mathbb E[X^2]-2\mathbb E[XY] =1+1-2\rho =2(1-\rho). $$ For \(f(w)=w\), the exact identity reads $$ \mathbb E[\Delta f(W)] =\mathbb E[(Y-X)X] =\rho-1 =-\frac12\mathbb E[\Delta^2]. $$ This matches the general formula because \(f(W')-f(W)=\Delta\). When \(\rho\) is close to one, the pair is close in mean square and the increment is typically small; when \(\rho=-1\), the increment has mean square \(4\). The example shows how the coupling’s dependence controls the scale of the increment.

Worked Example: Replacing One Coordinate in a Sum

Worked Example: Replacing One Coordinate in a Sum

Let \(X_1,\ldots,X_n\) be independent Rademacher variables, each equal to \(-1\) or \(1\) with probability \(1/2\), and define $$ W=\frac{1}{\sqrt n}\sum_{j=1}^n X_j. $$ Then \(\mathbb E W=0\) and \(\mathbb E W^2=1\): in the variance calculation, each \(X_j^2=1\), and every cross term has expectation \(\mathbb E[X_iX_j]=0\) for \(i\ne j\).

Choose an index \(I\) uniformly from \(\{1,\ldots,n\}\), independently of the variables, and let \(X_I'\) be a fresh independent Rademacher variable. Replace \(X_I\) by \(X_I'\) to form $$ W'=W-\frac{X_I}{\sqrt n}+\frac{X_I'}{\sqrt n}, \qquad \Delta=\frac{X_I'-X_I}{\sqrt n}. $$ The pair is exchangeable: conditional on the chosen index and all the other coordinates, the two values \(X_I\) and \(X_I'\) are independent with the same distribution. Swapping them therefore leaves the joint distribution unchanged, and the other coordinates are unaffected.

The increment is zero if \(X_I'=X_I\), an event of probability \(1/2\); otherwise it is \(2/\sqrt n\) or \(-2/\sqrt n\), each with probability \(1/4\). Consequently, $$ \mathbb E[\Delta^2] =\frac12\cdot 0+\frac14\cdot\frac{4}{n} +\frac14\cdot\frac{4}{n} =\frac{2}{n}, \qquad \mathbb E|\Delta|^3 =\frac12\cdot 0+\frac12\cdot\frac{8}{n^{3/2}} =\frac{4}{n^{3/2}}. $$ The increment becomes small as \(n\) grows, and its third absolute moment decreases faster than its second moment. For any \(f\) satisfying the conditions of the Taylor result, exchangeability gives $$ \mathbb E[\Delta f(W)] =-\frac12\mathbb E[\Delta^2 f'(W)]+\eta, \qquad |\eta|\le \frac{L}{n^{3/2}}. $$ The bound follows by substituting \(\mathbb E|\Delta|^3=4/n^{3/2}\) into \(L\mathbb E|\Delta|^3/4\). The construction demonstrates how a local replacement creates a tractable increment and a quantitatively controlled Taylor error.

What Exchangeability Does—and Does Not—Provide

Exchangeable pairs are useful because their symmetry yields an exact identity before any approximation is made. The Taylor step then reveals why the square of the increment appears in normal approximation and why a third-moment quantity controls the local expansion error.

It is important not to confuse this structural identity with a complete normal-approximation bound. The pair may be exchangeable while its first coordinate is far from normal, as the independent Rademacher example illustrates. To obtain a quantitative conclusion, one must also control the terms that arise when the identity is matched to the Gaussian Stein equation. In particular, a small increment does not by itself ensure that its squared size has the right effect across the values of \(W\).

The practical lesson is to design the joint construction deliberately. A useful pair has a transparent swap symmetry, an increment whose scale can be computed, and a manageable Taylor remainder. Those features turn exchangeability from a formal definition into a method for organizing a normal-approximation argument.

Check Your Understanding

Try to answer these questions using the definitions and identities above.

  1. What distributional condition defines an exchangeable pair, and what happens to \(\Delta\) when the coordinates are swapped?
  2. Why does exchangeability imply that \(\mathbb E[\Delta F(W,W')]=0\) when \(F\) is symmetric and the expectation exists?
  3. Use the increment identity with \(f(w)=w\) to express \(\mathbb E[\Delta W]\) in terms of \(\mathbb E[\Delta^2]\).
  4. In the Taylor expansion, which moment of \(\Delta\) controls the remainder when \(f'\) is Lipschitz?
  5. Why does exchangeability alone not guarantee that \(W\) is close to a standard normal variable?

Previous

Next

Back to Tutorials
Clinical Biostats