Conditional and Finite-Group Exact Inference

Let ${\pi }_S:S\times \mathbb{R}\to S$ be the first-coordinate projection and define $\tilde{K}((s,t),C):=K(s,C)$. The projection is measurable because ${\pi }_S^{-1}(A)=A\times \mathbb{R}$ for every $A\in \mathrm{\Sigma }$; hence [F1] and [F2] show that $\tilde{K}$ is a probability kernel from $(S\times \mathbb{R},\mathrm{\Sigma }\otimes \mathcal{B}(\mathbb{R}))$ to $\mathbb{R}$.

The relation $\{(t,y):y>t\}$ is ${\bigcup }_{q\in \mathbb{Q}}(-\mathrm{\infty },q)\times (q,\mathrm{\infty })$: density in [F3] supplies a rational strictly between $t$ and $y$, and every point in a displayed rectangle has $t<y$. The relation $\{(t,y):y<t\}$ has the analogous representation ${\bigcup }_{q\in \mathbb{Q}}(q,\mathrm{\infty })\times (-\mathrm{\infty },q)$. These are countable unions of Borel rectangles by [F3] and [F4], and the equality relation is their joint complement. Therefore all three relations belong to $\mathcal{B}(\mathbb{R})\otimes \mathcal{B}(\mathbb{R})$. The coordinate map $(s,t,y)\mapsto (t,y)$ is measurable because inverse images of generating rectangles are $S\times B\times C$; taking inverse images now proves the two relation indicators in the domain of $\tilde{K}$ are product-measurable.

Apply [F5] to $\tilde{K}$ and the two indicator functions of the relation sets in step 1.2. Their section integrals are $\int 1_{\{y>t\}}K(s,dy)=K(s,(t,\mathrm{\infty }))=a(s,t)$ and $\int 1_{\{y=t\}}K(s,dy)=K(s,\{t\})=b(s,t)$, so both maps are product-measurable.

For $n=2,3$, fix a bijection $e:\mathbb{Q}\to \mathbb{N}$ supplied by [F3]. Each rational open box is encoded by a finite tuple of natural numbers, and iterating the injection $(a,b)\mapsto 2^a(2b+1)$ shows there are only countably many such boxes. Density of $\mathbb{Q}$ then shows they form a base of ${\mathbb{R}}^n$: each point of an open set lies in such a box contained in that set. Thus each open set is a countable union of rectangles in the finite product sigma-algebra, giving $\mathcal{B}({\mathbb{R}}^n)\subseteq \mathcal{B}(\mathbb{R}{)}^{\otimes n}$. Conversely, each coordinate projection ${\pi }_i:{\mathbb{R}}^n\to \mathbb{R}$ is continuous, so [F7] makes ${\pi }_i^{-1}(A)$ Borel for every $A\in \mathcal{B}(\mathbb{R})$; finite intersections show every measurable rectangle is Borel, giving the reverse inclusion. Hence the Borel product and Euclidean Borel sigma-algebras agree in both dimensions. The map $\omega \mapsto (S_0(\omega ),T_0(\omega ))$ is measurable because the inverse image of each generating rectangle $A\times B$ is $S_0^{-1}(A)\cap T_0^{-1}(B)$; therefore $a(S_0,T_0)$ and $b(S_0,T_0)$ are measurable by [F6] and [F7]. The sets $(t,\mathrm{\infty })$ and $\{t\}$ are disjoint and their union is $[t,\mathrm{\infty })$, so finite additivity gives $a(S_0,T_0)+b(S_0,T_0)=K(S_0,[T_0,\mathrm{\infty }))$. The map $(x,z)\mapsto x+z$ is continuous by $\mathrm{\mid }(x+z)-(x_0+z_0)\mathrm{\mid }\le \mathrm{\mid }x-x_0\mathrm{\mid }+\mathrm{\mid }z-z_0\mathrm{\mid }$. The map $(x,z,u)\mapsto x+uz$ is continuous because $\mathrm{\mid }(x+uz)-(x_0+u_0{z}_0)\mathrm{\mid }\le \mathrm{\mid }x-x_0\mathrm{\mid }+\mathrm{\mid }u\mathrm{\mid }\cdot \mathrm{\mid }z-z_0\mathrm{\mid }+\mathrm{\mid }{z}_0\mathrm{\mid }\cdot \mathrm{\mid }u-u_0\mathrm{\mid }$, and $\mathrm{\mid }u\mathrm{\mid }$ is bounded in a sufficiently small neighborhood of $u_0$. The pairs and triples of the real measurable functions already obtained and $U$ are measurable because inverse images of generating product rectangles are finite intersections of coordinate preimages. The established Borel-product equalities make these continuous maps measurable by [F7]. Composition by [F7] proves measurability of the asserted sums.

By [F1] and [F2], $F$ is nondecreasing. For each real $c$, $\{x:F(x)>c\}$ is an upper set, hence is empty, all of $\mathbb{R}$, or a ray with or without its finite endpoint; each such ray is Borel by [F11]. Thus every strict superlevel set is Borel, and [F10] makes $F$ Borel-measurable. For each $x$, the sets $(-\mathrm{\infty },x+1\mathrm{/}n]$ decrease to $(-\mathrm{\infty },x]$ and have finite measure, so [F4] gives right continuity. The sets $(-\mathrm{\infty },-n]$ decrease to $\mathrm{\varnothing }$ and $(-\mathrm{\infty },n]$ increase to $\mathbb{R}$, so [F3] and [F4] give the limits $0$ and $1$ at the two infinities. Also $(-\mathrm{\infty },x-1\mathrm{/}n]$ increases to $(-\mathrm{\infty },x)$, so [F3] gives $F(x-)=\mu ((-\mathrm{\infty },x))$; [F5] then gives $F(x)-F(x-)=\mu (\{x\})$.

For every $x$, step 1.1 gives $F(x-)={\lim }_{n}F(x-1\mathrm{/}n)$. Each translate $x\mapsto F(x-1\mathrm{/}n)$ is measurable because translation is continuous and [F8] preserves measurability under composition; [F9] makes their increasing limit $F(x-)$ measurable. Thus $\mathrm{\Delta }F=F-F(\cdot -)$ is measurable by [F9]. Since $Y$ is measurable, $F(Y-)$ and $\mathrm{\Delta }F(Y)$ are measurable. Fix a bijection $e:\mathbb{Q}\to \mathbb{N}$ supplied by [F12]. Each rational open rectangle is encoded by four natural numbers, and iterating the injection $(a,b)\mapsto 2^a(2b+1)$ shows there are only countably many such rectangles. Density of $\mathbb{Q}$ makes them a base of ${\mathbb{R}}^2$. Every Euclidean open set is therefore a countable union of rectangles in $\mathcal{B}(\mathbb{R})\otimes \mathcal{B}(\mathbb{R})$. Conversely the coordinate projections are continuous, and [F8] makes the inverse image of each Borel set under either projection Borel; finite intersections then show every Borel rectangle is Euclidean Borel. Thus the product Borel sigma-algebra equals $\mathcal{B}({\mathbb{R}}^2)$. The pair $(U,\mathrm{\Delta }F(Y))$ is measurable into the product sigma-algebra because preimages of generating rectangles are intersections of coordinate preimages, hence it is measurable into $\mathcal{B}({\mathbb{R}}^2)$. The map $(u,d)\mapsto ud$ is continuous, as $\mathrm{\mid }ud-u_0{d}_0\mathrm{\mid }\le \mathrm{\mid }u\mathrm{\mid }\cdot \mathrm{\mid }d-d_0\mathrm{\mid }+\mathrm{\mid }{d}_0\mathrm{\mid }\cdot \mathrm{\mid }u-u_0\mathrm{\mid }$ and $\mathrm{\mid }u\mathrm{\mid }$ is bounded near $u_0$; hence [F8] makes it Borel-measurable. Composing and then summing with $F(Y-)$ proves $V$ is measurable.

Fix $0<u<1$ and set $A_u:=\{x:F(x)\ge u\}$. The upper-tail limit in step 1.1 makes $A_u$ nonempty, and the lower-tail limit makes it bounded below. Applying [F6] to $-A_u$ gives $q:=-\sup (-A_u)=\inf A_u$. For every $n$, the infimum property gives $F(q+1\mathrm{/}n)\ge u$, so right continuity from step 1.1 yields $F(q)\ge u$. Since $q-1\mathrm{/}n<q$ and $q$ is a lower bound for $A_u$, $F(q-1\mathrm{/}n)<u$; the sets $(-\mathrm{\infty },q-1\mathrm{/}n]$ increase to $(-\mathrm{\infty },q)$, so [F3] and step 1.1 give $F(q-)={\lim }_{n}F(q-1\mathrm{/}n)\le u$. Put $a:=F(q-)$ and $b:=F(q)$. If $Y<q$, then $F(Y)\le a\le u$, so $V\le u$; this event has probability $a$. If $b>a$, then $P(Y=q)=b-a$ and, conditional on $Y=q$, $V=a+U(b-a)$ is uniform on $[a,b]$, contributing $(u-a)$ to $P(V\le u)$. If $b=a$, the inequalities force $a=b=u$ and $P(Y=q)=0$, so this contribution is zero.

For $Y>q$, monotonicity gives $F(Y-)\ge F(q)=b\ge u$. If $F(Y-)>u$, then $V>u$. If $F(Y-)=u$ and $\mathrm{\Delta }F(Y)>0$, the event $V\le u$ requires $U=0$, which has probability zero by [A1]. In the remaining case $F(Y-)=F(Y)=u$, put $L:=\{y>q:F(y-)=F(y)=u\}$. By steps 1.1 and 2.1, both $F$ and $F(\cdot -)$ are Borel-measurable, so $L=\{y>q\}\cap \{F(y-)=u\}\cap \{F(y)=u\}$ is Borel and therefore $\mu$-measurable. If $L$ is empty it contributes no mass. Otherwise let $r=\sup L$, allowing $r=+\mathrm{\infty }$ when $L$ is unbounded. For every $z$ with $q<z<r$, some $y\in L$ has $z<y$, so monotonicity gives $u=F(q)\le F(z)\le F(y-)=u$ and hence $F(z)=u$. If $r<\mathrm{\infty }$, define $c_n=q+(r-q)n\mathrm{/}(n+1)$; if $r=+\mathrm{\infty }$, define $c_n=q+n$. In either case $c_n\uparrow r$ (with the limit interpreted as $+\mathrm{\infty }$ in the second case), and [F5] gives $\mu ((q,c_n])=F(c_n)-F(q)=0$. By [F3], $\mu ((q,r))=0$. If finite $r$ belongs to $L$, its mass is $\mathrm{\Delta }F(r)=0$, so $\mu (L)=0$. Thus $Y>q$ contributes no probability, and step 2.2 yields $P(V\le u)=a+(u-a)=u$.

For $u_n=1\mathrm{/}n$ with $n\ge 2$, the events $\{V\le u_n\}$ decrease to $\{V\le 0\}$; [F4] and the formula from step 3.1 give $P(V\le 0)=0$. For $v_n=1-1\mathrm{/}n$ with $n\ge 2$, the events $\{V\le v_n\}$ increase to $\{V<1\}$; [F3] and step 3.1 give $P(V<1)=1$. Finally $0\le V\le 1$ by its definition, so $P(V\le 1)=1$. Thus $P(V\le u)=u$ for all $u\in [0,1]$, which is the uniform law.

Starting from the given list, repeatedly take the maximum of the remaining entries and remove every index carrying that value. By [F2] each nonempty remaining list has a maximum, and each iteration removes at least one of the original $m$ indices, so the process ends after at most $m$ iterations. It produces distinct values $b_1>b_2>\cdots >b_k$ with block sizes $r_j$. Put $c_j:={\sum }_{\mathrm{\ell }<j}{r}_{\mathrm{\ell }}$, so ${\sum }_j{r}_j=m$. By [F1], the event that $a_J=b_j$ has probability $r_j\mathrm{/}m$. On that event, $R_0=(c_j+r_j)\mathrm{/}m$ and, by [A1] and [F3], $R_U=(c_j+r_{j}U)\mathrm{/}m$, uniform on the interval $I_j=[c_j\mathrm{/}m,(c_j+r_j)\mathrm{/}m]$ of length $r_j\mathrm{/}m$.

By step 1.1, the intervals $I_j$ are consecutive, begin at $0$, and end at $1$. Conditional on $a_J=b_j$, $R_U=(c_j+r_{j}U)\mathrm{/}m$, so for $u\in [0,1]$ its conditional CDF is $0$ below the left endpoint, $(mu-c_j)\mathrm{/}{r}_j$ between the endpoints, and $1$ above the right endpoint, by [A1]. Multiplying each conditional CDF contribution by $P(a_J=b_j)=r_j\mathrm{/}m$ gives the length of $I_j\cap [0,u]$. These lengths sum to $u$ because the intervals partition $[0,1]$ up to shared endpoints. Hence $P(R_U\le u)=u$ for every $u\in [0,1]$, so $R_U$ is uniform.

For $u\in [0,1]$, $P(R_0\le u)$ is the sum of $r_j\mathrm{/}m$ over those blocks whose right endpoint $(c_j+r_j)\mathrm{/}m$ is at most $u$. These blocks form an initial segment; if the last is $j$, the sum telescopes to $(c_j+r_j)\mathrm{/}m\le u$, and if there is no such block the sum is zero. Hence $P(R_0\le u)\le u$.

For each $s$, let ${\mathrm{\Lambda }}_s:=K(s,\cdot )\otimes \lambda$, where $\lambda$ is the uniform law of $U$. By [F4] this is a probability measure with rectangle values ${\mathrm{\Lambda }}_s(C\times D)=K(s,C)\lambda (D)$. For $A\in \sigma (S)$ and Borel $C,D$, the conditional-law identity [F2] gives ${\int }_A{\mathrm{\Lambda }}_S(C\times D)d{P}_0=\lambda (D)P_0(A\cap \{T\in C\})$. Independence in [F3] makes the right side $P_0(A\cap \{T\in C,U\in D\})$. The class of product-Borel sets where the evaluation $s\mapsto {\mathrm{\Lambda }}_s(E)$ is measurable and every such conditional identity holds is a Dynkin system: complements subtract from the probability-one whole-space evaluation, and disjoint unions follow by countable additivity and increasing limits. It contains the generating rectangles, so [F5] and [F6] extend measurability and the conditional identity to every product-Borel set. Thus ${\mathrm{\Lambda }}_S$ is a conditional law of $(T,U)$ given $S$.

For almost every conditioning value $s$, the conditional law just constructed makes $T$ have law $K(s,\cdot )$ and keeps $U$ independent uniform. Write $F_s(t):=K(s,(-\mathrm{\infty },t])$ and ${\mathrm{\Delta }}_s(t):=F_s(t)-F_s(t-)$. By [F7], $V=F_s(T-)+(1-U){\mathrm{\Delta }}_s(T)$ is uniform, since $1-U$ is also uniform. The p-value formula in [F1] gives $p_U=1-V$, so $p_U$ is conditionally uniform.

For the same $s$, $p_0=1-F_s(T-)$ and $p_U=1-F_s(T-)-(1-U){\mathrm{\Delta }}_s(T)\le p_0$. Hence $\{p_0\le u\}\subseteq \{p_U\le u\}$ conditionally on $S=s$. Step 2.1 gives $P_0(p_0\le u\mid S=s)\le u$. This holds for each $u\in [0,1]$ and almost every conditioning value, proving conditional superuniformity.

Fix a positive-probability orbit $O$ and points $x,y\in O$. Choose $h\in G$ with $y=h\cdot x$. Invariance gives $P(X=y)=P(h\cdot X=y)=P(X=h^{-1}\cdot y)=P(X=x)$. Thus all $\mathrm{\mid }O\mathrm{\mid }$ distinct points have equal mass; by [F3] their conditional probabilities given $X\in O$ are each $1\mathrm{/}\mathrm{\mid }O\mathrm{\mid }$.

For fixed $x\in O$, define its stabilizer $G_x:=\{g\in G:g\cdot x=x\}$. If $y=h\cdot x$, then $\{g:g\cdot x=y\}=h{G}_x$: every $hg$ with $g\in G_x$ sends $x$ to $y$, and if $g\cdot x=y$ then $h^{-1}g\in G_x$. Hence every distinct point of $O$ occurs exactly $\mathrm{\mid }{G}_x\mathrm{\mid }$ times in the group-transformed list. The strict and tied counts and denominator in [F2] all have this same factor, so the group-average ranks equal the ranks computed on the distinct orbit points.

Conditional on $O$, [step 1.1] makes the observed orbit point a uniform index in the finite list $(T(y){)}_{y\in O}$. By [F5] and [A2], the randomizer remains independent and uniform. Apply [F4] to this list and use [step 2.1]: $p_U$ is Uniform$(0,1)$ and $P(p_0\le u\mid X\in O)\le u$ for every $u\in [0,1]$.

The positive-probability orbits form a finite partition up to null orbits. Summing the conditional superuniform bounds from step 3.1 with weights $P(X\in O)$ gives $P(p_0\le u)\le u$; summing the conditional uniform laws gives $p_U\sim \mathrm{Unif}(0,1)$. The argument applies to each invariant null law. Only finite counting is used, so no choice axiom is needed.

The map $(s,x)\mapsto \phi (x)$ is product-measurable by [F5]. Kernel integration [F2] therefore makes $q$ measurable. Since $K(s,\cdot )$ is a probability measure and $0\le \phi \le 1$, every value satisfies $0\le q(s)\le 1$.

Fix $\eta \in {\mathrm{\Theta }}_0$. By [A1] and [F1], $K(S,\cdot )$ is a regular conditional distribution of $X$ given $\sigma (S)$ under $P_{\eta }$. Applying [F3] to the bounded function $\phi$ shows that for every $A\in \sigma (S)$, ${\int }_{A}q(S)d{P}_{\eta }={\int }_A\phi (X)d{P}_{\eta }$. Thus $q(S)$ is a version of the conditional rejection probability under this null law. The same kernel in [A1] defines the same $q$ for every $\eta$, proving nuisance-freeness; only the individual laws' almost-sure qualifications are used.

Fix $\theta \in {\mathrm{\Theta }}_0$ and choose the conditional version $q_{\theta }$ supplied by [F1]. Taking $A=\mathrm{\Omega }$ in [F2] gives $E_{\theta }{q}_{\theta }=E_{\theta }\phi (X)$.

Since $q_{\theta }\le \alpha$ almost surely and both variables are integrable, [F3] gives $E_{\theta }{q}_{\theta }\le E_{\theta }\alpha =\alpha$. Combining with step 1.1 yields $E_{\theta }\phi (X)\le \alpha$.

The argument holds for every $\theta \in {\mathrm{\Theta }}_0$, so taking the supremum of these rejection expectations gives size at most $\alpha$ under the convention [A1]. No common exceptional null set across parameter values is needed.