3.5 WHAT IS A RANDOM SEQUENCE? 143 an (Sri lanka web server)
3.5 WHAT IS A RANDOM SEQUENCE? 143 an adequate definition of randomness according to these criteria, although many interesting questions remain to be answered. Let u and u be real numbers, 0 5 u < u 2 1. If U is a random variable that is uniformly distributed between 0 and 1, the probability that u 5 U < w is equal to ZI - u. For example, the probability that 3 5 U < $ is 4. How can we translate this property of the single number U into a property of the infinite sequence UO, VI, Uz, . . . ? The obvious answer is to count how many times U, lies between u and w, and the average number of times should equal w - u. Our intuitive idea of probability is based in this way on the frequency of occurrence. More precisely, let v(n) be the number of values of j, 0 5 j < n, such that u 5 Uj < v; we want the ratio v(n)/n to approach the value v - u as n approaches infinity: lim V(n)/n = 2, - u. (4 n-00 If this condition holds for all choices of u and v, the sequence is said to be equidistributed. Let S(n) be a statement about the integer n and the sequence VI, U2, . . . ; for example, S(n) might be the statement considered above, u < U, < v. We can generalize the idea used in the preceding paragraph to define the probability that S(n) is true with respect to a particular infinite sequence: Let v(n) be the number of values of j, 0 5 j < n, such that S(j) is true. Definition A. We say Pr(S(n)) = X, if limn–rm u(n)/n = X. (Read, The probability that S(n) is true equals X, if the limit as n tends to infinity of v(n)/n equals A. ) In terms of this notation, the sequence Uo, VI, . . . is equidistributed if and only if Pr(u 2 U,, < V) = v -u, for all real numbers u, u with 0 5 u < v 5 1. A sequence may be equidistributed without being random. For example, if uo, Ul, … and VO, VI, . . . are equidistributed sequences, it is not hard to show that the sequence ~,~,W2,~,.*. = @Jo, $+po, gJ1, i+g4 7 … is also equidistributed, since the subsequence DUO, $UI, . . . is equidistributed between 0 and 4, while the alternate terms f + $VO, 3 + JVl, . . . , are equi- distributed between 4 and 1. In the sequence of W s, a value less than i is always followed by a value greater than or equal to 4, and conversely; hence the sequence is not random by any reasonable definition. A stronger property than equidistribution is needed. A natural generalization of the equidistribution property, which removes the objection stated in the preceding paragraph, is to consider adjacent pairs of numbers of our sequence. We can require the sequence to satisfy the condition Pr(ul 5 U, < 211 and ~2 2 G+I < 7~2)= (ul -u1)(v2 - u2) (4)