TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Conformal rank superuniformity under exchangeability

Statement

Let $R_{1}, \dots, R_{n}$ be an exchangeable real random vector with $n \geq 1$ . Define its last-coordinate upper-rank p-value by $p_{n} = \frac{1}{n} # {i \leq n : R_{i} \geq R_{n}} .$ Then $P (p_{n} \leq u) \leq u$ for every $u \in [0, 1]$ . If $U$ has Lebesgue probability law on $[0, 1]$ and is independent of $R$ , define $p_{U, n} = \frac{# {i \leq n : R_{i} > R_{n}} + U # {i \leq n : R_{i} = R_{n}}}{n} .$ Then $p_{U, n}$ has the uniform law on $[0, 1]$ .

Facts & Assumptions

Given: The exchangeable score vector, $n \geq 1$ , and, for the randomized assertion, an independent $[0, 1]$ -valued random element with Lebesgue probability law.

[F1]

Exchangeability means joint-law invariance under every coordinate permutation. Exchangeable random elements

[F2]

The upper-rank and tie-randomized p-values count scores greater than or equal to the candidate, with the randomized formula spreading uniformly across all tied scores. Conformal scores and rank p-values

[F3]

These finite comparison sums are measurable, so their probability events are defined. Finite order statistics and rank maps are measurable

[F4]

Independence of random elements or their generated sigma-algebras is defined by factorization of probabilities of finite intersections. Independent sigma-algebras and independent events

[F5]

An indicator has expectation equal to the probability of its event, and expectation is linear for finite sums of integrable random variables. The expectation of an indicator is the probability of the event Linearity, monotonicity, and the modulus bound for expectation

Proof

1.1givenF2

Fix a deterministic vector $r \in R^{n}$ . List its distinct values in decreasing order $v_{1} > \dots > v_{s}$ , let $d_{j}$ be the multiplicity of $v_{j}$ , and put $D_{j} = \sum_{ℓ = 1}^{j} d_{ℓ}$ . Each coordinate in the $j$ th tie group has upper rank $D_{j} / n$ . Hence the number of coordinates whose upper rank is at most $u$ is either zero or one of the cumulative counts $D_{j} \leq n u$ , and is therefore at most $n u$ .

1.2givenF2

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}) / n$ . Averaging uniformly over the $n$ coordinate indices selects this interval with probability $d_{j} / n$ ; conditional on the group, its value is uniform on $[D_{j - 1} / n, D_{j} / n]$ . These intervals partition $[0, 1]$ and their lengths are $d_{j} / n$ , so the averaged rank law is Uniform $[0, 1]$ .

2.1F1F3F5step 1.1

By exchangeability [F1], each coordinate has the same upper-rank distribution. Thus [F5] and the pointwise bound of step 1.1 give $P (p_{n} \leq u) = \frac{1}{n} \sum_{i = 1}^{n} P (\frac{1}{n} # {j : R_{j} \geq R_{i}} \leq u) = E [\frac{1}{n} \sum_{i = 1}^{n} 1 {\frac{1}{n} # {j : R_{j} \geq R_{i}} \leq u}] \leq u$ . The last coordinate therefore has a superuniform upper-rank p-value.

3.1F1F4step 1.2∎

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]$ .

Depends on

Used by

Full conformal ranks a candidate in an augmented sample Example
Split conformal coverage can be conservative when scores tie Example
Full conformal marginal coverage Theorem
Split conformal marginal coverage Theorem

Dependency tree · two levels

29 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jing Lei et al., Distribution-Free Predictive Inference for Regression, JASA 113(523) (2018), §2.1 and Appendix A.1 (standard reference, not scraped)
Glenn Shafer and Vladimir Vovk, A Tutorial on Conformal Prediction, JMLR 9 (2008), §§3.1, 4.1–4.2 (standard reference, not scraped)
Ryan Tibshirani, Conformal Prediction, Advanced Topics in Statistical Learning, Spring 2024, §§1–2 (standard reference, not scraped)