Pseudo random numbers

Question

I am learning how to use pseudo random number generators but the instructor just told us how they work without explaining why they work. For example, can one prove that the numbers generated by LCG methods are really uniform deviates in [0,1)? Experiments show that it looks like yes. But can we prove this mathematically? I am always puzzled by the basic philosophy behind pseudo random numbers. If the algorithm is deterministic, how can the outcome be random?

Answer 1

Psudorandom numbers generated via methods like LCG are generated via a discrete dynamical system (i.e. a system where $x_n = f(x_{n-1})$). For these types of systems, tools such as Ergodic Theory can be applied to learn the the long-term distribution of such processes. This is one way to get the long-run probability distribution which generalizes well and can thus be used to develop better methods.

These psudorandom numbers are taken to be cycles in the dynamical system which have a long period length and which have an asymptotically uniform distribution. For example, you can come up with a system where $x_n = x_1$ for every $n=5$. This would mean that your solution is a 5-cycle. This wouldn't be very good because then it would repeat a lot. So psudorandom number generators are made to have very long periods. Mathworks has a good table which shows the periods of common random number generators.

With a long period with the points distributed almost uniformly, this matches what you'd intuitively believe is psudo-random uniform.