Mathematics
Let’s suppose we have found ourselves in the following surreal scenario. We finally were able to book an appointment with the Higher Power of the universe regarding some questions which arose during an existential crisis. While in the waiting room, the secretary makes an announcement:
Due to an overbooking issue, we only have time to fulfill one more appointment. To decide who gets to take that last appointment, we present a challenge: everyone must come up with a random number. Your number will be presented to the Higher Power and the person with the number deemed the most random will be rewarded the last remaining appointment.
What strategy should we employ to come up with the most random number?
But first, what does it mean for a set of numbers to be random?
A set of numbers is completely random if when we pick a single number from the set, all numbers have an equal chance of being picked. Since there are 10 digits (0–9), each number would have a 10% chance of being picked if the set of numbers was completely random. Another equally important characteristic of a completely random set would be the inability to predict the next number. The set can have no pattern. Using this information, we can decide how to best simulate randomness.
Using these two criteria, we will look at 4 different options for generating a random number: use a random number generator in python, use an irrational number, make a number on our own, or use a non-computable number.
Use Random Function in Python
The random function is a pseudorandom number generator (PRNG). A PRNG begins with a seed, which is a value that is typically inspired by a hardware-related value in your computer (usually from the time). This seed is fed into a function and it outputs a long string of pseudorandom numbers. These strings have a “period”, the number of digits before the number would repeat itself. Simple PRNG’s or PRNG’s with a small period are not reliable for security because if the seed is known, it is easy to reproduce the output.
Specifically, python uses the Mersenne Twister to randomly generate numbers. Below is a link to a nice description of this specific PRNG:
I used python to create a random number and plotted its distribution of numbers in a pie-chart:
The random number generated appears to pass our first criterion, all 10 digits occur equally often. Now we need to check for a pattern.
Several tests exist to measure the randomness of a set of numbers. I chose to use the test called “Runs Test”. This is a test used to determine if a generated set of numbers is random. I think this is an acceptable test for this purpose, but if you disagree or know of a more appropriate test, please share in the comments!
The Runs Test
This is a hypothesis based test. The null hypothesis is that the number python generated is random. The alternate hypothesis is that the number is not random. A score is generated using the expected number of runs in the number and the real number of runs in the number. If this score is less than 1.96 (with a 95% confidence interval) the number is random. I recommend this medium article for a brief overview of using the Runs Test in python:
The Runs Test results returned Z = 0.509 which is less than 1.96 so the number that the random.randint generated is random (at least by the standards of the Runs Test).
Python has several forms of a PRNG and the one you choose to use depends on what the purpose of the random number is. Random.randint might be good enough to book that last appointment but lets first look at some other options.
Irrational Numbers
There is a technicality here we should consider. Presenting the Higher Power with an irrational number might be like someone presenting your own phone number to you and calling it random digits. It’s not really random, since irrational numbers are something anyone could google to a known value. However, I think it would be wrong to not at least consider these numbers as a possibility. Let’s see just how random they are.
Let’s start with the world’s most famous irrational number: pi(π). First let’s plot the distribution of all 10 digits over the first 500 digits of pi.
This doesn’t look too good. Why are there so few 7’s and significantly more 1's? Well, we are only looking at 500 digits of pi (over 60 trillion are known). Sample size is important, so let’s instead look at the first 160 million digits of pi.
Now, it looks like every digit occurs at a similar frequency. If my poor computer could handle tallying the digits of pi to a trillion places, our distribution would likely sneak closer to 10% for all digits. Let’s look at the distributions of other irrational numbers.
It looks like all of these irrational numbers (e, the golden ratio, log(2) and sqrt(2)) have a reasonably even distribution of digits in their first 160 million digits. Next we will use the Runs Test from above to make sure these numbers don’t have a pattern.
Runs Tests Results: Random if Z < 1.96
pi: Z = 0.2778
e: Z = 0.659
Golden Ratio: Z = 1.182
Log2: Z = 0.853
Sqrt2: Z = 0.150
All of these irrational numbers pass the Runs Test. We’ve determined that these irrational numbers have an equal probability to pick any digit at random and a pattern of digits which are statistically unpredictable but not mathematically unpredictable (since there are algorithms to find them, which we will discuss again later). So we can conclude that these irrational numbers are statistically random but shouldn’t be presented to the Higher Power.
Random Number D.I.Y.
Instinctively it might appear to us that we could make our own random number that would be more random than anything a computer could generate or a number which already exists. However, humans are surprisingly bad at imagining what random should look like.
A great example of this happened when Apple released its shuffle feature for iPods. The company received complaints claiming the new function was faulty. Users explained that the shuffle feature often played bands or artists’ songs back-to-back. Depending on the size of the playlist and its variety of artists, it’s sometimes more likely than not that our iPods will randomly play two songs by the same artist one after another!
If you still don’t believe that humans are poor random number generators, I recommend this neat party trick from one of my favorite books, Alex’s Adventures in Numberland.
You will need a volunteer, a coin, and 2 sheets of paper. Your volunteer is going to flip a coin 30 times and record the results on one sheet of paper. Next your volunteer will imagine flipping a coin 30 times and record the results of their imaginary coin flips on the other sheet of paper. Now have your volunteer present you with the two pieces of paper, but not to share which list is the imaginary coin toss or the real coin toss results. It is surprisingly easy to guess which list belongs to which trial. Firstly, find which list has the longest run. We often think that if something happens enough times in a row, the next outcome must be different (known as the gamblers fallacy). So, the list with the longest run is likely the one from a real coin toss. Next count how many times the lists alternate between heads and tails. If we have 30 coin tosses, the list should alternate about 15 times. However a human-made list will likely alternate more to try to fake randomness.
I hope I have convinced you that the Higher Power will certainly see through our attempts at creating our own random number.
Non-computable Numbers
In my goal to find the method of determining a completely random number, I came across non-computable numbers. An non-computable number is a number which cannot be approximated with an algorithm to some finite precision. This was a hard topic for me to understand, so I will share the means in which I finally understood this topic.
Understanding non-computable numbers
As is often the case when learning something new, it’s easier to grasp a topic’s inverse and then realize, “okay, so it’s not that”. So we will begin with what it means for a number to be computable.
Is 1/2 a computable number? Of course, we can write that as 0.5.
Is 1/3 a computable number? Yes, even though it’s decimal representation could continue forever, we can write 0.333333… and the more 3's we write we are getting arbitrarily closer to 1/3. This means we can approximate 1/3 to some finite precision, which is the definition of a computable number.
How about pi? By definition, pi is the circumference of a circle divided by its diameter. If you are ever in the strange circumstance where you forgot pi, need to know it, and have no access to the internet, you could always take a circle and measure its diameter and circumference to approximate pi to some finite value. Also, Gottfried Leibniz, constructed a formula to approximate pi to a finite value:
Example of non-computable numbers
What are some examples of non-computable numbers? For one we have Chaitin’s Constant (defined by Ω). Ω is the probability that any arbitrary and randomly constructed program will halt (as opposed to entering an endless loop). Chaitin’s Constant exists and is a real number, we just don’t know what it is and perhaps have no way of actually finding it. All we know for certain is that it is a very abstract idea and lies somewhere between 0 and 1 (since it is a probability).
Because Chaitin’s Number is currently unknown, it’s not going to help us here. However, the concept of this constant is useful in showing how complicated it gets when we try to find something truly random. You must be comfortable entering a part of mathematics that is incredibly abstract and slightly paradoxical sounding.
If anyone reading this can provide anymore insight on this topic or found a mistake in my logic, please leave a comment! This topic is incredibly difficult to understand but is very interesting so I want to spread the idea! Below is the youtube video I watched to further my knowledge of Chaitin’s Constant:
We learned in the irrational number section that we would prefer a number with a lot of digits. This will ensure we have a better distribution. And the PRNG returned a good result in the Runs Test. So overall, it seems like using a PRNG with a tremendously large period would be our best chance at booking the final appointment. I hope you brought your laptop with you!
Thank you for reading! Please leave a comment if I made any mistakes or left out any important information on this topic!
