Do pseudo-random number generator test batteries have any theoretical grounding?

Question

There are a lot of PRNG test batteries, like DieHarder. They do check that some statistical tests expected for random sequence are indeed present.

But is there any theoretical motivation, why this should work? Why all other statistical tests would probably work too? And why PRNG would be good in crypto way, meaning that it could not be predicted?

By this answer it appears like currently non-relative proofs of PRNG security are not available at all, but maybe there are at least justifications why some statistical tests are "better" (i.e. generating all others)?

This seems similar to definition of randomness in algorithmic randomness theory, but I am not sure if there is a direct link.

Answer 1

But is there any theoretical motivation, why this should work?

They absolutely have theoretical grounding, they are all statistical tests that any true random oracle should satisfy.

It 'works', however, only in one specific way: they can prove something is not a good source of randomness. But an absence of evidence is not evidence of absence, they can not prove something is a good source of randomness.

Tests like DieHarder are just a tool for automatically filtering methods that have easily shown issues. It is not a tool for showing a method is good.

Answer 2

Found one well-known connection.

Seems like notion of "normality", which is generalization of law of large numbers from single sampling values to n-blocks of them, does coincide to notion for random sequences resource-bounded to FSM.

https://en.wikipedia.org/wiki/Normal_number#Connection_to_finite-state_machines