Notes

Chapter 10: Processes of Perception and Analysis

Section 3: Defining the Notion of Randomness


Inevitable regularities and Ramsey theory

One might have thought that there could be no meaningful type of regularity that would be present in all possible data of a given kind. But through the development since the late 1920s of Ramsey theory it has become clear that this is not the case. As one example, consider looking for runs of m equally spaced squares of the same color embedded in sequences of black and white squares of length n. The pictures below show results with m=3 for various n. For n<9 there are always some sequences in which no runs of length 3 exist. But it turns out that for n>=9 every single possible sequence contains at least one run of length 3. For any m the same is true for sufficiently large n; it is known that m=4 requires n>=35 and m=5 requires n>=178. (In problems like this the analog of n often grows extremely rapidly with m.) If one has a sufficiently long sequence, therefore, just knowing that a run of equally spaced identical elements exists in it does not narrow down at all what the sequence actually is, and can so cannot ultimately be considered a useful regularity.

(Compare pattern-avoiding sequences on page 944.)


From Stephen Wolfram: A New Kind of Science [citation]