Question about calculating mutual information

Question

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?

Answer 1

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).$$