# Question about calculating mutual information

I have two vectors $x,y \in \mathbb{R}.$ Based on the count and vector length I can compute $p(x)$ and $p(y)$ but I have no information on the joint density. How can I calculate mutual information in this case?

• What do you mean by $p(x)$ and $p(y)$? What are you counting? How exactly did these vectors arise--what are they modeling? – whuber Jul 20 '12 at 12:41
• Imagine I have two vectors $x = \begin{pmatrix} -1 \\ -2 \\ -3 \\ 1 \\ 2 \\ 3 \end{pmatrix}$ and $y = \begin{pmatrix} 1 \\ 4 \\ 9 \\ 1 \\ 4 \\ 9 \end{pmatrix}.$ If I were to compute the correlation I need to evaluate $\frac{E\left[(x-\mu_x)(y-\mu_y)\right]}{\sigma_x \sigma_y}$ which I can readily compute from vectors $x,y$ to obtain $corr(x,y) = 0.$ However, for mutual information I need $p(x)$ which I have (p(x=-1) = 1/6, p(x=-2)= 1/6, p(x=-3)= 1/6, p(x=1)= 1/6, p(x=2)= 1/6, p(x=3) = 1/6 and $p(y)$ which I also have p(y=1)=1/3, p(y=4)=1/3, p(y=9)=1/3... – user1137731 Jul 20 '12 at 13:22
• and inferred based on the empirical frequencies counting occurrences and taking the vector length into account. However, then I have no information on the joint density $p(x,y).$ How could I calculate mutual information then? – user1137731 Jul 20 '12 at 13:22
• You seem to be confusing vectors, random variables, and paired observations. Mathematically they may look similar, but they function quite differently. In this case it seems you intend your "vectors" really to be paired observations, whence your "$p$" is really an observed frequency, not a probability. But because you have paired data, you can just as readily estimate the joint density: it's the empirical joint density of $(x,y)$. – whuber Jul 20 '12 at 13:25
• Indeed, I would like to use the observed frequencies to model $p(x)$ and $p(y).$ For my example above, could you please give me pointers on how to compute it as example? – user1137731 Jul 20 '12 at 13:37

The Mutual Information of two discrete random variables $X$ and $Y$ taking values in $R_X$ and $R_Y$ respectively is the difference between the expectation of $\log p(x,y)$ (the logarithm of the joint probability of $(X,Y)$) and the expectation of $\log\left(p(x)p(y)\right)$ (which would be the joint probability for independent variables having marginal probabilities of $p(x)$ and $p(y)$).

When the vectors constitute an iid sample of $(X,Y)$, we can compute the mutual information of their joint empirical density. This is just the observed frequency: if a particular combination of values $(x,y)$ occurs $k(x,y)$ times in the dataset out of $n$ total occurrences, the empirical density $\hat{p}(x,y)$ is just the ratio $k(x,y)/n$.

To compute expectations with respect to the empirical density, let's introduce some notation. Let $R$ ("rows") be the set of distinct observed values of $X$ and $C$ ("columns") the set of distinct observed values of $Y$. For $x\in R$ and $y\in C$, $k(x,*) = \sum_{y\in C}k(x,y)$ is the row sum, counting all elements of the dataset whose first component is $x$. Likewise, $k(*,y) = \sum_{x\in R}k(x,y)$ is the column sum. These determine the marginal densities. Notice that the sum of all the $k(x,y)$, the sum of all the $k(x,*)$, and the sum of all the $k(*,y)$ all count the elements of the dataset, whence they are all equal to $n$. The mutual information equals

\eqalign{ &\sum_{x\in R, y\in C} \frac{k(x,y)}{n} \left(\log \frac{k(x,y)}{n} - \log \left(\frac{k(x,*)}{n} \frac{k(*,y)}{n}\right)\right)\\ =&\frac{1}{n}\sum_{x\in R, y\in C}k(x,y)\left(\log k(x,y) - \log(n)\right)\\ &- \frac{1}{n}\sum_{x\in R}k(x,*)\left(\log k(x,*) - \log(n)\right) \\ &- \frac{1}{n}\sum_{y\in C}k(*,y)\left(\log k(*,y) - \log(n)\right) \\ =&\log(n) + \\ & \frac{1}{n} \left( \sum_{x\in R, y\in C}k(x,y)\log k(x,y) - \sum_{x\in R}k(x,*)\log k(x,*) - \sum_{y\in C}k(*,y)\log k(*,y) \right). }

The first equality is just exploiting properties of logarithms while the last equality is due to the sum-to-$n$ properties of the $k(,)$.

In the example, $n=6$, $R=\{-1,-2,-3,1,2,3\}$, $C=\{1,4,9\}$, all the $k(x,*)=1$, all the $k(*,y)=2$, and all the $k(x,y)$ are either $0$ or $1$. The mutual information equals

$$\log(6) + \frac{1}{6}\left(6 \times (1\times \log(1)) - 6\times(1\times \log(1)) - 3\times(2\times \log(2)) \right) = \log(3).$$

• (+1) It seems the important point for addressing the OP's concern may be to emphasize the necessity of observing $(X,Y)$ pairs. Observing only marginal counts tells you next to nothing about the (empirical) mutual information. – cardinal Jul 20 '12 at 14:34
• Indeed, based on his answer to my question on how to infer $p(x,y)$ we look at counts of $(x_i,y_i) \in \mathbb{R}^2, i \in \{1,\ldots,n\},$ i.e. the joint density is inferred the same way we count event occurrences for the marginal densities $p(x), p(y).$ Thanks whuber and cardinal! :) – user1137731 Jul 20 '12 at 20:39
• Note that the plugin estimator (given by whuber) can be severely biased. It is asymptotically unbiased, and it is the ML estimate, but it can be quite off when only a handful of observations are given. – Memming Jul 21 '12 at 14:51
• User1137731, I would caution you, adding my voice to that of @Memming, not to use this as an estimator of mutual information unless you have a lot of data, and even then you probably should do some careful smoothing and binning first. As far as being a computation of MI of the data goes, there's nothing in my analysis that required integer values: it works regardless. – whuber Jul 23 '12 at 14:17
• There exists a paper by Strimmer 'Entropy Inference and the James-Stein Estimator, with Application to Nonlinear Gene Association Networks' jmlr.csail.mit.edu/papers/volume10/hausser09a/hausser09a.pdf with an associated package 'entropy' cran.r-project.org/web/packages/entropy/index.html. But this approach seems to expect count data and not continuous data for vectors $x,y.$ – user1137731 Jul 26 '12 at 15:15