<p>Yes, (it is believed that) there are sequences that can't be learned by any ML model: <a href="https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator" rel="nofollow noreferrer">cryptographic pseudorandom generators</a> (see also <a href="https://en.wikipedia.org/wiki/Pseudorandom_generator" rel="nofollow noreferrer">here</a>) are one good candidate.</p>
<p>If a sequence fails some <a href="https://en.wikipedia.org/wiki/Diehard_tests" rel="nofollow noreferrer">Diehard test</a>, then the sequence is not pseudorandom, and in particular, there is some way to predict the next bit of output with probability better than <span class="math-container">$1/2$</span>.  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 <span class="math-container">$1/2$</span>, 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 <span class="math-container">$1/2$</span>, 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.</p>
<p>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., <a href="https://crypto.stackexchange.com/q/394/351">https://crypto.stackexchange.com/q/394/351</a>, <a href="https://security.stackexchange.com/q/83254/971">https://security.stackexchange.com/q/83254/971</a>, <a href="https://security.stackexchange.com/q/32410/971">https://security.stackexchange.com/q/32410/971</a>, <a href="https://security.stackexchange.com/q/33185/971">https://security.stackexchange.com/q/33185/971</a>.</p>

CC BY-SA 4.0
2023-06-16T05:39:42.940Z
2023-06-16T05:39:42.940Z
D.W.
<p>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 &quot;learn&quot; 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?</p>
<p>Again, I am not a theoretical computer scientist, but rather a mathematician. It is likely that I am misunderstanding some key concept.</p>

<machine-learning><st.statistics><pseudorandomness><pseudorandom-generators>
Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?
AaronYeloy
# Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

(Asked by: username_0 on 2023-06-15)

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.

**Tags:** machine-learning, st.statistics, pseudorandomness, pseudorandom-generators

---

## 1 answers

### Answer by username_1 on 2023-06-16. Score: 4

Yes, (it is believed that) there are sequences that can't be learned by any ML model: [cryptographic pseudorandom generators](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) (see also [here](https://en.wikipedia.org/wiki/Pseudorandom_generator)) are one good candidate.

If a sequence fails some [Diehard test](https://en.wikipedia.org/wiki/Diehard_tests), 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>.


---

