# Validity Idea

This article gives an intuitive explanation of why smoothed conformal predictors are valid in the on-line prediction protocol: the random variables  are independent Bernoulli with parameter  (see the article about conformal prediction for the definitions). Our heuristic explanation will ignore the difference between conformal predictors and smoothed conformal predictors.

Let us show first that the probability that  is approximately  . We will even show that the conditional probability, given the bag of the first  observations, that  is approximately  . The bag of observations determines the bag of the alphas; because of the randomness assumption all orderings of the alphas have the same probability (  ). An error is made (  ) if and only if the p-value  corresponding to the true label is  if and only if  is among the  largest  . And the last event has probability  .

Let us see that  are independent. It suffices to show that, for each  ,  are independent. Fix  . It suffices to show that  are independent. We will show that they are independent given the bag of the first  observations. We already know that the probability of  , given the bag, is  . Draw  from the bag. The same argument shows that the probability of  , given the bag and  , is  . Therefore, the probability of  , given the bag and  , is  . In the same way we obtain that  is the probability of  , given the bag and  .

For a formal proof see, e.g., Vovk et al. (2005), Theorem 8.1. For a less general but easier to understand proof, see Vovk (2002), Theorem 1.