# What is empirical mutual information?

The topic says it all - I've been seeing this referenced a few times in information theory literature (Feedback in the non-asymptotic regime, Y. Polyanskiy et. al. among others), oftentimes making mentions to an article by a guy called Goppa. I've not seen it defined in any of the referencing articles and the article is nowhere to be found online.

So, can anyone tell me what it is? A reasonable guess would be that it relates to information density, i.e. $i(x;y) = \log \frac{p(x,y)}{p(x)p(y)}$, but it's hard to say.

EDIT: There seems to be consensus as to what it SHOULD mean at least, i.e. basically the average information density, i.e. $\sum \log \frac{p(x_i,y_i)}{p(x_i)p(y_i)}$ where we're summing over observations. Not going to accept however as I am looking for a definite statement.

• Mutual information is $\sum_{x,y} p(x,y) i(x,y)$, so maybe it is simply replacing $p$ in this formula with the empirical distribution $\hat{p}$, where: Given some set of samples, $\hat{p}(x,y) := \frac{\text{# times$(x,y)$appears}}{\text{total # of samples}}$. But this is just a guess. – usul Jan 28 '16 at 17:30
• I have seen the mutual information of two random events defined exactly as you suggested in Bahl et al. (1986). Maximum Mutual Information Estimation of Hidden Markov Model Parameters for Speech Recognition. – Seppo Enarvi Sep 29 '17 at 12:33

The article by Goppa you're referring to is presumably

Goppa, V.D. (1975) Nonprobabilistic mutual information without memory. PCIT 4, 97-102.

from Problems of Control and Information Theory and is available online.

The article is in Russian, but there is an English summary attached, which starts as follows:

Let $X$, $Y$ be finite alphabets, $x = (x_1, x_2, \dots, x_n)$, $у = (y_1, y_2, \dots, y_n)$, $x_i \in X$, $y_i \in Y$, $i = 1, 2, \dots, n$. Construct the word $x \otimes y \in (X \otimes Y)^n$ as follows: $x \otimes y = ((x_1y_1), (x_2y_2), \dots, (x_ny_n))$.

Define $\Phi(x : y) = \Phi(x) + \Phi(y) - \Phi(x \otimes y), \Phi(y/x) = \Phi(х \otimes y) - \Phi(x)$, where $\Phi(x)$ is the Fitingoff weight of $x$. The following of their properties are readily verified: (а) $\Phi(x : y) = \Phi(y : x)$; (b) $\Phi(x : x) = \Phi(х)$; (с) $\Phi(x : y) = \Phi(x) - \Phi(x/y) = \Phi(y) - \Phi(y/x)$.

The definition of the "Fitingoff weight" mentioned here is given in

Goppa, V.D. (1975), Universal Decoding for Symmetric Channels, Problems Inform. Transmission, 11:1, 11–18.

which is also available online.

The relevant excerpt, translated from Russian is:

Let $a_i \in X$ occur in $x \in X^n$ exactly $m_i$ times ($i = 1, 2, \dots, N=|X|$). The sequence $(m_1, m_2, \dots, m_N)$ is called the composition of $x$. The quasi-entropy or Fitingoff weight is then given by $\Phi(x) = H(m_1/n, m_2/n, \dots, m_N/n) = -\sum_{i=1}^N (m_i/n) \log (m_i/n)$.

So the Fitingoff weight is what we would call the empirical entropy and $\Phi(x : y)$ is the empirical mutual information. The definitions given here match what was said in the other answer.

I agree with @usul. I've also never seen the term empirical mutual information mentioned, but I've seen the term empirical entropy quite a lot, especially in the compression community. The definition of empirical information is $-\Sigma p_i \log p_i$, where $p_i$ are the empirical probabilities, i.e. the fraction of the time that each value appears in your samples.

To compute empirical mutual information given samples $(x_1,y_1),\ldots,(x_n,y_n)$, I'd just compute the empirical entropy of the $x$'s separately, and of the $y$'s separately, and of the pairs together, and then I'd use the standard equation $I(X:Y)=H(X)+H(Y)-H(XY)$, where all quantities on the right hand side are replaced by their empirical analogue.

I don't know if this is equivalent to the equation that @usul gave, and I don't know if this is the quantity referenced in the articles you're reading, but this seems like the natural interpretation to me.