Why conditional variance enters an exchangeable-pair bound
Exchangeability supplies a useful symmetry: the pair \((W,W')\) has the same distribution after its coordinates are swapped. A linear regression condition turns that symmetry into an identity involving \(W\) and a test function. But the identity alone does not guarantee a sharp normal approximation. The quality of the approximation also depends on how much the conditional squared increment varies and on how large the increments can be.
This tutorial derives a Wasserstein bound that displays those effects separately. A regression remainder is included as well, so the same calculation explains why an inaccurate regression parameter can degrade a bound even when the pair itself is unchanged.
Regression condition and notation
A pair of real-valued random variables \((W,W')\) is exchangeable if \((W,W')\) and \((W',W)\) have the same distribution. Write \(\Delta=W'-W\). Assume throughout the main result that \(E W=0\), \(E W^2=1\), and \(E|\Delta|^3<\infty\).
The conditional variance term in the bound will be expressed through \(E[\Delta^2\mid W]\). This is a conditional second moment of the increment; it need not be constant even when the regression condition is exact.
For a random variable \(X\) with finite first moment and a standard normal \(Z\), the Wasserstein distance is $$ d_{\mathrm W}(\mathcal L(X),\mathcal L(Z)) = \sup_{\|h\|_{\mathrm{Lip}}\leq 1}|E h(X)-E h(Z)|, $$ where the supremum is over real-valued functions satisfying \(|h(x)-h(y)|\leq |x-y|\). The normal Stein equation for such a test function is $$ f'(x)-xf(x)=h(x)-E h(Z). $$ We use the standard normal Stein bounds: the solution can be chosen with \(\|f\|_\infty\leq C_0\), \(\|f'\|_\infty\leq C_1\), and \(f'\) Lipschitz with constant at most \(C_2\), where \(C_0,C_1,C_2\) are universal finite constants. Equivalently, these constants can be taken as any valid uniform Stein factors for the chosen solution class.
The exchangeable-pair Wasserstein bound
The Stein equation now expresses the approximation error as \(E h(W)-E h(Z)=E[f'(W)-Wf(W)]\). Since \(f'\) is \(C_2\)-Lipschitz, the first-order expansion at \(W\) has a remainder \(T\) satisfying $$ f(W')-f(W)=\Delta f'(W)+T, \qquad |T|\leq \frac{C_2}{2}\Delta^2. $$ Substitution gives $$ E h(W)-E h(Z) = E\left[\left(1-\frac{E[\Delta^2\mid W]}{2\lambda}\right)f'(W)\right] -\frac{1}{2\lambda}E[\Delta T] -\frac{1}{\lambda}E[R(W)f(W)]. $$ Here we used the defining property of conditional expectation to replace \(E[\Delta^2 f'(W)]\) by \(E[E[\Delta^2\mid W]f'(W)]\).
Apply the triangle inequality and the Stein-factor bounds. The first term is at most $$ C_1 E\left|1-\frac{E[\Delta^2\mid W]}{2\lambda}\right|. $$ The second is at most \(C_2 E|\Delta|^3/(4\lambda)\), since \(|\Delta T|\leq C_2|\Delta|^3/2\). The last is at most \(C_0 E|R(W)|/\lambda\). These bounds hold for every 1-Lipschitz \(h\); taking the supremum proves the claim. \(\square\)
Reading the three error terms
The first term measures whether the conditional squared increment is close to \(2\lambda\). If \(E[\Delta^2\mid W]=2\lambda\) almost surely, this source of error vanishes. More generally, its average absolute fluctuation matters; merely knowing that the unconditional mean of \(\Delta^2\) equals \(2\lambda\) does not make this term zero.
The second term controls the error in replacing a Stein-solution increment by its linear approximation. It depends on the third absolute moment of \(\Delta\), divided by the regression scale \(\lambda\). The final term records the cost of failing to have exact linear regression. It is a bound involving the remainder itself, not just its mean: cancellation in \(E[R(W)]\) does not suffice.
Worked Example: A normalized Rademacher sum
Let \(X_1,\ldots,X_n\) be independent random variables with \(P(X_i=1)=P(X_i=-1)=1/2\), and set \(W=n^{-1/2}\sum_{i=1}^n X_i\). Choose \(I\) uniformly from \(\{1,\ldots,n\}\), independently of the variables, and let \(X_I'\) be an independent Rademacher variable. Replace \(X_I\) by \(X_I'\) to form \(W'\). The pair is exchangeable: conditional on the selected coordinate, the old and new coordinate are independent and identically distributed, and all other coordinates are unchanged. Also \(EW=0\) and \(EW^2=1\).
The increment is \(\Delta=(X_I'-X_I)/\sqrt n\). Given \(W\), the expected change from replacing a uniformly selected coordinate is $$ E[\Delta\mid W]=-\frac{W}{n}, $$ so \(\lambda=1/n\) and \(R(W)=0\). Each possible coordinate has square \(X_i^2=1\), and conditional on the old coordinate, \(E[(X_i'-X_i)^2]=2\). Thus $$ E[\Delta^2\mid W]=\frac{2}{n}=2\lambda, $$ and the conditional-variance term is exactly zero. The increment is nonzero precisely when the new sign differs from the old sign, an event of probability \(1/2\). Hence \(E|\Delta|^3=(1/2)(2/\sqrt n)^3=4n^{-3/2}\). The theorem therefore gives $$ d_{\mathrm W}(\mathcal L(W),\mathcal L(Z)) \leq \frac{C_2}{\sqrt n}. $$ The vanishing variance-fluctuation term is useful here, while the third-moment term supplies the rate.
Worked Example: Independent summands with variable conditional variance
Let \(X_1,\ldots,X_n\) be independent and identically distributed, with \(E X_i=0\), \(E X_i^2=1\), and \(E|X_i|^3<\infty\). Put \(W=n^{-1/2}\sum_i X_i\), and make \(W'\) by replacing a uniformly chosen \(X_I\) with an independent copy \(X_I'\). As in the preceding construction, the pair is exchangeable, and direct conditional expectation gives \(E[\Delta\mid W]=-W/n\). Thus \(\lambda=1/n\), with no regression remainder.
Condition first on all the original summands. Averaging over the coordinate and its replacement gives $$ E[\Delta^2\mid X_1,\ldots,X_n] =\frac{1}{n^2}\sum_{i=1}^n (X_i^2+1). $$ Conditioning this identity again on \(W\) yields $$ \frac{E[\Delta^2\mid W]}{2\lambda} =\frac{E[n^{-1}\sum_i X_i^2\mid W]+1}{2}. $$ The conditional-variance fluctuation is therefore $$ \frac12 E\left|1-E\left[\frac1n\sum_i X_i^2\middle|W\right]\right| \leq \frac12 E\left|\frac1n\sum_i X_i^2-1\right| \leq \frac{\sqrt{\operatorname{Var}(X_1^2)}}{2\sqrt n}, $$ where the first inequality is conditional Jensen and the second is Cauchy–Schwarz and independence. Also, $$ E|\Delta|^3=\frac{E|X_1'-X_1|^3}{n^{3/2}}. $$ The bound thus separates a fluctuation in the empirical squared summands from an increment-moment term. If \(E X_1^4<\infty\), both terms are of order at most \(n^{-1/2}\), with constants depending on the summand distribution and the Stein factors.
Regression remainders and step-size choices
The parameter \(\lambda\) is not a free normalization constant: the regression identity determines how it relates to the conditional drift. A poor choice can introduce a remainder even when an exact choice is available.
Worked Example: A refreshed sign and a mismatched regression parameter
Let \(W\) be a Rademacher variable. Independently, with probability \(p\in(0,1]\), replace it by an independent Rademacher variable \(X'\); otherwise set \(W'=W\). This pair is exchangeable, and $$ E[\Delta\mid W]=-pW,\qquad E[\Delta^2\mid W]=2p,\qquad E|\Delta|^3=4p. $$ With the correct choice \(\lambda=p\), the regression remainder and conditional-variance fluctuation both vanish. The third-moment contribution to the theorem is \(C_2\), which does not tend to zero as \(p\) decreases. That is not a contradiction: \(W\) remains a two-point variable, and this particular bound does not become accurate merely because updates are rare.
If instead one uses any \(\lambda>0\), the regression identity holds with \(R(W)=(\lambda-p)W\). Its contribution is \(C_0|\lambda-p|/\lambda\), while the conditional-variance contribution is \(C_1|1-p/\lambda|\). Both reflect the same mismatch. In this example \(E|W|=1\), so the remainder calculation is exact. Taking \(\lambda=p\) removes these avoidable errors; choosing a different value cannot improve the identity.
A related caution concerns thinning an exchangeable pair: retain the original pair with probability \(q\), and otherwise set the new variable equal to \(W\). If the original exact regression parameter is \(\lambda_0\), the thinned pair has parameter \(q\lambda_0\). Its conditional squared increment is multiplied by \(q\), and its third absolute increment moment is also multiplied by \(q\). Thus the ratio of conditional second moment to twice the regression parameter, and the ratio of third moment to the parameter, do not improve just by making updates less frequent. The same scaling applies to an existing regression remainder when the entire update is thinned. Step-size choices matter through the balance of the terms, not through a smaller \(\lambda\) in isolation.
When the bound is useful—and a common pitfall
The bound is most informative when the pair has a drift that closely matches \(-\lambda W\), the conditional squared increment is nearly \(2\lambda\), and the increment distribution has a small third moment relative to \(\lambda\). These are distinct properties. An exact regression condition alone does not control the other two, and a constant unconditional second moment does not guarantee a small conditional-variance fluctuation.
A common pitfall is to substitute \(E[\Delta^2]\) for \(E[\Delta^2\mid W]\) in the first term. That substitution removes information the bound needs. In fact, the expectation of the conditional variance may match \(2\lambda\) while its value varies substantially with \(W\). Another pitfall is to report only the drift identity while omitting its remainder: the theorem charges for \(E|R(W)|/\lambda\), so the chosen parameter and conditioning must be stated precisely.
Check Your Understanding
Use the derivation and examples above to check how each assumption contributes to the bound.
- Which identity follows from exchangeability, and why does swapping the pair change the sign of \(\Delta\)?
- What conditional quantity must be close to \(2\lambda\) for the variance-fluctuation term to be small?
- In the Rademacher-sum example, why does the third-moment term have order \(n^{-1/2}\)?
- For the independent-summand example, where does conditional Jensen enter the variance-fluctuation estimate?
- In the refreshed-sign example, what regression remainder results from using \(\lambda\ne p\)?