What is randomness? - Lance Fortnow

What is randomness?

(By Lance Fortnow)

Chapter 7 de CIENCIA, y además lo entiendo!!!

We deal with chance every day. The weatherman says there is a 30% chance of rain today. I flip a coin with a friend to decide which movie to see. The cost of my automobile insurance depends on the insurance company’s beliefs in the probability that I will have an accident.

It rains today. The coin lands on heads. I don’t have an accident. Who chose these outcomes or were they predetermined? If they were predetermined, why do we think of these as random events? This isn’t an article about probabilities but about how randomness occurs, or seems to occur in our everyday lives.

 

1          Coin Flips

Let’s looks at a coin flip. Our thumb pushes against the coin into the air causing it to turn over and over. The amount of effort of the thumb, the trajectory of the coin and to lesser extent the pressure and resistance of the air itself control how this coin flips. Eventually the coin hits the ground and depending on the angle will settle into one of two low-energy states, either with the “heads” side of top or the “tails” side.

There is nothing particularly random about this process. Every aspect could be controlled and simulated. Whether the coin lands on “heads” or “tails” is basically determined as soon as the coin leaves the thumb. Nevertheless, we allow or often require that one player call “heads” or “tails” while the coin is in the air and still treat whether the coin lands on “heads” or “tails” as a random event.

The weather and my safe driving depend on far more complex chains of events though again they seem predetermined from the base conditions. Two questions stick out:

-Why do we consider this processes random?

-Is there true randomness in nature?

We’ll tackle the second question first.

 

2          Randomness in Nature

“God does not play dice” famously claimed Albert Einstein, a believer in scientific determinism. Before the 20th century many scientists believed the same, that the world and the universe moves following a path full defined from its current state. In 46 the 20th century we saw the development of quantum mechanics that made us question this philosophy.

Suppose you have a light bulb and put in front of that bulb a piece of cardboard with a thin vertical slit. Then through that slip light will come through only oriented in a vertical direction. We can check that easy enough by putting another cardboard with another slit in front. If that second cardboard has a vertical slit lined up with the first cardboard, then all the light passing through the first cardboard passes through the second. If the second cardboard has its slit oriented horizontally then no light will go through

What if we orient the second cardboard’s slit at a 45-degree angle? About half of the light will go through. As we reduce the light coming from the source, we equally scale down the light that comes through the 45-degree slit.

According to quantum mechanics, light is not made up of a substance that one can make arbitrarily small. Instead light comes in packets, or quanta. Think grains of sand that make up a beach. We can reduce the light source so it emits a single quanta of light, a photon. What happens if that vertically oriented photon hits the 45-degree slit?

You can actually run this experiment and put a photo detector at the other end of the cardboard with a bell that will ring if a photon is detected. Perhaps not surprisingly, half of the time the photon is blocked and the other half of the time it comes out of the slit oriented at the 45-degree angle. Half of the time the bell is rung.

This seems like true randomness, a completely controlled and reproducible experiment that has two distinct outcomes, a bell ringing or a silent bell, each occurring seemingly independent and with probability one half. God does seem to roll dice to choose whether or not to ring the bell.

Or maybe not? Perhaps we are just observing a piece of a larger deterministic system and by measuring the photon we reduce the dimension of the system we see but it is still part of the larger picture. This is a bit confusing so let’s consider what happens if we don’t observe the outcome. Suppose instead of ringing a bell, the detector releases a poisonous gas into a box containing a live cat. If a photon is detected the cat is killed, otherwise that cat continues living unaware of the unreleased gas. Suppose we don’t look inside the box. Thus is the tale of Schrödinger's cat.

Without looking inside the box we don’t know whether the cat is alive or dead, whether or not the photon was detected. We can think of either that the cat is alive or dead and we just don’t know the answer. Or we can view it as a quantum state, where the cat is both possible alive or dead in quantum superposition. Only when we open the box and view the cat does the superposition collapse into one of the states where either the cat is alive or dead. Similarly, someone sitting outside our universe can model out universe with a deterministic transition of quantum states in superposition as long as they never look inside the system.

So do we get true randomness or not in quantum mechanics? There is no true clear answer and is more a philosophical debate than a scientific one. There are other potential sources of randomness, for example black holes that seem to destroy information, that are even harder to reason about.

While physics doesn’t yet give us a clear answer of whether we have true randomness in nature, this question does not address the flipping coin. No single photon knocks this coin off its course. The coin flips in highly controlled experiment will always land the same way. How can randomness happen when events are determined?

 

3          Randomness from Complexity

When we flip a coin, a very deterministic process, why do we consider whether the coin lands on heads or tails random? With the proper sensors and enough computing power we could determine the coin’s outcome from its movement in the air. Typically, the coin we flip these coins between two humans and we just lack the computation power to compute the answer. The outcome of the coin is unpredictable to us, and being unpredictable we treat the answer as a random event. Our inability to compute the answer makes the outcome for all practical purposes random to us.

We can say the same for the weather. The weather agencies have powerful tools and computers to predict the weather but they have to use limited models because even the most powerful machines cannot take into account all the factors that may drive the weather, even for the next day. A weather forecaster still gives a percentage of rain treating rain like a randomized event.

In a casino, the dice and roulette wheels are simple devices yet rely on a number of complex interactions that they too seem completely random. Random enough that casinos literally put their money on the line on the assumption that the bettors cannot predict the outcome of a dice throw or a roulette wheel better than random chance. In craps many casinos will allow the bettors themselves to throw the dice, knowing that even doing so won’t give them an advantage in predicting the outcome. In blackjack, the dealer will often shuffle the cards directly in front of the bettors, and yet the bettors cannot treat the deck as anything but in a perfectly random order. Even card counters assume the deck is perfectly random, they just use the outcomes of earlier cards to adjust the probabilities of later ones.

In financial markets traders need to assume a probability on future prices in order to properly price securities because these prices depend on a complex way on a series of events and future trading.

In the United Kingdom, you can bet on the outcome of sporting events, elections, winners of award ceremonies. The betting sites don’t take a risk here, they set betting odds so that both sides are equally represented and they make money independent of the outcome. But the bettors must make probability estimates, consciously or unconsciously, in order to decide on which outcome to make the bet.

Even consider the game of chess. There is no obvious randomness in chess. The current board position is fully known to both players and no random devices, such as dice used in backgammon or card shuffling used in poker, are involved in a chess match. Yet we talk about risky moves and how likely we think white will win after a certain move in the game. The complexity of chess turns this game of “perfect information” into a game of “imperfect information” seemingly adding a measure of randomness to a game with no obvious source of randomness.

When you ask a computer for a random number, it doesn’t truly give you a random number. Rather it gives you the result of a complex calculation, to give you a number you can treat as random. Similarly, cryptographic protocols make real messages appear to be truly random to those who don’t have the proper decryption keys. There are a number of theoretical results that show how to convert any sufficiently hard function into a pseudorandom generators and cryptographic protocols that cannot be distinguished from true randomness. In practice we have also developed protocols that no man or machine can distinguish from purely random.

 

4          Removing randomness by beating complexity

With better and more powerful algorithms and computers we can sometimes beat randomness built from unpredictability and complexity. Our recent ability to access large amounts of data combined with machine learning algorithms now made feasible on current technology can help break through the unpredictability barrier. We cannot usually completely predict with confidence, but we can gain enough information about future probabilities to get an advantage over those who still view the original events as completely unpredictable.

New models, stronger computers and better algorithms have greatly improved weather forecasting though we are still a long way from forecasting with certainty. Hedge funds use deep mathematical techniques to gain an advantage in trading securities. Some sophisticated bettors can find small imperfections in roulette wheels using hidden computation devices and use that to gain a small but real advantage in betting. A chess playing computer, even housed in your smart phone, can beat any human these days by doing a better job of predicting the chances of winning from potential future game boards better than humans can.

5          What is randomness?

Whether we get true randomness from nature depends on the interpretation of what nature does. Truly what we view as randomness is not randomness at all, rather it is simply what we cannot predict given the complex processes that generates the outcomes of events.

Powerful new machine learning and data analytic tools can help us do a stronger job of prediction but for many events we will never be able to fully predict outcomes. Best we can do is to understand the nature of randomness. Making decisions in the face of uncertainly is one of the great challenges that people go through every day. Even the greatest of leaders will make choices they may later regret given how events play themselves out. But understanding what we cannot predict give us the best chances to address the challenges we have in the future.

Lance Fortnow

Ph.D. Applied Math

Professor and Chair

School of Computer Science, Georgia Institute of Technolgy

Lance Fortnow is professor and chair of the School of Computer Science of the College of Computing at the Georgia Institute of Technology. His research focuses on computational complexity and its applications to economic theory.

Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Georgia Tech in 2012, Fortnow was a professor at Northwestern University, the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Since 2007, Fortnow holds an adjoint professorship at the Toyota Technological Institute at Chicago.

Fortnow's research spans computational complexity and its applications, most recently to microeconomic theory. His work on interactive proof systems and time-space lower bounds for satisfiability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97.

Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transaction on Computation Theory, served as chair of ACM SIGACT and on the Computing Research Association board of directors. He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has thousands of followers on Twitter.

Fortnow's survey The Status of the P versus NP Problem is CACM's most downloaded article. Fortnow has written a popular science book The Golden Ticket: P, NP and the Search for the Impossible loosely based on that article.