I found something of a direction to explore in. We can repurpose the NIST hypothesis tests to check random variables over binary strings by taking several samples, then passing a concatenated string in. This gives a question of whether the tests can detect if something is -close to uniformity.
This gives a bit of a headache when working with the actual tests though, since -close is a very weird condition. For something like the monobits test, the test statistic originally takes on a binomial distribution. -close cuts off the left tail and moves that mass to the rightmost value. I can’t think of “nice” way to compute this distribution, which is pretty bad since this is literally the first NIST test.
In other news, I did some reading on the Wishful Thinking Theorem, to better understand sample size bounds for distribution testing of symmetric properties. There is quite a bit of machinery needed to complete the proof, but it is quite interesting.
Papers:
- Testing Symmetric Properties of Distributions https://dl.acm.org/doi/10.1145/1374376.1374432
- Distribution Testing (continued) https://ccanonne.github.io/files/misc/main-survey-fnt.pdf