# Bounding mutual information given ROC curve statistics

When evaluating a binary classifier, the basic data are as in this contingency table, where rows represent groundtruth value and columns represent the estimated value: $$\begin{matrix} & + & - \\ \hline + & a & b \\ - & c & d \end{matrix}$$ where $a$ is the number of true positives, $c$ the number of false positives, etc. This information is often summarised on a ROC curve using the "true positive rate" and "false positive rate" statistics: $$t = \frac{a}{a+b} \\ f = \frac{c}{c+d}$$ and from this we can calculate single values which summarise the performance, such as Area Under the Curve (AUC) (with only one contingency table, we can use $\text{AUC} = (t-f+1)/2$).

Another thing we could calculate is the mutual information between the estimated values and groundtruth values. This is a classic statistic that would tell us about the probabilistic relationship between our estimates and the groundtruth. In this case: $$I = \frac{a}{n}\log{\frac{a n}{(a+b)(a+c)}} + \frac{b}{n}\log{\frac{b n}{(a+b)(b+d)}} + \frac{c}{n}\log{\frac{c n}{(c+d)(a+c)}} + \frac{d}{n}\log{\frac{d n}{(b+d)(c+d)}}$$ where $n=a+b+c+d$ and $0\log(0)=0$.

Calculating mutual information is straightforward if we know $a, b, c, d$. But what if we know only $t$ and $f$?

Clearly if all we know is $t$ and $f$ we can't directly calculate the mutual information, because the relative scale between $a$ and $b$ on one hand, and $c$ and $d$ on the other, isn't captured. But we must be able to lower-bound it. Here's a plot from random samples showing the relationship between AUC and mutual information: I've tried a few ways of writing out the mutual information but not been able to get it into a form where $t$ and $f$ lead to interesting bounds. Can you?

We know that the mutual information is upper-bounded by the entropy of either of the marginal distributions (at least for discrete distributions, as here). So the maximum possible value for $I$ is when the ground-truth is fiftyfifty split between $+$ and $-$, i.e. when $a + b = c + d = n/2$. (In that case the entropy comes out as $\log(2)$.)
So, consider the case of $a + b = c + d = n/2$. In that situation we have the following: $$a = \frac{n t}{2}, \quad b = \frac{n(1-t)}{2}, \quad c = \frac{n f}{2}, \quad d = \frac{n (1-f)}{2},$$ which can be substituted into the expression for $I$ given in the OP. After some rearrangement, this gives us $$I_{\text{fiftyfifty}} = \frac{1}{2}(2\log(2) + t\log(t) + f\log(f) - (t+f)\log(t+f) + (1-t)\log(1-t) + (1-f)\log(1-f) + (2-f-t)\log(2-f-t))$$
If we evaluate this in the ideal case (perfect prediction means $t=1$ and $f=0$), we get a value for $I_{\text{fiftyfifty}}$ as $\log(2)$, the maximum attainable. Any other choices for $t$ and $f$ lead to lower values.
Therefore in the fiftyfifty case, the maximum possible mutual information is attainable for a specific choice of $t$ and $f$; and because the mutual information is bounded by the entropy, and all other binary distributions have a lower entropy than the fiftyfifty case, there is no other case that can reach this maximum.
I haven't yet shown that $I_{\text{fiftyfifty}} \ge I$ for all possible choices of $t$ and $f$. Nor have I expressed a bound directly in terms of the AUC value, which was not my question but is an optional extra.