# 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.

### Bibliography

- Vladimir Vovk, Alexander Gammerman and Glenn Shafer. Algorithmic Learning in a Random World. New York: Springer, 2005.
- Vladimir Vovk. On-line confidence machines are well-calibrated. FOCS 2002.