4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – whuber
    Nov 6, 2017 at 14:55
  • $\begingroup$ Actually there is, see the answer below :) $\endgroup$
    – quant_dev
    Nov 6, 2017 at 16:04
  • $\begingroup$ 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." $\endgroup$
    – whuber
    Nov 6, 2017 at 16:41
  • $\begingroup$ 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. $\endgroup$ Nov 7, 2017 at 18:46

1 Answer 1

4
$\begingroup$

It is not a simple problem but special cases have been researched intensively and some techniques are quite mature.

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

Additional notes:

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.