Over-coverage/Coverage violation in APS-Randomized algorithm

[Lahav223]

Thank you for providing such a valuable resource. I have a few inquiries regarding the APS-Randomized algorithm. To begin, I'd like to refer to the upper bound result for CP calibration, as stated in Theorem 2.2 of "Distribution-Free Predictive Inference For Regression": $\mathbb{P}(Y_{test} \in C(X_{test}, U_{test}, \hat{q})) < 1 - \alpha + \frac{1}{n-1}$

Upon running the APS-Randomized algorithm for 100 trials, I observed a mean coverage of approximately 93%, consistent with the empirical coverage in the provided repo example (0.93020408163265). I can raise a rationale for this deviation: while the "split conformal algorithm" in the referenced paper operates with a deterministic model ($\mathcal{A}$), while in APS-Randomized, both the generated scores and the threshold are randomized, which may cause potential challenges.

Moreover, apart from the favorable over-coverage exhibited by this algorithm, its conditional coverage, quantifiable using metrics like SSCV, surpasses that of the APS algorithm outlined in the RAPS paper (which is RAPS with $\lambda = 0$), while maintaining identical set sizes. I'm interested in understanding the underlying rationale behind this algorithm and would appreciate insights into its origins, particularly if it was derived from a specific academic paper. Thank you for your assistance! Lahav.