What adequate tools are available for estimating entropy?

Question

This question seems to touch on the apparent fact that NIST SP 800-90B is not suitable for estimating entropy produced by sources that are not uniform, despite being IID or non-IID. It also seems that most phenomena for producing entropy are not uniform. If that's indeed right, then naturally one wonders what adequate tools are available for estimating entropy?

Clarification. The question is asking for tools like NIST SP 800-90B. What programs are out there that are ready to use, hopefully with a publication to introduce it? It seems only NIST SP 800-90B is available.

Answer 1

I'm assuming that you're referring to physical entropy sources, rather than Shakespeare and such.

You can go the compressive approach using strong archivers as discussed elsewhere. However, that will always leave you with a feeling of whether it's accurate enough? And this is an uncommon approach though it works for me.

The standard way, is to simply calculate $H_{\infty}$ based on the most probable value in your data set. Autocorrelation? Remove it. So ironically, your tool is a pseudo random number generator. And ent.

There is the concept of $(\epsilon, \tau)$ entropy per unit time, where $\epsilon$ is the sampling resolution and $\tau$ is the temporal sample lag. And it goes like this:-

1. Sample source at $(\epsilon, \tau^{-1})$ per second. Eg. 4 bits @ 10 kSaS.
2. Perform IID test on sample using permutation testing.
3. If sample = IID, run ent -c and get ${Pr_{max}}$.
4. $H_{\infty} = -log_2(Pr_{max})$. Done.
5. If sample $\ne$ IID, reduce $\epsilon$ or increase $\tau$. Eg. 3 bits @ 5 kSaS.
6. Goto 1.

Permutation testing is what's done by NIST's 90B ea_iid. Or roll your own. Or use mine. That link has a lot of NIST detail. The reason the bounds are tighter is that you set them yourself as to what constitutes IIDness. NIST uses p=0.01 and my slow test uses p=0.1 rather than relying on the perceived strength of your compressor.

Answer 2

The language of the question you link to is over the top unfortunately.

The main problem is not only non-uniformity but non-stationarity of real life sources, and that also has to be estimated, as in "exactly when did the properties of the source change?" given a long output, which then brings us into model estimation, mixture models, Bayesian analysis, the variations are endless.

So, then one has to limit the model to a set of admissible models, based on the structure of the source.

One other possibility is to use randomness extractors, but choosing the parameters of an extractor, and designing one which is efficient is also tricky.

So then some people just XOR long consecutive blocks of the output and use a hash function on it, and forget about all the complications.

I also would like to refer you to the answer

here

to a related question by @fgrieu. The most important basic pitfalls in terms of entropy estimation have to do with the difference between source and output.