I'm following in the steps of §5.1 Permutation Testing, NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation.

I'm developing my test for identifying IID data, using compression à la §5.1. I compress the original data sample. I then repeatedly shuffle the data and re-compress. The ratio between the original compressed size and the compressed shuffled sizes is the test metric (correlation factor). And so I get the following for 100 runs:-


where correlation factor >0 suggests non-IID data, whilst <0 suggests IID data. The pie chart currently ignores any =0's.You can see that approximately 30% of the tests compressed the shuffled data to more than the original un-shuffled sample.

NIST applies a simple binary pass/fail test in accordance with item 3:-


Q: Is there a $p$ type statistical test that can be applied to the number of higher/lower compressions? So for this example, we might say $p=0.x$ that 30 permutations would compress more simply by chance.

I'm hoping for something a bit more specific to this question than: Test for IID sampling, How to choose the test statistic for permutation test? or p-values for permutation tests.

In the above example, the data is cryptographic strength IID, so in the long run I would expect a 50% green/red split.


Your Answer

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

Browse other questions tagged or ask your own question.