144 RANDOM NUMBERS 3.5 general, for any positive integer k we can require our sequence to be k-distributed in the following sense: Definition B. The sequence (1) is said to be k-distributed if Pr(ul < U, . . . (vk -uk) (5) for a11 choices of real numbers Uj, vj, with 0 2 Uj < 1-j < 1, for 1 5 j 5 k. An equidistributed sequence is a l-distributed sequence. Note that if k > 1, a k-distributed sequence is always (k -1)-distributed, since we may set uk = 0 and vk = 1 in Eq. (5). Thus, in particular, any sequence that is known to be 4-distributed must also be 3-distributed, a-distributed, and equidistributed. We can investigate the largest k for which a given sequence is k-distributed; and this leads us to formulate Definition C. A sequence is said to be co-distributed if it is k-distributed for all positive integers k . So far we have considered [ 0,l) sequences, i.e., sequences of real numbers lying between zero and one. The same ideas apply to integer-valued sequences; let us say a sequence (Xn) = X0, X1, X2, . . . is a bary sequence if each X, is one of the integers 0, 1, . . . , b - 1. Thus, a 2-ary (binary) sequence is a sequence of zeros and ones. We also say that a k-digit bary number is a string of k integers ~1~2 . . . xk, where 0 5 xj < b for 1 5 j 5 k. Definition D. A b-ary sequence is said to be k-distributed if Pr(x,&+1.. .&f&l = X1X2.. . xk) = l/bk (6) for all b-ary numbers x1x2 . . . xk. It is clear from this definition that if U,-,, VI, . . . is a k-distributed [ 0,l) sequence, then the sequence LbUoJ, [bUIJ, . . . is a k-distributed bary sequence. (If we set Uj = xj/b, vj = (Zj + 1)/b, X, = [bun], Eq. (5) becomes Eq. (6).) Furthermore, every k-distributed bary sequence is also (k -1)-distributed, if k > 1: we add together the probabilities for the bary numbers xl.. . xk-10, Xl . . . xk-1 1, . . . , xl . . . xk-1 (b -1) to obtain Pr(x, . . .a&+&2 = X1 . . .x&l) = l/b - . (Probabilities for disjoint events are additive; see exercise 5.) It therefore is natural to speak of an co-distributed bary sequence, as in Definition C above. The representation of a positive real number in the radix-b number system may be regarded as a bary sequence; for example, 7r corresponds to the lo-ary
This entry was posted
on Saturday, March 22nd, 2008 at 1:14 am and is filed under Coldfusion.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.