Exact permutation tests and random-permutation Monte Carlo

For each $g\in G$, $x\mapsto T(g\cdot x)$ is measurable by [F1]. For measurable real functions $f,h$, $\{f>h\}={\bigcup }_{q\in \mathbb{Q}}\{f>q\}\cap \{h<q\}$, so strict comparisons are measurable; equality sets are complements of the union of the two opposite strict comparisons. Finite sums show that both rank counts are measurable. The identity belongs to $G$, so the tied count is at least one and both p-value formulas take values in $[0,1]$. For the joint tie-rank formula, partition the data space by the finitely many possible integer pairs $(N_{>},N_{=})$; on each part it is an affine function of $U$, so it is jointly measurable.

Fix $\theta \in {\mathrm{\Theta }}_0$ and let $H$ be uniform on $G$, independent of $(X,U)$. For each fixed $h\in G$, invariance gives . Averaging over the finite law of $H$ therefore gives , so replacing $X$ by $H\cdot X$ does not change either p-value distribution.

Fix $x$ and form the finite list $a_g=T(g\cdot x)$ indexed by $g\in G$, retaining repeated values and repeated orbit points. At $H=h$, the transformed list at $h\cdot x$ is $T((gh)\cdot x)$ as $g$ ranges over $G$. Right multiplication $g\mapsto gh$ is a bijection of $G$, and the observed value $T(h\cdot x)$ is the entry indexed by $h$. Thus $p_{\mathrm{o}\mathrm{r}\mathrm{b}}(h\cdot x)$ is the inclusive upper rank of a uniform index in $(a_g{)}_{g\in G}$, while $p_{\mathrm{t}\mathrm{i}\mathrm{e}}(h\cdot x,U)$ is its independently tie-randomized rank.

By [F3], conditional on each fixed $x$, the first rank in step 2.1 is superuniform and the second is uniform. Averaging over $X$ preserves these bounds. The distributional equality in step 1.2 transfers them from $H\cdot X$ back to $X$, proving both displayed claims for this $\theta$. Since $\theta$ was arbitrary in ${\mathrm{\Theta }}_0$, the claims hold under every null law. No orbit quotient or freeness assumption is used.

By [F6], $p_{\mathrm{o}\mathrm{r}\mathrm{b}}$ is a valid p-value; [F7] gives its level-$\alpha$ cutoff test when an alternative is specified. For the tied test put $N_{>}(x)=\mathrm{\#}\{g:T(g\cdot x)>T(x)\}$ and $N_{=}(x)=\mathrm{\#}\{g:T(g\cdot x)=T(x)\}$. Its conditional rejection probability is ${\varphi }_{\alpha }(x)=\min \{1,\max \{0,(\mathrm{\mid }G\mathrm{\mid }\alpha -N_{>}(x))\mathrm{/}{N}_{=}(x)\}\}$, because $p_{\mathrm{t}\mathrm{i}\mathrm{e}}(x,U)\le \alpha$ exactly when $U\le (\mathrm{\mid }G\mathrm{\mid }\alpha -N_{>}(x))\mathrm{/}{N}_{=}(x)$, with the threshold clipped to $[0,1]$. The counts are measurable by step 1.1 and $N_{=}(x)\ge 1$, so [F8] makes ${\varphi }_{\alpha }$ a randomized test. Its null rejection probability equals ${\mathbb{P}}_{\theta }(p_{\mathrm{t}\mathrm{i}\mathrm{e}}(X,U)\le \alpha )=\alpha$ by step 3.1, and [F9] identifies its size as $\alpha$ when a nonempty disjoint alternative is specified. The argument uses only a finite uniform group index and the stated uniform tie randomizer; it uses no choice axiom.

For the selected design, $\mathcal{W}$ is finite. Every $A\in \mathcal{A}\otimes 2^{\mathcal{W}}$ has measurable sections $A_w=\{x:(x,w)\in A\}$. The displayed finite sum ${\tilde{P}}_{\theta }(A)={\sum }_w\nu (w)P_{\theta }(A_w)$ is nonnegative with total mass one. For disjoint $A_n$, each section $({\bigcup }_n{A}_n{)}_w$ is the disjoint union of $(A_n{)}_w$, so countable additivity of $P_{\theta }$ and the finite sum over $w$ give countable additivity of ${\tilde{P}}_{\theta }$. Thus [F11] makes this a joint statistical experiment. For measurable real functions $f,h$, $\{f\ge h\}$ is measurable because $\{f<h\}={\bigcup }_{q\in \mathbb{Q}}\{f<q\}\cap \{h>q\}$. Therefore each section $x\mapsto p_B(x,w)$ is measurable. Since $\mathcal{W}$ is finite, each sublevel set of $p_B$ is a finite union of measurable sections $A_w\times \{w\}$, so $p_B$ is measurable on the joint space. The distinguished identity contributes one tied-or-higher value, so $1\mathrm{/}(B+1)\le p_B\le 1$; at $B=0$, $W=\{e\}$ and $p_B=1$.

First use the with-replacement design. Represent $W$ by its $B+1$ generating positions to choose an independent uniform position $J$, and write $H$ for the entry at that position. The unordered multiset $W{H}^{-1}$ has the same law as $W$: if $J$ is the identity position it is unchanged; if $J=j>0$, right multiplication by $H^{-1}=g_j^{-1}$ makes position $j$ equal to $e$, makes the former identity position $g_j^{-1}$ uniform on $G$, and leaves the other $B-1$ draws conditionally independent uniform on $G$. Thus, after order is ignored, there is again one distinguished identity and $B$ IID uniform group elements.

Now use the without-replacement design and put $w=B+1$. The possible sets $W$ are the $w$-element subsets of $G$ containing $e$, all equally likely. Given $W$, choose $H$ uniformly from its $w$ elements. The map $(W,H)\mapsto (W{H}^{-1},H)$ is a bijection from pairs with $e\in W$, $\mathrm{\mid }W\mathrm{\mid }=w$, $H\in W$ onto pairs $(S,h)$ with $e\in S$, $\mathrm{\mid }S\mathrm{\mid }=w$, $h^{-1}\in S$: its inverse is $(S,h)\mapsto (Sh,h)$. Each fixed $S$ in the image has exactly $w$ possible $h$, so $W{H}^{-1}$ has the same uniform-subset law as $W$.

Since $X$ is independent of $(W,J)$ and each fixed $H\in G$ preserves its null law, conditioning on $(W,J)$ gives . By step 1.2, $W{H}^{-1}$ has the same design law as $W$, so $(H\cdot X,W{H}^{-1})$ and $(X,W)$ have the same joint law. Now fix $x$ and a labelled presentation of a with-replacement multiset $W$ before drawing $J$. The value $p_B(H\cdot x,W{H}^{-1})$ counts, with multiplicity, the entries $w\in W$ for which $T(w\cdot x)\ge T(H\cdot x)$, because $(w{H}^{-1})\cdot (H\cdot x)=w\cdot x$. As $J$ is uniform over the $B+1$ positions, this is the inclusive upper rank of a uniform position in the score multiset $(T(w\cdot x){)}_{w\in W}$. By [F5] this rank is superuniform conditional on $x,W$; averaging and using the joint-law equality transfers the bound to $p_B(X,W)$. This proves the with-replacement case, with ties and duplicate transformations counted by position.

The auxiliary pair $(W,H)$ is independent of $X$. For each fixed value of that pair, invariance gives ; step 1.3 gives $W{H}^{-1}$ the same design law as $W$. Hence $(H\cdot X,W{H}^{-1})$ and $(X,W)$ have the same joint law. To bound the transformed p-value, fix $x,W$ before drawing $H$. Conditional on $W$, $H$ is uniform over its $B+1$ elements, and $p_B(H\cdot x,W{H}^{-1})$ is the inclusive upper rank of that selected position in $(T(g\cdot x){)}_{g\in W}$, since $(g{H}^{-1})\cdot (H\cdot x)=g\cdot x$. By [F5] this rank is superuniform conditional on $x,W$; averaging and using the joint-law equality transfers the bound to $p_B(X,W)$. This is a separate uniform-subset proof.

By [F7], the superuniform bounds in steps 2.1 and 2.2 make $p_B$ a valid p-value on the joint experiment. For each observed $x$, the probability over the finite simulation design of rejection is ${\varphi }_{\alpha }(x)={\sum }_{w\in \mathcal{W}}\nu (w)\mathbf{1}\{p_B(x,w)\le \alpha \}$, a finite average of measurable indicators by step 1.1. By [F9], ${\varphi }_{\alpha }$ defines a binary randomized test on the original experiment. Its null rejection probability is $E_{\theta }[{\varphi }_{\alpha }(X)]={\tilde{P}}_{\theta }(p_B\le \alpha )\le \alpha$, the rejection probability of the joint-experiment threshold test covered by [F8]. Thus, when a nonempty disjoint alternative is specified, [F10] gives size at most $\alpha$ and hence level $\alpha$. When $B=\mathrm{\mid }G\mathrm{\mid }-1$ without replacement, the only possible set is $W=G$, so the formula agrees with [F6]. No choice axiom is used.