I spent most of this week trying to construct concentration bounds for the NIST statistical tests. Hopefully, this effort can lead to some unified theory of statistical tests, or discovery of some property that quantifies the quality of each test. I also spent some time trying to think of a distribution that is far from uniform, but passes every NIST test. This definitely exists, but each one I can think of breaks a different property.
Unfortunately I couldn’t make much progress. Trying to convert a test to concentration bounds is proving to be very difficult. There is also a lot of math involved that it outside my knowledge, and alot of existing literature takes advantage of useful approximations (which we are trying to avoid). The fact I was sick for a bit of time also didn’t help.
Sources:
- On statistical distance based testing of pseudo random sequences (https://www.sciencedirect.com/science/article/pii/S0167404815000693)
- Linear rank of random binary matrix (https://epubs.siam.org/doi/epdf/10.1137/1117037)
- Randomness evaluation with DFT (https://arxiv.org/pdf/1701.01960)