Full Conformal Prediction under Stochastic Non-Conformity Measure

The theory of full conformal prediction uses deterministic non-conformity measure, but modern usage of full conformal prediction often relies on machine learning training, making stochasticity inevitable. A simple sufficient condition of almost sure permutation invariance of the non-conformity measure can be too restrictive, so many have suggested the relaxation to permutation in distribution as a condition for full conformal prediction validity. We, however, show that this commonly known condition is actually insufficient. We then provide a correct sufficient condition: \emph{Conditional Independence & Permutation Invariance in Distribution}, which encompasses several stochastic settings that may be used in machine learning.