Randomization Tests: Invariance, Ties, and Validity

A randomization test compares the observed statistic with the values obtained by transformations that preserve its null distribution. The validity argument is finite-sample: average the rejection rule over each orbit of the transformation group. Ties require explicit randomization at the boundary. Large-sample power is a separate question, requiring a limit for the randomization distribution and its critical values.

A sampling model and a treatment-assignment model provide different sources of randomness. For example, suppose independent units have independent components \(U_i\sim \mathcal{N}(\mu,\sigma_0^2)\) and \(V_i\sim \mathcal{N}(\omega,\sigma^2)\) for controls or \(\mathcal{N}(\nu,\sigma^2)\) for treatment. Their sums have means \(\mu+\omega\) and \(\mu+\nu\), and common variance \(\sigma_0^2+\sigma^2\), so the usual two-sample normal theory applies.

If instead the unit components \(u_i\) are arbitrary fixed constants and the assignment is fixed, the density is

\[(2\pi\sigma^2)^{-N/2}\exp\left\{-\frac1{2\sigma^2}\left[\sum_{i=1}^m(x_i-u_i-\omega)^2+\sum_{j=1}^n(y_j-u_{m+j}-\nu)^2\right]\right\}.\]

Every alternative distribution can be represented under the null by absorbing \(\nu-\omega\) into the treated units' \(u_i\)'s. Thus every level-\(\alpha\) test has power at most \(\alpha\) at every alternative in this unrestricted fixed-assignment model. The constant test \(\phi\equiv\alpha\) attains the bound. This does not prove that every optimal critical function is pointwise constant.

1. The Randomization Model

In the finite-population model, fix the units' control responses \(u_1,\ldots,u_N\), select \(n\) units uniformly for treatment, and put the remaining \(m=N-n\) in control. There are \(\binom Nn\) assignments. Equivalently, randomly order all \(N\) units in \(N!\) ways and use the last \(n\) positions for treatment; each assignment then occurs \(m!n!\) times. Under the sharp null of no unit-level effect, the ordered response vector is a random permutation of \(u\). Under a constant additive effect \(\Delta\), its treated entries are increased by \(\Delta\). This discrete design model requires no Gaussian noise or superpopulation sampling.

A separate noisy version adds independent \(\mathcal{N}(0,\sigma^2)\) errors to each response. With strata of sizes \(N_i=m_i+n_i\), let \(G=\prod_i\mathfrak S_{N_i}\), \(N=\sum_iN_i\), and let \(a\in\{0,1\}^N\) mark the treatment positions. Averaging the conditional Gaussian density over the random ordering gives

\[p_{\sigma,u,\omega,\Delta}(z)=\frac1{|G|}\sum_{g\in G}\gamma_\sigma(z-gu-\omega\mathbf1-\Delta a),\qquad\gamma_\sigma(v)=(2\pi\sigma^2)^{-N/2}e^{-\|v\|^2/(2\sigma^2)}.\]

The coordinates are conditionally independent given the assignment; mixing over assignments need not preserve independence. Under \(\Delta=0\), put \(\zeta=u+\omega\mathbf1\) to obtain

\[p_{\sigma,\zeta}(z)=\frac1{|G|}\sum_{g\in G}\gamma_\sigma(z-g\zeta).\]

Repeated values are counted with their group multiplicities. The following characterization is for this noisy density family and concerns Lebesgue-almost-everywhere validity. For the noiseless fixed-population model, validity for every fixed response vector instead requires the corresponding orbit bound at every vector.

Proposition 1. Let \(\phi:\mathbb R^N\to[0,1]\) be measurable and \(0\le\alpha\le1\). The condition

\[\mathbb{E}_{\sigma,\zeta}\phi(Z)\le\alpha\quad\text{for every }\sigma>0,\ \zeta\in\mathbb R^N\tag{1}\]

is equivalent to

\[\psi(z):=\frac1{|G|}\sum_{g\in G}\phi(gz)\le\alpha\quad\text{for Lebesgue-almost every }z.\tag{2}\]

The sufficiency follows by averaging over the group. For necessity, a Gaussian with small variance can concentrate near a density point of any positive-measure set where the orbit average is too large.

Lemma 2. If \(A\subset\mathbb R^N\) is Lebesgue measurable with positive measure, then for every \(\eta>0\) there are \(\mu\in\mathbb R^N\) and \(\sigma>0\) such that \(\Pr\{\mu+\sigma W\in A\}>1-\eta\), where \(W\sim\mathcal{N}(0,I_N)\).

Proof. Take a Lebesgue density point \(\mu\) of \(A\), and choose \(R\) with \(\Pr\{\|W\|>R\}<\eta/2\). Inside the ball \(B(\mu,R\sigma)\), the Gaussian density is at most \((2\pi)^{-N/2}\sigma^{-N}\). Thus

\[\Pr\{\mu+\sigma W\in A^c\}\le\Pr\{\|W\|>R\}+(2\pi)^{-N/2}\sigma^{-N}|A^c\cap B(\mu,R\sigma)|.\tag{3}\]

\[|A^c\cap B(\mu,R\sigma)|=o(\sigma^N),\qquad\sigma\downarrow0.\tag{4}\]

The second term is below \(\eta/2\) for sufficiently small \(\sigma\). The density-point argument applies whether the total measure of \(A\) is finite or infinite. □

Proof of Proposition 1. The density is invariant under \(G\), so \(\mathbb{E}_{\sigma,\zeta}\phi=\mathbb{E}_{\sigma,\zeta}\psi\). This proves sufficiency of (2). In addition, invariance of \(\psi\) and the rotational invariance of the Gaussian kernel give

\[\mathbb{E}_{\sigma,\zeta}\phi(Z)=\int\psi(z)\gamma_\sigma(z-\zeta)\,dz.\]

For necessity, suppose (1) holds but (2) fails. There is \(\delta>0\) such that \(A=\{z:\psi(z)>\alpha+\delta\}\) has positive measure. Choose \(\eta<\delta/(\alpha+\delta)\). Lemma 2 supplies a Gaussian center \(\zeta\) and scale \(\sigma\) assigning probability greater than \(1-\eta\) to \(A\). Nonnegativity of \(\psi\) then yields

\[\mathbb{E}_{\sigma,\zeta}\phi(Z)>(\alpha+\delta)(1-\eta)>\alpha,\]

a contradiction. The argument concerns the orbit average \(\psi\), not the individual critical function \(\phi\). □

The Gaussian argument above is unchanged from the repaired version: its density-point proof applies to the orbit average and does not assume finite total measure or distinct responses. For positive additive effects, the treatment-sum permutation rule is coordinatewise nondecreasing in treated outcomes. Coupling the same random assignment and errors at effect zero and effect \(\Delta>0\) consequently gives power at least \(\alpha\). The size result alone does not imply strict power improvement for every design and every effect.

2. Randomization Tests

Remark 3. Randomization can refer to allocating treatments before observations are collected, or to recomputing a statistic under transformations during analysis. The latter is exact only when the transformations preserve the relevant null law. A permutation-calibrated two-sample t statistic can therefore have exact null size for a common nonnormal distribution, while ordinary Student-t critical values generally do not.

Assumption 4. Let \(G\) be a finite group of measurable bijections of a measurable sample space \((\mathcal X,\mathcal A)\). For every null distribution \(P\) and every \(g\in G\), assume \(gX\stackrel d=X\) under \(P\). Each null law itself must be invariant; merely mapping one null law into some other member of the null family is insufficient.

Example 5. For two independent i.i.d. samples from the same distribution, the pooled sample is i.i.d., so its joint law is invariant under every coordinate permutation. Equality of means alone does not ensure this exchangeability.

Let \(M=|G|\), and order the multiset \(T(gx)\) as \(T^{(1)}(x)\le\cdots\le T^{(M)}(x)\). For \(0<\alpha<1\), set \(k=M-\lfloor M\alpha\rfloor\), \(c(x)=T^{(k)}(x)\), and

\[M^+(x)=\#\{g:T(gx)>c(x)\},\quad M^0(x)=\#\{g:T(gx)=c(x)\},\quad a(x)=\frac{M\alpha-M^+(x)}{M^0(x)}.\]

Here \(M^+\le M-k=\lfloor M\alpha\rfloor\) and \(M^++M^0\ge M-k+1>M\alpha\). Thus \(M^0>0\) and \(0\le a\le1\). Define

\[\phi(x)=\mathbf1\{T(x)>c(x)\}+a(x)\mathbf1\{T(x)=c(x)\}.\]

For any \(h\in G\), right multiplication \(g\mapsto gh\) permutes the group, so \(T^{(j)}(hx)=T^{(j)}(x)\) for every order index \(j\). This is a group identity and requires no distributional assumption. The cutoff and tie counts are invariant as well. Hence, at every \(x\),

\[\sum_{g\in G}\phi(gx)=M^+(x)+a(x)M^0(x)=M\alpha.\]

Proposition 6. Under Assumption 4, the preceding randomized test has \(E_P\phi(X)=\alpha\) for every null \(P\).

Proof. Average the invariant null expectations: \(E_P\phi=M^{-1}\sum_gE_P\phi(gX)=E_P[M^{-1}\sum_g\phi(gX)]=\alpha\). This remains valid with ties, fixed points, and repeated statistic values, since the average is over group elements.

Remark 7. The orbit \(Gx=\{gx:g\in G\}\) contains the sample points obtainable from \(x\). Orbits partition the sample space. To make conditioning precise even when individual orbits have probability zero, use the invariant sigma-field

\[\mathcal I=\{A\in\mathcal A:g^{-1}A=A\text{ for every }g\in G\}.\]

The following conditional-expectation identity avoids interpreting conditioning on a zero-probability event directly.

Theorem 8. For every bounded measurable \(f\), under an invariant null law,

\[E_P[f(X)\mid\mathcal I]=\frac1M\sum_{g\in G}f(gX)\quad\text{almost surely}.\]

In particular, taking \(f(x)=\mathbf1\{T(x)\in B\}\) gives the conditional law of the statistic for every Borel set \(B\).

Proof. The average \(Af(x)=M^{-1}\sum_gf(gx)\) is measurable and invariant, so all its measurable level sets belong to \(\mathcal I\). The individual summands need not be invariant or \(\mathcal I\)-measurable. For \(E\in\mathcal I\), null invariance gives

\[\int_EAf\,dP=\frac1M\sum_g E_P[\mathbf1_E(X)f(gX)]=\frac1M\sum_gE_P[\mathbf1_E(gX)f(gX)]=\int_E f\,dP.\]

These are the defining properties of conditional expectation.

On a standard Borel sample space this average also defines a conditional probability kernel. Each distinct point in the orbit is attained by exactly \(|\operatorname{Stab}(x)|\) group elements: the maps sending \(x\) to a fixed orbit point form a coset of its stabilizer. Thus the kernel is uniform on distinct orbit points even when \(M>|Gx|\). Its pushforward under \(T\) assigns mass in proportion to the multiplicities of statistic values, not necessarily uniformly over distinct values.

Example 9. For i.i.d. pairs \((Y_i,Z_i)\), under independence the joint law is \(P_Y^{\otimes n}\otimes P_Z^{\otimes n}\). Permuting only the \(Z\)-coordinates leaves this product law unchanged, so \(((Y_i,Z_{\pi(i)}))_{i=1}^n\) is a valid transformation group. No densities or continuity are needed. In a bivariate normal model, zero correlation implies independence; in a general model, zero correlation alone does not establish the permutation null.

Remark 10. The conservative upper-tail p-value is

\[\widehat p=\frac1M\#\{g:T(gX)\ge T(X)\}.\]

To prove \(P(\widehat p\le s)\le s\), fix an orbit and list its statistic levels from largest to smallest, with multiplicities \(b_1,b_2,\ldots\). At level \(j\), the p-value is \((b_1+\cdots+b_j)/M\). The total multiplicity of all levels with p-value at most \(s\) is therefore at most \(Ms\). Conditional averaging from Theorem 8, followed by expectation, proves superuniformity.

For an exactly uniform randomized p-value, let \(V\) be an independent uniform variable and use

\[p_V=\frac{\#\{g:T(gX)>T(X)\}+V\#\{g:T(gX)=T(X)\}}M.\]

Conditional on level \(j\), this is uniform on the interval of length \(b_j/M\) between the preceding and current cumulative counts. That level itself has probability \(b_j/M\), so the mixture is uniform on \([0,1]\). Rejecting \(p_V\le\alpha\) gives exactly the cutoff randomization above.

For large-sample analysis let \(X^n\sim P_n\), with a finite group \(G_n\), statistic \(T_n\), and \(M_n=|G_n|\). No i.i.d. assumption is needed in the next theorem. Define

\[\widehat R_n(t)=\frac1{M_n}\sum_{g\in G_n}\mathbf1\{T_n(gX^n)\le t\},\qquad\widehat r_n(p)=\inf\{t:\widehat R_n(t)\ge p\}.\]

This is the inverse of the cdf, so the defining inequality contains \(\widehat R_n\), not its inverse. If \(G_n^*\) is an independent uniform group element, then \(E\widehat R_n(t)=P(T_n(G_n^*X^n)\le t)\). Under null invariance this equals \(P(T_n(X^n)\le t)\); without invariance it need not.

Theorem 11. Let \(G_n^*,G_n^{*\prime}\) be independent uniform group elements, independent of \(X^n\). The joint convergence

\[(T_n(G_n^*X^n),T_n(G_n^{*\prime}X^n))\Rightarrow(Z,Z'),\]

where \(Z,Z'\) are independent with common cdf \(R\), is equivalent to \(\widehat R_n(t)\to_P R(t)\) at every continuity point of \(R\). If \(r=R^{-1}(p)\) is finite and \(R\) is continuous and strictly increasing at that quantile, then \(\widehat r_n(p)\to_P r\).

Proof. Conditional on the data the two transformed statistics are independent, each with cdf \(\widehat R_n\). Thus

\[E\widehat R_n(t)=P(T_n(G_n^*X^n)\le t),\quad E\widehat R_n(t)^2=P(T_n(G_n^*X^n)\le t,T_n(G_n^{*\prime}X^n)\le t).\]

Joint convergence at continuity points gives limits \(R(t)\) and \(R(t)^2\), so the variance tends to zero and hence \(\widehat R_n(t)\to R(t)\) in \(L^2\).

Conversely, bounded convergence in probability implies convergence in \(L^1\), and \(0\le\widehat R_n\le1\). Therefore for continuity points \(s,t\),

\[P(T_n(G_n^*X^n)\le s,T_n(G_n^{*\prime}X^n)\le t)=E[\widehat R_n(s)\widehat R_n(t)]\longrightarrow R(s)R(t).\]

These rectangle probabilities identify the product limit distribution; marginal convergence supplies tightness, proving joint weak convergence.

For the quantile, choose continuity points \(a,b\) with \(r-\varepsilon<a<r<b<r+\varepsilon\) and \(R(a)<p<R(b)\). With probability tending to one, \(\widehat R_n(a)<p<\widehat R_n(b)\), which forces \(a<\widehat r_n(p)\le b\). This proves convergence and explains the strictness assumption at the quantile.

The transformed statistics are independent conditionally on the data, not generally unconditionally. The theorem asks that their shared-data dependence disappear in the limit; marginal normality alone would not establish this.

Theorem 12. Let the group consist of all \(2^n\) coordinate sign vectors. Suppose \(P\) is symmetric about zero and, under its i.i.d. product law,

\[T_n=\frac1{\sqrt n}\sum_i\psi_P(X_i)+o_P(1),\]

where \(\psi_P\) is odd and \(0<\sigma_P^2=E_P\psi_P^2<\infty\). Then \(\widehat R_n(t)\to_P\Phi(t/\sigma_P)\) for every \(t\), and \(\widehat r_n(1-\alpha)\to_P\sigma_Pz_{1-\alpha}\).

For a general \(P\), let \(\widetilde P\) be the distribution of \(\epsilon X\), with an independent uniform sign. Its cdf is

\[\widetilde F(t)=\frac{F(t)+1-F((-t)-)}2.\]

The left limit is necessary when \(P\) has atoms. If the same asymptotic linearity holds under \(\widetilde P\), with an odd influence function and positive finite variance \(\sigma_{\widetilde P}^2\), the randomization cdf and quantile under \(P\) converge to \(\Phi(t/\sigma_{\widetilde P})\) and \(\sigma_{\widetilde P}z_{1-\alpha}\).

Proof. Use independent sign vectors \((\epsilon_i)\) and \((\epsilon_i')\), independent of the data. Under symmetry, each transformed sample has law \(P^{\otimes n}\), so both transformed remainders tend to zero in probability; a union bound makes this joint. Oddness gives

\[(T_n(\epsilon X),T_n(\epsilon'X))=\frac1{\sqrt n}\sum_i(\epsilon_i\psi_P(X_i),\epsilon_i'\psi_P(X_i))+o_P(1).\]

The summand vectors are i.i.d., centered, and have covariance matrix \(\sigma_P^2 I_2\): their cross moment is \(E\epsilon_iE\epsilon_i' E\psi_P(X_i)^2=0\). The bivariate CLT therefore gives independent normal limits, and Theorem 11 applies.

For arbitrary \(P\), its symmetrization has the same absolute-value distribution. The full sign-randomization multiset depends only on the absolute sample, so the random cdf and its quantile have identical laws under \(P^{\otimes n}\) and \(\widetilde P^{\otimes n}\). Apply the first part to the latter. Oddness must be imposed in this part too. For example, \(T_n=n^{-1/2}\sum_i(X_i^2-E X_i^2)\) has an even influence function and is unchanged by sign flips. Its randomization cdf is a random point mass, and cannot converge to a nondegenerate deterministic normal cdf. This shows why asymptotic linearity without oddness is insufficient.

Example 13. Take \(T_n=\sqrt n\overline X_n=n^{-1/2}\sum_iX_i\). For any mean-zero distribution with finite positive variance \(\sigma^2\), symmetrization leaves \(EX^2=\sigma^2\) unchanged, and \(\psi(x)=x\) is odd. Theorem 12 gives a randomization critical value converging to \(\sigma z_{1-\alpha}\). The ordinary CLT gives \(T_n\Rightarrow \mathcal{N}(0,\sigma^2)\). Hence the rejection probability tends to \(\alpha\).

The possible boundary randomization makes no difference to this limit. For a deterministic limit \(c\) of the critical values,

\[P(T_n=\widehat r_n)\le P(|\widehat r_n-c|>\varepsilon)+P(|T_n-c|\le\varepsilon).\]

The first term vanishes, and the limsup of the second tends to zero as \(\varepsilon\downarrow0\) because the limiting normal law is continuous. Thus the test is exact under symmetry, and pointwise asymptotically level \(\alpha\) under the wider mean-zero finite-variance null. This is not a uniform assertion over all such distributions, nor does the mean statistic detect every asymmetric distribution.

Under \(X_i\sim \mathcal{N}(h/\sqrt n,\sigma^2)\), the observed statistic has exactly the law \(\mathcal{N}(h,\sigma^2)\). The likelihood ratio relative to the centered product model is

\[L_n=\exp\left\{\frac h{\sigma^2}T_n-\frac{h^2}{2\sigma^2}\right\}.\]

Under the null, \(E_0L_n^2=e^{h^2/\sigma^2}\), uniformly in \(n\). Cauchy–Schwarz therefore gives \(P_h(A_n)\le e^{h^2/(2\sigma^2)}P_0(A_n)^{1/2}\), explicitly proving contiguity and transfer of the critical-value limit. The limiting power is

\[1-\Phi\left(z_{1-\alpha}-\frac h\sigma\right).\]

This matches the ordinary t-test under the same normal local model, giving efficacy \(1/\sigma\) and Pitman relative efficiency one in that comparison.