Who coined the term "empirical entropy"?

Question

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?

Answer 1

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