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 and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.