This is likely a very silly question which has a simple answer. As I understand, ML models are able to detect patterns in sequences. Given a sequence which is not truly random but rather only pseudorandom, the fact that there is some underlying pattern in such a sequence suggests that given a sufficient amount of training data, that an ML model should be able to approximately "learn" and generate the next digits of the sequence. Are there any pseudo-random sequences which could not be learned by an ML model? What is the relationship between learnability by an ML model and the ability of a pseudorandom sequence to pass the Diehard tests? i.e. does failure to be learned by any ML model imply that the pseudorandom sequence should pass the Diehard tests? Are there counterexamples to this?

Again, I am not a theoretical computer scientist, but rather a mathematician. It is likely that I am misunderstanding some key concept.


1 Answer 1


Yes, (it is believed that) there are sequences that can't be learned by any ML model: cryptographic pseudorandom generators (see also here) are one good candidate.

If a sequence fails some Diehard test, then the sequence is not pseudorandom, and in particular, there is some way to predict the next bit of output with probability better than $1/2$. Since Diehard uses fairly simple tests, the prediction algorithm will also be fairly simple. If there exists a simple algorithm to predict the next bit with probability significantly better than $1/2$, I expect it is likely that some ML algorithm can learn it. Therefore, if no ML algorithm can predict the next bit with probability significantly better than $1/2$, and if you use a sufficiently good ML method (with sufficient capacity, sufficient training data, etc.), then I expect it is likely the sequence will also pass all Diehard tests.

Diehard tests are not a gold standard. Passing Diehard tests is not a guarantee of pseudorandomness. Diehard only checks for some grossly inadequate PRNGs. Bad pseudorandom generators can still pass the Diehard tests. See, e.g., https://crypto.stackexchange.com/q/394/351, https://security.stackexchange.com/q/83254/971, https://security.stackexchange.com/q/32410/971, https://security.stackexchange.com/q/33185/971.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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