The Random Walk

The true definition of randomness is mathematical, and like all such models we would expect to find it embodied in natural processes. This mathematical concept of randomness is derived from the idea of a random walk, the path taken by a drunken walker in a pathless field of limitless size. Various questions can be asked about such an ideal being. How far will he have wandered away from his starting place in a certain time? After a certain time, what is the probability of arriving back at his starting place? How often will his path intersect itself? To define a random walk, we assume that there is a sequence of steps and that it is equally probable that a given step will be in any particular direction.1

The concept of the random walk has been developed and applied to many kinds of situations. The question is, how do we know that the mathematical model applies to the real world? Since the definition of randomness depends on probability theory, we have to test the appropriateness of probability theory for the situations to which randomness has been applied: it must be a matter for experiment rather than mathematics to determine whether it fits or not. This involves counting frequencies of events to see whether they fit the predictions of an idealized random walk. (It also depends on various episte-mological assumptions, particularly the assumption that future events will follow past trends.)

To the assumption that probability theory is a good description of the world, there are two kinds of objections, one purely mathematical and one empirical. The mathematical objection is that a truly random sequence must be infinite in length, otherwise the probabilities it generates will not be equal, so in a finite world there cannot be any such thing as a set of truly random numbers. The empirical objection, or objections, come from studies of randomness, which have all come to the conclusion that it is very hard, if not impossible, to find a genuinely random distribution in nature.

A textbook2 on the applications of random noise written in the nineteen fifties begins: "There are many examples of random processes in nature, some of which are meteorological phenomena, thermal noise in electrical circuits, Brownian motion of particles, vibration phenomena and certain economic fluctuations." Since those words were written, there has been a huge develop ment of nonlinear science and its ramifications, particularly in the field of chaos theory. Studies of the phenomena this book mentioned now suggest that at least two, and possibly three, of these examples of supposedly random processes can be modeled in a deterministic way. It seems that what at first appears to be random may not prove to be so on closer examination. We must seek deeper for examples of randomness.

Scientists bet on the outcome of their theories because their careers depend on them, but spies often depend on the secrecy of information for their very lives. For the secure encoding of information, a representation must be found that cannot be read by the other side. This depends on finding a sequence of symbols that is completely random to represent the message; otherwise the code-breaker can use the nonrandomness of the message, perhaps in conjunction with a guess as to its likely content, to force an entry. It has proved very difficult in practice to achieve this; there seem to be no unbreakable codes, because there are no completely random processes in nature.3

One possible definition (though by itself it isn't sufficient) is that any sequence of numbers is random if any subsequence of it contains, on average, the same distribution of numbers or sequences of numbers. However, as we have seen, in this sense there can be no such thing as a random number in the world, since all sequences are finite in length.

A definition of randomness that became popular in the seventies is that devised by G. J. Chaitin, based on information theory. It follows. All numbers that can be written down can be regarded as capable of being produced by computer programs; for example, there is a program that will print the number 0.5; there is another that will produce the number n; and there is one that will print the decimal 0.142857. Even if there is not a formula to generate the number, a program can still be written simply to print the sequence of digits that comprise it—its decimal expansion. Now the amount of information in a sequence, whether it is a number or a computer program, can be measured by the number of symbols it takes to write it down, so the informational content of the program and the number it generates can be compared. For any program and its output there will be a relationship between the length of the program and the length of the number it produces. The degree of randomness4 in a number is defined to be a function of the relation between the length of the number and the length of the program that produced it. A random number is one whose corresponding program is greater than or equal in length to the number it generates: if the program is very much shorter than the number it produces, then the output is nonrandom.

This definition of randomness has problems. The ratio of the circumference of a circle to its diameter is called n, a number that starts 3.141592. . . . A for mula to produce the value of n is very simple to write, and using recursive notation, it can be expressed in very few symbols.5 A computer program to produce n can therefore be written, using recursive programming methods based on such a formula, that will eventually produce more digits than are required to represent the program. No one, however, would assert that n was a number that was predictable or had a recognizable pattern.

Many different programs—indeed, an infinity of programs—will generate the same number. Which is the one that should be used for the comparison of lengths? The shortest perhaps. But how do you know which is the shortest? Many programs have been discovered for the calculation of n; perhaps a shorter one will be found someday. Would this alter the degree of randomness of n?

Defining randomness by the arbitrary nature of how a computer operates seems to evade the problem. There is no simple relation between a set of statements in a computer language and the operations carried out inside the machine. A computer program may be simple, but the operations carried out by the computer may be very long-winded. For example, "Print the square root of 2" is a short program, but the extraction of a square root takes many microinstructions and the duration of computation itself is of indefinite length. Is the sequence of digits in the square root of 2 random or not? There seem to be three possibilities here: (1) since the program required to produce the square root of 2 can be written using very few symbols, then by the preceding definition it is highly nonrandom; (2) but because the program is really much longer than it appears to be, the square root of 2 is less random than this would suggest; and (3) because the sequence of digits in the decimal expansion of the square root of 2 is completely unpredictable, it also appears to be completely random. Which is the correct answer?

Was this article helpful?

0 0

Post a comment