154 RANDOM NUMBERS (Sri lanka web server) 3.5 Note that the definition
154 RANDOM NUMBERS 3.5 Note that the definition of equidistribution says that Pr(u 2 U, < U) = v -U. There is an obvious way to generalize this definition, using measure theory: If S c [ 0,l) is a set of measure 1-1, then Pr(U, E S) = p, (27) for all random sequences (Un). In particular, if S is the set of rationals, it has measure zero, so no sequence of rational numbers is equidistributed in this generalized sense. It is reasonable to expect that Theorem B could be extended to Lebesgue integration instead of Riemann integration, if property (27) is stipulated. However, once again we find that definition (27) is too strict, for no sequence satisfies that property. If Ue, Ui, . . . is any sequence, the set s = {UO,Ul,...} is of measure zero, yet Pr(U, E S) = 1. Thus, by the force of the same argument we used to exclude rationals from random sequences, we can exclude all random sequences. So far Definition Rl has proved to be defensible. There are, however, some quite valid objections to it. For example, if we have a random sequence in the intuitive sense, the infinite subsequence uo, Ul, u4, us, . ", u,a, . . . (28) should also be a random sequence. This is not always true for an oo-distributed sequence. In fact, if we take any oo-distributed sequence and set U,Z c 0 for all n, the counts ok that appear in the test of k-distributivity are changed by at most fi, so the limits of the ratios vk(n)/n remain unchanged. Definition Rl unfortunately fails to satisfy this randomness criterion. Perhaps we should strengthen Rl as follows: Definition R3. A [ 0,l) sequence is said to be random if each of its infinite subsequences is oo-distributed. Once again, however, the definition turns out to be too strict; any equidistributed sequence (Un) has a monotonic subsequence with US, < US, < US, < . . . . The secret is to restrict the subsequences so that they could be defined by somebody who does not look at U, before deciding whether or not it is to be in the subsequence. The following definition now suggests itself: Definition R4. A [ 0,l) seqyence (Un) is said to be random if, for every effective algorithm that specifies an infinite sequence of distinct nonnegative integers sn for n > 0, the subsequence US,, U,,, US,, . . . corresponding to this algorithm is oo-distributed. The algorithms referred to in Definition R4 are effective procedures that compute s,, given n. (See Section 1.1.) Thus, for example, the sequence (.rr mod 1) will not satisfy R4, since it is either not equidistributed or there is an effective algorithm that determines an infinite subsequence sn with (~$0 mod 1) < (+ modl) < (7rITs2 < ... . Similarly, no explicitly defined sequence modl) can satisfy Definition R4; this is appropriate, if we agree that no explicitly defined sequence can really be random. It is quite likely, however, that the sequence (19~ mod 1) will satisfy Definition R4, for almost all real numbers 0 > 1; this is no