I am trying to learn various cross validation methods, primarily with intention to apply to supervised multivariate analysis techniques. Two I have come across are K-fold and Monte Carlo cross-validation techniques. I have read that K-fold is a variation on Monte Carlo but I'm not sure I fully understand what makes up the definition of Monte Carlo. Could someone please explain the distinction between these two methods?
$k$-Fold Cross Validation

Suppose you have 100 data points. For $k$-fold cross validation, these 100 points are divided into $k$ equal sized and mutually-exclusive 'folds'. For $k$=10, you might assign points 1-10 to fold #1, 11-20 to fold #2, and so on, finishing by assigning points 91-100 to fold #10. Next, we select one fold to act as the test set, and use the remaining $k-1$ folds to form the training data. For the first run, you might use points 1-10 as the test set and 11-100 as the training set. The next run would then use points 11-20 as the test set and train on points 1-10 plus 21-100, and so forth, until each fold is used once as the test set.

Monte-Carlo Cross Validation

Monte Carlo works somewhat differently. You randomly select (without replacement) some fraction of your data to form the training set, and then assign the rest of the points to the test set. This process is then repeated multiple times, generating (at random) new training and test partitions each time. For example, suppose you chose to use 10% of your data as test data. Then your test set on rep #1 might be points 64, 90, 63, 42, 65, 49, 10, 64, 96, and 48. On the next run, your test set might be 90, 60, 23, 67, 16, 78, 42, 17, 73, and 26. Since the partitions are done independently for each run, the same point can appear in the test set multiple times, which is the major difference between Monte Carlo and cross validation.

Comparison

Each method has its own advantages and disadvantages. Under cross validation, each point gets tested exactly once, which seems fair. However, cross-validation only explores a few of the possible ways that your data could have been partitioned. Monte Carlo lets you explore somewhat more possible partitions, though you're unlikely to get all of them--there are $\binom{100}{50} \approx 10^{28}$ possible ways to 50/50 split a 100 data point set(!). 

If you're attempting to do inference (i.e., statistically compare two algorithms), averaging the results of a $k$-fold cross validation run gets you a (nearly) unbiased estimate of the algorithm's performance, but with high variance (as you'd expect from having only 5 or 10 data points). Since you can, in principle, run it for as long as you want/can afford, Monte Carlo cross validation can give you a less variable, but more biased estimate.

Some approaches fuse the two, as in the 5x2 cross validation (see Dietterich (1998) for the idea, though I think there have been some further improvements since then), or by correcting for the bias (e.g., Nadeau and Bengio, 2003).
