Conformal Prediction and Exchangeable Ranks

By induction on $n$, the finite product sigma-algebra is generated by the $n$-coordinate rectangles. The base case is $n=1$. At the induction step, let $\mathcal{S}$ be the sigma-algebra generated by $(n+1)$-coordinate rectangles. For each measurable last-coordinate set $B$, the class of first-coordinate sets $A$ with $A\times B\in \mathcal{S}$ is a sigma-algebra: it contains the whole first product since the whole-first-product times $B$ is a coordinate rectangle, and complements and countable unions follow by relative difference inside that set and by countable unions. It contains the $n$-coordinate rectangles by construction, so it contains the recursively defined $n$-fold product sigma-algebra. Thus $\mathcal{S}$ contains every rectangle used in the recursive binary product. Conversely, each $(n+1)$-coordinate rectangle belongs to that recursive product sigma-algebra by its defining binary rectangle clause, so the two generated sigma-algebras agree.

For a generating rectangle $E_1\times \cdots \times E_n$, its preimage under $f$ is ${\bigcap }_{i=1}^n{f}_i^{-1}(E_i)$. Each set in this finite intersection belongs to $\mathcal{F}$ by [A1], so the preimage belongs to $\mathcal{F}$ by [F4]. The class of target sets whose preimages under $f$ lie in $\mathcal{F}$ is a sigma-algebra because preimages preserve complements and countable unions; by step 1.1 it contains the generators, so it contains the product sigma-algebra and [F3] makes $f$ measurable.

For $\pi$ a permutation, ${\tau }_{\pi }^{-1}(E_1\times \cdots \times E_n)=E_{{\pi }^{-1}(1)}\times \cdots \times E_{{\pi }^{-1}(n)}$, which is a generating rectangle by [F2]. The same generated-sigma-algebra argument of step 2.1 proves that ${\tau }_{\pi }$ is measurable.

Let $\mathcal{D}$ consist of product-measurable sets $E\subseteq \mathrm{\Omega }\times S$ for which $k_E(\omega ):=K(\omega ,E_{\omega })$ is $\mathcal{G}$-measurable and ${\int }_H{k}_{E}dP=P(H\cap \{(\omega ,X(\omega ))\in E\})$ for every $H\in \mathcal{G}$. For a rectangle $E=A\times B$, $k_E={\mathbf{1}}_{A}K(\cdot ,B)$ is measurable by [F1], and its integral identity follows by applying [F1] to $H\cap A$. Thus all rectangles lie in $\mathcal{D}$.

For each $\omega$, define $\bar{K}(\omega ,\cdot )=K(\omega ,\cdot )\otimes \lambda$, which is a probability measure by [F4]. On a rectangle $B\times C$, its evaluation is $K(\omega ,B)\lambda (C)$, a $\mathcal{G}$-measurable function. For $H\in \mathcal{G}$, the integral of this evaluation over $H$ equals $\lambda (C)P(H\cap \{X\in B\})$ by [F1]. Since $H\cap \{X\in B\}\in \mathcal{G}\vee \sigma (X)$, independence [A2, F5] makes this $P(H\cap \{X\in B\}\cap \{U\in C\})$.

The whole space is in $\mathcal{D}$. If $E\in \mathcal{D}$, then $k_{E^c}=1-k_E$ and the integral identity for $E^c$ follows by subtracting the identity for $E$ from $P(H)$. If $E_j$ are disjoint members of $\mathcal{D}$, then their sections are disjoint, so $k_{{\cup }_j{E}_j}={\sum }_j{k}_{E_j}$ pointwise; [F8] makes the increasing partial sums' limit measurable, and [F6] gives the integral identity for the union. Hence $\mathcal{D}$ is a lambda-system. Measurable rectangles contain $\mathrm{\Omega }\times S$ and are closed under finite intersections, so they form a pi-system generating $\mathcal{G}\otimes \mathrm{\Sigma }$ by [F2]; [F7] therefore gives $\mathcal{D}=\mathcal{G}\otimes \mathrm{\Sigma }$.

For $B\in \mathrm{T}$, [A1] makes $E=g^{-1}(B)$ product-measurable and [F10] makes its sections measurable, so $K_g(\omega ,B)$ is defined. The map $\omega \mapsto (\omega ,X(\omega ))$ is measurable from $(\mathrm{\Omega },\mathcal{F})$ into $(\mathrm{\Omega }\times S,\mathcal{G}\otimes \mathrm{\Sigma })$: the identity map into $(\mathrm{\Omega },\mathcal{G})$ is measurable because $\mathcal{G}\subseteq \mathcal{F}$, and $X$ is measurable, so [F9] applies. Therefore $\{g(\omega ,X(\omega ))\in B\}$ is the measurable preimage of $E$ under this map. Step 2.1 gives measurability and the conditional-event identity for $K_g(\cdot ,B)$. For every $\omega$, $K_g(\omega ,\cdot )$ is the pushforward of the probability measure $K(\omega ,\cdot )$, hence is a probability measure. These are exactly the clauses in [F1], so $K_g$ is a regular conditional distribution of $g(\omega ,X(\omega ))$.

The tuple $(X,U)$ is measurable into the product space by [F9]. The class of sets in $\mathrm{\Sigma }\otimes \mathcal{V}$ for which the evaluation of $\bar{K}$ is measurable and the conditional-event identity holds is a lambda-system: complements subtract from the whole-space identity, and disjoint unions follow from countable additivity, measurable increasing limits [F8], and [F6]. It contains all rectangles by step 1.2, so [F2, F7] show that it contains $\mathrm{\Sigma }\otimes \mathcal{V}$. Every section is the product probability measure from [F4]; consequently $\bar{K}$ is a regular conditional distribution of $(X,U)$ given $\mathcal{G}$.

For each $k$-element subset $I\subseteq \{1,\dots ,m\}$, let $M_I={\max }_{i\in I}{R}_i$. Then $R_{(k)}={\min }_{\mathrm{\mid }I\mathrm{\mid }=k}{M}_I$: every $k$-element subset has maximum at least the $k$th smallest score, and the subset of the $k$ smallest scores has that maximum exactly. There are finitely many such nonempty subsets, so [F1] makes this finite minimum of finite maxima measurable.

For any two indices, $\{R_i\ge R_j\}=\{R_i-R_j\in [0,+\mathrm{\infty })\}$ is measurable by [F1]–[F3]. The upper-rank p-value is a finite sum of indicators of these events divided by $n$, so is measurable.

On the same domain, the tie count is a finite sum of the comparison indicators from step 1.2. Multiplication by the measurable real function $U$, addition, and division by the positive integer $n$ preserve measurability by [F1]. Hence the randomized rank map is measurable.

The measurable map $A$ sends $Z$ to a random vector by the composition rule for measurable maps; [F3] makes every coordinate permutation of that vector measurable, so its law is defined.

For each permutation $\pi$, [F2] gives ${\tau }_{\pi }A(Z)=A({\tau }_{\pi }Z)$. By exchangeability [F1], ${\tau }_{\pi }Z$ and $Z$ have the same law; applying the measurable map $A$ shows that $A({\tau }_{\pi }Z)$ and $A(Z)$ have the same law. Hence $A(Z)$ is exchangeable.

Fix a deterministic vector $r\in {\mathbb{R}}^n$. List its distinct values in decreasing order $v_1>\cdots >v_s$, let $d_j$ be the multiplicity of $v_j$, and put $D_j={\sum }_{\mathrm{\ell }=1}^j{d}_{\mathrm{\ell }}$. Each coordinate in the $j$th tie group has upper rank $D_j\mathrm{/}n$. Hence the number of coordinates whose upper rank is at most $u$ is either zero or one of the cumulative counts $D_j\le nu$, and is therefore at most $nu$.

For fixed $r$, the $j$th tie group has $D_{j-1}$ scores strictly above it and $d_j$ scores equal to it, so for any index in that group the randomized rank is $(D_{j-1}+U{d}_j)\mathrm{/}n$. Averaging uniformly over the $n$ coordinate indices selects this interval with probability $d_j\mathrm{/}n$; conditional on the group, its value is uniform on $[D_{j-1}\mathrm{/}n,D_j\mathrm{/}n]$. These intervals partition $[0,1]$ and their lengths are $d_j\mathrm{/}n$, so the averaged rank law is Uniform$[0,1]$.

By exchangeability [F1], each coordinate has the same upper-rank distribution. Thus [F5] and the pointwise bound of step 1.1 give $\mathbb{P}(p_n\le u)=\frac{1}{n}{\sum }_{i=1}^n\mathbb{P}(\frac{1}{n}\mathrm{\#}\{j:R_j\ge R_i\}\le u)=\mathbb{E}[\frac{1}{n}{\sum }_{i=1}^n\mathbf{1}\{\frac{1}{n}\mathrm{\#}\{j:R_j\ge R_i\}\le u\}]\le u$. The last coordinate therefore has a superuniform upper-rank p-value.

Since $R$ is exchangeable and $U$ is independent of $R$ by [F4], permuting score coordinates leaves the joint law of $(R,U)$ unchanged. Thus every randomized coordinate rank has the same distribution, equal to the averaged distribution in step 1.2. In particular $p_{U,n}$ is Uniform$[0,1]$.

Define $g(\omega ,z)=(s(H(\omega ),z_i){)}_{i=1}^{m+1}$. For each $i$, the map $(\omega ,z)\mapsto (H(\omega ),z_i)$ is measurable into $\mathcal{H}\times \mathcal{Z}$: the preimage of a rectangle $A\times B$ is $H^{-1}(A)\times \{z:z_i\in B\}$, which belongs to $\mathcal{T}\otimes {\mathcal{Z}}^{\otimes (m+1)}$, and such rectangles generate the target product sigma-algebra. Joint measurability of $s$ therefore makes every coordinate of $g$ measurable. The finite tuple $g$ is measurable into the product Borel sigma-algebra because preimages of Borel rectangles are finite intersections of coordinate preimages. For each fixed $\omega$, $g(\omega ,\cdot )$ is permutation-equivariant because the same fixed rule $s(H(\omega ),\cdot )$ is applied coordinatewise. By [F2] its pushforward is a regular conditional distribution of the score vector; by the sectionwise exchangeability in the hypothesis and [F3], that score-vector distribution is exchangeable.

Put $n=m+1$ and $k=\lceil n(1-\alpha )\rceil$. If $k=n$, [F5] sets $q=+\mathrm{\infty }$, so every true response is covered. If $k\le m$ and the true test score $R_n$ exceeds the $k$th calibration score $q$, then at least $k$ calibration scores are strictly below $R_n$; consequently at most $n-k$ of all $n$ scores are at least $R_n$, and $p_n\le (n-k)\mathrm{/}n\le \alpha$. Thus $p_n>\alpha$ implies coverage in every case.

Apply [F4] to the conditional exchangeable score law from step 1.1. The event $p_n>\alpha$ has conditional probability at least $1-\alpha$, and step 1.2 includes it in the nonrandomized coverage event. For the randomized version, the second assertion of [F2] makes $Q_{\omega }\otimes \lambda$ a regular conditional distribution of $(Z,U)$ given $\mathcal{T}$. The map that sends $(\omega ,z,u)$ to the tie-randomized rank computed from $g(\omega ,z)$ and $u$ is jointly measurable: the score coordinates are measurable by step 1.1, comparisons of real-valued measurable functions are measurable, and the rank formula uses finite sums, products, and scalar division. Applying the first assertion of [F2] to this map gives the conditional law of $p_{U,n}$. For almost every $\omega$, $Q_{\omega }$ is exchangeable, $H(\omega )$ is fixed, and $\lambda$ is independent uniform; [F4] therefore gives conditional probability exactly $1-\alpha$ for $p_{U,n}>\alpha$, which is precisely randomized-set coverage.

The conditional-kernel identity in [F1], applied with the conditioning event $H=\mathrm{\Omega }$, integrates the conditional coverage probabilities from step 2.1 to their unconditional probabilities. The lower bound and the exact equality therefore also hold marginally.

By [F1], the data tuple has an exchangeable law. The full score assignment is measurable and permutation-equivariant by hypothesis, so [F2] makes the augmented score vector exchangeable.

For the true candidate $Y_{m+1}$, the full set membership condition in [F3] is $p_{m+1}>\alpha$. By [F4], its probability is at least $1-\alpha$; for the randomized version, $p_{U,m+1}$ is uniform and $\mathbb{P}(p_{U,m+1}>\alpha )=1-\alpha$.