If two random variables $X, Y$ have high mutual information $I(X;Y)$, intuitively does that mean $X,Y$ have almost deterministic relationships, say $Y=f(X)+\epsilon$ where $\epsilon$ is a noise random variable?
If this is true, can we prove this relationship?
You’re on the right track, but I am hesitant to go that far.
Consider variables forming a perfect “X” scatterplot. In that case, given one one of the variable values, you can narrow it down to two possibilities for the other value. That is, knowing the value of the one variable gives you tremendous information about the value of the second variable, thus, high mutual information between the two variables.
However, those two possible values could be quite far apart, so I am hesitant to go as far as to consider the relationship (nearly) deterministic, even if there is technically a way to write $\epsilon$ to accommodate the uncertainty about which of the two possible values the other variable would take.
The way I think about mutual information is that knowing the value of one of the marginal variables tightens up your sense of where the value of the other marginal variable would be. In my example, instead of just knowing the value to be somewhere on the infinite number of values on the “X”, you know that it is one of two values.
In addition to the answer by @Dave, I will give an example showing that a deterministic (or one-to-one) relationship is not always possible. I will use a categorical data example, so the joint distribution can be given by a two-way table. But first, one formula for the mutual information is $$ I(X, Y) = H(X) + H(Y) - H(X, Y) $$ where $H$ is the Shannon entropy, with one argument the marginal, with two arguments the joint. If $X, Y$ are independent, then $H(X,Y)= H(X)+H(Y)$, so then the mutual information is zero, the minimum possible value.
But you ask for maximizing mutual information, so intuitively, to go as far away from independence as possible. And we cannot get further away from independence than a one-to-one relationship. So, to maximize mutual information (say, with the two marginals given) we must minimize $H(X, Y)$.
First, one example where a 1-1 relationship is possible:
| 0.5 | 0.5 | |
|---|---|---|
| 0.5 | ||
| 0.5 |
This shows only the two marginals. There are multiple joints that fulfills the conditions, just fill in two 0.5, two 0, with one 0 in each row and each column. Then an example where it is impossibe to fill in a solution which is 1-1:
| 0.2 | 0.2 | 0.2 | 0.2 | 0.2 | |
|---|---|---|---|---|---|
| 0.4 | |||||
| 0.6 |
