1. Prove k k & F(X 1 ) . max 1,..., N - 1 N'N F ( F.) , 1- F(XN ) k - 1 =max MAX max N - F(3.) F (3.) -1,...,N -1 ....,N which was used in the derivation of D N . 2. Consider the Fibonacci generator : S | = $, + ,, | mod 231, where So = $1 = 1. Apply the Kolmogorov-Smirnov test to the first 1000 numbers (including the seeds) obtained from this generator. What are your conclusions 3. Show that the serial correlation coefficient p is equal to -1, if n = 2, provided the denominator is not 4. In this problem , you can use any good pseudorandom generator . Let u (i) be the runs-up of length i, for i = 1, 2,3, and "(4) be the runs -up of length 4 or more . Compute the serial correlation coefficient pA for u (1), " (2), "(3), u(4). Repeat this procedure 100 times to obtain 100 correlation coefficients. Does the serial coefficient test indicate dependency ? Can you explain the result intuitively ? Based on your conclusions , explain whether one can apply the x3- test directly to the run -up counts (assuming that we know the probability of run-up of length i) like it was applied in the gap test? (Hint: think about the basic assumptions required to apply the x3- test, and investigate whether these assumptions are satisfied by "run-up events".) 5. Consider the following modification of the run test . Let's start with the same sequence used in the run test description 2, 7, 8, 1, 9, 6, 4, 0, 3, 11, 10, 17 The first run -up is | 2 7 8 |, and it is a run -up of length three . Now we discard the number that comes after the run -up, in this case , it is 1, and use the next number in the sequence , 9, to start the next run. Since after 9 comes 6, we have a run-up of length one, | 9 |, and we discard the number 6, and continue in this way, discarding the number that comes next after a run-up event occurs. Here are the new runs-up events for the above sequence: 2 7 8 9 4 3 11 [ 17 | Under this modified run test , we have run -up of lengths 3,1,1,2,1 (a) Argue that in the modified run test , the run -up events are independent , and a simple x'-test can be used to design a modified run test. (You can use the approach in the previous exercise to investigate independence numerically). (b) Prove that in the modified run test, the probability of having a run-up of length n is my -m. and the probability of having a run-up of length n or more is . (c) Design a modified run test using parts (a) and (b), and apply it to Mersenne twister . 6. Design a statistical test for random number generators , based on the following result . Then apply the test to any generator you want and explain the results. Fact: A coin is flipped consecutively until the number of heads obtained equals the number of tails . The output of a flip is heads with probability p. Define the random variable X as: X = the first time the total number of heads is equal to the total number of tails. Observe that X takes values 2,4,6,.... For example, if the outcomes of one experiment are: H, H, T, H,T,T then the value of X for this outcome is 6. Here is the probability density function of X : 2n P(X = 2n } = 2n - I n p(1 -p)". (A proof of this statement can be found in "Introduction to Probability Models ", Sheldon Ross , 8th edition , page 128 .)
