<p>I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment.</p>

<p>But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts: </p>

<ol>
<li>"Large Alphabets and Incompressibility" by Travis Gagie (2008)  </li>
<li>"Emprical entropy" by Paul M. B. Vitányi (2011)</li>
</ol>

<p>Gagie rephrase the definition of $k$th order empirical entropy to:  </p>

<ul>
<li>$H_{k}(w)=\frac{1}{|w|}\min\limits_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$</li>
</ul>

<p>where $Q$ is a $k$th order Markov process. He also showed that this definition is equivalent to the previous one.<br>
The next step from Vitányi was a generalization to arbitrary classes of processes (not only Markov-processes):</p>

<ul>
<li>$H(w|\mathcal{X})=\min\limits_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$</li>
</ul>

<p>where $\mathcal{X}$ is the class of allowed processes and $K(X)$ is the Kolmogorov complexity.<br>
If we choose $\mathcal{X}$ to be the class of $k$th order Markov processes producing  a sequence of $|w|$ random variables and ignoring the Kolmogorov complexity, than this also leads to the definition of Gagie (multiplied with $|w|$).</p>

CC BY-SA 3.0
2014-02-26T16:02:38.003Z
2014-02-26T16:08:43.967Z
2014-02-26T16:08:43.967Z
Danny
<p>I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which <em>empirical</em> entropy is often used as part of the storage analysis. </p>

<p>Shannon defined the entropy of the information produced by a discrete information source as $-\sum_{i=1}^k p_i \log{p_i}$, where $p_i$ is the probability of event $i$ occurring, e.g. a specific character generated, and there are $k$ possible events.</p>

<p>As pointed out by MCH in the comments, the <em>empirical</em> entropy is the entropy of the empirical distribution of these events, and is thus given by $-\sum_{i=1}^k \frac{n_{i}}{n} \log{\frac{n_{i}}{n}}$ where $n_{i}$ is the number of observed occurrences of event $i$ and $n$ is the total number of events observed. This is called <em>zero-th order empirical entropy</em>. Shannon's notion of <em>conditional entropy</em> has a similar <em>higher order</em> empirical version.</p>

<p>Shannon did not use the term empirical entropy, though he surely deserves some of the credit for this concept. Who did first used this idea and who first used the (very logical) name <em>empirical entropy</em> to describe it?</p>

CC BY-SA 3.0
2013-06-04T22:07:37.957Z
"pointwise defined for every string" sounds like Kolmogorov complexity: is that what you're referring to ? If not, can you point to a link that defines it, or better still provide a defn in the question itself ?
Suresh Venkat
CC BY-SA 3.0
2013-06-04T22:40:38.500Z
It is called so because empirical entropy is the entropy of the empirical distribution of a sequence.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-05T10:50:18.480Z
@SureshVenkat I've tried to elaborate the question.
deleted user 42
CC BY-SA 3.0
2013-06-05T14:24:06.833Z
Take a look to Kosaraju S. Rao, Manzini G., "Compression of low entropy strings with Lempel-Ziv algorithms" (1998), too. They analyze the performance of the Lempel-Ziv algorithms using the "*so-called empirical entropy*".
Marzio De Biasi
CC BY-SA 3.0
2013-06-05T14:38:35.723Z
Following my previous comment, instead of asking who coined the term "empirical entropy" you should ask who coined the term "empirical distribution". It's hard to think of any more natural term for empirical distribution, so I don't think there's a need to credit the term to anyone.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-05T18:15:02.530Z
@MarzioDeBiasi They also use wordings like _"We define k'th order empirical..."_. And they say that they use a different approach than previous by using the empirical distribution (at least for Lempel-Ziv).
deleted user 42
CC BY-SA 3.0
2013-06-05T19:51:10.067Z
Note that the "empirical distribution" is really the ML distribution for a given set of frequency counts. So I wonder if this dates back to Bayes. Even Laplace had pondered the problem of defining a distribution from empirical counts.
Suresh Venkat
<reference-request><shannon-entropy><succinct>
Who coined the term "empirical entropy"?
deleted user 42
# Who coined the term "empirical entropy"?

(Asked by: username_0 on 2013-06-04)

I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which *empirical* entropy is often used as part of the storage analysis.

Shannon defined the entropy of the information produced by a discrete information source as $-\sum\_{i=1}^k p\_i \log{p\_i}$, where $p\_i$ is the probability of event $i$ occurring, e.g. a specific character generated, and there are $k$ possible events.

As pointed out by MCH in the comments, the *empirical* entropy is the entropy of the empirical distribution of these events, and is thus given by $-\sum\_{i=1}^k \frac{n\_{i}}{n} \log{\frac{n\_{i}}{n}}$ where $n\_{i}$ is the number of observed occurrences of event $i$ and $n$ is the total number of events observed. This is called *zero-th order empirical entropy*. Shannon's notion of *conditional entropy* has a similar *higher order* empirical version.

Shannon did not use the term empirical entropy, though he surely deserves some of the credit for this concept. Who did first used this idea and who first used the (very logical) name *empirical entropy* to describe it?

**Tags:** reference-request, shannon-entropy, succinct
> **Comments:**
> **username_1**: "pointwise defined for every string" sounds like Kolmogorov complexity: is that what you're referring to ? If not, can you point to a link that defines it, or better still provide a defn in the question itself ?  
> **username_2**: It is called so because empirical entropy is the entropy of the empirical distribution of a sequence.  
> **username_0**: @SureshVenkat I've tried to elaborate the question.  
> **username_3**: Take a look to Kosaraju S. Rao, Manzini G., "Compression of low entropy strings with Lempel-Ziv algorithms" (1998), too. They analyze the performance of the Lempel-Ziv algorithms using the "*so-called empirical entropy*".  
> **username_2**: Following my previous comment, instead of asking who coined the term "empirical entropy" you should ask who coined the term "empirical distribution". It's hard to think of any more natural term for empirical distribution, so I don't think there's a need to credit the term to anyone.  
> **username_0**: @MarzioDeBiasi They also use wordings like _"We define k'th order empirical..."_. And they say that they use a different approach than previous by using the empirical distribution (at least for Lempel-Ziv).  
> **username_1**: Note that the "empirical distribution" is really the ML distribution for a given set of frequency counts. So I wonder if this dates back to Bayes. Even Laplace had pondered the problem of defining a distribution from empirical counts.  

---

## 1 answers

### Answer by username_4 on 2014-02-26. Score: 3

I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment.

But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts:

1. "Large Alphabets and Incompressibility" by Travis Gagie (2008)
2. "Emprical entropy" by Paul M. B. Vitányi (2011)

Gagie rephrase the definition of $k$th order empirical entropy to:

* $H\_{k}(w)=\frac{1}{|w|}\min\limits\_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$

where $Q$ is a $k$th order Markov process. He also showed that this definition is equivalent to the previous one.  
The next step from Vitányi was a generalization to arbitrary classes of processes (not only Markov-processes):

* $H(w|\mathcal{X})=\min\limits\_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$

where $\mathcal{X}$ is the class of allowed processes and $K(X)$ is the Kolmogorov complexity.  
If we choose $\mathcal{X}$ to be the class of $k$th order Markov processes producing a sequence of $|w|$ random variables and ignoring the Kolmogorov complexity, than this also leads to the definition of Gagie (multiplied with $|w|$).


---

