I read this caption in a paper and have never seen AUC described in this way anywhere else. Is this true? Is there a proof or simple way to see this?

Fig. 2 shows the prediction accuracy of dichotomous variables expressed in terms of the area under the receiver-operating characteristic curve (AUC), which is equivalent to the probability of correctly classifying two randomly selected users one from each class (e.g., male and female).

It seems to me that it can't be true, since for AUC = 0.5, the above would suggest one has a 50% probability of correctly predicting a coin flip twice in a row, but in reality, you only have a 25% chance of correctly predicting two coin flips in a row. At least, that's how I'm thinking of this statement.