Smallest possible difference between AUC of two ranker

Question

If there are 10 positive examples, and 90 negative examples in the test set, what is the smallest possible difference in AUC, between two rankers giving different AUC?

Answer 1

If rankers aren't allowed to give ties, then the minimum positive differences in AUROC for two rankers on a population with $N$ negative and $P$ positives examples is $1/(NP)$. The ROC space for such a population is a $(N+1)\times(P+1)$ grid of points, because the true positive rate and false positive rate have denominators $P$ and $N$ respectively. Without ties, the ROC curves consist of axis-aligned segments joining these points, and so the area is a collection of full grid squares (there are $N\times P$ such squares). Finding two curves that differ in exactly one square is pretty easy.

If rankers are allowed to give ties, then the minimum positive difference is $1/(2NP)$, from a simple observation related to Pick's theorem, namely that a polygon with integer coordinates has half-integer area. Scaling our grid to integers and back, the 1/2 gets scaled by $1/(NP)$. Then it's just up to us to find two curves realizing that. The perfect ROC curve and one almost-perfect one works, namely having just the two nontrivial points $(FPR, TPR)=(0, 1-1/P)$ and $(1/N, 1)$. In terms of the ranking, that's something like $(0<0<\dotsc<0<0<1=0<1<1<\dotsc<1)$.