3.5 WHAT IS A (Best web hosting site) RANDOM SEQUENCE? 145 sequence
3.5 WHAT IS A RANDOM SEQUENCE? 145 sequence 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, . . . . It has been conjectured that this sequence is co-distributed, but nobody has yet been able to prove that it is even l-distributed. Let us analyze these concepts a little more closely in the case when Ic equals a million. A binary sequence that is lOOOOOO-distributed is going to have runs of a million zeros in a row! Similarly, a [ 0,l) sequence that is lOOOOOO-distributed is going to have runs of a million consecutive values each of which is less than 4. It is true that this will happen only (4) loooooo of the time, on the average, but the fact is that it does happen. Indeed, this phenomenon will occur in any truly random sequence, using our intuitive notion of truly random. One can easily imagine that such a situation will have a drastic effect if this set of a million truly random numbers is being used in a computer-simulation experiment; there would be good reason to complain about the random number generator. However, if we have a sequence of numbers that never has runs of a million consecutive U s less than f , the sequence is not random, and it will not be a suitable source of numbers for other conceivable applications that use extremely long blocks of U s as input. In summary, a truly random sequence will exhibit local nonrandomness. Local nonrandomness is necessary in some applications, but it is disastrous in others. We are forced to conclude that no sequence of random numbers can be adequate for every application. In a similar vein, one may argue that there is no way to judge whether a finite sequence is random or not; any particular sequence is just as likely as any other one. These facts are definitely stumbling blocks if we are ever to have a useful definition of randomness, but they are not really cause for alarm. It is still possible to give a definition for the randomness of infinite sequences of real numbers in such a way that the corresponding theory (viewed properly) will give us a great deal of insight concerning the ordinary finite sequences of rational numbers that are actually generated on a computer. Furthermore, we shall see later in this section that there are several plausible definitions of randomness for finite sequences. B. co-distributed sequences. Let us now undertake a brief study of the theory of sequences that are co-distributed. To describe the theory adequately, we will need to use a bit of higher mathematics, so we assume in the remainder of this subsection that the reader knows the material ordinarily taught in an advanced calculus course. First it is convenient to generalize Definition A, since the limit appearing there does not exist for all sequences. Let us define Fr(S(n)) = lim sup (~(n)/n), &(S(n)) = lim&f (~(n)/n). (7) 72-00 Then Pr(S(n)), i f i t exists, is the common value of Pr(S(n)) and E(S(n)). We have seen that a k-distributed [ 0,l) sequence leads to a k-distributed bary sequence, if U is replaced by [MY]. Our first theorem shows that a converse result is also true.