Isn’t the problem with detecting bad randomness that you can’t be sure about your decision?

That is, if you accept a certain probability of falsely identifying a RNG as biased, I don’t see why this should be a fundamentally difficult problem, at the very least for the generator with four million 0s and a single 1: The probability that a good RNG spits out less than a thousand 1s in four million queries is negligible compared to the probability that it returns between 1.5 and 2.5 million 1s.

Of course, it will be harder to detect more sophisticatedly broken generators, but still, without requiring certainty, it should be possible to make some sensible claims?