Antithetic Variates and the Synchronization of Paired Runs

Two variance-reduction techniques look unrelated until their mechanism is examined. Antithetic variates pair each uniform draw with its mirror $1 - u$ and average the two results, which cancels the part of the variance that changes sign under reflection. Common random numbers run two configurations through the same stream so their outputs share fluctuations and their difference is estimated far more precisely than either output. Both work by inducing correlation, and both break when the correlation is destroyed by a desynchronized stream.

The reflection that cancels the odd part

For an estimator $Y = h(U)$ of $\mu = \int_0^1 h(u), du$, the antithetic estimator is

$$\hat\mu_A = \frac{1}{2n}\sum_{i=1}^{n}\bigl(h(U_i) + h(1 - U_i)\bigr),$$

using $n$ uniforms to produce $2n$ evaluations. Its variance is

$$\mathrm{Var}(\hat\mu_A) = \frac{1}{2n}\left(\mathrm{Var}(h(U)) + \mathrm{Cov}(h(U), h(1-U))\right).$$

If the covariance is negative, the variance is below $\mathrm{Var}(h(U))/(2n)$, which is what plain sampling with $2n$ draws would give; if it is positive, antithetics are worse than doing nothing. Whether the technique helps is decided entirely by the sign of that covariance, and for a monotone $h$ the covariance is negative because $U$ and $1-U$ are perfectly negatively correlated and the reflection reverses the ordering of $h$‘s values.

The exact saving is cleanest for a linear $h$. With $h(u) = \beta_0 + \beta_1 u$, the pair average $[h(u) + h(1-u)]/2$ is exactly $\beta_0 + \beta_1/2$, the true mean, so the estimator has zero variance from a single pair. The mechanism is that the linear term is odd about the midpoint and cancels in the pair sum. A quadratic term does not cancel, so the residual variance comes from the even part of $h$; a strong linear term with a weak even term is the ideal case.

For a monotone nonlinear $h$ the covariance is negative but the cancellation is partial, and the variance reduction is bounded rather than total. The bound comes from the fact that $-1 \le \rho \le 0$ for the pair correlation, so the variance is between zero and the uncorrelated value, and the best case halves the work needed for a target precision. A factor of two is the ceiling for a single antithetic pairing, which is modest next to the orders of magnitude that importance sampling or stratification can deliver in the right problem.

The symmetry the estimator assumes

The reflection $u \mapsto 1 - u$ is a symmetry of the uniform distribution, and the estimator exploits it. If the quantity being estimated is not a function of a single uniform but of a transformation of many, the antithetic partner is not always $1 - u$ in the obvious place. The mirror has to be applied at the level of the source of randomness, which is why the technique is stated for the primitive uniforms rather than for the output variates: pairing $h(X)$ with $h(1 - X)$ where $X$ is the transformed variate is not antithetic unless $X$ itself is built monotonically from a single uniform.

The inverse-transform link makes the condition precise. When $X = F^{-1}(U)$, the reflection $U \mapsto 1 - U$ maps to $X’ = F^{-1}(1 - U)$, the value at the mirror tail, and the pair $(X, X’)$ is the antithetic pair for the target distribution. The monotonicity of $F^{-1}$ is what carries the negative correlation of $U$ and $1-U$ into negative correlation of $X$ and $X’$. A sampler that does not use inversion, such as rejection or Box-Muller, has no such monotone map, and an antithetic pair has to be constructed inside that sampler by reflecting the uniforms it consumes, which is fragile.

import math, random

def normal_quantile(u):
    # Inverse of the standard normal CDF via the Acklam rational
    # approximation; the central branch is an odd function of (u - 0.5).
    if u < 0.5:
        # Symmetry: F^-1(u) = -F^-1(1 - u); only the lower half is needed.
        pass
    # ... central rational branch and a tail branch ...
    return 0.0  # replaced by the branch value in a full implementation

def antithetic_pair(n):
    xs = []
    for _ in range(n):
        u = random.random()
        xs.append(normal_quantile(u))
        xs.append(normal_quantile(1.0 - u))
    return xs

The symmetry of the normal quantile, $F^{-1}(1-u) = -F^{-1}(u)$, is exactly what makes antithetics exact for this distribution: the pair $(z, -z)$ averages to zero, the true mean, in a single pair. The same argument applies to any symmetric distribution, and fails for a skewed one, where the reflected pair still correlates negatively but no longer cancels the mean exactly.

Synchronization is the contract

Antithetic variates depend on the stream advancing by exactly one uniform per evaluation, because the partner is the very next value in a fixed pairing. If the sampler consumes a random number of uniforms, as rejection sampling does, the pairing drifts and $h(U_i)$ is averaged against $h$ of something that is not its mirror. The result is a small positive correlation instead of a large negative one, and the estimator silently becomes worse than plain sampling.

The same contract underlies common random numbers. To compare two configurations $A$ and $B$, run each through the same seed and the same sequence of draws, then estimate the difference $E[h_A] - E[h_B]$ by averaging $h_A(X_i) - h_B(X_i)$ on paired draws. The variance of the difference is

$$\mathrm{Var}(h_A - h_B) = \mathrm{Var}(h_A) + \mathrm{Var}(h_B) - 2,\mathrm{Cov}(h_A, h_B),$$

and the covariance term is what buys the precision. When the two configurations consume the stream identically, the correlation is high and the difference is estimated with far fewer runs than either mean alone; when one consumes a rejection step that the other does not, the streams desynchronize at that point and every subsequent pair is mismatched.

The desynchronization is the recurring failure. It is invisible in the output, because both runs still produce valid-looking means, and it is invisible in the seeds, which match. The signature is a difference estimate whose error bar is no smaller than the individual error bars, which means the covariance has been lost. The fix is to make the two configurations consume the stream in lockstep, which usually means routing every branch, every rejection, and every table lookup through the same draw count in both.

def paired_estimate(n, h_a, h_b):
    rng = random.Random(12345)
    total = 0.0
    for _ in range(n):
        u = rng.random()
        total += h_a(u) - h_b(u)
    return total / n

Here the pairing is forced by the loop: the same $u$ feeds both configurations, so the difference is computed on exactly paired draws regardless of what each function does internally. The moment one function draws its own random number inside, the loop no longer controls the synchronization, and the estimator silently reverts to the unpaired variance.

The covariance a monotone map can buy

The negative covariance is not automatic; it is bounded by how much the reflection reorders the values. For a strictly monotone $h$, the antithetic pair $(h(U), h(1-U))$ is a pair of counter-monotone random variables, which maximizes the negative dependence among pairs with those marginals. Counter-monotonicity is the strongest possible negative association, and the antithetic covariance is the most negative it can be while keeping the marginal distribution fixed. Any other coupling of the same two marginals produces a covariance closer to zero.

This is what makes the saving a ceiling of a factor of two. The estimator pairs $n$ mirrored values, and the variance per pair is $\mathrm{Var}(h)/2$ plus $\mathrm{Cov}/2$; the covariance cannot drive the per-pair variance below zero, and in the limit of perfect counter-monotonicity the per-pair variance is $\mathrm{Var}(h)/2 - \mathrm{Var}(h)/2 = 0$ only when the pair average is exactly the mean, which happens for the linear case. For a monotone nonlinear $h$ the pair averages are not constant, and the residual variance is the variance of those averages, which is positive.

Generalizing to more than two values in a cycle, where $u$ is paired with $1-u$ and possibly with reflections across other symmetries, does not push past the factor of two for a single pair, because the coupling of two points is already extremal. The route to larger savings is stratification, which partitions the interval so that each stratum is estimated with less variance, or control variates, which subtract a correlated quantity with a known mean.

A control variate carries the idea past the pair. Given a quantity $Z$ with known mean $m_Z$ that correlates with $Y$, the estimator $Y - c(Z - m_Z)$ has mean $\mathbb{E}[Y]$ for any constant $c$ and variance

$$\mathrm{Var}(Y) - 2c,\mathrm{Cov}(Y, Z) + c^2 \mathrm{Var}(Z),$$

minimized at $c = \mathrm{Cov}(Y,Z)/\mathrm{Var}(Z)$, where the variance is $\mathrm{Var}(Y)(1 - \rho^2)$. A control variate correlated at $\rho = 0.95$ removes $90%$ of the variance, far beyond the antithetic factor of two, because it subtracts a measured fluctuation rather than reflecting one. The cost is knowing $m_Z$ exactly, which the antithetic construction gets for free by using the symmetry of the uniform.

When the correlation points the wrong way

Antithetics can hurt, and the condition is straightforward to state. The covariance is negative when $h$ is monotone; it is positive when $h$ has a minimum in the interior and the reflection pairs two points on the same side of the minimum. An integrand shaped like $h(u) = (u - 1/2)^2$ has $h(u) = h(1-u)$ exactly, so the pair covariance is the variance and the antithetic estimator has double the variance of plain sampling. The technique is a bet on monotonicity, and it is lost whenever the integrand is symmetric rather than monotone.

The same wrong-way correlation appears in common random numbers when the two configurations are not similar enough. The correlation is high when the paired outputs move together, which they do when the same underlying randomness drives both in the same direction. Two configurations that respond oppositely to the same draw produce negatively correlated outputs, and the difference estimate becomes worse than independent runs. The method assumes the alternatives being compared are alternatives in the same neighborhood, not contraries.

A subtler failure is shared across both techniques: the variance reduction changes the estimator, so the standard error must be recomputed for the paired estimator and cannot be inherited from the unpaired one. An antithetic estimator with a negative covariance has a smaller variance, and a paired difference has a variance that depends on the induced covariance; reporting the unpaired standard error for a paired estimate overstates the error in the good case and misleads in the bad case. The error bar has to be computed from the paired data itself.

The design constraint behind both methods is the cost of correlation. Antithetic variates cost one extra evaluation per uniform and a factor of two ceiling on the saving; common random numbers cost the discipline of lockstep stream consumption and pay off only when the comparison is the quantity of interest. Where they lose, the alternatives are the reweighting of importance sampling, which pays in weight variance instead of correlation, or plain independent sampling, whose error is described by the square-root law.