[proofplan] The proof avoids quotienting by orbits by introducing an independent uniformly distributed group element $H$. The invariance hypothesis implies that $HX$ has the same distribution as $X$, so it is enough to prove the p-value bound after randomly reselecting the observed representative from the finite group orbit. For a fixed realised sample point $x$, the values $\{T(gx):g\in G\}$ form a finite multiset, and the event $p_G(Hx)\le\alpha$ counts only those indices whose weak descending rank is at most an $\alpha$ fraction of the group. Random tie-breaking replaces weak ranks by strict ranks, which are exactly uniform because the observed index is uniform over $G$. [/proofplan]

[step:Randomise the observed representative without changing its law] Let $m:=|G|$. Let $(\Omega,\mathcal F,\mathbb P)$ be the probability space on which $X$ is defined. Let $H:(\Omega',\mathcal F',\mathbb P')\to G$ be a [random variable](/page/Random%20Variable) with the uniform distribution on the finite set $G$, so that $\mathbb P'(H=h)=1/m$ for every $h\in G$. Work on the product probability space $(\Omega\times\Omega',\mathcal F\otimes\mathcal F',\mathbb P\otimes\mathbb P')$, and define $X(\omega,\omega'):=X(\omega)$ and $H(\omega,\omega'):=H(\omega')$. Then $H$ and $X$ are independent on this product space. We claim that $HX$ and $X$ have the same distribution. Indeed, for every measurable set $A\subset\mathcal X$, independence of $H$ and $X$ gives \begin{align*} \mathbb P(HX\in A)=\frac{1}{m}\sum_{h\in G}\mathbb P(hX\in A). \end{align*} By the assumed distributional invariance, $\mathbb P(hX\in A)=\mathbb P(X\in A)$ for every $h\in G$. Hence \begin{align*} \mathbb P(HX\in A)=\frac{1}{m}\sum_{h\in G}\mathbb P(X\in A)=\mathbb P(X\in A). \end{align*} Therefore $HX$ and $X$ are identically distributed. Since $p_G:\mathcal X\to[0,1]$ is measurable as a finite sum of measurable indicator functions, it follows that \begin{align*} \mathbb P(p_G(X)\le\alpha)=\mathbb P(p_G(HX)\le\alpha). \end{align*} [/step]

[step:Compute the conditional permutation p-values on a fixed group orbit]Fix $x\in\mathcal X$. For each $a\in G$, define the statistic value \begin{align*} S_a:=T(ax)\in\mathbb R. \end{align*} For each $h\in G$, using the group property that the map $G\to G$, $g\mapsto gh$, is a bijection, we have \begin{align*} p_G(hx)=\frac{1}{m}\sum_{g\in G}\mathbb{1}_{\{T(ghx)\ge T(hx)\}}=\frac{1}{m}\sum_{a\in G}\mathbb{1}_{\{T(ax)\ge T(hx)\}}=\frac{1}{m}\#\{a\in G:S_a\ge S_h\}. \end{align*}[/step]

[guided]We now freeze the sample point $x$ and study only the finite list of numbers obtained from the [group action](/page/Group%20Action). For every group element $a\in G$, define \begin{align*} S_a:=T(ax)\in\mathbb R. \end{align*} This gives a finite multiset indexed by $G$; different group elements may give the same transformed point or the same statistic value, and the argument allows this. Now fix $h\in G$. The p-value at the transformed point $hx$ is \begin{align*} p_G(hx) &=\frac{1}{m}\sum_{g\in G}\mathbb{1}_{\{T(ghx)\ge T(hx)\}}. \end{align*} The key algebraic fact is that right multiplication by $h$ permutes the finite group $G$. Thus the map $G\to G$ defined by $g\mapsto gh$ is a bijection. Therefore, when $g$ ranges over $G$, the element $a:=gh$ also ranges over every element of $G$ exactly once. Reindexing the finite sum by this bijection gives \begin{align*} p_G(hx)=\frac{1}{m}\sum_{a\in G}\mathbb{1}_{\{T(ax)\ge T(hx)\}}=\frac{1}{m}\#\{a\in G:S_a\ge S_h\}. \end{align*} So $p_G(hx)$ is exactly the weak descending rank fraction of $S_h$ inside the finite multiset $(S_a)_{a\in G}$.[/guided]

[step:Count the indices whose weak rank fraction is at most $\alpha$] List the distinct values appearing among $(S_a)_{a\in G}$ in strictly decreasing order: \begin{align*} v_1>v_2>\cdots>v_r. \end{align*} For each $j\in\{1,\dots,r\}$, define the tie block \begin{align*} B_j:=\{a\in G:S_a=v_j\}, \end{align*} and let \begin{align*} N_j:=\#(B_1\cup\cdots\cup B_j). \end{align*} If $h\in B_j$, then \begin{align*} p_G(hx)=\frac{N_j}{m}. \end{align*} Hence \begin{align*} \#\{h\in G:p_G(hx)\le\alpha\}=\max\{N_j:1\le j\le r,\ N_j\le \alpha m\}, \end{align*} with the maximum interpreted as $0$ if the set is empty. Therefore \begin{align*} \frac{1}{m}\#\{h\in G:p_G(hx)\le\alpha\}\le \alpha. \end{align*} Since this bound holds for every fixed $x\in\mathcal X$, conditioning on $X=x$ in the auxiliary experiment with uniform $H$ gives \begin{align*} \mathbb P(p_G(HX)\le\alpha\mid X)\le\alpha. \end{align*} Taking expectations yields \begin{align*} \mathbb P(p_G(HX)\le\alpha)\le\alpha. \end{align*} Combining this with the equality in law from the first step gives \begin{align*} \mathbb P(p_G(X)\le\alpha)\le\alpha. \end{align*} [/step]

[step:Break ties uniformly to obtain exact finite-grid uniformity] Fix again $x\in\mathcal X$. Introduce, independently of $H$ and $X$, a random ordering inside each tie block $B_j$, chosen uniformly among all permutations of that block. This produces a strict descending order of the group elements: all elements in $B_1$ precede all elements in $B_2$, and so on, with uniform random order inside each $B_j$. Let $R_x:G\to\{1,\dots,m\}$ denote the strict rank map produced by this random ordering, where rank $1$ is the largest statistic value after tie-breaking. Define the randomised permutation p-value associated with this fixed orbit ordering on the indexed orbit by assigning, for each $h\in G$, \begin{align*} p_{G,\mathrm{rand},x}(hx):=\frac{R_x(h)}{m}. \end{align*} If two elements $h_1,h_2\in G$ satisfy $h_1x=h_2x$, this definition is understood on the indexed orbit: the index $h$ is the observed representative selected uniformly from $G$, and the statistic multiset is indexed by $G$. For every realised strict ordering, the map $R_x:G\to\{1,\dots,m\}$ is a bijection. Since $H$ is uniform on $G$, for each $k\in\{1,\dots,m\}$, \begin{align*} \mathbb P(p_{G,\mathrm{rand},x}(Hx)=k/m\mid X=x,\ R_x)=\mathbb P(R_x(H)=k\mid X=x,\ R_x)=\frac{1}{m}. \end{align*} Thus, conditionally on $X=x$ and hence conditionally on the realised statistic multiset, $p_{G,\mathrm{rand},x}(Hx)$ is uniform on $\{1/m,2/m,\dots,1\}$. It remains to state the sample-level randomisation without referring to the auxiliary base point $x$. For a generic observed point $y\in\mathcal X$, form the indexed statistic multiset $(T(gy))_{g\in G}$, choose independently a uniform random ordering inside each equal-value tie block, and let $R_y:G\to\{1,\dots,m\}$ be the resulting strict descending rank map. Let $\mathcal O$ denote the finite auxiliary ordering space, and let $e_G\in G$ denote the identity element. Define the sample-level randomised p-value by \begin{align*} p_{G,\mathrm{rand}}(y,\omega):=\frac{R_y(e_G;\omega)}{m} \end{align*} for $(y,\omega)\in\mathcal X\times\mathcal O$. This is the randomised p-value computed from the observed sample $y$ itself. The transfer from $HX$ back to $X$ preserves this construction. For each $h\in G$, define the right-translation map $\rho_h:G\to G$ by $\rho_h(g)=gh$. This map is a bijection, and the indexed statistic vector at $hX$ satisfies \begin{align*} (T(g h X))_{g\in G}=(T(aX))_{a\in G}\circ \rho_h. \end{align*} Thus replacing $X$ by $hX$ only relabels the same finite indexed multiset by the bijection $a=gh$. The tie blocks are carried bijectively to tie blocks with the same sizes, and the rule that chooses a uniform random ordering inside each tie block is equivariant under this relabelling: pushing a uniform ordering forward by $\rho_h$ again gives the uniform ordering on the relabelled tie block. Consequently, conditional on $H=h$ and $X$, the randomised rank of the selected index for the orbit of $hX$ has the same law as the randomised rank of $h$ in the orbit of $X$. Since $H$ is uniform on $G$, the selected index $h$ is uniform before the tie-breaking is sampled. Since $HX\overset{d}=X$ and the auxiliary ordering is sampled independently from the tie-block kernel determined by the indexed statistic multiset, the joint law of the observed sample, its indexed statistic vector, and its equivariant tie-breaking ordering is unchanged when passing from $HX$ back to $X$. Therefore the finite-grid uniformity proved for $p_{G,\mathrm{rand},x}(Hx)$ holds for $p_{G,\mathrm{rand}}(X,\omega)$ under the null invariance assumption. This proves the asserted exact randomised validity. [/step]