## Sunday, October 4, 2009

### Is A Coin Toss Random?

Randomness is a slippery concept. If you teach it in an AI class you are quick to point out that what we call random is really a matter of ignorance: because we don't know and/or model all the details of the world we lump together everything that is outside the scope of our models and call it a random effect. Under this reasoning the toss of a coin is *not* really random in a philosophical sense.

Unless of course, quantum mechanics has anything to do with it. Imagine we toss a coin through a quantum measurement. Now we are confident to claim true randomness. The quantum world is with a nice world "irreducibly random", meaning that there is no deeper theory from which quantum mechanics would emerge and where the coin toss is once again the result of our ignorance. However, as I reported in an earlier blog, there may even be ways out of the seemingly "irreducibly random" nature of quantum mechanics. In this view we are back to square one: what then is randomness?

There is a beautiful definition of randomness in a mathematical discipline called algebraic complexity. To understand this definition let's consider a very long sequence of coin flips. Now let's try to compress this sequence of "HTTTHHHTTHTTTTHHHTHTHTHHH" into a smaller sequence by building a model. If the sequence where just "HTHTHTHTH..." things would be easy: "I will simply state that head and tails alternate and the sequence starts with H (I will have to count the symbols in this sentence as the cost of encoding it). The sequence is not random because I could compress it. The definition of randomness is thus: a sequence is random if it cannot be described (encoded) using a smaller sequence. In terms of learning theory: one cannot learn anything from a random sequences.

Using this definition, a sequence can be random yet and at the same time be generated by a fully deterministic process. This process will have to be "chaotic" which we will not define here but has nothing to do with quantum mechanics. In fact, it snugly fits the definition of a random coin toss. For instance, if you toss a coin in a deep tank of moving water and record whether it landed head or tails on the bottom, then I am pretty sure that the details of the trajectory of the coin are chaotic. Hence, there is no model that can predict anything about the final outcome. This is not because we don't know how to model moving water in a tank, but because trajectories of coins in these tanks have something inherently unpredictable about them.

I therefore conclude that the flip of a coin toss can be truly random and deterministic at the same time. We don't need quantum mechanics for true randomness, we have something far better: chaotic dynamics. In fact, I predict that the so called "irreducible randomness" of quantum mechanics will in the end be reduced to randomness derived from chaotic dynamics.