# Entropy estimation with fewer data lines than bins

Assume you have a variable $X$ that can take a big number of values (bins), say $2^{32}$, for example a 32-bits random number generator.

Assume you want to find an estimate of the (discrete) entropy of $X$ based on a sample of independent values. Standard estimation requires that you can estimate the probability $p(X=x)$ for all $2^{32}$ bins. Thus you need several samples per bin $x$: more than $2^{32}$ samples.

This does not work if you have (much) fewer samples. Assume $X$ is uniformly distributed in all $2^{32}$ bins (perfect random generator). You have a sample of $2^{20}$ values. Since most values appear only once in the sample, the (naive) estimate of the entropy would be:

$$h\approx\sum_{2^{20}\text{ times}} -log_2\left(\frac{1}{2^{20}}\right)\frac{1}{2^{20}}\approx 20$$

It's very far from true entropy 32.

I wonder if there is still a way to do with much fewer than $2^{32}$ samples possibly with additional theoretical assumptions.

For example, if you assume $X$ is uniform on a subset of $m$ of all $2^{32}$ bins (entropy is then $\log_2(m)$), the average number of coincidences (number of lines whose value appears a least twice in the sample) for a sample of size $n$ is approximatively $k=\frac{n^2}{m}$ (mean) when $n$ is quite smaller than $m$.

Thus maybe $log_2(\frac{n^2}{k})$ could be used as an estimate for the entropy. You would need $n^2$ to be only several times bigger than $m$ which requires a small $n$.

I wonder if there are any ideas in this direction? Or is it definitely something believed to be impossible?

A classical method is NSB. It is a mature and efficient Bayesian method to estimate the entropy with a sample size around $2^{H/2}$ instead of $2^H$. There is a nice introductory text in this site: http://www.nowozin.net/sebastian/blog/estimating-discrete-entropy-part-3.html. There are a few comments by the inventor of NSB, that points out that NSB actually relies on counting the number of coincidences.