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?
 A: 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'.
A: 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).
