a world of randomness.pdf

Chapter 5A world of randomnessHow the Marquis de Laplace had a strong intuition that was proved correct a century and a half later, and how many other things that happened afterwards were to leave a clear imprint in the digitized world.The study of mathematical chance is a relatively recent development. Dem- ocritus, a Greek philosopher, is often credited as being the earliest scholar of random phenomena for his assertion that the universe was born from the col- lisions of tiny atoms agitating in chaos. Lucretius, a Roman poet and natural scientist, went much further, giving an explanation of the restless motion of the particles of dust in a sunlight ray that anticipated, with astonishing precision, Einstein’s theory of Brownian motion.1However none of the ancient sages seem to have thought deeply about the mathematical rules of chance. Ran- dom phenomena were appreciated in relation to gambling, but it was not until the sixteenth century that a real treatise on the theory of chance appeared. No wonder that the author, a weirdo Italian with multiform interests, was a hardened gambler. His name was Gerolamo Cardano, a mathematician andphysician, with a body disfigured by one of the recurrent epidemics of Black Death that tormented Europe in those times, and a consuming addiction to gambling. In Cardano’s book Liber de ludo alee (The Book of Games of Chance), a primitive version of the theory of probability was laid down, along the lines followed by nearly all the other mathematicians until the twentieth century when these studies were given new, stronger foundations. What Cardano es- tablished is something that may sound very familiar, that is, the probability of a favorable event equals the number of all favorable events divided by the number of all possible events. So for example if you bet on an outcome of 2on a six sided die, your chance of winning is 1/6. This definition lasted for centuries, but requires that all events occur with the same probability (i.e.,1Lucretius lived in the first century B.C. Many assertions contained in his poem De Rerum Natura (On the Nature of Things) have proved correct many centuries later, although they are not at all intuitive. For example he stated that all bodies would fall with equal acceleration in the vacuum, although he could not conduct any experiment to validate his theory. All this is described in elegant verse.71© 2012 by Taylor six bits for the Chinese hexagrams; eight bits for the Nigerian en- counters of Od` u. These events determine an interesting combinatorial setting that accompanies the rite, proving that the babalawo must have mathemati- cal skills and, once again, showing the power of exponential growth. Sixteen special beings called Od` u were trained by a god to spread wisdom through the world. The names of the Od` u are coded by four-bit numbers that ap- pear during the rite as the positions of the half-nuts thrown by the babalawo. The half-nuts can land with the concave side up (0) or the convex side up (1). The table of all Od` u, ordered row-wise by their rank, is shown in Figure 5.1. They pay ritual visits to each other, or stay by themselves, as revealed by the combination of two groups of four nuts out of the eight nuts thrown, thus giving rise to a total of 28 = 256 dispositions of their pairs, each one4Taken from: Sergeant, R.B. Islam. In: Loewe M. and C. Blacker, eds. 1981. Divinationand Oracles. George Allen or musical notes on a song score; or sentences in the Latin alphabet as in this text. So messages,mathematical definitions, and computing algorithms, are all citizens in thesame world of sequences if a common alphabet is fixed, and since this alpha- bet is arbitrary we will refer to the binary one. On these grounds Information Theory took an unexpected direction in the 1960s with the computationalapproach independently adopted first by Solomonoffin the U.S.A., then by Kolmogorov in Russia and Chaitin in the U.S.A. again. The concept of algo- rithmic complexity of a sequence arose, leading to a new characterization of randomness that is no longer a consequence of the source but entirely depends on the inner nature of the sequence. As the name suggests these studies are strictly dependent on the theory of algorithms that had begun to develop in the preceeding decades. This is the new tool by which many intuitions of the past were rephrased in solid mathematical terms.6 The reference system is strictly mathematical and quite sophisticated. Computations are ideally performed on Turing Machines that, as we havealready seen, may execute any of an infinite set of algorithms. In practical terms the machine can be any computer if no limitation is put on the memory size, and the algorithms may be coded in any programming language. A point to be remembered is that, in any family of machines, there always exists at least one that is universal in the sense that it can simulate the computation of any other machine that executes any one of its progr。