1. Write a program (any language, sequential is o.k.) for a linear congruential random number generator of the form LCG ( a, c, m, seed ). The program will call the random number generator for some number of trials. Calculate the average and variance of the sequence of random numbers generated.
Run the program for LCG (a=13445, c=0, m=65536, seed=16811) with sequence sizes of 10, 100, 1000, and 10000. Plot the errors in the average and variance versus sample size. Discuss your results. (Many people like gnuplot, we also have xmgr which has a tutorial in the CSEP book.)
Solution: The source code is written by C. And click output file to see the result. Then the plot graph is listing here.
After 10000 times, the average error is getting to be 0. The variance error is also getting 0. Roughly to say, the linear congruential random number generator, LCG (a=13445, c=0, m=65536, seed=16811), would be a random number generator. But it still needs some tests to identify.
2. Modify your program to print the sequence of numbers that it generates and run it on a small simple generator LCG ( a=5, c=0, m=16, seed ) for one cycle of numbers and vary the seed from 0 to 15. How many independent (i.e. not cyclical shifts of one another) sequences are there? Is there a pattern observable in even versus odd integers? Discuss possible reasons for this behavior.
Solution: Click the source code to see program file. And also output file to see the result.
The result points out that:
Seed Pattern
0 0
1 5 9 13 1
2 10 2
3 15 11 7 3
4 4
5 9 13 1 5
6 14 6
7 3 15 11 7
8 8
9 13 1 5 9
10 2 10
11 7 3 15 11
12 12
13 1 5 9 13
14 6 14
15 11 7 3 15
And there are some kinds of patterns:
Pattern Seed
0 0
5 9 13 1 1, 5, 9, 13
10 2 2, 10
15 11 7 3 3, 7, 11, 15
4 4
14, 6 6, 14
8 8
12 12
Thus, there are eight independent sequences. Parts of seeds become the
same patterns. The seed 1, 5, 9, and 13, fall in the 5, 9, 13, 1 cyclic
sequence.
In original view, Even numbers become one seed one pattern except seed 6 and 14. The seed 6 and 14 become a pattern. On the other hand, the odd numbers become two patterns. in each pattern, the differences of seeds are four's multipler.
Since the equation of linear congruential random number generator becomes Xn+1 = (5 * Xn) mod 16. If let Xn = X0, then
(5 * X0) mod 16
= ((1 + 4) * X0) mod 16
= (X0 + 4 * X0) mod 16 ----------- (1)
In addition, the X0 , 4 * X0, and (4*X0) mod 16 are listing:
X0 4 * X0 mod 16
1 4 4
3 12 12
5 20 4
7 28 12
9 36 4
11 44 12
13 52 4
15 60 12
Thus, the conclusion is:
(1) => X0 + 4 (when X0 = 1, 5, 9, 13)
+ 12 (when X0 = 3, 7, 11, 15)
The same process is applying on the even number:
X0 4 * X0 mod 16
0 0 0
2 8 8
4 16 0
6 24 8
8 32 0
10 40 8
12 48 0
14 56 8
Wen X0 is even number, the
(1) => X0 + 0 (when X0 = 0, 4, 8, 12)
+ 8 (when X0 = 2, 6, 10, 14)
Therefore, the behavior of the random number sequence is very clear.
3. Modify your program to output (x,y) pairs of numbers for all adjacent numbers (X0,X1), (X1,X2), (X2,X3), and so on. Plot these (x,y) values for the following generators:
LCG ( a=66, c=0, m=2**31, seed=0) for 4,096 random numbers.
LCG ( a=5, c=0, m=2**31-1, seed=0) for 4,096 random numbers.
Discuss why these are poor (or not) generators.
Solution:
Since when seed = 0, the all random numbers are 0. I change seed to the
prime number 7.
The LCG ( a=66, c=0, m=2**31, seed=7) program is here, and the output file is here. The LCG (a=5, c=0, m=2**31-1, seed=7) program is here, and the output file is here. After using xgmr to plot the all adjacent numbers, the results are listing in postscript file one and two.
From the two plots, these two are poor generators. The first one will become 0 for good after some n. On the other side, the second one only become five lines. The other side, a good generator should have the random number sequence equally distribute in the square 1.0 * 1.0. Therefore, they are not good generators.