主要先修：16.5 抽样设计、偏差与随机化实验、18.1 检验、功效与p值。
从抽样设计与检验水平进入交换性排名；这条精确路线无需经验过程或贝叶斯推断。接22.2的有限样本秩方法及22.6的保形覆盖。 查看全书依赖图与分支路线。
22.1.1 置换依据来自哪里
置换检验重新安排标签、顺序或符号，比较原统计量在这些变换中的位置。它的有限样本保证来自零假设下的分布不变性，不依赖正态近似。依据有两种：随机实验中，已知的处理分配机制使某些标签排列等概率；观察性两样本中，零假设下的共同分布与独立抽样使合并数据可交换。相同的重排算法可以对应不同的科学假设。
本节接续随机实验与潜在结局及检验与第一类错误。在前一种模型里，单位的潜在结局可以完全固定；在后一种模型里，随机性来自总体抽样。不能仅因计算上能打乱数据，就断言任意打乱都保留零假设分布。
22.1.2 有限群与条件秩 p 值
设 \(G\) 为数据空间上的有限可测变换群：含恒等变换 \(e\)，对复合与取逆封闭。令 \(m=|G|\)，零假设要求对每个 \(g\in G\)，都有 \(gX\overset d=X\)。预先指定可测统计量 \(T\)，其值越大表示越不符合零假设。轨道 \(GX=\{gX:g\in G\}\) 是所有可达的数据状态。
包括原数据在内，枚举群的全部元素，定义
计数单位是群元素；多个变换得到相同数据或相同统计量时，仍按各自次数计入。也可合并成带正确权重的表格，不能只对不同统计量值做等权平均。
在上述不变性下，令 \(\mathcal I\) 为数据中所有群不变事件构成的 \(\sigma\) 代数，即轨道信息，则对任意 \(\alpha\in[0,1]\)，
这叫超均匀性，意味着按 \(p_G\le\alpha\) 拒绝可控制第一类错误。“精确检验”在此表示无需渐近近似的有限样本控制，并不保证每个水平都恰好达到等号。
证明。固定数据 \(x\)，列出 \(v_h=T(hx)\)，\(h\in G\)。由于 \(gh\) 遍历 \(G\)，\(p_G(hx)=r_h/m\)，其中 \(r_h=\#\{g:v_g\ge v_h\}\)。将这 \(m\) 个数从大到小排列，第 \(j\) 项的上尾秩至少为 \(j\)；平局时秩是整个同值组的末位。因此能满足 \(r_h/m\le\alpha\) 的项至多有 \(\lfloor m\alpha\rfloor\) 个：
对任意不变事件 \(C\in\mathcal I\)，变换数据不会改变其指示函数。利用 \(hX\overset d=X\)，可得
这对所有 \(C\in\mathcal I\) 成立，故条件拒绝概率不超过 \(\alpha\)，再取期望得到无条件结论。相同平均论证还给 \(E[f(X)\mid\mathcal I]=m^{-1}\sum_h f(hX)\)，其中 \(f\) 有界可测；每个轨道点对应相同数量的群元素，说明给定轨道后原数据在轨道点中均匀分布。
22.1.3 平局、随机化与双侧规则
使用“至少同样大”的计数会把整个平局组纳入尾部，因此通常保守。如果希望在任意水平都达到等号，可引入与数据独立的 \(U\sim\operatorname{Uniform}(0,1)\)，定义随机化 p 值：
给定轨道，一个平局组若占 \(b/m\) 的概率质量，前面更大值的质量为 \(a/m\)，就把它均匀铺到长度 \(b/m\) 的区间 \([a/m,(a+b)/m]\)。各组区间不重叠并覆盖单位区间，组选择概率等于区间长度，所以 \(p_{\mathrm{rand}}\mid\mathcal I\) 精确均匀。无需额外随机化时，保留式(22.1-1)即可。
双侧检验应预先把极端程度定义为 \(T=|D|\)、平方或其他明确函数，再计算该统计量的上尾。双侧值不必等于某个单侧值的简单翻倍；不能看见原数据的正负后，临时挑选更小的单侧尾部。统计量、变量选择与数据处理规则均须对原数据和变换数据一致应用。
22.1.4 随机实验：检验尖锐零假设
固定 \(N\) 个单位，潜在结局为 \(Y_i(1),Y_i(0)\)，处理有明确版本、单位间无干扰。完全随机分配恰有 \(n_1\) 个单位接受处理，\(0<n_1<N\)。观察结局 \(Y_i^{\mathrm{obs}}=Y_i(Z_i)\)，分配向量满足
尖锐零假设可以由已观测结局补全每个未观测结局，所以任何允许分配下的统计量都能算出。条件于这些固定结局，处理标签按设计等概率；这不要求单位是 iid 总体样本。仅有平均处理效应为零不能补全缺失结局，不足以赋予同一个检验上述精确保证。分层设计必须在允许的层内重排；非均匀分配必须按实际设计概率构造分布。
观察到六个结局为 \((1,2,3,4,5,6)\)，处理组为后三个单位。预先使用 \(T=|D|\)，其中 \(D\) 是处理组均值减对照组均值，观察值为三。尖锐零假设下结局固定，\(\binom63=20\) 种分配等概率。若处理组结局之和为 \(s\)，则 \(D=(2s-21)/3\)。
处理组和从六到十五的分配次数依次为 \(1,1,2,3,3,3,3,2,1,1\)，总和二十。只有处理组 \(\{1,2,3\}\) 与 \(\{4,5,6\}\) 给出 \(|D|\ge3\)，故双侧 p 值为 \(2/20=0.1\)。若事先指定处理增加响应的单侧检验，p 值为 \(1/20=0.05\)；不能看过结果再换检验方向。
22.1.5 两样本标签置换检验的是共同分布
设两组互相独立，组内 \(X_1,\ldots,X_{n_1}\) iid 来自 \(F\)，\(Y_1,\ldots,Y_{n_0}\) iid 来自 \(H\)，样本量固定且均为正。零假设 \(F=H\) 下，合并后的 \(N=n_1+n_0\) 个观测 iid 来自共同分布，因而联合分布在所有坐标置换下不变。这就是交换性；分布可离散，也不必正态。
取 \(T=|\bar X-\bar Y|\)，每个大小为 \(n_1\) 的标签分配在 \(N!\) 个排列中重复 \(n_1!n_0!\) 次。因此可以枚举 \(\binom N{n_1}\) 个等概率分配来计算 p 值，仍须保留不同分配产生的平局。使用均值差只是统计量的选择，并不把零假设缩成均值相等。
两组均值相同、方差不同，一般不满足共同分布和标签交换性；习题22.1-3给出第一类错误达到一的反例。学生化统计量在额外条件下可有渐近有效性，但不能仅凭学生化就宣称任意异分布下的有限样本精确性。时间序列、重复测量也不能自动当作独立坐标打乱。观察性分组没有已知随机分配机制时，标签置换本身不建立因果识别。
22.1.6 配对数据：何时可以翻转符号
对 \(r\) 个配对差值 \(D=(D_1,\ldots,D_r)\)，符号翻转群为
所需零假设是联合分布在每个这种翻转下不变。一个充分条件是差值互相独立，且每个分布关于零对称；它们不必同分布。仅有 \(E[D_i]=0\) 不够：取值负一的概率为 \(0.9\)、正九的概率为 \(0.1\) 时，均值为零，正负符号却不等概率。零差值会让多个群元素得到相同数据，仍应保留其计数。
另一依据是随机配对实验：每对内部独立、公平地随机分配处理与对照，在无干扰的尖锐零假设下，交换每对的标签产生等概率符号翻转。此时依据来自实验设计，不要求总体配对差值先满足对称分布假设。
观察差值 \((1,2,3)\)，事先采用 \(T=|D_1+D_2+D_3|\)，并假设独立、各差值关于零对称。给定绝对值，一共八种等概率符号组合。差值和按大小排列为 \((-6,-4,-2,0,0,2,4,6)\)，原统计量为六。
至少同样极端的组合是全负与全正，所以双侧 p 值为 \(2/8=1/4\)。若事先检验正方向并使用未取绝对值的和，p 值为 \(1/8\)。两个零来自不同的符号组合，不能把八个组合去重后视作七个等概率取值。即使只有三个差值，计算及错误概率控制都是有限样本的。
22.1.7 Monte Carlo 置换：原样本与加一构造
全枚举不可行时，先固定正整数 \(B\)。从整个有限群 \(G\) 独立、均匀、有放回抽取 \(g_1,\ldots,g_B\)，抽样随机性与数据独立；置 \(g_0=e\)，原样本另作为第零项加入。重复变换、重复统计量以及再次抽到恒等变换均保留。定义
在定理22.1-1的不变性及上述抽样方案下，对任何 \(\alpha\in[0,1]\)，\(P_{H_0}(p_{\mathrm{MC}}\le\alpha)\le\alpha\)，条件于轨道也成立。统计保证同时考虑数据及抽样随机性；p 值始终不小于 \(1/(B+1)\)。
证明。记统计量向量为 \(V=(T(X),T(g_1X),\ldots,T(g_BX))\)。引入与一切独立的均匀群元素 \(h\)。由不变性，
映射 \((h,g_1,\ldots,g_B)\mapsto(h,g_1h,\ldots,g_Bh)\) 是 \(G^{B+1}\) 的双射，所以右边使用的 \(B+1\) 个群元素独立均匀。给定 \(X\)，右边各分量可交换，故原向量也可交换；同一论证可在不变信息条件下进行。对任何固定的 \(B+1\) 个数，以上尾秩除以 \(B+1\) 后，至多 \(\lfloor\alpha(B+1)\rfloor\) 个位置不超过 \(\alpha\)。可交换性使第零项被拒绝的概率等于所有位置拒绝比例的期望，因而不超过 \(\alpha\)。第零项的秩包含它自己，正好产生分子中的一。
给定已观测数据，\(K\sim\operatorname{Binomial}(B,p_G(X))\)。因此 \(K/B\) 是全枚举尾概率的无偏估计，却不自动是有效 p 值：它可能以正概率等于零。加一值则是上面证明的检验 p 值，其条件均值为 \([1+Bp_G(X)]/(B+1)\)，不是全枚举值的精确数值。
对例22.1-2的数据，设按上述方案抽七次，得到符号组合 \((---),(--+),(-+-),(-++),(+--),(++-),(+++)\)。这是一组可能的抽样结果，差值和依次为 \((-6,0,-2,4,-4,0,6)\)。其中两次的绝对值至少为原值六，所以 \(K=2\)，\(p_{\mathrm{MC}}=3/8\)。
最后一次再次抽到恒等变换，应作为随机抽样项计数；原样本仍另贡献一项。该结果不同于全枚举的 \(1/4\)，因为抽样结果有随机波动。图22.1-2用这组给定结果说明原样本与重复恒等变换的计数方式。
本文证明的是固定 \(B\)、均匀独立有放回抽样方案。只偏选部分变换、抽样后删除重复项或根据中途的 p 值决定停止，都需要另作有效性论证。若目标水平为 \(0.001\)，至少要有 \(B=999\) 才能让最小 p 值达到该水平；这只是分辨率要求，不保证 Monte Carlo 波动已经很小。
22.1.8 习题与解答
习题22.1-1 平局的秩与随机化
一个四点轨道条件均匀，统计量值为 \((5,5,3,1)\)。求各点的非随机化 p 值及水平 \(1/2\) 的拒绝概率；若观察值为五、辅助均匀变量实现值为 \(0.2\)，求随机化 p 值。
两个五各有两项至少同样大，上尾秩均为二；三的上尾秩为三，一的上尾秩为四。因此 p 值为 \((1/2,1/2,3/4,1)\)，条件拒绝概率为 \(2/4=1/2\)。观察到五时，没有严格更大的值，平局数为二，随机化值为 \(0.2\times2/4=0.1\)。该实现值可低于非随机化值，但精确校准来自独立的均匀随机化；不能为获得小 p 值人为选择这个辅助数。
习题22.1-2 抽样次数与分辨率
独立均匀有放回抽取 99 次变换，四次至少同样极端。求有效加一 p 值，并解释零次命中时应报告什么。若要求最小可能值不超过 \(10^{-3}\)，最少抽多少次？
分子包含原数据的一项及四次命中，故 p 值为 \(5/100=0.05\)，不能用 \(4/99\) 代替后声称仍有相同的有限样本检验保证。零次命中给 \(1/100=0.01\)，不是零。要求 \(1/(B+1)\le10^{-3}\)，解得 \(B\ge999\)。抽样次数决定可报告的最小值，真实全枚举 p 值还可能更小；若需估计该尾概率的精度，应另分析条件二项抽样的不确定性。
习题22.1-3 相同均值不足以交换标签
一组只有一个观测 \(X\)，它等概率取正一与负一；另一组有 19 个独立、恒为零的观测。两组独立、总体均值都为零。使用绝对均值差，均匀重分配一个观测到第一组，求置换 p 值及水平 \(0.05\) 的真实拒绝概率。
原第一组含唯一非零值，所以绝对均值差为一。二十个标签分配中，仅把该非零值放回第一组时得到一；其他十九种中第一组为零，第二组均值为正或负 \(1/19\)，绝对差为 \(1/19\)。因此 p 值恒为 \(1/20=0.05\)，按“不超过水平”拒绝时，真实拒绝概率为一。均值零的假设仍真，但两组分布不同，不能交换标签。这个反例否定的是将共同分布检验的精确保证套到仅有均值相等的假设。
习题22.1-4 看过数据再挑选方向
六个独立差值各等概率取正一、负一。分析者先看差值和的符号，再选相应方向的单侧符号翻转 p 值，按水平 \(1/64\) 拒绝。求真实第一类错误，并与预先指定绝对和的检验比较。
全部正与全部负各有概率 \(1/64\)。事后挑选方向时，这两个结果都得到单侧 p 值 \(1/64\)，其他结果的所选尾部至少含更多符号组合。因此总拒绝概率为 \(2/64=1/32\)，是标称水平的两倍。预先指定绝对和，则这两个极端结果共同构成尾部，p 值为 \(2/64\)，在水平 \(1/64\) 都不拒绝。选择方向本身也使用了数据，必须计入统计规则，不能把两个单侧机会当成一个。
关键术语
- 交换性：联合分布在指定的坐标重排下保持不变，比均值相同更强。
- 变换群：包含恒等变换并对复合与取逆封闭的变换集合。
- 轨道：从一份数据经群作用可到达的全部数据状态。
- 置换 p 值：在允许变换下至少同样极端的统计量所占的概率质量。
- 超均匀性：零假设下 p 值不超过任意水平的概率至多为该水平。
- 尖锐零假设：每个单位的全部比较处理下潜在结局相同，可补全缺失结局。
- 随机化分配：按已知概率机制给单位分配处理，提供设计上的随机性。
- 符号翻转：改变配对差值的正负，需要相应联合对称性或随机配对设计。
- 平局：多个变换产生同值统计量，须保留概率权重或使用独立随机化。
- Monte Carlo 置换：随机抽取允许变换，并将原数据纳入秩计算的检验构造。
参考文献
- Jesse Hemerik、Jelle Goeman，Exact testing with random permutations，TEST 27，811–825，2018，§2–3：有限群、条件秩、随机置换及原样本的作用。
- Philip B. Stark，Berkeley Statistics 240，Notes, Chapter 3: The randomization model for comparing two treatments：固定单位、已知随机分配，以及强弱零假设的区别。
- Siva Balakrishnan，CMU 36-700，Lecture 28: Causal Inference，2016，§28.2–28.7：潜在结局、完全随机分配与尖锐零假设；本节随机抽样 p 值的严格校准另见第一项。