# Entropy of a non-representative sample of discrete distribution

Let $X$ be a discrete random variable which can take $K$ distinct values. Let $S$ be a random i.i.d. sample of $X$ containing $n$ values, $n \ll K$. What can be said about the relation between the entropy of true distribution of $X$ and the entropy of the empirical distribution calculated from sample $S$? Are there any scaling laws?

• Since $n\ll K$, then with extremely high probability the sample consists of $n$ distinct values, whence you would compute its entropy as $\log(n)$. It doesn't seem there's much more to say...
– whuber
Nov 6, 2017 at 14:55
• Actually there is, see the answer below :) Nov 6, 2017 at 16:04
• Thank you--that answer helps me appreciate that you're not focusing on a uniform variable $X$, which is how I first read your question. Thus my conclusion that the sample would have $n$ distinct values with high probability was wrong. What confused me was your characterization of the sample as "non-representative." I still cannot see in what sense that would be true: you seem to use that simply as a synonym of "small."
– whuber
Nov 6, 2017 at 16:41
• I think that even if $X$ is (close to) be uniformly distributed ($K\approx 2^S$), advanced entropy estimation methods work when $n<<K$. Typically with $n>\sqrt K$. I added a few notes in my answer. Nov 7, 2017 at 18:46

Most of them assume a certain structural property about the distribution of $X$ (often stated as a Bayesian prior). The most classical case is when $X$ is "a word chosen in usual language". Some techniques work very well with small $n$ (compared to $K$ that is total vocabulary size). This applies to a variety of situations (not just language).
There is a very good summary of entropy estimation methods (when $n≪K$) here: https://math.stackexchange.com/questions/604654/estimating-the-entropy
I've only looked at NSB so far. A rule of thumb is that NSB starts providing useful results when $n$ is above $2^{S/2}$ while a naive method works only when $n$ is above $2^S$. It relies on exploiting the number of collisions. This text is an easy to read introduction ot NSB: http://www.nowozin.net/sebastian/blog/estimating-discrete-entropy-part-3.html. I don't mean I recommend NSB over other methods, I'm far from being an expert in all this. I have asked the same question as you a while ago, and my naive thoughts about it may be of some use: Entropy estimation with fewer data lines than bins