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.

What happens here is that you compare one model that you know to be the true one with fixed true parameters to another model that will estimate these parameters. Obviously if you fix the parameters at the true values, you will normally be better on new data than if you estimate the parameters. But with a certain probability, any model selection method will select the model with estimated parameters, so will appear to be overfitting. This is not a specific problem with LOO-CV but applies to any model selection approach. If you compare a simpler model that you know to be true with a more complex model, the more complex model can be selected with a probability that is not negligible, in which case overfitting takes place.
If you set up the problem so that underfitting cannot happen, you will overfit with a certain probability and underfit with probability zero, so on average overfitting will happen. Only if you also look at what happens in case the more complex model is true you get a fair assessment of the model selection procedure.
Note furthermore that LOO-CV is known to be asymptotically equivalent to the AIC, which even asymptotically will overfit, see https://www.jstor.org/stable/2984877 (Note that I haven't made an effort to check whether potential assumptions in that paper apply here.)
The AIC (and equivalently LOO-CV) is however asymptotically good at finding an optimal prediction rule (for which overfitting is not as bad as underfitting). Note that in the given setup, if you just try to predict the target 1 or 0, rather than predicting their probabilities, any rule will be wrong 50% of the time, so that the "overfitted" model will not be worse than the true one when it comes to point prediction.
