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.

Overfit meaning: you get better results on your train set then on your test set.

*

*There is no clear definition of a train / test set here


*lets assume we divide your uniformly dataset of 1000 data points into: 700 data points in the train set and 300 in the test set. becuse it is uniformly distributed, you can achieve an accuracy of ~0.5 on your train set. Now, you test your model on your test set. if the performance is about the same (we expect ~0.5 accuracy), this means there is no overfit in your model.


*regardless of the overfit question, an accuracy of ~0.5 mean that your model cannot predict very well (on any set)
