Random Number Generation � Handout #12

Random Number Generation � Handout #12 (Note HW!)

So, we've learned that the behavior of a system can be characterized by two things:� the interarrival time distribution and the service time distribution (given that the arrivals and servicing are independent and identically distributed).� With a computer program simulation, we may have to rely on random numbers to test the simulation.

We know though that a computer's memory is finite and that only a certain range of numbers can be generated.� For example if integers on a certain computer are 16-bits long (assume without using exponents and negative numbers), then we can only generate 2¹⁶ numbers, or 65536 numbers.� How then do we select from this range so that we get random numbers?

We can't get "real" random numbers!

We have to use techniques to get pseudo-random numbers.

We know that we can generate integers in some range.

Let i = {�� }

Let X_i be the integers generated.

Let m be a positive integer.

Let 1..m-1 be the range of integers generated.

Then we know:

R_i = X_i/m

lies between �� and �� .

For example, let the number of bits that represent positive integers be 16 as above.� Then:

{�� } is the range of numbers generated

m �1 = ��

m = ��

So, we see that R lies between 0 and 1.

R₁ = X₁/m = 1/65537 = 1.525855623541e-5

R₂ = X₂/m = 2/65537 = 3.051711247082e-5

R₁₀₀₀ = X₁₀₀₀/m = 1000/65537 = 0.01525855623541

R₁₀₀₀₀ = X₁₀₀₀₀/m = 10000/65537 = 0.1525855623541

R₆₅₅₃₄ = X₆₅₅₃₄/m = 65534/65537 = 0.9999542243313

R₆₅₅₃₅ = X₆₅₅₃₅/m = 65535/65537 = 0.9999694828875

R₆₅₅₃₆ = X₆₅₅₃₆/m = 65536/65537 = 0.9999847414438

Thus,

R_i = {1.525855623541e-5�0.9999847414438}

Given these numbers, how do we make a random sequence R_i?

A sequence of random numbers R1, R2, �., must have two statistical properties:

1. �� .� Random numbers must be selected from a continuous uniform distribution between zero and one.

2. �� .� The choice of one random number does not affect the choice of another.

Midsquare Method

Let:

X₀:� initial seed

X_i = middle digits ( (X_i-1)² )

R_i = X_i (10^{-#middle digits})

Example:

X₀ = 151

middle digits are 10³, 10², and 10¹ places

X₁ => (151)² = 22801 => ��

R₁ = �� (10^-3) = ��

X₂ => (�� )² = 78400 => 840

R₂ = 840 (10^-3) = 0.84

X₃ => (840)² = 705600 => 560

R₃ = 560 (10^-3) = 0.56

�

Midproduct Technique

Let:

X₀', X₀: initial seeds with same number of digits, D.

U₁ = ( X₀' ) ( X₀ )

X₁ = D middle digits ( (U₁) )

R₁ = X₁ (10^-D)

Continue with U₂ = ( X₀ ) ( X₁ )

Example:

X₀' = 151, X₀ = 780

U₁ = ( X₀' ) ( X₀ ) = (151)(780) = 117780

X₁ = ��

R₁ = ��

U₂ = ( X₀ ) ( X₁ ) = (780)(�� ) = 606840

X₂ = 684

R₂ = 0.684

�

Linear Congruential Method

Another way is a simple recurrence relation:

X_i = a � X_i-1�+ c (mod m)

R_i = (X_i)/m

where,

a � constant multiplier:� positive integer, and

c � increment:� non-negative integer, and

m � modulus:� positive integer, and

X₀ � starting seed: positive integer.

When �� , the Linear Congruential Method is called the Multiplicative Congruential Method, and when �� , it is called the Mixed Congruential Method.

Note that the numbers generated from X_i = a � X_i-1�+ c (mod m) can only take on the values:

{0, 1, 2, �, m-1}

and that the random numbers generated from R_i = (X_i)/m can only take on the values,

I = {0, 1/m, 2/m, �, (m-1)/m}

Therefore, each R_i is �� on I, not �� .� This will be acceptable if m is very large.��

Example:

a = 7, c = 23, m = 8, X₀ = 1.

What is the range of possible numbers?� {�� }

X_i = 7 � X_i-1�+ 23 (mod 8)

R_i = (X_i)/8

i	7 � X_i-1�+ 5 (mod 8)	X_i	R_i
0	-	1	0.125
1	7 � 1+ 23 (mod 8) = 30 mod 8	6	0.75
2	7 � 6+ 23 (mod 8) = 65 mod 8	2	0.25
3	7 � 2+ 23 (mod 8) = 37 mod 8	5	0.625
4	7 � 5+ 23 (mod 8) = 58 mod 8	2	0.25
�	Sequence repeats!	�	�

This sequence is cyclic with period equal to �� repeats.

Kobayashi's example:

a = 13, c = 10, m = 10, X₀ = 2.

What is the range of possible numbers?� {�� }

X_i = 13 � X_i-1�+ 10 (mod 10)

i	13 � X_i-1�+ 10 (mod 10)	X_i
0	-	2
1	13 � 2_�+ 10 (mod 10) = 26 mod 10	6
2	13 � 6_�+ 10 (mod 10) = 88 mod 10	8
3	13 � 8_�+ 10 (mod 10) = 114 mod 10	4
4	13 � 4_�+ 10 (mod 10) = 62 mod 10	2
5	13 � 2_�+ 10 (mod 10) = 26 mod 10	6
�	Sequence repeats!	�

This sequence is also cyclic and has a period of �� .

We need to be careful about choices of a, c, m, and X₀ or we'll get a small period.� We would like the period to be close to �� �(a full cycle period).

To obtain the largest period possible for m equal to a power of two we need:

m = 2^b

c = relatively prime to m

a = 1 + 4k, where k is an integer.

The longest possible period then is P = m = 2^b.

Multiplicative Congruential Method

Let c = 0, then we have a Multiplicative Congruential Method:

X_i = a � X_i-1(mod m)

where,

a:� positive integer, and

m:� positive integer, and

X₀:� starting seed.

The longest period for the multiplicative congruential method for m a power of two (m = 2^b), is:

P = m/4 = m^b-2.

This occurs when:

m = 2^b, c = 0, a = �3 + 8k, where k is an integer, and, X₀ = an odd integer.

A good Mulitplicative Congruential Generator is one where the period is �� .� A way to achieve this is when:

m = 2p^e, where p is an odd prime number and e is a positive integer.

a is a primitive root of m.

X₀ is relatively prime to m.

Lewis, Goodman, & Miller (1969), page 237 Kobayashi and page 266 Banks:

m = 2³¹ � 1 (which happens to be a prime number)

a^k = 7⁵

X_i = 7⁵ X_i-1(mod 2³¹ � 1)

Then,

P = m � 1, which is over ��

Homework:� Answer the following two questions:

Using the multiplicative method, set m = 32, and a = 3.� What is the period if the seed Z₀ is an odd number?� Find the sequence when Z₀ = 1.� Do the same for Z₀ = 5.� What will happen if an even number is chosen as a seed?
Using the mixed congruential method, set m = 32, a = 5, and c = 3.� What is the period of the resultant sequence?� Generate the sequence with Z₀ = 2.

Due Tuesday, November 4, 2003.