Classification when Learning is not Feasible

Consider classification problems, where attributes do not give any information about the class label. I do not know what kind of behavior to expect when running a classification algorithm in this setting (let's assume ID3 decision trees for simplicity). The decision tree constructed should be some kind of "empty" model, because it's even less than a decision stump (i.e. In practice, the model is likely to fit the noise, and find some kind of pattern that does not exist. The algorithm could still manage to come up with some decision tree on data that is in actual fact random.