0
$\begingroup$

Suppose we have two independent variables X and Y. Intuitively the mutual information, I(X,Y), between the two should be zero, as knowing one tells us nothing about the other.

The math behind this also checks out from the definition of the mutual information (https://en.wikipedia.org/wiki/Mutual_information).

Now let us compute it actually. First generate two simple random vectors of length 10 in R:

X=sample(seq(1,100),10)
Y=sample(seq(1000,10000),10)

I got these:

X={3, 35, 93, 13, 90, 89, 34, 97, 49, 82}
Y={7611, 5041, 2612, 4273, 6714, 4391, 1000, 6657, 8736, 2443}

The mutual information can be expressed with the entropies H(X), H(Y) and the joint entropy between X and Y, H(X,Y)

I(X,Y) = H(X) + H(Y) - H(X,Y)

Moreover

H(X) = -10*[(1/10)*log(1/10)] = log(10)

since each observation occurs only once and thus has a frequency of 1/10 of occurring. The maximum entropy for a random variable of length N is log(N) so this calculation checks out.

Similarly

H(Y) = log(10)

The joint entropy is similar to the individual entropies but this time we count the frequencies of pairs occurring. For example the pair {X=3,Y=7611} occurs only once out of a total of 10 paired observations, hence it has a frequency of 1/10. Therefore:

H(X,Y) = -10*[(1/10)*log(1/10)] = log(10)

since each paired observation occurs only once.

So

I(X,Y) = log(10) + log(10) - log(10) = log(10)

which is clearly non-zero. This is also the result that various R packages (e.g. infotheo) produce.

The question is where is the mistake in my thinking? Why is I(X,Y) not zero?

$\endgroup$
  • $\begingroup$ I don't understand what are you doing here. $X$ , as a random variable, is a single integer value, of which you generate 10 samples? Why do you generate it by sampling from a sequence? $\endgroup$ – leonbloy Oct 24 '15 at 13:08
0
$\begingroup$

Notice how in the formula of Mutual Information there are probabilities, not frequences. A frequency is just an approximation of probability, and with a sample so small, you get very inaccurate approximations, hence the result.

In order to calculate the Mutual Information of a discrete random variable X uniformly distributed over [1,100] and an independent random variable Y uniformly distributed over [1000, 10000], you calculate:

H(X) = -100*[(1/100)*log(1/100)] = log(100)

H(Y) = -9001*[(1/9001)*log(1/9001)] = log(9001)

H(X,Y) = -(900100)*[(1/900100)*log(1/900100)] = log(900100)

I(X,Y) = log(100) + log(9001) - log(900100) = 0

What you have actually calculated is the Mutual Information of two discrete random variables with the following joint probability distribution:

p(3, 7611) = 0.1

p(35, 5041) = 0.1

p(93, 2612) = 0.1

p(13, 4273) = 0.1

p(90, 6714) = 0.1

p(89, 4391) = 0.1

p(34, 1000) = 0.1

p(97, 6657) = 0.1

p(49, 8736) = 0.1

p(82, 2443) = 0.1

These variables are not independent; in fact, knowing one of the values is sufficient to find the other one. That is why their Mutual Information is not zero.

$\endgroup$
1
$\begingroup$

I believe you were on the correct path but you did a small mistake while calculating the joint entropy. There will be 100 unique pairs of symbols so the joint entropy will be $\log 100$, that will make the mutual information equal to zero.

$\endgroup$
  • $\begingroup$ Which would mean that all R packages that compute this do it wrong. I am somewhat skeptical about that. $\endgroup$ – Pavlin Mavrodiev Oct 22 '15 at 8:21
  • $\begingroup$ More precisely, I don't think we have 100 pairs.We only have the pairs we actually observe, i.e. we have the pair {X=3,Y=7611},but not the pair {X=3,Y=5041}. Alternatively if you want to count all possible permutations as number of pairs, then the probability of observing the pair {X=3,Y=5041} is 0, because we never observed it in the data. I think the calculation is correct, i.e. mutual info should not be 0 after you observe data, since the mere fact of observing something is information. So this points to a conceptual misunderstanding on my side, which I am not perfectly clear about. $\endgroup$ – Pavlin Mavrodiev Oct 22 '15 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.