置换检验

置换检验（permutation test）用零假设下可以互换的观测标签，构造检验统计量的参照分布。它的可靠性来自实验设计或概率模型所保证的交换性，并不来自“把数据打乱很多次”这个动作本身。

设两组独立教学读数为 $x=(1,2)$、$y=(4,5)$，考察均值差 $T=\bar{x}-\bar{y}=-3$。如果零假设规定两组来自同一分布，而且所有四次观测独立同分布，那么给定合并后的四个观测，把其中任意两个编号分给第一组的六种分法等可能。若原来是从四个单位中等概率抽取两个接受处理的完全随机试验，这一分配分布也可用于检验“每个单位的处理效应都为零”的尖锐零假设。两种依据不同，不能省略。

六种分配与精确尾概率

把第一组写在左边，按原始编号选择而不重复计组内次序，得到：

第一组	第二组	均值差
1，2	4，5	−3
1，4	2，5	−1
1，5	2，4	0
2，4	1，5	0
2，5	1，4	1
4，5	1，2	3

本文用 $|T|$ 衡量双侧极端程度，并把与观察值相等的情况计入尾部。因此本次精确值为 $$p_{\mathrm{a}\mathrm{b}\mathrm{s}}=\frac{\mathrm{\#}\{|T_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{m}}|\ge 3\}}{6}=\frac{2}{6}=\frac{1}{3}.$$ 若事先提出的单侧备择为第一组较小，则尾概率为 $Pr(T_{\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{m}}\le -3)=1/6$。双侧检验需要先说明“更极端”的规则；绝对值尾概率与“两倍较小单侧概率”并非对所有统计量和所有非对称参照分布都相同。SciPy文档也明确列出软件所用的双侧约定。

相同的数值统计量可以由不同分配产生。零的概率是三分之一；绝对值至少为三的两个端点合计三分之一。

条件检验水平的证明

设零假设下，给定一个可置换的轨道后共有 $N$ 个等可能编号分配。对每个分配 $a$，取事先指定的极端程度 $E(a)$，定义 $$p(a)=\frac{\mathrm{\#}\{b:E(b)\ge E(a)\}}{N}.$$ 将这些分配按 $E$ 从大到小排列。没有并列值时，第 $j$ 项的值就是 $j/N$；有并列值时，同一组均取该并列块的末尾名次除以 $N$。所以满足 $p(a)\le \alpha$ 的项不超过 $\lfloor N\alpha \rfloor$ 个，从而 $$\underset{0}{Pr}\{p\le \alpha \mid \text{轨道}\}\le \alpha .$$ 再对轨道取平均，得到无条件的一类错误率也至多为 $\alpha$。这就是有限样本的有效性证明；离散取值与并列往往使检验偏保守。上述结论的前提是轨道内确实等可能，不能把分配数很多替代这个条件。

保留编号的枚举程序

下面程序接受可由 Fraction 转换的有限有理数，例如整数、分数字符串或十进制字符串；用精确分数比较，避免接近尾界时的浮点并列误判。相等的观测仍有不同编号，因而每个编号分配都被保留。

Python 3

from fractions import Fraction
from itertools import combinations
from math import comb

def exact_mean_permutation(x, y):
    x = tuple(Fraction(v) for v in x)
    y = tuple(Fraction(v) for v in y)
    if not x or not y:
        raise ValueError("both groups must be nonempty")
    pooled = x + y
    m, n = len(x), len(y)
    total = sum(pooled, Fraction(0))
    observed = sum(x, Fraction(0))/m - sum(y, Fraction(0))/n
    extreme = 0
    for indices in combinations(range(m+n), m):
        left = sum((pooled[i] for i in indices), Fraction(0))
        statistic = left/m - (total-left)/n
        extreme += abs(statistic) >= abs(observed)
    return observed, Fraction(extreme, comb(m+n, m))

print(exact_mean_permutation([1, 2], [4, 5]))
# (Fraction(-3, 1), Fraction(1, 3))

共有 $(\genfrac{}{}{0ex}{}{m+n}{m})$ 个分配。按单位有理数运算计时，每个分配求和至多用 $O(m+n)$ 步，故时间上界为 $O((\genfrac{}{}{0ex}{}{m+n}{m})(m+n))$；不保存整个参照分布，额外存储为 $O(m+n)$。若输入分子的位数增长，精确整数运算还要计入位复杂度。大样本可随机抽取分配，但应使用适当的蒙特卡罗检验规则；常见的含观察分配的修正为 $(b+1)/(B+1)$，不能把零次超出直接写成概率零。

配对设计的变式

现在同样四个数来自两对：$(1,4)$ 与 $(2,5)$。若设计允许每对内独立交换处理标签，或零假设下每对差值具有相应的联合符号对称性，那么可以交换的是对内标签。两项原始差均为 $-3$，四种符号给出平均差 $-3,0,0,3$，绝对值双侧概率为 $2/4=1/2$。它不等于把四个数任意分成两组所得的 $1/3$，因为实验允许的随机化不同。

“两个总体均值相同”本身不能推出独立样本标签可任意交换；例如均值相同而方差不同的两个分布，一般不具有这个交换性。学生化统计量在附加条件下可得到某些渐近结果，但那是另一项需要证明的结论。置换检验的 $p$ 值也不是零假设为真的后验概率。