3. Randomization and Thermodynamics

It is observed that many systems, starting from almost any state, evolve rapidly to states which seem for practical purposes random. The sense in which the states are random is that their properties (say, statistical ones) are typical of the ensemble of all possible states. Several explanations and conditions for such randomness have been given. No complete understanding yet exists.

A common approach is based on ergodicity. Only reversible systems can be ergodic. The condition for ergodicity is that starting from any initial state, the evolution of the system eventually visits all possible states. The state transition diagram for the system thus consists of a single large cycle. If a system is ergodic, then at least after a sufficiently long time, it must evolve to an arbitrary, and thus ``typical'' state. In practice, however, the maximum period of time necessary to reach arbitrary states is usually astronomically large (it is typically exponential in the system size, and comparable to the recurrence time). Evolution for practical times reaches only some small subset of possible states.

What must now be explained is why these states seem random.

This is a subtle issue. There are always special choices of initial conditions for which the states reached are far from random. For example, one could choose initial conditions which are obtained from some orderly state by time reversal of the dynamics for some number of steps. These initial conditions would yield evolution which would not show degradation to randomness: rather it would suddenly yield orderly behaviour, seemingly violating the Second Law of thermodynamics.

One approach often taken is to consider the dependence of the evolution on small changes in initial conditions. It is supposed that the initial conditions cannot be determined precisely, so that in practice, measurements or experimental preparations can be guaranteed to yield only one of an ensemble of states, which differ slightly. The effects of small changes in initial conditions can be seen quite clearly in cellular automata.

One considers the evolution of a cellular automaton from two states, which differ say by a change in the value of a single site. The pattern of differences between states produced as a function of time shows the effect of this small initial perturbation. Figure 3.1 shows such difference patterns for the rules of figure 2.2. In some cases, initial changes remain localized; the evolution in such cases may be considered ``stable''. (Notice that in a reversible cellular automaton, the effects of changes in initial conditions can never die out completely, because information on the initial state must be preserved.) In other cases (``class 3'' cellular automata), small initial changes are progressively amplified by the evolution. Change of the value of one site can ultimately affect the values of sites an arbitrary distance away. The patterns produced by such cellular automata can thus be considered unstable with respect to arbitrarily small perturbations.

[ Figure 3.1 ] Difference patterns for the rules of figure 2.2. The patterns show the evolution of the difference between two random configurations which initially differ just by a change in a single bit. Some rules are seen to be stable under such perturbations; for other rules, the effect of these changes grows with time. The rate of growth gives the Lyapunov exponent of dynamical systems theory. Such instability leads to a sensitive dependence on the initial conditions for the evolution.

This phenomenon is central to much of what has been studied in the theory of chaotic dynamical systems. It implies that with incomplete knowledge of initial conditions, a time must ultimately come at which the results of measurements can no longer be predicted, because they depend on unknown features of the initial conditions.

It is not however guaranteed that the system will at this point be random. Its randomness depends on the randomness of the unknown features of the initial conditions. It is by no means clear in fact that in actual experiments, these features are indeed adequately random. Certainly one can consider cases in which for example only a few cellular automaton sites are nonzero, and all sites beyond some point are zero. In this case, randomness in final configurations cannot be directly attributed to random unknown data in the initial conditions.

A further, related, problem is the exact definition of ``apparently random'' states. A sequence or configuration is commonly considered ``random'' if no pattern can be discerned in it, so that no procedure can be used to predict additional elements of it, or to compress the information associated with it. The meaning of randomness depends on the kinds of pattern recognition which are considered.

If one starts with an orderly initial state, all states generated with time can be specified by giving this state, and the number of steps required to generate them. Such a specification will usually represent a substantial compression in the information associated with the state. Yet despite the possibility for such compression, many aspects of the state may still seem random. Although compression is possible, it may not be revealed by the kinds of statistical procedures commonly used to analyse the states.

Figure 3.2 shows examples of some simple , cellular automata which illustrate this phenomenon. In each case, a simple initial condition is chosen, consisting of a single nonzero site. With these initial conditions, some cellular automata yield simple patterns, and sequences of sites in these patterns are for example periodic. Other cellular automata yield slightly more complicated, self similar, patterns. But here again sequences of site values are almost periodic, and are readily predictable. Some cellular automata, however, can yield apparently random sequences even starting from these simple initial conditions. The two simplest examples (found by explicit search) are rules 30 and 45. In both cases, the sequences generated seem random according to all standard statistical tests (see S. Wolfram, ``Random sequence generation by cellular automata'', Adv. Applied Math. 7 (1986) 123 and in Theory and Applications of Cellular Automata). Figure 3.3 shows a more detailed example of evolution according to rule 30.

The phenomenon observed in this case occurs in other mathematical systems. Even though a simple specification for , for example, can be given, its digit sequence, once generated, seems random for all practical purposes. The fractional parts of successive powers of , which can be generated by a , cellular automaton, provide another example. In all cases, what is observed is that a sequence which can be generated easily can be hard to invert or compress. This phenomenon is the basis for the possibility of pseudorandom number generation or cryptography. Given a short seed or key as an initial specification, there are algorithms (such as that of figure 3.3) which yield long sequences from which the simplicity of the initial conditions is not apparent. The dynamics of the evolution has effectively ``encrypted'' the initial data to the point where it cannot be recovered by any simple computation.

Computation theory provides a characterization of this phenomenon. The process of generating a sequence is in the polynomial time class . But the process of recognizing the origins of the sequence is in the class of non-deterministic polynomial time computations. It seems that so that there exist at least some cases in which the problem of recognition cannot be solved by a polynomial time computation.

It is clear that an exhaustive search through all possible initial conditions would reveal whether any ``simple'' one yielded a particular sequence. But the number of such possible initial conditions is exponentially large, so that such a search could take an exponentially long time. As a result, it would rapidly become infeasible.

The standard statistical tests of randomness applied to physical systems are computationally quite simple. As a result, they are unable to detect regularities that require say exponential time computations to recognize. Thus if a system ``encrypts'' its initial data to the same degree as that of say figure 3.3 does, it will yield behaviour that appears random for practical purposes.

[ Figure 3.2 ] Examples of patterns generated by various simple , cellular automata, evolving from a single nonzero initial site. Some rules are seen to give comparatively simple patterns, while other rules give patterns which seem in many respects random. The generation of randomness in this way may well be the source of thermodynamic behaviour in many systems. It is necessary for the reproduction of continuum phenomena such as diffusion.

[ Figure 3.3 ] The pattern generated by , rule 30 starting from a single site initial seed. This rule has the form Despite the simplicity of this rule, the patterns it generates are so complicated as to seem in many respects random. Thus for example the centre column in this picture seems random for at least a million sites according to standard statistical randomness tests. This rule is probably the simplest cellular automaton which generates random behaviour in this way. It was found by an explicit search over all possible rules.

I believe that most of the randomization associated with thermodynamic behaviour is of the mathematical type illustrated in figure 3.3. Even though the initial conditions are simple, the system encrypts them to the point where no feasible measurements or computations can recover them.

previous  l  next