0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

More general cases of entropy estimation is covered in the answer to this very similar question : https://math.stackexchange.com/questions/604654/estimating-the-entropy

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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