Validity of identity-corrected random-permutation Monte Carlo p-values

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.