# Predicting the next number output by a random number generator

Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence?

For example, having a series of random numbers like this

40 46 15 37 9 4
32 26 5 33 17 21
12 19 13 36 25 29


These are the output numbers from a random number generator and I want to know the pattern that was used to generate them.

It is a well-known fact concerning (cryptographically secure) pseudorandom generators (PRGs) that pseudorandomness is equivalent to next-bit unpredictability. That is, distinguishing the output of a PRG from the uniform distribution is just as hard as predicting its next bit of output (when the PRG works on a uniformly distributed seed). This goes back to a result by Yao.

If we are talking about standard (i.e., not necessarily cryptographically secure) random number generators (RNGs), then things are a bit different. If the RNG simply has to fulfill a set of heuristics, then it can be the case that it does so despite being (almost) fully predictable. (As an extreme example, consider the rather naive heuristic $$\lim_{n \to \infty} E(|G(1^n)|_0) = \lim_{n \to \infty} E(|G(1^n)|_1) = \frac{1}{2}$$, that is, the string $$G(1^n)$$ tends to have just as many zeroes as ones and the "generator" $$G(1^n) = 0^{\lfloor \frac{n}{2} \rfloor} 1^{\lceil \frac{n}{2} \rceil}$$.)