Web hosting script - 3.5 WHAT IS A RANDOM SEQUENCE? 155 contradiction,
3.5 WHAT IS A RANDOM SEQUENCE? 155 contradiction, since almost all 6 tire uncomputable by algorithms. The following facts are known, for example: (i) The sequence (en mod 1) satisfies Definition R4 for almost all real 0 > 1, if co-distributed is replaced by l-distributed. This theorem was proved by J. F. Koksma, Compositio Mathematics 2 (1935), 250- 258. (ii) The particular sequence (escn) mod 1) is co-distributed for almost all real 19 > 1, if (s(n)) . for which s(n + 1) -s(n) -+ co 1s a sequence of integers as n + co. For example, we could have s(n) = n2, or s(n) = LnlgnJ. Definition R4 is much stronger than Definition Rl; but it is still reasonable to claim that Definition R4 is too weak. For example, let (Un) be a truly random sequence, and define the subsequence (Us,) by the following rules: SO = 0, and (for n > 0) s, is the smallest integer 2 n for which Us,–l, Us,-2, . . . , Usn-n are all less than 4. Thus we are considering the subsequence of values following the first consecutive run of n values less than 4. Suppose that U, < 3 corresponds to the value heads in the flipping of a coin. Gamblers tend to feel that a long run of heads makes the opposite condition, tails, more probable, assuming that a true coin is being used; and the subsequence (Us,) just defined corresponds to a gambling system for a man who places his nth bet on the coin toss following the first run of n consecutive heads. The gambler may think that Pr(Us, 2 4) is more than 4, but of course in a truly random sequence (Us,) will be completely random. No gambling system will ever be able to beat the odds! Definition R4 says nothing about subsequences formed according to such a gambling system, so apparently we need something more. Let us define a subsequence rule R as an infinite sequence of functions (fn(G,.. . > 2,)) where, for n 2 0, fn is a function of n variables, and the value of fn(sl,. . . , z,) is either 0 or 1. Here x1, . . . , 2, are elements of some set S. (Thus, in particular, fo is a constant function, either 0 or 1.) A sub- sequence rule R defines a subsequence of any infinite sequence (Xn) of elements of S as follows: The nth term X, is in the subsequence (Xn)R if and only if fn(XO,Xl,… ,XnpI) = 1. Note that the subsequence (Xn)R thus defined is not necessarily infinite, and it may in fact contain no elements at all. For example, the gambler s subsequence just described corresponds to the following subsequence rule: fo = 1; and for n > 0, fn(zl,. . . , z,) = 1 if and only if there is some k in the range 0 < k 2 n such that the k consecutive parameters x,, x,-l, . . . , x,-k+1 are all < 3 when m = n but not when k < m < n. A subsequence rule R is said to be computable if there is an effective algo- rithm that determines the value of fn(xl,. . . ,x,), when n and x1, . . . , 2, are given as input. We had better restrict ourselves to computable subsequence rules when trying to define randomness, lest we obtain an overly restrictive definition like R3 above. But effective algorithms cannot deal nicely with arbitrary real numbers as inputs; for example, if a real number x is specified by an infinite radix-10 expansion, there is no algorithm to determine if x is < 6 or not, since all digits of the number 0.333.. . have to be examined. Therefore computable subsequence rules do not apply to all [ 0,l) sequences, and it is convenient to base our next definition on bary sequences.