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?
