Looking for guidance/references with/about calculations:

I am designing a widget that creates N-bit binary sequences. My customers target spec for the sequence's minimum entropy is X bits/bit. I plan to count occurrences of run lengths of 1,2,..R in M of the N-bit output strings and compare to min and max thresholds Tmin1,Tmin2,..TminR, and Tmax1,Tmax2,..TmaxR respectively in order to pass/fail each widget on the factory floor.

I am looking for the math to help me determine the parameters M and R as well as the thresholds [Tmin] and [Tmax] in order to have a given level of confidence in my result.

Apologies if I butchered the notation. I am not a mathematician :)

Any tips greatly appreciated.

  • $\begingroup$ This might interest you. It sounds like you want to estimate the entropy of the n-bin binary sequences and want to make sure you choose the parameters so that you have a given confidence level. This question might be better off on CV.se. $\endgroup$ – mikeazo Aug 1 '14 at 18:31
  • $\begingroup$ Perhaps ENT (fourmilab.ch/random) might help you. One question, are you trying to check, if the bit sequence is sufficient random ? $\endgroup$ – Thor Aug 1 '14 at 19:14
  • $\begingroup$ Please, do not use simple tools like ENT as Thor commented, because such little thingies are far from complete and surely don’t check all the stuff you should check. If you really need a test-suite, simply take a look at this answer which provides a quick overview of the most prominent, well-vetted, and respected test suites. (Disclaimer: yes, that’s one of my answers…) $\endgroup$ – e-sushi Aug 1 '14 at 23:22
  • $\begingroup$ This question looks off-topic to me. The site is for questions about cryptography (see here); your question does not appear to fit the fall within the scope of the site. $\endgroup$ – D.W. Aug 2 '14 at 0:31

If the sequences are supposed to be perfectly random, you may want to take a look at e.g. the NIST statistical test suite. However, you should be aware that statistical tests don't prove or really even estimate entropy. They are just a sanity check that tells you whether the numbers look random. Non cryptographic PRNGs that are completely predictable can pass them.

If the numbers are meant to be used for cryptographic purposes, I would recommend approaching the problem from the opposite direction: start from real entropy from the OS, use known good primitives to build a CSPRNG. Better yet, find a library that already does all that.


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