Why is leave-one-out cross-validation (LOOCV) variance about the mean estimate for error high? In leave-one-out cross-validation (LOOCV), each of the training sets looks very similar to the others, differing in only one observation. When you want to estimate the test error, you take the average of the errors over the folds. That average has a high variance. 
Is there a mathematical formula, visual, or intuitive way to understand why that average has a higher variance compared with the $k$-fold cross validation? 
 A: From An Introduction to Statistical Learning

When we perform LOOCV, we are in effect averaging the outputs of $n$ fitted models, each of which is trained on an almost identical set of observations; therefore, these ouputs are highly (positively) correlated with each other. In contrast, when we perform $k$-fold CV with $k<n$, we are averaging the outputs of $k$ fitted models that are somewhat less correlated with each other, since the overlap between the training sets in each model is smaller. Since the mean of many highly correlated quantities has higher variance than does the mean of many quantities that are not as highly correlated, the test error estimate resulting from LOOCV tends to have higher variance than does the test error estimate resulting from $k$-fold CV.
To summarize, there is a bias-variance trade-off associated with the choice of $k$ in $k$-fold cross-validation. Typically, given these considerations, one performs $k$-fold cross-validation with $k=5$ or $k=10$, as these values have been shown empirically to yield test error rate estimates that suffer neither from excessively high bias nor from very high variance.

A: The original version of this answer was missing the point (that's when the answer got a couple of downvotes). The answer was fixed in October 2015.
This is a somewhat controversial topic.
It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is so because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance. See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation
  estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the $N$ "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). The accepted and the most upvoted answers in Variance and bias in cross-validation: why does leave-one-out CV have higher variance? give the same reasoning.
HOWEVER, note that Hastie et al. do not give any citations, and while this reasoning does sound plausible, I would like to see some direct evidence that this is indeed the case. One reference that is sometimes cited is Kohavi 1995 but I don't find it very convincing in this particular claim.
MOREOVER, here are two simulations that show that LOOCV either has the same or even a bit lower variance than 10-fold CV:


*

*https://stats.stackexchange.com/a/357572.

*Does $K$-fold CV with $K=N$ (LOO) provide the MOST or LEAST variable estimates, and what is the role of "stability"?. 

*See also the paper linked in https://stats.stackexchange.com/a/252031. It says that it is a "misconception" that LOOCV has high variance.

A: *

*In simple cases I think the answer is: the grand mean (over all test cases and all folds) has the same variance for $k$-fold and LOO validation. 

*Simple means here: models are stable, so each of the $k$ or $n$ surrogate models yields the same predicion for the same sample (thought experiment: test surrogate models with large independent test set).

*If the models are not stable, the situation gets more complex: each of the surrogate models has its own performance, so you have additional variance. In that case, all bets are open whether LOO or $k$-fold has more additional variance*. But you can iterate the $k$-fold CV and taking the grand mean over all test cases and all $i \times k$ surrogate models can mitigate that additional variance. There is no such possibility for LOO: the $n$ surrogate models are all possible surrogate models.

*The large variance is usually due to two factors: 


*

*small sample size (if you weren't in a small sample size situation, you'd not be worried about variance ;-) ). 

*High-variance type of error measure. All proportion-of-test-cases-type of classification errors are subject to high variance. This is a basic property of estimating fractions by counting cases. Regression-type errors like MSE have a much more benign behaviour in this respect.



For classification errors, there's a number of papers that looks at the  properties of different resampling validation schemes in which you also see variances, e.g.:


*

*Kohavi, R.: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection, Mellish, C. S. (ed.) Artificial Intelligence Proceedings 14$^th$ International Joint Conference, 20 -- 25. August 1995, Montréal, Québec, Canada, Morgan Kaufmann, USA, , 1137 - 1145 (1995).

*We observed very similar behaviour for vibrational spectroscopic data:
 Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G.: Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005). 
(I guess similar papers may exist for regression errors as well, but I'm not aware of them)
* one may expect LOO to have less variance because the surrogate models are trained with more cases, but at least for certain types of classification models, LOO doesn't behave very well.
A: It's like taking a test with just one question - it's a lot more hit-and-miss.
This is an intuitive explanation of the standard deviation of an instance versus that of a mean - the score on a batch of instances has less variance.
Here are some more details.
A: There are no folds in LOOCV like k-Fold Cross validation(actually they can be name as folds but meaningless). in LOOCV what it does is leave one Instance from the whole dataset for test data and use all other instances for training. So in each iteration it will leave one instance from the dataset to test.So in a particular iteration of evaluation there is only one  instance in the test data and rest are in training data.that is why you saw all the training data sets equal all the time.
In K-fold Cross validation by using Stratification(an advanced method use to balance the data set ensuring that each class represents approximately in equal proportion in all the samples) we can reduce the variance of the estimates.
as LOOCV is using only one instance for testing, it cannot apply Stratification.So LOOCV has a higher variance in error estimates than k-fold cross validation.
