Homework 6, Chapter 7 Solution

Problem 7: The sequence .54, .73, .98, .11, .68 has been generated.
Use the Kolmogorov-Smirnov test with a =.05 to determine if the
hypothesis that the numbers are uniformly distributed on the
interval [0,1] can be rejected.

Sort the numbers in order

Generate the test values to compare to. For ease of expression in MathCad, I have
separated the upper and lower limits into two arrays.

Compute the differences between the random values and the expected distribution limits

Find the greatest deviation

The critical value to compare to for N=5 and a = .05 is .565. Since the maximum
deviation is less than the critical value, the null hypothesis cannot be rejected.

Problem 26: Use the principles described in this chapter to develop your own
linear congruential random number generator

To create a generator with the maximum possible period, we can pick parameters as follows:
m is a power of 2
c is relatively prime to m
a = 1+4k, where k is an integer.

Generate a set of random numbers

Verify that the sequence does not repeat over 0..m-1

This is a maximal length sequence

Plotting the sequence, it looks noise-like

Problem 27: Use the principles described in this chapter to develop your own combined
linear congruential random-number generator.

Generate (at least) two sequences with different cycle lengths.
They both use a prime modulus with a^k-1 relatively prime to m.
m1 and m2 are chosen to be adjacent primes so (m1-1) and (m2-1)
have minimal small divisors.

Verify that the smallest k, such that m divides (a^k)-1 is k=m-1

This a2, m2 combination passes the test.

Any set of parameters would do, as long as the sequence lengths are different
and the sequences are maximal length. See pp 259-260 for properties of the
parameters that guarantee the maximal length sequence.

Note: if m is prime, the longest sequence length is m-1, which is even.
If m is a power of 2, the longest sequence length will be a power of 2,
which is also even. This means that the sequence lengths will have a
common factor of 2 (at least), which results in a shorter overall sequence
length.

Generate two sets of random numbers

Combine them using the techniques of Section 7.3.2