Let’s Roll a Die
Let’s say I want to create the ability to roll a die in my program. Without giving it a second thought, we would call the the built-in function Math.random() in JavaScript (or the equivalent in any other language) and tweak it with some simple manipulation to our desired range. But is this number actually random? The dictionary definition of random is described as follows:
“made, done, happening, or chosen without method or conscious decision.”
This is almost the total opposite of what we expect computer programs to be. Computers and programs are by nature procedural and intentionally designed. How can an instructional program produce something that resembles randomness?
Looking at MDN for Math.random() gives us some insight into what is actually happening behind the scene.
“pseudo-random number in the range 0–1 (inclusive of 0, but not 1) with approximately uniform distribution over that range — which you can then scale to your desired range. The implementation selects the initial seed to the random number generation algorithm; it cannot be chosen or reset by the user.”
Pseudo-Random Number Generator
Random numbers generated by our programs are actually pseudo-random number because numbers generated by an algorithm is by definition not random. However these numbers are seemingly random enough that most users don’t complain about them. There are many implementations of pseudorandom number generator (PRNG) and they vary from language to language. Many PRNGs today use the linear congruential method. Here is a formula of how to get the next random number xₙ₊₁ based on the previous random number xₙ:
k, c, and m are constants chosen by user to generate the sequence. To start the whole process an initial number 𝑥₀ seed is chosen.
Not every implementation is created equal. For example if we chose k=23, c = 51 and m = 100 with an initial seed value 𝑥₀ = 19, we can see how quickly the sequence start repeating:
function randomNumGenerator(k, c, m, seed, loop) {
let prevNum = seed
let randNums = [seed] for(let i = 0; i < loop; i++) {
prevNum = (k * prevNum + c) % m
randNums.push(prevNum)
}
console.log(randNums.join())
}randomNumGenerator(23, 51, 100, 19, 22)//=>19,88,75,76,99,28,95,36,79,68,15,96,59,8,35,56,39,48,55,16,19,88
It only took 20 iterations for the number 19 to show up again. Since we are generating the numbers in a deterministic way, we can expect this sequence of double 19 to exist again in a predictable way. The length of this double number sub-sequence is called a period. In this case our subsequence has a period of 20.
Can I Be More ‘Random’?
We already expected the numbers to repeat since we gave it a formula to generate the numbers. The question we should be asking is not whether or not they will repeat but rather how long until they repeat.
If we change m slightly to 101, we can see a significant change in period from 20 to 50.
randomNumGenerator(23, 51, 101, 19, 50)//=>19,84,64,8,33,2,97,60,17,38,16,15,93,69,22,52,35,48,44,53,58,72,91,23,75,59,95,14,70,45,76,82,18,61,40,62,63,86,9,56,26,43,30,34,25,20,6,88,55,3,19
If we are more deliberate with choosing the m and c values, we can improve the length of the period so our numbers are seemingly more random. If we choose m to be a power of 2 like 2³² or 2⁶⁴ or if m or c are relatively prime, we can get closer to fooling our users that the numbers are random.
Logistic Map
We can further improve our appearance of randomness by leveraging logistic map that’s used to illustrate chaos in simple non-linear dynamic systems.
Starting with a seed value between 0 and 1 the sequence of values will bounce back and forth within a sub interval [a, b] between 0 and 1. We can then transform this with the following
However this only behaves chaotically for certain values of r; notably 𝑟 > 3.56995.
Even though the systems are deterministic, a small change in the initial value can drastically change the result. This is why we can never have perfect weather forecasts for the future. Even if we are extremely precise and measured the weather perfectly today, a butterfly wing flap can change the wind condition in a way that we can end up with a sunny day a few days later instead of cloudy sky. This makes predicting their values virtually impossible and seemingly more random (but really we need to look harder for chaotic patterns).
Chaos: When the present determines the future, but the approximate present does not approximately determine the future.
Next time you don’t want the same song to keep playing from your favorite music app, you can introduce a little chaos and tweak the randomness to your liking.
Still don’t believe in your programming language?
Your computer is actually pretty good at generating random numbers. Not the programming language, but the computer itself. There are numbers that can be created that are closer to true randomness via hardware random number generator(HRNG). These numbers are generated from physical processes instead of an algorithm. Your operating system has a much bigger source of data than a user chosen seed value to create a random number such as CPU temperature, number of seconds since last key was pressed, number of pixels from previous mouse position. These events are likely unpredictable and mirror randomness much closer.
How Do I Know If I Look Random Enough?
To the human eye, if we do not recognize a pattern we would hastily deem something to be random. For example, let’s take a look at the below two strings.
string1 = "abcabcabcabcabcabcabcabcabcabc"
string2 = "31832jdksnckjanlml201lakcnqwli"We can easily recognize string1’s pattern as repeating “abc” but it’s hard to gather a pattern for string2. In this case, string2 is more complex than string1. Chaitin-Kolmogorov Theory helps us measure this type of complexity.
Chaitin-Kolmogorov Theory measures the complexity of a finite sequence in terms of the length of the shortest program that will generate it.
function generateString1() {
return "abc".repeat(10)
}function generateString2() {
return "31832jdksnckjanlml201lakcnqwli"
}
In the above functions, we can see that generateString1 has less characters than generateString2 but they generate the same length of string. The Kolmogorov complexity of string2 is greater than that of string1.
This can be further illustrated if we extend the length of both strings to 60. The length of generateString1 would have the same number of characters but generateString2 would extend the return statement by an additional 30 characters.
function generateString1() {
return "abc".repeat(20)
}
//=>abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcfunction generateString2() {
return "31832jdksnckjanlml201lakgcnqwli92jsksmz01pq26hsunx81lz01me92"
}
//=>31832jdksnckjanlml201lakgcnqwli92jsksmz01pq26hsunx81lz01me92
In other words, as defined by Kolmogorov randomness, random strings are incompressible. We cannot generate string2 with a program that is shorter than the length of the string itself. Kolmogorov randomness defines a string as being random if and only if it is shorter than any computer program that can produce that string.
