I have what seems to be a very basic confusion about cross-validation.
Let us say I am building a linear binary classifier, and I want to use cross-validation to estimate the classification accuracy. Imagine now that my sample size $N$ is small, but the number $k$ of features is large. Even when features and classes are randomly generated (i.e. "actual" classification accuracy should be 50%), it can so happen that one of the features will perfectly predict the binary class. If $N$ is small and $k >> N$, such a situation is not unlikely. In this scenario I will get 100% classification accuracy with any amount of cross-validation folds, which obviously does not represent the actual power of my classifier, in a sense that probability to classify a new sample correctly is still only 50%. [Update: this is wrong. See my answer below for the demonstration of why it is wrong.]
Are there any common methods of dealing with such a situation?
For example, if I want to assess statistical difference between my two classes, I could run MANOVA which in case of two groups reduces to computing Hotelling's T. Even if some of the features yield significant univariate differences ("false positives"), I should get an overall non-significant multivariate difference. However, I do not see anything in the cross-validation procedure that would account for such false positives ("false discriminants"?). What am I missing?
One thing that I can think of myself, would be to cross-validate over features, e.g. to select random subset of features (in addition to randomly selecting a test set) on each cross-validation fold. But I do not think such an approach is often (ever?) used.
Update: Section 7.10.3 of "The Elements of Statistical Learning" entitled "Does Cross-Validation Really Work?" asks exactly the same question and claims that such a situation can never arise (cross-validation accuracy will be 50%, not 100%). So far I am not convinced, I will run some simulations myself. [Update: they are right; see below.]