<p>The article by Goppa you're referring to is presumably</p>

<blockquote>
  <p>Goppa, V.D. (1975) Nonprobabilistic mutual information without memory. <em>PCIT</em> <strong>4</strong>, 97-102.</p>
</blockquote>

<p>from <em>Problems of Control and Information Theory</em> and is available <a href="http://real-j.mtak.hu/7983/" rel="nofollow noreferrer">online</a>.</p>

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

<blockquote>
  <p>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))$.</p>
  
  <p>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)$.</p>
</blockquote>

<p>The definition of the "Fitingoff weight" mentioned here is given in</p>

<blockquote>
  <p>Goppa, V.D. (1975), Universal Decoding for Symmetric Channels, <em>Problems Inform. Transmission</em>, <strong>11</strong>:1, 11–18.</p>
</blockquote>

<p>which is also available <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=ppi&amp;paperid=1567&amp;option_lang=eng" rel="nofollow noreferrer">online</a>.</p>

<p>The relevant excerpt, translated from Russian is:</p>

<blockquote>
  <p>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 <em>composition</em> of $x$. The <em>quasi-entropy</em> or <em>Fitingoff weight</em> 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)$.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2018-04-09T19:46:43.467Z
2018-04-09T19:46:43.467Z
NikiC
<p>I agree with @usul. I've also never seen the term <em>empirical mutual information</em> mentioned, but I've seen the term <em>empirical entropy</em> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-29T02:05:34.290Z
2016-01-29T02:05:34.290Z
greg
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-28T17:30:35.560Z
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
CC BY-SA 3.0
2017-09-29T12:33:41.073Z
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
<it.information-theory>
What is empirical mutual information?
luegofuego
# What is empirical mutual information?

(Asked by: username_0 on 2016-01-27)

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.

**Tags:** it.information-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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_.  

---

## 2 answers

### Answer by username_3 on 2018-04-09. Score: 3 | Accepted answer

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](http://real-j.mtak.hu/7983/).

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](http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1567&option_lang=eng).

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.


---

### Answer by username_4 on 2016-01-29. Score: 6

I agree with @username_1. 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 @username_1 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.


---

