Deterministic Randomness ?

True randomness is very hard to find and verify. In complexity theory, we can have a notion of randomness even if the universe is deterministic. I’ll explain with an analogy.

Bob the Alien

Bob is an Alien who has decided to spend two years on earth. He wants to learn about how the earthlings live and how their lives differ from his. In Bob’s world, it is always freezing cold. When Bob arrives it is scorchingly hot, after three months, it becomes cooler and Bob is surprised. To us humans, we know that it is the seasons which are changing, but to Bob the Alien this seems to be random. At least in the first year.

After Bob has spent a year on earth, he notices that the weather seems to be getting scorchingly hot again. This time Bob is prepared and he forms a prediction that after three months, the weather will change… And it does!

To us humans, we know that it is the seasons which are changing, but to Bob the Alien this seems to be random.

Bob is now able to predict the seasons, as he has seen it before.

Are The Seasons Random?

From a complexity theory perspective, the answer is still no. Even though it seemed random to Bob at first because he was not accustomed. The devil is in the detail here; notice that Bob was eventually able to figure out the patterns of the seasons. This is what makes it still non-random. If Bob was never able to figure out the seasons, then it would be seen as random.

So given that I have the power in the analogy, how can I make the seasons random?

We have two choices:

• Either we shorten Bob’s stay on planet earth or we add many more seasons.
• We make the seasons change every so often and only after 2 million years does a cycle form. Instead of a cycle forming every year.

In the latter, even to us humans the seasons could be seen as random. Assuming we humans do not keep records for 2 million years.

Interestingly, if we shorten Bob’s stay, then Bob cannot efficiently distinguish the seasons. He needs more time. But the humans can.

Example

An example of the seasons changing every so often is the following:

• For the first month of the year(January) it is winter.
• For the first day of the February it is Spring.
• For the rest of of February it is Winter.
• For the rest of the year it is Summer.

This is only for the first year though, the cycle repeats every two years. The second year may look like so:

• For the first day of the year(January) it is Autumn.
• For the rest of the year it is Spring.

Unless you have records for more than 2 million years, you will think that this is random.

Deterministically Expanding Randomness

Notice that when we made the seasons appear random, we only added more seasons; instead of four seasons, we now have two million. There is no extra requirement. As long as no-one can efficiently predict when the next season will arrive, then this is random. Of course, if the deterministic pattern I use to generate the seasonal change is easy to figure out, then you would not need 2 million years.

This leads us to the question of if I can deterministically expand randomness without someone figuring out the pattern I’ve used? In complexity theory, if we assume an construct called a One Way Function exists, then the answer is yes! This is because one way functions imply the existence of pseudo-random generators. Pseudo-random generators are deterministic programs which expand on randomness to produce a longer object which is now pseudo-random. However, because you cannot distinguish between the pseudo-random object and an actual object, then it is seen as Random!