Tutorials › Probability Theory (Graduate) › Linear Regression Conditions for Exchangeable Pairs

Home  /  Tutorials  /  Coupling and Stein Methods

Coupling and Stein Methods · Tutorial 913 of 946

Linear Regression Conditions for Exchangeable Pairs

Learn how linear regression of an exchangeable pair yields a normal Stein bound and how resampling or reversible transitions can produce pairs with the required condition.

Advanced 10 min read

What You'll Learn

  • State the exchangeability and linear regression conditions used for normal approximation
  • Derive the exchangeable-pair identity for the normal Stein operator
  • Obtain a Wasserstein bound in terms of conditional variance and increment errors
  • Construct regression pairs by resampling a coordinate or using a reversible transition
  • Check the regression condition and error terms in explicit examples

Why Linear Regression Is Useful

An exchangeable pair gives two random variables whose joint distribution is unchanged when their order is swapped. That symmetry creates an identity useful for normal approximation, but by itself it does not make the identity resemble the normal Stein operator.

The useful additional structure is a linear conditional drift: given the current variable, the expected change in the next one is proportional to the negative of the current value. This condition turns the exchangeable-pair identity into an expression involving \(Wf(W)\), the term that appears in the normal Stein equation. The remaining error can then be controlled using the conditional squared increment and the size of individual increments.

Definition: A pair \((W,W')\) is exchangeable if \((W,W')\) and \((W',W)\) have the same joint distribution. It satisfies a linear regression condition with parameter \(\lambda>0\) if $$ \mathbb{E}[W'-W\mid W]=-\lambda W $$ almost surely.

For the standard normal target, we assume throughout that \(W\) is square-integrable with \(\mathbb{E}W=0\) and \(\mathbb{E}W^2=1\). Write \(\Delta=W'-W\), and assume the moments used below are finite. Under the regression condition, the centering also follows from exchangeability: \(\mathbb{E}\Delta=0=-\lambda\mathbb{E}W\). The variance-one assumption sets the scale of the approximation.

The Exchangeable-Pair Identity

The symmetry of the pair gives an identity for any suitable function \(f\). Swapping \(W\) and \(W'\) changes the sign of \(\Delta\), but leaves \(f(W')+f(W)\) unchanged. Therefore

$$ \mathbb{E}\big[\Delta\{f(W')+f(W)\}\big]=0. $$

It follows that \(\mathbb{E}[\Delta f(W)]=-\frac12\mathbb{E}[\Delta\{f(W')-f(W)\}]\). On the other hand, conditional regression gives \(\mathbb{E}[\Delta f(W)]=-\lambda\mathbb{E}[Wf(W)]\). Combining these equalities yields the identity below.

Proposition: If \((W,W')\) is exchangeable and satisfies the linear regression condition, then $$ \mathbb{E}[Wf(W)] = \frac{1}{2\lambda}\mathbb{E}\big[\Delta\{f(W')-f(W)\}\big], $$ whenever the expectations exist.

This is the key conversion. A term involving \(Wf(W)\) is represented using the difference of \(f\) across the pair. For small increments, that difference is approximately \(\Delta f'(W)\), bringing the derivative term in the normal Stein operator into view.

From the Identity to a Normal Bound

For a 1-Lipschitz test function \(h\), the standard normal Stein equation is

$$ f'(x)-xf(x)=h(x)-\mathbb{E}h(Z), $$

where \(Z\) has the standard normal distribution. The normal Stein solution satisfies \(\|f'\|_\infty\leq 1\) and \(\|f''\|_\infty\leq 2\). These derivative estimates allow the exchangeable-pair identity to control the difference between \(\mathbb{E}h(W)\) and \(\mathbb{E}h(Z)\).

Theorem: Suppose \((W,W')\) is exchangeable, \(\mathbb{E}W=0\), \(\mathbb{E}W^2=1\), and \(\mathbb{E}[\Delta\mid W]=-\lambda W\) for some \(\lambda>0\). If \(\mathbb{E}|\Delta|^3<\infty\), then $$ d_{\mathrm W}(\mathcal{L}(W),\mathcal{N}(0,1)) \leq \mathbb{E}\left|1-\frac{\mathbb{E}[\Delta^2\mid W]}{2\lambda}\right| + \frac{1}{2\lambda}\mathbb{E}|\Delta|^3. $$ Here \(d_{\mathrm W}\) is the supremum of \(\left|\mathbb{E}h(W)-\mathbb{E}h(Z)\right|\) over all 1-Lipschitz \(h\).
Proof. First, exchangeability and regression imply the increment normalization $$ \mathbb{E}\Delta^2 = \mathbb{E}\big[(W')^2-W^2\big]-2\mathbb{E}[W\Delta] = 0-2\mathbb{E}\big[W\mathbb{E}(\Delta\mid W)\big] = 2\lambda. $$ The first expectation vanishes because \(W'\) and \(W\) have the same distribution; the last equality uses \(\mathbb{E}W^2=1\). Let \(f\) solve the Stein equation for a 1-Lipschitz \(h\). By the proposition, $$ \mathbb{E}h(W)-\mathbb{E}h(Z) = \mathbb{E}[f'(W)-Wf(W)] = \mathbb{E}f'(W)-\frac{1}{2\lambda}\mathbb{E}\big[\Delta\{f(W')-f(W)\}\big]. $$ Taylor's theorem with a bounded second derivative gives $$ f(W')-f(W)=\Delta f'(W)+R, \qquad |R|\leq \frac12\|f''\|_\infty\Delta^2. $$ Substitution separates the error into a conditional-variance term and a Taylor remainder: $$ \mathbb{E}h(W)-\mathbb{E}h(Z) = \mathbb{E}\left[f'(W)\left(1-\frac{\mathbb{E}[\Delta^2\mid W]}{2\lambda}\right)\right] -\frac{1}{2\lambda}\mathbb{E}[\Delta R]. $$ Taking absolute values, using \(\|f'\|_\infty\leq 1\), and then using \(\|f''\|_\infty\leq 2\), bounds the first term by $$ \mathbb{E}\left|1-\frac{\mathbb{E}[\Delta^2\mid W]}{2\lambda}\right| $$ and the second by $$ \frac{1}{2\lambda}\cdot\frac12\|f''\|_\infty\mathbb{E}|\Delta|^3 \leq \frac{1}{2\lambda}\mathbb{E}|\Delta|^3. $$ The bound holds for every 1-Lipschitz \(h\), so taking the supremum proves the result.

\(\square\)

The two terms measure different features of the pair. The conditional variance term asks whether \(\mathbb{E}[\Delta^2\mid W]\) is close to its required scale \(2\lambda\), given \(W\). The increment term penalizes large individual changes. The identity \(\mathbb{E}\Delta^2=2\lambda\) only matches the variance on average; it does not guarantee that the conditional variance term is small.

Worked Example: Resampling One Coordinate

Worked Example: Resampling One Coordinate

Let \(X_1,\ldots,X_n\) be independent, centered random variables with finite variances, and let \(\sigma^2=\sum_{i=1}^n\mathbb{E}X_i^2>0\). Set \(W=\sigma^{-1}\sum_{i=1}^n X_i\), so \(\mathbb{E}W=0\) and \(\mathbb{E}W^2=1\). Choose an index \(I\) uniformly from \(\{1,\ldots,n\}\), independently of the variables, and replace \(X_I\) by an independent copy \(X_I'\). Define $$ W'=W+\frac{X_I'-X_I}{\sigma}. $$

The original and resampled coordinate have the same distribution, and the other coordinates are unchanged. Conditional on the chosen index, the pair of old and new coordinate values has a symmetric joint distribution. Thus swapping \(W\) and \(W'\) preserves the joint law, so the pair is exchangeable.

Given all the original coordinates, the conditional expected change is $$ \mathbb{E}[W'-W\mid X_1,\ldots,X_n] = -\frac{1}{n\sigma}\sum_{i=1}^n X_i = -\frac{W}{n}, $$ because each independent copy has mean zero. Conditioning again on \(W\) gives the regression condition with \(\lambda=1/n\).

The conditional squared increment is $$ \mathbb{E}[\Delta^2\mid X_1,\ldots,X_n] = \frac{1}{n\sigma^2}\sum_{i=1}^n\left(\mathbb{E}X_i^2+X_i^2\right). $$ Consequently, conditioning on \(W\) averages this expression over the original coordinates given their sum. Its expectation is \(2/n=2\lambda\), as required, although it need not be constant given \(W\). This construction illustrates how resampling creates the drift condition even when the conditional variance error still requires analysis.

Worked Example: A Reversible Transition and an Eigenfunction

A general way to construct regression pairs uses a reversible transition. Let \(X\) have a stationary distribution \(\pi\), and let \(X'\) be obtained from \(X\) by one step of a transition kernel \(P\). Reversibility means that \((X,X')\) and \((X',X)\) have the same distribution. If a centered function \(g\) satisfies $$ Pg=(1-\lambda)g, $$ where \(Pg(x)=\mathbb{E}[g(X')\mid X=x]\), then \(W=g(X)\) and \(W'=g(X')\) are exchangeable and satisfy \(\mathbb{E}[W'-W\mid W]=-\lambda W\). Indeed, conditioning first on \(X\) gives \(\mathbb{E}[W'-W\mid X]=-\lambda g(X)\), and conditioning on \(W=g(X)\) gives the claimed regression in \(W\).

Worked Example: Flipping a Random Sign

Let \(X=(X_1,\ldots,X_n)\) be uniform on \(\{-1,1\}^n\). Choose \(I\) uniformly from \(\{1,\ldots,n\}\), and form \(X'\) by replacing \(X_I\) by \(-X_I\). The uniform distribution is stationary, and the transition is reversible: every transition that flips coordinate \(i\) has the same probability in both directions.

Take \(W=n^{-1/2}\sum_{i=1}^n X_i\) and \(W'=n^{-1/2}\sum_{i=1}^n X_i'\). The coordinates are independent symmetric signs, so \(W\) is centered with variance one. A flip changes the sum by \(-2X_I\), hence $$ \mathbb{E}[W'-W\mid X] = -\frac{2}{n\sqrt n}\sum_{i=1}^n X_i = -\frac{2}{n}W. $$ Thus \(\lambda=2/n\), and conditioning on \(W\) preserves the same equation.

Here \(\Delta=-2X_I/\sqrt n\), so \(\Delta^2=4/n\) always. It follows that $$ \frac{\mathbb{E}[\Delta^2\mid W]}{2\lambda} = \frac{4/n}{4/n} = 1. $$ There is no conditional variance error. Since \(|\Delta|^3=8/n^{3/2}\), the theorem gives the bound \(2/\sqrt n\). The calculation displays how a reversible move and an eigenfunction supply the linear drift, while the size of each move determines the remaining bound.

Worked Example: An Exchangeable Pair That Is Already Normal

Worked Example: An Exchangeable Pair That Is Already Normal

Let \(W\) and \(Z\) be independent standard normal variables, fix \(\rho=1/2\), and set \(W'=\rho W+\sqrt{1-\rho^2}\,Z\). The pair is jointly Gaussian, both coordinates have variance one, and their covariance is \(\rho\). Its joint distribution is therefore unchanged by swapping the coordinates, so it is exchangeable.

The conditional drift is $$ \mathbb{E}[W'-W\mid W] = (\rho-1)W = -\frac12W, $$ so \(\lambda=1/2\). Also \(\Delta=-W/2+\sqrt{3}\,Z/2\), and independence gives $$ \mathbb{E}[\Delta^2\mid W]=\frac{W^2}{4}+\frac34, \qquad \frac{\mathbb{E}[\Delta^2\mid W]}{2\lambda} = \frac{W^2}{4}+\frac34. $$ The conditional variance error is not identically zero. Nevertheless, \(W\) is exactly standard normal. This example shows that the theorem is an upper bound, not an equivalence: its error terms need not vanish even when the target distribution is already attained.

How to Use the Condition Well

The linear regression condition is a design principle. One seeks a pair that is both exchangeable and has a tractable conditional drift. Resampling a randomly chosen component is useful for sums of independent variables; reversible transitions can work when the random object has a natural stationary dynamics and the statistic of interest behaves like an eigenfunction.

After finding the pair, check the assumptions in order: verify exchangeability, compute the conditional drift, and identify \(\lambda\). Then evaluate the conditional squared increment and the third absolute moment. A common mistake is to verify only the regression equation and conclude that the bound is small. Regression supplies the identity, but a useful approximation also needs sufficiently stable conditional variance and sufficiently small increments.

Check Your Understanding

Use the definitions and calculations above to test your understanding of how the regression condition contributes to a normal approximation.

  1. Why does exchangeability imply \(\mathbb{E}[\Delta\{f(W')+f(W)\}]=0\)?
  2. How does the conditional regression condition turn \(\mathbb{E}[\Delta f(W)]\) into an expression involving \(Wf(W)\)?
  3. Why does \(\mathbb{E}\Delta^2=2\lambda\) not imply that the conditional variance error is zero?
  4. In the coordinate-resampling construction, which step uses that the replacement variable is an independent copy?
  5. For a reversible transition, why does an eigenfunction of the transition operator produce linear conditional drift?

Previous

Next

Back to Tutorials
Clinical Biostats