What is randomness?

In common sense, randomness is the apparent lack of pattern or predictability in events. If a random number is unpredictable, then how can a computer, which is deterministic and relies on algorithms, generate a truly unpredictable outcome? This article will explore true randomness and pseudo randomness, the latter often generated by computers.

Consider the following example from [2]. Suppose Alice and Bob play “head or tail” where Alice throws a coin in the air and Bob has a guess the outcome of the coin. There are 4 ways how Bob can guess:

  • Bob has to announce his guess before Alice flips the coin,
  • Bob has to announce his guess while the coin is spinning in the air,
  • Bob has to guess while the coin is spinning and he has access to some vision technology that can figure out the outcome. Unfortunately, Bob cannot process the information from the vision in time,
  • This time, Bob can process the information and can make more accurate guesses.

The probability that Bob guesses correctly is 1/2 for the first three cases, but not the fourth. This example tells us that proper definitions of randomness depend on the power of observers: a number that looks random for one observer may not be random for more powerful observers. In computer science, observers with different powers correspond to algorithms under different time/space constraints. A number that appears random to computers under time/space constraints are called pseudo random. This definition is similar to the 4-digit bike lock; someone might try to break the lock by trying all 9999 different combinations, but under time constraint, the bike lock is practically safe.

Now, let say a computer is able to produce a sequence of random numers. Since computers do not have infinite memory, after the computer reaches its limit, it has to produce a number that it has produced before, entering a cycle. Then, any number that comes after that will be totally predictable. Since computers are bounded by time/space constraints, random numbers generated from computers are pseudo random as opposed to truly predictable.

How do computers generate pseudorandom numbers?

Middle-square method

An early pseudorandom number generated was developed by John von Neumann in 1946 to approximate the process of nuclear fission. The algorithm, called middle-square method, is as follows: take any number, square it, remove the middle part and use it as input for next iteration [3]. For example, if we start out with 121, squaring it yiels 14641. Then, we output the middle, which is 464, and square it again, yielding 215296 with the middle being 519. The sequence generated by this algorithm so far is 464529.

The middle-square method has since been supplanted by more elaborate generators, most of which are completely determined by an initial value, called the seed.

Python example

In Python, the code block below gives a different number between 0 and 1 everytime it is run.

>>> import random
>>> random.random()
0.8645593473325841

However, if we set the random seed to be 19, Python will return the value below no matter what.

>>> random.seed(19)
>>> random.random()
0.6771258268002703 

While the algorithm behind Python random function might not be the middle-square method, computer-generated numbers that appears to be random are still pre-determined by some underlying algorithm and the seed. It is important to distinguish this kind of randomness from true randomness where there is no underlying algorithm.

Now, in addition to computer-generated randomness, randomness can also come from initial conditions. The ball in a roulette can be used as a source of apparent randomness, because its behavior is very sensitive to small variations in initial conditions (related to chaos theory!). Randomness continues to have a lot of applications (in security/cryptography; think back about the bike lock analogy) and continues to be an exciting research area for mathematicians and computer scientists!!


References

[1] “Pseudorandom number generators (video),” Khan Academy. https://www.khanacademy.org/computing/computer-science/cryptography/crypt/v/random-vs-pseudorandom-number-generators (accessed Jun. 07, 2020).

[2] K. Mehlhorn and H. Sun, “Lecture 3: Randomness in Computation,” p. 7.

[3] “Random number generation,” Wikipedia. May 26, 2020, Accessed: Jun. 07, 2020. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Random_number_generation&oldid=958943591.