Why leave-one-out cross validation fails to detect overfit? I have an extremely simple classification problem. My data-set looks like this:
| feature | target |
| A       | 1      |
| A       | 1      |
| B       | 0      |
| A       | 0      |
....................
| A       | 0      |
| B       | 0      |
| A       | 1      |

As you can see the feature cant take only two values (A and B) and the target is always either 0 or 1. My goal is to predict probability of target = 1 given a value of the feature.
I construct a data set such that probability of target = 1 does not depend on feature and is equal to 0.5. I have generated a data set in which feature is equal to A 1000 times and equal to B also 1000 times.
Just by chance for the feature = A 1 is observed 515 times out of 1000 and for the feature = B 1 is observed 482 times out of 1000.
I have two alternative models. The first one states that probability of target = 1 does not depend on values of the feature (this model is correct per construction). The second model states that probability of target = 1 depends on the value of the feature (this model is an overfit per construction).
Now assume that I run a standard leave-one-out cross validation to find out if the second model is an overfit or not. When I take one observation with feature = A out, the number of 1s for feature = A will fluctuate between 515 and 514 and, therefore, the predicted probability for A will be either 515 / 999 or 514 / 999, which is very close to in-sample probability (515 / 1000). So, the second model will be better than the first model not only in-sample but also out-of-sample (obtained via leave-one-out cross validation)!
So, it means that we were not able to detect an over-fit with the leave-one-out procedure and the second model, which has smaller predictive power, wins the first model, which has better predictive power.
Is it a known problem? How to deal with this? Is there a procedure that is free of errors like this?
I understand that one could run a test that checks if there is statistically significant difference between probability of 1 for different values of features but my question is about cross-validation and leave-one-out specifically. For more complex data we do not have a test, we run a cross-validation there and I want to be sure that for those more complex cases the cross-validation does not fool me like in the described simple case.

The problem here is that your dataset is a bit of an outlier in the population of datasets from the stated data generating process, in that the feature is more correlated with the target than average.
If the feature and target were randomly generated with equal probabilities, then the probability that the feature matches the target is a Bernoulli trial with probability 0.5.  In this case, out of 2000 samples, there are 1033 = 515 + (1000 - 482) "successes", and I think the probability of there being 1033 or more "successes" from 2000 trials is only about 0.073.
Now the statistical distribution for the "test set" in each fold of the leave-one-out data is the same as that for the "training set", so the test data is also an unlikely sample from the true data generating mechanism, so it can't be expected to give the "right" answer.
There is nothing wrong with leave-one-out cross-validation, the problem lies with being unlucky in the sample of data you have obtained.
One thing you might want to do is to compute the Bayes factor comparing the two hypotheses, which I suspect would tell you that the evidence is not strongly in favour of either hypothesis, which is reasonable as the difference is only in 33 of the 2000 observations.
Another way of looking at this would be to use NHSTs and consider the power of the test, which would probably be rather low.  If you took either model as H0 in the test, you would be unable to reject it, which indicates that there isn't enough data to be confident of a difference in performance between the models.  Essentially you need a lot of data to be able to be "confident" that a very small effect (such as this one) is not a random artefact.
The key point is that cross-validation can provide evidence of over-fitting, it does not itself provide a reliable indicator of over-fitting.  You need to consider the uncertainties involved.
