We perform a theoretical investigation of the variance of the cross-validation estimate of the generalization error that takes into account the variability due to the choice of training sets and test examples. This allows us to propose two new estimators of this variance. We show, via simulations, that these new statistics perform well relative to the statistics considered in Dietterich (1998). In particular, tests of hypothesis based on these don't tend to be too liberal like other tests currently available, and have good power.