derivation of mutual information

The maximum likelihood estimater for mutual information is identical (except for a scale factor) to the generalized log-likelihood ratio for multinomials and closely related to Pearson’s${\chi }^2$ test. This implies that the distribution of observed values of mutual information computed using maximum likelihood estimates for probabilities is ${\chi }^2$ distributed except for that scaling factor.

In particular if we sample each of $X$ and $Y$ and combine the samples to form $N$ tuples sampled from $X\times Y$. Now define $T(x,y)$ to be the total number of times the tuple $(x,y)$ was observed. Further define $T(x,*)$ to be the number of times that a tuple starting with $x$ was observed and $T(*,y)$ to be the number of times that a tuple ending with $y$ was observed. Clearly, $T(*,*)$ is just $N$, the number of tuples in the sample. From the definition, the generalized log-likelihood ratio test of independence for $X$ and $Y$ (based on the sample of tuples) is

$$-2log\lambda =2\sum _{xy}T(x,y)\log \frac{{\pi }_{x|y}}{{\mu }_x}$$

where

$${\pi }_{x|y}=T(x,y)/\sum _{x}T(x,y)$$

and

$${\mu }_x=T(x,*)/T(*,*)$$

This allows the log-likelihood ratio to be expressed in terms of row and column sums,

$$-2log\lambda =2\sum _{xy}T(x,y)\log \frac{T(x,y)T(*,*)}{T(x,*)T(*,y)}$$

This reduces to the following expression in terms of maximum likelihood estimates of cell, row and column probabilities,

$$-2log\lambda =2\sum _{xy}T(x,y)\log \frac{{\pi }_{xy}}{{\mu }_{*y}{\mu }_{x*}}$$

This can be rearranged into

$$-2log\lambda =2N\left[\sum _{xy}{\pi }_{xy}\log {\pi }_{xy}\sum _x{\mu }_{x*}\log {\mu }_{x*}\sum _y{\mu }_{*y}\log {\mu }_{*y}\right]=2N\widehat{I}(X;Y)$$

where the hat indicates a maximum likelihood estimation of $I(X;Y)$.

This also gives the asymptotic distribution of $\widehat{I}(X;Y)$ as $2N$ times a ${\chi }^2$ deviate.