# Number of needed samples for entropy estimation

I would like to estimate the entropy of a source generating binary vectors of length M which are very sparse (just a few 1s), using the naive (empirical) estimator $\hat{H}=-\sum\hat{p}(x)\log\hat{p}(x)$.

Is there some result on the number of samples needed to do this with certain precision, or equivalently, the error in calculating this value given finite number of samples?

Entropy estimation is a surprisingly difficult problem. The fundamental issue is that your estimate is heavily biased by "unobserved" events (which nevertheless have nonzero probability).

There are quite a few different entropy estimators designed specifically to address this problem. For instance, see the BUB esimator by Liam Paninski, the NSB estimator by Nemenman et al, the coverage-adjusted estimator by Vu et al (also see Chao et al, 2003), and the PYM estimator by Archer et al.

There are many other papers that address the problem. Each has a somewhat different approach, and some may be more appropriate under different situations. Several of the papers I suggest provide free code online which automatically computes an estimate and measure of confidence. You may also be interested in this and the R package 'entropy'.

You need to apply standard propagation of uncertainty (in the non-linear case) to Poisson distribution (i.e. assuming that each count is independent).

That is, you need to expand $H(p_1+\Delta p_1, \ldots, p_n + \Delta p_n)$ in Taylor series of $n$ variables $(\Delta p_1,\ldots ,\Delta p_n)$ around $(0,\ldots, 0)$, i.e.: $$H(p_1+\Delta p_1, \ldots, p_n + \Delta p_n) =H(p_1,\ldots,p_n)-\frac{1}{\ln2}\sum_{i=1}^n (\ln p_i+1)\Delta p_i -\frac{1}{2\ln2} \sum_{i=1}^n p_i^{-1} \Delta p_i^2 + \ldots$$

Remembering that $p_i = \frac{N_i}{N}$ and calculating appropriate moments to as many terms as you want.

However, it does not work around $p_i=0$, as it has no Taylor expansion here. In such cases the only possibility I know is Monte Carlo - you estimate parameters of distributions, take random distributions and then take random results according to them and look at the distribution of results (here: entropy).

• In general, rare events are going to cause a giant problem for using MLE estimates of entropy, because lim x->0+ log(x) is inf. If you ever assign probability 0 to an event that actually happens, you have suffered infinite loss. – rrenaud Nov 3 '12 at 2:12
• @rrenaud For zero the error is not infinite (only Taylor expansion does not work here). It should be sth like $\log(N)/N$ (or maybe even less, for this case, e.g. $\log(\min(n,N))/\min(n,N)$, but I'm not sure). Of course, the problem arrises when you have a lot $p_i=0$ entries. In particular when you have infinite number of states $n=\infty$ and finite number of total counts $N$, the error is infinite (unless you make some more assumptions on the distribution of probabilities). – Piotr Migdal Nov 3 '12 at 10:49
• Yeah, I am very wrong, tried to apply intuition about cross entropy between two distributions to this, and it breaks down. – rrenaud Nov 3 '12 at 16:11