This paper is available on arxiv under CC 4.0 license. Authors: (1) Ulysse Gazin, Universit´e Paris Cit´e and Sorbonne Universit´e, CNRS, Laboratoire de Probabilit´es, Statistique et Mod´elisation, (2) Gilles Blanchard, Universit´e Paris Saclay, Institut Math´ematique d’Orsay, (3) Etienne Roquain, Sorbonne Universit´e and Universit´e Paris Cit´e, CNRS, Laboratoire de Probabilit´es, Statistique et Mod´elisation. Table of Links Abstract & Introduction Main results Application to prediction intervals Application to novelty detection Conclusion, Acknowledgements and References Appendix A: Exact formulas for Pn,m Appendix B: Numerical bounds and templates Appendix C: Proof Appendix D: Explicit control of (16) for α=0 Appendix E: Proof of Corollary 4.1 Appendix F: The Simes inequality Appendix G: Uniform FDP bound for AdaDetect Appendix H: Additional experiments C Proofs C.1 Proof of Proposition 2.1 which finishes the proof. C.2 Proof of Proposition 2.2 If there are no tied scores, which by assumption (NoTies) happens with probability 1, the ranks Ri of the ordered scores are well-defined and the vector (p1, . . . , pm) is only a function of the rank vector (R1, . . . , Rn+m). Namely, Ri ≤ Rj if and only if Si ≤ Sj , and the conformal p-values (1) can be written as C.3 Proof of Theorem A.1 By (Exch),(NoTies) the permutation that orders the scores (S1, . . . , Sn+m) that is σ such that Proof of (ii) This event can be formally described as follows: By using (27) of (ii), we have Proof of (i) Now, we have where we have used (ii) and the multinomial coefficient C.4 Proof of Theorem 2. First observe that the LHS of (9) is 0 if λ ≥ 1 so that we can assume λ < 1 Let us prove (9) with the more complex bounce Below, we establish This leads to