Randomized Experiments

Why random assignment licenses a causal reading, and how the assignment itself becomes the basis of an exact test. Randomization proved to balance every attribute of the units, measured or not, in expectation and in distribution, with the size and correlation of chance imbalances derived; Fisher's randomization test proved exact under the sharp null hypothesis for any statistic and any design; the sharp null against Neyman's weak null, with the exact expected variance of the randomization distribution derived and the reason the difference-in-means test can lose its level under the weak null, and the studentized test, which keeps it in large samples (Wu and Ding, 2021, cited); confidence intervals for a constant effect by inverting the test; Bernoulli against complete randomization, with the Horvitz-Thompson estimator's variance derived; and A/B tests and interleaving read as randomized experiments. Worked on the Cranfield science table of stemmed and unstemmed BM25. Worked problems on Fisher's tea-tasting experiment, a randomization test and interval enumerated on six units, and the permutation variance under the weak null on four.

In the running experiment of Potential Outcomes and the Average Treatment Effect, 113 of the 225 Cranfield queries (Cleverdon, 1967) are stemmed at random and 112 are not, and the difference in mean average precision comes out at $-0.0021$ although stemming raises these queries' average precision by 0.0243 on average. The stemmed queries happen to be harder ones: under the unstemmed ranker their mean average precision is 0.2654, against 0.2992 for the others. Random assignment did not make the groups alike. Why, then, is a randomized comparison trusted to measure a cause, and what exactly does randomization guarantee?

A randomized experiment is a study in which the experimenter assigns the treatments by a known random mechanism, chosen without regard to the units' outcomes. The potential-outcomes article proved one consequence, that the difference in means is unbiased for the average effect, using only the first two moments of the assignment. This article uses the whole distribution of the assignment.

Here is the route. First what randomization balances: every attribute of the units, in expectation and in distribution, with chance imbalances whose size and correlations can be computed. Then Fisher's randomization test, proved exact for any statistic and any design under the hypothesis that the treatment affects no unit. Then the difference between that sharp hypothesis and Neyman's hypothesis of no average effect, with an exact formula showing when the test can mislead about the second. Then confidence intervals obtained by inverting the test. Then two designs compared, Bernoulli and complete randomization. Finally, online A/B tests and interleaving, read as randomized experiments. The article assumes the potential-outcomes article for notation and for its Lemmas 1 and 2, and Permutation Tests for the counting lemma and Monte Carlo p-values, which it does not repeat.

What randomization balances

Under complete randomization the treated set is a simple random sample of the units. Every number attached to the units before assignment is therefore split between the groups by chance alone: a covariate that was measured, one that was not, and each unit's potential outcomes, which are fixed attributes like any other.

Theorem 1 (balance). Under complete randomization with $n_1$ treated, $n_0$ controls and $p = n_1/n$, let $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ be any fixed attributes of the units, with finite-population variances $S_x^2$, $S_y^2$ and covariance $S_{xy}$ (divisor $n - 1$), and let $D_x = \bar x_1 - \bar x_0$ be the difference between the treated and control means of $x$. Then

  1. $E[D_x] = 0$ and $\operatorname{Var}(D_x) = \dfrac{n}{n_1n_0}S_x^2$;
  2. $\operatorname{Cov}(D_x, D_y) = \dfrac{n}{n_1n_0}S_{xy}$, so the correlation of the two imbalances equals the finite-population correlation of $x$ and $y$;
  3. for every $t$, the empirical distribution functions of $x$ in the two groups, $\hat F_1(t) = \frac{1}{n_1}\sum_{W_i = 1}\mathbf 1[x_i \le t]$ and $\hat F_0(t)$, both have expectation $F(t) = \frac1n\sum_i\mathbf 1[x_i \le t]$.

Proof. Since $\bar x_1 = \frac{1}{np}\sum_iW_ix_i$ and $\bar x_0 = \frac{1}{n(1 - p)}\sum_i(1 - W_i)x_i$,

$$D_x = \frac{(1 - p)\sum_iW_ix_i - p\sum_i(1 - W_i)x_i}{np(1 - p)} = \frac{\sum_i(W_i - p)x_i}{np(1 - p)}.$$

By Lemma 1 of the potential-outcomes article $E[W_i] = p$, so $E[D_x] = 0$; by its Lemma 2, $\operatorname{Var}(D_x) = \frac{np(1 - p)S_x^2}{(np(1 - p))^2} = \frac{S_x^2}{np(1 - p)} = \frac{n}{n_1n_0}S_x^2$. Lemma 2 applied to $x + y$, minus its applications to $x$ and to $y$, gives $\operatorname{Cov}(\sum_iW_ix_i, \sum_iW_iy_i) = np(1 - p)S_{xy}$, hence part 2. Part 3 is part 1's expectation statement applied to the attribute $\mathbf 1[x_i \le t]$, since $E[\hat F_1(t)] = \frac{1}{n_1}\sum_iE[W_i]\mathbf 1[x_i \le t] = F(t)$, and likewise for the controls. $\square$

In a superpopulation the statement becomes exact rather than average: if $W$ is independent of $(X, Y(1), Y(0))$, the distribution of the covariates and of the potential outcomes is the same among the treated as among the controls. That is what "balance in distribution" means, and it holds for attributes nobody thought to measure. Fisher put the point in words that Data Collection and Sampling quotes: "the uncontrolled causes which may influence the result are always strictly innumerable", and randomization deals with them all at once.

The running experiment, examined. The script tools/experiments/statistics/randomized-experiments.py computes the imbalance $d = D_x/\sqrt{\operatorname{Var}(D_x)}$, standardized by the exact randomization standard deviation of Theorem 1, for three covariates that a researcher could measure and for the two potential outcomes, which no researcher sees:

Attribute Treated mean Control mean Standardized imbalance $d$
TF-IDF average precision 0.2917 0.2966 $-0.16$
relevant documents 7.04 7.29 $-0.36$
query terms (after stop-word removal) 12.30 11.42 1.45
$Y(0)$, unstemmed AP 0.2654 0.2992 $-1.11$
$Y(1)$, stemmed AP 0.2971 0.3161 $-0.60$

The error of the estimate is itself an imbalance of the potential outcomes. Since $\tau_{\mathrm{fp}} = \bar Y(1) - \bar Y(0)$ and $\hat\tau$ compares the treated mean of $Y(1)$ with the control mean of $Y(0)$,

$$\hat\tau - \tau_{\mathrm{fp}} = \big(\bar Y_1(1) - \bar Y(1)\big) - \big(\bar Y_0(0) - \bar Y(0)\big),$$

where $\bar Y_1(1)$ is the treated units' mean of $Y(1)$ and $\bar Y_0(0)$ the controls' mean of $Y(0)$. Here the treated queries' stemmed AP falls short of the all-query mean 0.3066 by 0.0095, and the controls' unstemmed AP exceeds the all-query mean 0.2822 by 0.0170. The error is $-0.0095 - 0.0170 = -0.0265$, the figure of the potential-outcomes article.

Example (balance in expectation is not balance in each experiment). "The groups are balanced because the experiment was randomized" is a common misreading. Over 30 seeds of 20,000 assignments, each attribute's $\lvert d\rvert$ exceeded 1.96 in a median 0.050 of assignments for TF-IDF AP (interquartile range 0.048 to 0.051), 0.049 for relevant documents (0.049 to 0.050), 0.049 for query terms (0.048 to 0.050) and 0.049 for $Y(0)$ (0.048 to 0.050): the 5% that a normal approximation predicts. At least one of the three measured covariates was imbalanced at that level in 0.141 of assignments (0.139 to 0.142). Randomization guarantees that imbalances are chance imbalances of a known size, so that the probability statements of the analysis are correct. It does not guarantee that a particular experiment is balanced. The remedies act before or after assignment: blocking (Blocking and Factorial Designs) rules out unbalanced assignments, and regression adjustment (the potential-outcomes article, Theorem 6) corrects for the part of an imbalance that a covariate measures.

Part 2 of Theorem 1 says how much a measured covariate can tell about the unmeasured imbalance. The correlation between the imbalance in TF-IDF AP and the imbalance in $Y(0)$, over the simulated assignments, had median 0.868 (interquartile range 0.866 to 0.870), the finite-population correlation of the two attributes, 0.868, as the theorem requires. A covariate correlated 0.868 with $Y(0)$ accounts, by linear regression of one imbalance on the other, for about three quarters ($0.868^2$) of the variance of the imbalance in $Y(0)$ over assignments; in the running experiment it happens to show little of it ($d = -0.16$ against $-1.11$).

Fisher's randomization test

The balance argument justifies estimation. Fisher (1935) used randomization for a second purpose, which Ding (2024, §3.1) lists among the advantages of randomization that Fisher pointed out: it "serves as a 'reasoned basis' for statistical inference". It yields a test whose null distribution is created by the experimenter.

The sharp null hypothesis is that the treatment has no effect on any unit:

$$H_0^{\mathrm F}\colon\ Y_i(1) = Y_i(0) \quad\text{for every } i = 1, \ldots, n.$$

Ding (2024, §3.2) reports that the name "sharp" is Rubin's (1980): the hypothesis determines every missing potential outcome, because each must equal the observed one. Under $H_0^{\mathrm F}$ the observed outcome vector $\mathbf y$ would have been the same under every assignment. So for any test statistic $T(\mathbf w, \mathbf y)$, a function of an assignment and the outcomes with large values counting against the hypothesis, the experimenter knows its distribution exactly: it is the distribution of $T(\mathbf W', \mathbf y)$ as $\mathbf W'$ ranges over the assignments the design could have produced, with their probabilities. The randomization p-value is

$$p(\mathbf w) = P\big(T(\mathbf W', \mathbf y) \ge T(\mathbf w, \mathbf y)\big), \qquad \mathbf W' \sim \text{the design},$$

computed with $\mathbf y$ held fixed. Under complete randomization $\mathbf W'$ is uniform over the $\binom{n}{n_1}$ assignments, and the test is the two-sample permutation test of Permutation Tests, justified here by the design rather than by exchangeability of the outcomes.

Theorem 2 (exactness of the randomization test). Under $H_0^{\mathrm F}$, $P\big(p(\mathbf W) \le \alpha\big) \le \alpha$ for every $\alpha \in [0, 1]$, for any statistic $T$ and any design, uniform or not.

Proof. Under $H_0^{\mathrm F}$ the outcome vector does not depend on the assignment, so $T_{\mathrm{obs}} = T(\mathbf W, \mathbf y)$ has the same distribution as $T(\mathbf W', \mathbf y)$. Write $G(t) = P(T_{\mathrm{obs}} \ge t)$, so that $p(\mathbf W) = G(T_{\mathrm{obs}})$. The function $G$ is nonincreasing. Let $t^* = \inf\{t : G(t) \le \alpha\}$ (if no $t$ has $G(t) \le \alpha$, the event $G(T_{\mathrm{obs}}) \le \alpha$ is empty and there is nothing to prove). Since $G$ is nonincreasing, $\{t : G(t) \le \alpha\}$ is either $[t^*, \infty)$ or $(t^*, \infty)$. In the first case $P(G(T_{\mathrm{obs}}) \le \alpha) = P(T_{\mathrm{obs}} \ge t^*) = G(t^*) \le \alpha$. In the second, $P(G(T_{\mathrm{obs}}) \le \alpha) = P(T_{\mathrm{obs}} > t^*) = \lim_{t \downarrow t^*}P(T_{\mathrm{obs}} \ge t) = \lim_{t \downarrow t^*}G(t) \le \alpha$, since $G(t) \le \alpha$ for every $t > t^*$. $\square$

For a uniform design the theorem is the counting argument of Permutation Tests (Lemma 1 and Theorem 1); this proof also covers designs whose assignments are not equally likely, such as the Bernoulli design below. When the assignments are too many to list, the p-value $(b + 1)/(B + 1)$ computed from $B$ assignments drawn at random from the design is still valid. For any design the reason is that, under $H_0^{\mathrm F}$, the realized assignment and the $B$ independent draws from the design are independent and identically distributed, so the $B + 1$ values of the statistic are exchangeable and Step 3 of the proof of Theorem 6 of Permutation Tests, with its Lemma 1, applies directly. For complete randomization this is also the group argument of that theorem, since relabeling the units maps each assignment to another with the same probability.

On Cranfield. For the running experiment the randomization test with the difference in means, from 99,999 random assignments, gives $p = 0.946$; with the studentized statistic $\hat\tau/\sqrt{\hat V}$ it gives the same 0.946, and the normal approximation to Neyman's test gives 0.947. None detects the effect, which is real but small. Over 30 seeds of 1,000 experiments, each tested with 499 random assignments, the test with the difference in means rejected at the 5% level in a median 0.112 of experiments (interquartile range 0.107 to 0.118); its power against this alternative is about 11%. Neyman's normal test rejected in 0.115 (0.110 to 0.124), and a normal approximation with the true variance predicts 0.115. An experiment of this size cannot reliably see an effect of this size; the potential-outcomes and blocking articles show what would.

The sharp null and the weak null

Neyman's question is different: is the average effect zero?

$$H_0^{\mathrm N}\colon\ \tau_{\mathrm{fp}} = 0.$$

The sharp null implies Neyman's weak null, not the reverse: under $H_0^{\mathrm N}$ some units may gain and others lose. Ding (2017, abstract) shows a surprising consequence in completely randomized experiments: rejecting Neyman's null "does not imply rejection of Fisher's null for many realistic situations, including the case with constant causal effect". Can the randomization test be used to test the weak null? Its p-value pretends that the observed outcomes would have been seen under every assignment, which is false under $H_0^{\mathrm N}$ alone. The next theorem measures the consequence for the difference in means, exactly.

For the difference in means, the randomization distribution computed from the observed outcomes has mean zero and variance $s^2\,\frac{n}{n_1n_0}$, where $s^2$ is the sample variance of all $n$ observed outcomes pooled (Permutation Tests, Theorem 4). Call this the permutation variance. A randomization test of the difference in means behaves roughly like a normal test that uses this variance in place of the true one, so the question is how the two compare.

Theorem 3 (the expected permutation variance). Under complete randomization, for any science table,

$$E[s^2] = pS_1^2 + (1 - p)S_0^2 + \frac{n}{n - 1}p(1 - p)\tau_{\mathrm{fp}}^2 - \frac{p(1 - p)}{n - 1}S_\tau^2.$$

Under the weak null $\tau_{\mathrm{fp}} = 0$, the expected permutation variance exceeds Neyman's variance $V = S_1^2/n_1 + S_0^2/n_0 - S_\tau^2/n$ by

$$E\Big[s^2\frac{n}{n_1n_0}\Big] - V = \frac{(S_1^2 - S_0^2)(n_1 - n_0)}{n_1n_0} + \frac{n - 2}{n(n - 1)}S_\tau^2.$$

Proof. With $Y_i$ the observed outcomes and $\bar Y$ their mean, $(n - 1)s^2 = \sum_iY_i^2 - n\bar Y^2$. First, $\sum_iY_i^2 = \sum_i\big(W_iY_i(1)^2 + (1 - W_i)Y_i(0)^2\big)$ has expectation $p\sum_iY_i(1)^2 + (1 - p)\sum_iY_i(0)^2 = p\big((n - 1)S_1^2 + n\bar Y(1)^2\big) + (1 - p)\big((n - 1)S_0^2 + n\bar Y(0)^2\big)$. Second, $\bar Y = \bar Y(0) + \frac1n\sum_iW_i\tau_i$, so $E[\bar Y] = m = p\bar Y(1) + (1 - p)\bar Y(0)$ and, by Lemma 2 of the potential-outcomes article, $\operatorname{Var}(\bar Y) = \frac{1}{n^2}np(1 - p)S_\tau^2$; hence $nE[\bar Y^2] = nm^2 + p(1 - p)S_\tau^2$. Subtracting, and using $p\,a^2 + (1 - p)b^2 - (pa + (1 - p)b)^2 = p(1 - p)(a - b)^2$ with $a = \bar Y(1)$, $b = \bar Y(0)$,

$$(n - 1)E[s^2] = (n - 1)\big(pS_1^2 + (1 - p)S_0^2\big) + np(1 - p)\tau_{\mathrm{fp}}^2 - p(1 - p)S_\tau^2,$$

which is the first formula. With $\tau_{\mathrm{fp}} = 0$, multiply by $\frac{n}{n_1n_0}$, noting $\frac{np}{n_1n_0} = \frac{1}{n_0}$, $\frac{n(1 - p)}{n_1n_0} = \frac{1}{n_1}$ and $\frac{np(1 - p)}{n_1n_0} = \frac1n$:

$$E\Big[s^2\frac{n}{n_1n_0}\Big] = \frac{S_1^2}{n_0} + \frac{S_0^2}{n_1} - \frac{S_\tau^2}{n(n - 1)}.$$

Subtracting $V$ gives $S_1^2\big(\frac{1}{n_0} - \frac{1}{n_1}\big) + S_0^2\big(\frac{1}{n_1} - \frac{1}{n_0}\big) + S_\tau^2\big(\frac1n - \frac{1}{n(n - 1)}\big)$, which is the second formula. $\square$

The theorem is the finite-population, randomization-based counterpart of Theorem 5 of Permutation Tests, which compared the same two variances for independent samples from two populations. The first term has the same shape: the permutation variance attaches each group's spread to the other group's size, so it is too small when the smaller group has the larger variance. The second term is new. Heterogeneous unit effects make the permutation distribution wider than the truth, as they made Neyman's estimator conservative. Ding (2024, §8.1) gives a large-sample heuristic version of this comparison.

A weak null on Cranfield. Subtracting $\tau_{\mathrm{fp}} = 0.0243$ from every stemmed AP gives a science table in which the average effect is exactly zero but the unit effects still vary as before ($S_1^2 = 0.0573$, $S_0^2 = 0.0519$). The theorem gives the ratio of the expected permutation variance to the true variance, and a normal approximation turns it into the rejection rate of a nominal 5% test, $2\big(1 - \Phi(1.96\sqrt{\text{ratio}})\big)$:

Treated / control Ratio Predicted level, difference in means Simulated, difference in means Simulated, studentized Simulated, Neyman's normal test
25 / 200 0.945 0.057 0.060 (0.054 to 0.063) 0.048 (0.041 to 0.052) 0.064 (0.055 to 0.068)
113 / 112 1.058 0.044 not simulated not simulated not simulated
200 / 25 1.105 0.039 0.041 (0.037 to 0.043) 0.048 (0.046 to 0.056) 0.062 (0.056 to 0.070)
The level of a nominal 5% randomization test of no effect, applied when only the average effect is zero, as the number of stemmed queries varies. The curve is the normal-approximation prediction from Theorem 3 for the difference in means: notice that it rises above 0.05 when the stemmed group is small, because the stemmed outcomes, which are slightly more variable (S_1^2 = 0.0573 against S_0^2 = 0.0519), are then observed on the smaller group, and falls below it as the group grows. The points are the simulated medians with interquartile ranges at 25 and 200 stemmed queries, for the difference in means and for the studentized statistic.
The level of a nominal 5% randomization test of no effect, applied when only the average effect is zero, as the number of stemmed queries varies. The curve is the normal-approximation prediction from Theorem 3 for the difference in means: notice that it rises above 0.05 when the stemmed group is small, because the stemmed outcomes, which are slightly more variable ($S_1^2 = 0.0573$ against $S_0^2 = 0.0519$), are then observed on the smaller group, and falls below it as the group grows. The points are the simulated medians with interquartile ranges at 25 and 200 stemmed queries, for the difference in means and for the studentized statistic.

The simulated rates are medians over 30 seeds of 1,000 experiments, each randomization test using 499 random assignments, with interquartile ranges. With 25 treated queries, whose stemmed outcomes are slightly more variable, the test with the difference in means rejects a true weak null somewhat too often; with the sizes reversed it is conservative. In both simulated designs the median rejection rate of the test with the studentized statistic stays at or below 5%. Wu and Ding (2021, abstract) prove the large-sample version of this in general: the randomization test with a studentized statistic is "finite-sample exact under the sharp null hypothesis" and "conservatively controls large-sample type I error under the weak null hypothesis". So the studentized statistic is the one to use when the question is about the average effect. The normal approximation to Neyman's test also exceeded 5% in this simulation, by more than the randomization test with the difference in means did. Average precision is skewed and bounded, and 25 queries are few, so the normal approximation is poor here: an observation about this table and these sizes. The randomization test with the studentized statistic needs no normal approximation under the sharp null.

Confidence intervals from the test

Any sharp hypothesis can be tested, not only that of no effect. The hypothesis of a constant effect $c$,

$$H_0(c)\colon\ Y_i(1) - Y_i(0) = c \quad\text{for every } i,$$

determines the missing outcomes: a treated unit's control outcome is $Y_i - c$ and a control unit's treated outcome is $Y_i + c$. Equivalently, the adjusted outcomes $Y_i - cW_i$ are the control outcomes $Y_i(0)$, which do not depend on the assignment, so the randomization test of $H_0(c)$ is the test of no effect applied to the adjusted outcomes. By Theorem 2, if the effect really is constant and equal to $c$, the test rejects with probability at most $\alpha$. The set of values $c$ that the test does not reject at level $\alpha$ is therefore a confidence set with coverage at least $1 - \alpha$ for a constant effect. Ding (2024, §3.6.1) attributes this construction to Rosenbaum and notes its limitation: the constant-effect assumption is strong, and the set says nothing guaranteed about the average effect when effects vary. The same inversion applied to the sign-flip test gives the interval of Permutation Tests for paired data.

For the running experiment, inverting the test with the difference in means (the same 19,999 random assignments for every $c$, endpoints found by bisection and checked on a grid of step 0.0005) gives the interval from $-0.064$ to 0.061. Neyman's interval, $\hat\tau \pm 1.96\sqrt{\hat V}$, runs from $-0.064$ to 0.060. Both contain the true average effect, 0.0243, and both contain zero. Over 30 seeds of 1,000 experiments on the real table, where the effects are far from constant, the test of $H_0(\tau_{\mathrm{fp}})$ failed to reject, so that the inverted interval covered the average effect, in a median 0.956 of experiments (interquartile range 0.954 to 0.960); Neyman's interval covered it in 0.956 (0.951 to 0.960). The first figure is an observation for this table, not a guarantee.

Bernoulli and complete randomization

Complete randomization fixes the number treated. A Bernoulli design instead treats each unit independently with probability $p$, as a coin flip per unit or per website visitor would. The number treated, $N_1$, is then binomial.

Theorem 4 (the Bernoulli design). Under a Bernoulli design with $0 < p < 1$:

  1. conditionally on $N_1 = m$ with $1 \le m \le n - 1$, the assignment is a complete randomization with $m$ treated; so, given $N_1$, the difference in means is unbiased for $\tau_{\mathrm{fp}}$ and Neyman's theorems apply with $n_1 = m$;
  2. the Horvitz–Thompson estimator $\hat\tau_{\mathrm{HT}} = \frac1n\sum_i\big(W_iY_i/p - (1 - W_i)Y_i/(1 - p)\big)$ is unbiased for $\tau_{\mathrm{fp}}$, with $$\operatorname{Var}(\hat\tau_{\mathrm{HT}}) = \frac{p(1 - p)}{n^2}\sum_ia_i^2, \qquad a_i = \frac{Y_i(1)}{p} + \frac{Y_i(0)}{1 - p},$$ while complete randomization with $n_1 = pn$ gives the difference in means the variance $\frac{p(1 - p)}{n^2}\cdot\frac{n}{n - 1}\sum_i(a_i - \bar a)^2$.

Proof. (1) Each assignment with $m$ treated has probability $p^m(1 - p)^{n - m}$, the same for all of them, so given $N_1 = m$ the assignment is uniform over the $\binom nm$ such assignments. (2) As in equation (2) of the potential-outcomes article, $\hat\tau_{\mathrm{HT}} - \tau_{\mathrm{fp}} = \frac1n\sum_i(W_i - p)a_i$; the identity uses only the definition of $\hat\tau_{\mathrm{HT}}$, which here divides by $p$ and $1 - p$ rather than by the realized group sizes. Now the $W_i$ are independent with variance $p(1 - p)$, so the variance is $\frac{1}{n^2}\sum_ip(1 - p)a_i^2$. The variance under complete randomization is Theorem 2 of the potential-outcomes article, $\frac{p(1 - p)}{n}S_a^2$. $\square$

Part 1 is why the difference in means is the usual analysis of a Bernoulli experiment: it is the analysis of a completely randomized experiment conditional on the number treated. A randomization test may likewise condition on $N_1$, permuting the observed assignment, or use the Bernoulli distribution itself; both are exact by Theorem 2, and Ding (2024, Problem 4.7) poses the comparison. The difference in means is undefined when everyone or no one is treated; with $p = 1/2$ and 225 queries that has probability $2 \cdot 2^{-225}$, about $10^{-67.4}$.

Part 2 shows what the Horvitz–Thompson estimator, which Survey Weights and the Horvitz–Thompson Estimator proves unbiased under any design, pays for dividing by the expected rather than the realized group size. Its variance contains $\sum_ia_i^2$, not $\sum_i(a_i - \bar a)^2$: the level of the outcomes, not only their variation, enters. On Cranfield with $p = 1/2$, the difference in means under the Bernoulli design (conditionally on at least two units in each group, averaging Neyman's variance over the binomial count) has variance 0.000922, close to complete randomization's 0.000917 with 112 or 113 treated. The Horvitz–Thompson estimator has variance 0.002454, 2.66 times larger. Adding 1 to every outcome, which changes no effect, raises it to 0.030699, 33.3 times the difference in means. The difference in means is the ratio (Hájek) form of the same weighting, which the survey-weights article treats.

A/B tests and interleaving

An A/B test is a randomized experiment on the users of a website or application: each user is assigned to the current version (control) or a new one (treatment), and a behavior such as clicking or returning is compared. Online Evaluation describes the practice for search engines and works out how many users such a test needs. Seen through this unit's results:

  • Assignment by a per-user coin flip is a Bernoulli design, and by Theorem 4 the difference in means is analyzed as a completely randomized experiment given the group sizes.
  • The unit is the unit of randomization. If users are randomized but the metric is computed per query, a user's queries share that user's treatment and habits, and treating them as independent units overstates precision. The online-evaluation article makes this point; Clustered Standard Errors gives the variance that respects such grouping.
  • SUTVA can fail. When treated and control users share a resource, such as a stock of goods, drivers, or each other's posts and messages, one user's assignment can change another's outcome. Ding (2024, §2.2) gives vaccination and online advertising seen by friends as examples of interference. The difference in means then estimates the effect of treating some users while others are untreated, not the effect of switching everyone.

Interleaving is a randomized experiment of a different shape. In team-draft interleaving each impression, a query from one user, is shown a single list merged from both rankers, and coin flips decide which ranker contributes the higher-placed result in each round (Online Evaluation traces every coin sequence). The unit is the impression, and both "treatments" are applied within it, in the spirit of the paired design of Blocking and Factorial Designs: what varies between users and queries cancels within the comparison, which is where its sensitivity comes from. The randomization is in the coin flips, and the online-evaluation article proves what they guarantee: a user who clicks a result at random, ignoring its content, credits each ranker with probability exactly 1/2. The outcome is credit, and the estimand is a preference, the expected share of impressions won. That is not the average effect of deploying one ranker instead of the other. The online-evaluation article works through Chapelle et al.'s (2012) ambiguous query, on which team-draft interleaving prefers the ranking that serves users worse. An experiment estimates the quantity its design defines, and the design must be chosen for the question.

What is proved here, what is cited, what the experiment shows

Proved here. Balance under complete randomization: unbiased imbalance of every attribute, its exact variance, the correlation of two attributes' imbalances, and the unbiasedness of each group's empirical distribution function (Theorem 1). The decomposition of the estimation error into imbalances of the potential outcomes. The exactness of the randomization test under the sharp null, for any statistic and any design (Theorem 2). The exact expectation of the pooled sample variance under complete randomization, and the difference between the expected permutation variance and Neyman's variance under the weak null (Theorem 3). The test-inversion confidence set's coverage under a constant effect, as a consequence of Theorem 2. The Bernoulli design's conditional equivalence to complete randomization and the Horvitz–Thompson estimator's unbiasedness and variance (Theorem 4).

Cited. The counting lemma, Monte Carlo p-values and the moments of the permutation distribution (Permutation Tests, Lemma 1 and Theorems 1, 4 and 6). Fisher's (1935) role for randomization and Rubin's (1980) name "sharp", as Ding (2024) reports them; Fisher's quotation as Data Collection and Sampling gives it. Ding's (2017) paradox, from its abstract. Wu and Ding's (2021) result for studentized statistics, from their abstract. Chapelle et al.'s (2012) ambiguous query, as the online-evaluation article reports it. The constant-effect inversion and its attribution to Rosenbaum (Ding, 2024, §3.6.1). The interleaving results of the online-evaluation article.

What the experiments show. For the running experiment, the imbalances, p-values and intervals. Over 30 seeds: the 5% rate of large imbalances and the correlation of imbalances predicted by Theorem 1; the power of the tests against the real effect; the levels of three tests under a weak null at two designs, with Theorem 3's predictions at three; the coverage of the inverted interval on a table with heterogeneous effects. The exact variances of the Bernoulli and Horvitz–Thompson estimators. Statements about levels and coverage that are not covered by a theorem are observations for this table and these group sizes.

Worked problems

These problems are posed here; the first restates Fisher's tea-tasting experiment as Ding (2024, §§3.5.2 and 3.5.3) reports it. The article's script checks every number exactly.

Problem 1 (the lady tasting tea). A lady says she can tell whether milk or tea was poured first. Fisher prepared eight cups, four of each kind, presented them in random order, and asked her to pick the four with milk first. If she cannot tell, what is the distribution of the number $X$ of milk-first cups among her four picks, and what is the p-value if she picks all four correctly? What if she picks three? And what is the smallest p-value with six cups, three of each?

Solution. Under the sharp null her four picks are fixed whatever the preparation, and the randomization makes the set of milk-first cups uniform among the $\binom84$ = 70 sets of four. So $X$ is the number of her picks in a random set of four from eight, of which four are her picks: $P(X = k) = \binom4k\binom{4}{4 - k}/70$, which is 1/70, 8/35, 18/35, 8/35, 1/70 for $k = 0, \ldots, 4$. All four correct gives $p = P(X \ge 4) = 1/70 = 0.014$, the value Ding reports. Three correct gives $p = P(X \ge 3) = (16 + 1)/70$ = 17/70, about 0.24, no evidence at all. With six cups the most extreme outcome has probability $1/\binom63$ = 1/20, so no result can give a p-value below 0.05: replication is needed before a test can say anything.

Problem 2 (a test and an interval, enumerated). Six units are completely randomized, three treated. The treated outcomes are 9, 7, 8 and the control outcomes 3, 5, 4. Find the two-sided randomization p-value for the difference in means under the sharp null, and the set of constant effects $c$ not rejected at level 0.10.

Solution. The observed difference is $8 - 4$ = 4. There are $\binom63 = 20$ assignments. The treated values are the three largest, so the observed split has the largest $\lvert\hat\tau\rvert$, and only its mirror image (3, 5, 4 treated) matches it; the count is 2 and $p = 2/20 = 0.10$. Since every split and its mirror give the same $\lvert\hat\tau\rvert$, no p-value can be below 2/20, so a test at level 0.10 rejects exactly when the observed split is the most extreme. For $H_0(c)$ the adjusted outcomes are $9 - c$, $7 - c$, $8 - c$ for the treated and 3, 5, 4 for the controls. If the two groups do not overlap, every treated value strictly above every control value or strictly below, the observed split is the most extreme and $H_0(c)$ is rejected: this happens when $7 - c > 5$, that is $c < 2$, or when $9 - c < 3$, that is $c > 6$. For $2 \le c \le 6$ the groups overlap or touch, so the split that puts the three largest adjusted values together is a different split from the observed one, or ties it, and together with the two mirror pairs at least four splits reach $\lvert\hat\tau\rvert$: $p \ge 4/20$ and $H_0(c)$ is not rejected. The set is the interval from 2 to 6, a 90% confidence interval for a constant effect, and the script's scan of $c$ in steps of 1/3 finds the same endpoints.

Problem 3 (the permutation variance under a weak null). Take the four-unit table of the potential-outcomes article, $Y(1) = (7, 5, 4, 2)$ and $Y(0) = (3, 4, 1, 2)$, and subtract 2 from every $Y(1)$, so that the average effect is zero. With two units treated, compare the average permutation variance $s^2 \cdot n/(n_1n_0)$ with the true variance of the difference in means.

Solution. The shifted unit effects are $(2, -1, 1, -2)$, with $S_\tau^2 = 10/3$ as before, and the column variances are unchanged. The true variance is $V = 13/6$ (the potential-outcomes article, Problem 1: shifting a column changes no variance). Averaging $s^2 \cdot 4/(2 \cdot 2) = s^2$ over the six assignments gives 49/18. Theorem 3 predicts the excess $\frac{(S_1^2 - S_0^2)(n_1 - n_0)}{n_1n_0} + \frac{n - 2}{n(n - 1)}S_\tau^2 = 0 + \frac{2}{12}\cdot\frac{10}{3}$ = 5/9, and indeed $49/18 - 13/6 = 49/18 - 39/18 = 10/18 = 5/9$. With equal groups only the heterogeneity term remains, and it makes the randomization test of the difference in means conservative for the weak null.

Summary

  • Randomization balances every attribute of the units, measured or not and including the potential outcomes, in expectation and in distribution; each realized imbalance is a chance imbalance of known size, and imbalances in different attributes are correlated as the attributes are (Theorem 1). The estimation error is an imbalance of the potential outcomes.
  • Under the sharp null of no effect on any unit, the randomization test is exact for any statistic and any design (Theorem 2).
  • Under the weak null of no average effect, the test with the difference in means can be too liberal when the smaller group has the larger variance and is made conservative by heterogeneous effects (Theorem 3); with a studentized statistic it remains exact under the sharp null and is asymptotically conservative under the weak null (Wu and Ding, 2021).
  • Inverting the test gives a confidence set for a constant effect, valid when the effect is constant.
  • A Bernoulli design is a complete randomization given the number treated; the Horvitz–Thompson estimator is unbiased but its variance depends on the level of the outcomes (Theorem 4).
  • A/B tests are randomized experiments on users, analyzed at the level at which users were randomized; interleaving randomizes within each impression and estimates a preference, not the effect of deployment.

What we have learned

Randomization makes the probability in a causal analysis real: the experimenter knows the distribution of the assignment, so the chance of any imbalance, and the null distribution of any statistic under the sharp null, can be computed rather than modeled. The guarantees are precise and limited. They are about averages over assignments, not about the balance of a given experiment, and the exact test answers the sharp question unless its statistic is studentized.

Balance on average still leaves a given experiment free to be unbalanced, and the experiments of this article had standard errors larger than the effect they sought. Blocking and Factorial Designs shows how the design can remove the largest imbalances before assignment, by how much exactly, and how one experiment can study several treatments at once.

References