Stein Couplings for Sums

Why Couple a Sum to a Perturbed Copy?

A normal approximation problem often starts with a centered random variable $W$ of variance one. Stein's equation turns the difference between the distribution of $W$ and the standard normal distribution into an expression involving $W$ and a test function. A Stein coupling gives a way to rewrite the term involving $W$ as an expectation of a difference between two coupled random variables.

The useful point is not just that $W'$ is related to $W$. The expectation identity makes the relationship precise, while the size of the perturbation $W'-W$ controls the error left after applying Stein's equation. For a sum of independent variables, removing one randomly selected summand gives a particularly direct construction.

The Stein-Coupling Identity

Definition: Let $W$ be an integrable, mean-zero random variable. A triple $(W,W',G)$, defined on a common probability space, is a Stein coupling if, for every absolutely continuous function $f$ for which the expectations below exist, $$ \mathbb{E}[W f(W)] = \mathbb{E}\!\left[G\bigl(f(W')-f(W)\bigr)\right]. $$ Here $W'$ is another random variable on the same space, and $G$ is an integrable random variable that may depend on both $W$ and $W'$. Write $\Delta=W'-W$ for the coupling difference.

The identity, rather than any requirement that $W'$ have the same distribution as $W$, is the defining feature. In many constructions $W'$ is a perturbed version of $W$, but it need not be exchangeable with $W$. If $W$ has finite second moment and the identity applies to $f(x)=x$, it also implies $$ \mathbb{E}[G\Delta]=\mathbb{E}[W^2]. $$ Indeed, substituting $f(x)=x$ makes the left side $\mathbb{E}[W^2]$ and the right side $\mathbb{E}[G(W'-W)]$. In the standard normal approximation setting, $\mathbb{E}[W^2]=1$, so the coupling has $\mathbb{E}[G\Delta]=1$.

For $W$ with mean zero and variance one, the standard normal Stein equation for a test function $h$ is $$ f'(x)-x f(x)=h(x)-\mathbb{E}[h(Z)], $$ where $Z$ has the standard normal distribution. When this equation has a sufficiently regular solution $f$, taking expectations at $W$ and using the Stein-coupling identity gives an exact expression for the approximation error.

The Exact Error Decomposition

Theorem: Suppose $W$ has mean zero and variance one, $(W,W',G)$ is a Stein coupling, and $f$ solves the standard normal Stein equation for $h$. Assume the expectations in the identities below exist. Then $$ \mathbb{E}[h(W)]-\mathbb{E}[h(Z)] = \mathbb{E}\!\left[(1-G\Delta)f'(W)\right] - \mathbb{E}\!\left[G\{f(W')-f(W)-\Delta f'(W)\}\right]. $$

Proof: Evaluate the Stein equation at $W$ and take expectations: $$ \mathbb{E}[h(W)]-\mathbb{E}[h(Z)] = \mathbb{E}[f'(W)]-\mathbb{E}[Wf(W)]. $$ By the defining identity of a Stein coupling, $$ \mathbb{E}[Wf(W)] = \mathbb{E}[G\{f(W')-f(W)\}]. $$ Insert this expression and add and subtract $G\Delta f'(W)$ inside the expectation. The result is $$ \begin{aligned} \mathbb{E}[h(W)]-\mathbb{E}[h(Z)] &=\mathbb{E}[f'(W)]-\mathbb{E}[G\{f(W')-f(W)\}]\\ &=\mathbb{E}[(1-G\Delta)f'(W)] -\mathbb{E}[G\{f(W')-f(W)-\Delta f'(W)\}], \end{aligned} $$ which proves the identity. $\square$

The first term measures how far $G\Delta$ is from one. The second is the error in approximating the increment of $f$ by its first-order Taylor term at $W$. The decomposition is exact; bounds enter only when estimating these two terms.

For example, suppose $f'$ is Lipschitz with constant $L$, meaning $|f'(x)-f'(y)|\leq L|x-y|$ for all real $x,y$. The fundamental theorem of calculus gives $$ f(W')-f(W)-\Delta f'(W) = \int_0^\Delta \{f'(W+t)-f'(W)\}\,dt. $$ For either sign of $\Delta$, the Lipschitz property therefore yields $$ |f(W')-f(W)-\Delta f'(W)| \leq \frac{L}{2}|\Delta|^2. $$ Consequently, if $f'$ is also bounded, then $$ |\mathbb{E}[h(W)]-\mathbb{E}[h(Z)]| \leq \|f'\|_\infty\,\mathbb{E}|1-G\Delta| + \frac{L}{2}\mathbb{E}[|G|\,|\Delta|^2]. $$ For Lipschitz test functions $h$, the normal Stein equation has solutions with suitable derivative bounds. Applying those bounds to the last display turns the coupling quantities into a normal-approximation bound. No independence between $G$, $W$, and $\Delta$ is assumed.

Worked Example: A Two-Term Leave-One-Out Coupling

Let $X_1$ and $X_2$ be independent, mean-zero random variables with finite second moments, and suppose $\mathbb{E}[X_1^2+X_2^2]=1$. Set $W=X_1+X_2$. Choose $I$ independently of the variables, with $\mathbb{P}(I=1)=\mathbb{P}(I=2)=1/2$, and define $W'=W-X_I$ and $G=-2X_I$. Thus $\Delta=-X_I$.

Conditioning on the choice of $I$ gives $$ \begin{aligned} \mathbb{E}[G\{f(W')-f(W)\}] &=\frac12\sum_{i=1}^2 \mathbb{E}[-2X_i\{f(W-X_i)-f(W)\}]\\ &=\sum_{i=1}^2\mathbb{E}[X_i\{f(W)-f(W-X_i)\}]. \end{aligned} $$ For each $i$, $W-X_i$ is the other summand and is independent of $X_i$. Hence $\mathbb{E}[X_i f(W-X_i)]=\mathbb{E}[X_i]\mathbb{E}[f(W-X_i)]=0$. The expression reduces to $\mathbb{E}[(X_1+X_2)f(W)]=\mathbb{E}[Wf(W)]$, verifying the coupling identity.

In this construction $G\Delta=2X_I^2$, and averaging over $I$ gives $\mathbb{E}[G\Delta]=\mathbb{E}[X_1^2+X_2^2]=1$, as required for a variance-one sum.

Leave-One-Out Couplings for Independent Sums

The two-term calculation extends directly to any finite collection of independent centered summands. The random index is a convenient way to package a sum of identities into a single triple $(W,W',G)$. The probabilities used to select the index can be chosen freely, as long as each summand is selected with positive probability.

Theorem: Let $X_1,\ldots,X_n$ be independent, mean-zero random variables with finite second moments, and let $W=\sum_{i=1}^n X_i$. Choose numbers $p_1,\ldots,p_n>0$ with $\sum_{i=1}^n p_i=1$. Let $I$ be independent of the summands with $\mathbb{P}(I=i)=p_i$, and set $$ W'=W-X_I,\qquad G=-\frac{X_I}{p_I}. $$ Then $(W,W',G)$ is a Stein coupling.

Proof: Conditional on $I=i$, the contribution to the coupling expectation is $$ p_i\,\mathbb{E}\!\left[-\frac{X_i}{p_i}\{f(W-X_i)-f(W)\}\right] = \mathbb{E}[X_i\{f(W)-f(W-X_i)\}]. $$ Summing over $i$ gives $$ \mathbb{E}[G\{f(W')-f(W)\}] = \sum_{i=1}^n\mathbb{E}[X_i f(W)] - \sum_{i=1}^n\mathbb{E}[X_i f(W-X_i)]. $$ For each $i$, independence makes $X_i$ independent of $W-X_i$. Since $\mathbb{E}[X_i]=0$, the corresponding expectation in the second sum is zero. The first sum is $\mathbb{E}[Wf(W)]$, because $W=\sum_i X_i$. Thus the defining identity holds. $\square$

If $\mathbb{E}[W^2]=1$, this construction gives an immediate check on the scale of the coupling: $$ \mathbb{E}[G\Delta] = \sum_{i=1}^n p_i\,\mathbb{E}\!\left[\frac{X_i^2}{p_i}\right] = \sum_{i=1}^n\mathbb{E}[X_i^2] = 1. $$ The equality uses independence and centering to identify $\mathbb{E}[W^2]$ with the sum of the variances. If the variance is not one, the same construction still gives a Stein coupling, but $\mathbb{E}[G\Delta]=\mathbb{E}[W^2]$.

Worked Example: Weighted Rademacher Summands

Let $R_1,\ldots,R_n$ be independent random variables with $\mathbb{P}(R_i=1)=\mathbb{P}(R_i=-1)=1/2$. Choose positive numbers $a_i$ with $\sum_i a_i^2=1$, and put $X_i=a_iR_i$. Then $W=\sum_i a_iR_i$ is centered and has variance one. In the leave-one-out construction, choose $p_i=a_i^2$.

For the selected index $I$, the coupling variables satisfy $$ \Delta=-a_I R_I,\qquad G=-\frac{a_I R_I}{a_I^2}=-\frac{R_I}{a_I}. $$ Since $R_I^2=1$, their product is exactly $$ G\Delta = \left(-\frac{R_I}{a_I}\right)(-a_I R_I) = R_I^2 = 1. $$ Thus the first error term in the decomposition, $\mathbb{E}[(1-G\Delta)f'(W)]$, vanishes identically, not merely in expectation. The other coupling quantity in the remainder bound is $$ \mathbb{E}[|G|\,|\Delta|^2] = \sum_{i=1}^n a_i^2\,\frac{1}{a_i}\,a_i^2 = \sum_{i=1}^n a_i^3. $$ For equal weights $a_i=1/\sqrt{n}$, this is $1/\sqrt{n}$. This calculation shows concretely how a small perturbation and a controlled Taylor remainder can produce a useful normal-approximation estimate.

Worked Example: An Exact Coupling for a Standard Normal Variable

Let $W$ itself have the standard normal distribution, and set $W'=0$ and $G=-W$. Then $\Delta=-W$. For any suitable $f$, $$ \begin{aligned} \mathbb{E}[G\{f(W')-f(W)\}] &=\mathbb{E}[-W\{f(0)-f(W)\}]\\ &=-f(0)\mathbb{E}[W]+\mathbb{E}[Wf(W)]\\ &=\mathbb{E}[Wf(W)]. \end{aligned} $$ The last equality uses $\mathbb{E}[W]=0$, so this is a Stein coupling. Also $G\Delta=W^2$, whose expectation is one. Unlike the leave-one-out examples, $W'$ here is not a small perturbation of $W$; the identity still holds. This illustrates that a Stein coupling is defined by its expectation identity, while a useful bound also depends on the size of its error terms.

Choosing and Interpreting the Coupling

For the independent-sum construction, the choice of index probabilities affects the first error term and the sizes of $G$ and $\Delta$, even though the coupling identity remains valid. If the summands have nonzero variances $\sigma_i^2=\mathbb{E}[X_i^2]$ and the total variance is one, a common choice is $p_i=\sigma_i^2$. Then $$ \mathbb{E}[G\Delta] = \sum_i \mathbb{E}[X_i^2] = 1, \qquad \mathbb{E}[|G|\,|\Delta|^2] = \sum_i \mathbb{E}[|X_i|^3]. $$ The second equality follows by conditioning on $I=i$: its $i$-th contribution is $p_i\mathbb{E}[|X_i|^3/p_i]=\mathbb{E}[|X_i|^3]$. This choice is available when zero-variance summands are omitted; such summands equal zero almost surely and do not affect $W$.

A useful coupling therefore does more than verify the identity: it makes the resulting error terms manageable. The decomposition separates two possible sources of error: the failure of $G\Delta$ to equal one, and the nonlinear remainder from changing $f$ between $W$ and $W'$. A common pitfall is to check only that $\mathbb{E}[G\Delta]=1$. That scalar equality alone does not make the first term vanish, because the decomposition contains the expectation of $(1-G\Delta)f'(W)$, not just $\mathbb{E}[1-G\Delta]$. Dependence on $W$ matters.

Check Your Understanding

Use the identity and error decomposition to answer these questions.

What is the defining expectation identity for a Stein coupling, and which random variables must be defined on a common probability space?
In the normal-approximation decomposition, what does each of the two error terms measure?
Why does independence and centering imply $\mathbb{E}[X_i f(W-X_i)]=0$ for a leave-one-out construction?
For weighted Rademacher summands with $p_i=a_i^2$, why is $G\Delta$ equal to one for every outcome?
Why does $\mathbb{E}[G\Delta]=1$ not by itself imply that the first error term vanishes?

What You'll Learn