Scratch pad → AUC-ROC as the fraction of correctly ranked positive-negative pairs

The area under the receiver operating characteristic curve (AUC-ROC) is typically defined in terms of the true positive and false positive rates: it is the area under the curve traced by the true positive rate against the false positive rate as the decision threshold varies. Today I learnt that there exists an equivalent (and simpler) formulation: the fraction of positive-negative pairs that are ranked in the correct order (the score of the positive sample is greater than that of the negative one). Put mathematically, if $N_+$ and $N_-$ denote the number of positive and negative samples, and $s_i$ the score of sample $i$, we have:

$$ \mathrm{AUC} = \frac{1}{N_+ N_-}\sum_{i\in\text{pos}}\sum_{j\in\text{neg}}\mathbf{1}(s_i > s_j) $$

Note: Ties ($s_i = s_j$) are usually counted as half-correct (assigned a score of 0.5); with this convention, the formula matches exactly the area under the ROC curve.

This formulation makes it easy to see why two common properties of the metric hold:

the metric is invariant to the class prevalence (i.e., the fraction of positives), since it averages over pairs and never compares the two class sizes;
a random classifier has an expected AUC of 0.5, since each pair is ranked correctly with probability 1/2.

This formulation also allows us to compute the AUC analytically in certain cases. For example, consider this exercise:

Assume that we have $2N$ samples ($N$ positive and $N$ negative) that are scored and have an AUC-ROC of $a$. Assume, moreover, that we have $M$ negative samples that get scores lower than any of those $2N$ samples, and $M$ positive samples that get scores larger than any of those $2N$ samples. So, sorting the samples by score in increasing order, we have something like:
- - - ... - + - - + + - + ... + + +
←   neg   →←   mixed   →←   pos   →
What is the AUC over the entire set of $2N + 2M$ samples?

Solution

We count the positive-negative pairs that are ranked correctly:

each of the $M$ top positives ranks above all $N + M$ negatives, giving $M(N + M)$ correct pairs;
each of the $N$ middle positives ranks above the $M$ bottom negatives, giving $MN$ correct pairs;
the middle positives and negatives give $aN^2$ correct pairs by definition.

Dividing by the total number of pairs, $(N + M)^2$, we obtain:

$$ \mathrm{AUC} = \frac{M^2 + 2MN + aN^2}{(N + M)^2} $$

By making the square in the numerator, we get:

$$ \mathrm{AUC} = 1 - (1 - a)\left(\frac{N}{N + M}\right)^2 $$

As sanity checks, for $M = 0$ we recover $a$, and as $M \to \infty$ the AUC tends to 1.