In the last lecture we saw how some processes that are not random may appear random to an
observer.
Some authors have taken advantage of this phenomenon to produce fake randomness or what
is officially known as pseudo-randomness.
Pseudorandom number generators have applications to many areas, from simulation to game-playing,
cryptography, statistical sampling, optimisation algorithms and machine learning.
One first documented pseudo-random generator or PRNG for short, is that of John von Neumann,
a mathematician that made contributions to many areas of science including quantum mechanics
and cellular automata.
This piece of code reproduces his famous PRNG.
The method illustrated by this program, known as the middle-square method, is a generalisation
of the first computer-based pseudorandom number generator (PRNG) based on a simple arithmetic
formula.
John von Neumann suggested it in 1946 for the purpose of devising, together with Stan
Ulam, what would later become known as the Monte Carlo method for the simulation of physical
processes, motivated by their work at Los Alamos National laboratory while building
the atomic bomb.
Iterating von Neumann's procedure produces a series of numbers generated by a deterministic
process intended merely to imitate a random sequence.
The procedure is very simple:
1.
take any n-digit number 2.
square it 3.
take the middle n digits of the resulting number as the "random number"
4.
use that number as the seed for the next iteration
Eventually the whole sequence repeats in the same order and eventually a number comes up
that was squared before.
Another flaw is when the sequence reaches 000\[Ellipsis], from which all squares from
then on are 0 and the resulting sequences (after padding) are also 0.
In other words, the method eventually reaches a fixed point.
One way to avoid this is to pad with 1s rather than 0s, as was done in this computer program.
Each iteration starts from a random seed and produces a sequence of sequences of numbers
generating the grid shown.
The irregularity of the grid shows that the procedure succeeds in producing a random-looking
output in spite of the simplicity and deterministic nature of the procedure.
There are many different methods for generating random bits and test their quality.
Clearly when generating randomness one does not want to enforce only Borel normality and
allow cases such as the Champernowne or Copeland-Erdos constants.
These methods may vary as to how unpredictable or statistically random they look and how
quickly they work.
Nowadays, the kind of arithmetic PRNGs as the one suggested by von Neumann, also called
congruential PRNG, fail under basic statistical tests, and better PRNGs have been developed.
In version Mathematica 4 and older, for example, the central column of ECA rule 30 was used
as pseudo-random number generator and since Mathematica 6 a new default RNG based on another
cellular automaton is used.
Here is a pie chart similar to the ones before, showing how the central column of the ECA
rule 30 produces about the same number of 0s than 1s, which would be a first basic property
of a good Pseudo Random Number Generator, in this case, a pseudo-random bit generator:
Modern versions of the Wolfram Language allow the user to choose between 6 different PRNGs
called "congruential", "ExtendedCA", "Legacy", "MersenneTwister", "MKL" and "Rule30CA" and
8 other RNG methods for "MKL".
The full tutorial is available online at: http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneration.html
and here are some examples:
You can see how all these sequences look random.
Here is a small computer program that allows you to visualise and even test some of this
PRNGs with some simple statistical tests where we can see that the so called congruential
PRNGs such as the one proposed by von Neumann fails, and how some more modern methods pass,
in general it is a cat and mouse chasing game where better PRNGs also suggest better statistical
tests and the other way around:
Among the most popular statistical tests are the following:
-Normality - Compressibility
- Linear complexity - Autocorrelation
- Fourier coefficients - Run and gap tests
- Partitioning the set of m-bit strings and counting hits in subsets
- Serial tests - Rank of a binary matrix
- Longest run of 1's - Hamming weights
- Random walk tests - Close pairs
All of them can also be used to test PRNGs and thus make better PRNGs.
Popular statistical batteries can run up to 40 tests or more.
When failing one of those tests a piece of data is found to have an atypical characteristic
defined by what that tests evaluates, such as an over-representation of certain symbols,
to mention one.
A good pseudo-random sequence can pass any finite set of tests but a truly random sequence
would pass all known and future tests.
In the next lecture we will see what mathematical true randomness really is, as opposed to pseudo-randomness.