Random Number Generators

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.”

-John von Neumann, 1951

Contents:

• Properties of Random Numbers
• Pseudo-Random Numbers
• Generating Random Numbers
• Midsquare method
• Linear Congruential Method (Mixed type)
• Multiplicative Linear Congruential Method
• Additive Congruential Method

Properties of Random Numbers:

• Uniformity: The numbers generated appear to be distributed uniformly on (0, 1);

• Independence: The numbers generated show no correlation with each other;

A ‘good’ random-number generator should satisfy the following properties:

• Replication: The numbers should be replicable (e.g., for debugging or comparison of different systems).

• Cycle length: It should take long before numbers start to repeat;

• Speed: The generator should be fast;

• Memory usage: The generator should not require a lot of storage

Pseudo Random Numbers:

So, we cannot generate True Random Numbers. But Pseudo Random Numbers can be generated with Mathematical formulae.

Approach: Arithmetically generation (calculation) of random numbers

“Pseudo”, because generating numbers using a known method removes the potential for true randomness.

Goal: To produce a sequence of numbers in [0,1] that simulates, or imitates, the ideal properties of random numbers (RN).

Properties:

Uniformity

Independence

Random number R_i must be independently drawn from a uniform distribution with PDF:

Advantages of Pseudo Random Numbers:

1. Fast
2. Portable to different computers
3. Have sufficiently long cycle
4. Replicable
   1. Verification and debugging
   2. Use identical stream of random numbers for different systems
5. Closely approximate the ideal statistical properties of
   1. uniformity and
   2. independence

Problems when generating pseudo-random numbers:

1. The generated numbers might not be uniformly distributed
2. The generated numbers might be discrete-valued instead of continuous-valued
3. The mean of the generated numbers might be too high or too low
4. The variance of the generated numbers might be too high or too low
5. There might be dependence:
   1. Autocorrelation between numbers
   2. Numbers successively higher or lower than adjacent numbers
   3. Several numbers above the mean followed by several numbers below the mean

1. Generating Random Numbers:

Most random-number generators are of the form:

Start with z₀ (seed)

For n = 1, 2, . . . generate

z_n = f (z_n−1)

and

u_n = g(z_n)

f is the pseudo-random generator

g is the output function

{u₀, u₁, . . .} is the sequence of uniform random numbers on the interval (0, 1).

Midsquare method

Start with a 4-digit number z0 (seed)

Square it to obtain 8-digits (if necessary, append zeros to the left)

Take the middle 4 digits to obtain the next 4-digit number z1; then square z1 and take the middle 4-digits again and so on.

We get uniform random number by placing the decimal point at the left of each z_i (i.e., divide by 10000).

Examples

For z0 = 1234 we get 0.1234, 0.5227, 0.3215, 0.3362, 0.3030, 0.1809, 0.2724, 0.4201, 0.6484, 0.0422, 0.1780, 0.1684, 0.8361, 0.8561, 0.2907, …

i	Zi	Ui	Zi×Zi
0	7182	–	51581124
1	5811	0.5811	33767721
2	7677	0.7677	58936329
3	9363	0.9363	87665769

Clearly, random-number generators involve a lot more than doing ‘something strange’ to a number to obtain the next

Linear Congruential Method

Most random-number generators in use today are linear congruential generators. They produce a sequence of integers between 0 and m − 1 according to

This can be alternatively denoted as:

a is the multiplier, c the increment and m the modulus.

To obtain uniform random numbers on (0, 1) we take

Assumption: m > 0 and a < m, c < m, X₀ < m

The selection of the values for a, c, m, and X₀ drastically affects the statistical properties and the cycle length

Examples:

• For (a, c, m) = (1, 5, 13) and x₀ = 1 we get the sequence 1, 6, 11, 3, 8, 0, 5, 10, 2, 7, 12, 4, 9, 1, … which has full period (of 13).

• For (a, c, m) = (2, 5, 13) and x₀ = 1 we get the sequence 1, 7, 6, 4, 0, 5, 2, 9, 10, 12, 3, 11, 1, … which has a period of 12. If we take x₀ = 8, we get the sequence 8, 8, 8, … (period of 1).

Use a = 13, c = 0, and m = 64

• The period of the generator is very low

• Seed X₀ influences the sequence

i	Xi X0=1	Xi X0=2	Xi X0=3	Xi X0=4
0	1	2	3	4
1	13	26	39	52
2	41	18	59	36
3	21	42	63	20
4	17	34	51	4
5	29	58	23
6	57	50	43
7	37	10	47
8	33	2	35
9	45	7
10	9	27
11	53	31
12	49	19
13	61	55
14	25	11
15	5	15
16	1	3

NOTE

if c == 0 (equal to) it is called a multiplicative congruential generator

if c != 0 (not equal to) it is called a mixed congruential generator

Maximum Density

• The values assumed by Ri , i=1,2,… leave no large gaps on [0,1]
• Problem: Instead of continuous, each Ri  is discrete
• Solution: a very large integer for modulus m. Approximation appears to be of little consequence

Maximum Period

• To achieve maximum density and avoid cycling
• Achieved by proper choice of a, c, m, and X0

Most digital computers use a binary representation of numbers

• Speed and efficiency are aided by a modulus, m, to be (or close to) a power of 2.

A linear congruential generator has full period (cycle length is m) if and only if the following conditions hold:

• The only positive integer that exactly divides both m and c is 1;
• If q is a prime number that divides m, then q divides a − 1;
• If 4 divides m, then 4 divides a − 1.

Multiplicative congruential generators

These generators produce a sequence of integers between 0 and m − 1 according to

So, they are linear congruential generators with c = 0.

They cannot have full period, but it is possible to obtain period m − 1 (so each integer 1, …, m − 1 is obtained

exactly once in each cycle) if a and m are chosen carefully. For example, as a = 630360016 and m = 2³¹ − 1.

Additive congruential generators

These generators produce integers according to

where k ≥ 2. Uniform random numbers can again be obtained from

These generators can have a long period upto m^k

Disadvantage:

Consider the case k = 2 (the Fibonacci generator). If we take three consecutive numbers u_n−2, u_n−1 and u_n, then it will never happen that

u_n−2 < u_n < u_n−1

or

u_n−1 < u_n < u_n−2

whereas for true uniform variables both of these orderings occur with probability 1/6.

Applications in Security and privacy:

Desirable properties:

• given only a number produced by the generator, it is impossible to predict previous and future numbers;
• the numbers produced contain no known biases;
• the generator has a large period;
• the generator can seed itself at any position within that period with equal probability.

For example, when using the generator to produce a session ID on a web server: we don’t want user n to predict user n + 1’s session ID.

Choosing the initial seed

We need to find entropy or “genuine randomness” as the seed starting point for generating other random numbers. Some typical sources that in principle we may be able to access in software include:

• time between key presses,

• positions of mouse movements,

• amount of free memory,

• CPU temperature.

In practice: Operating Systems collect information and help to generate the random seed using

• time (wall-clock and since boot),

• performance and CPU counter data,

• timings of context switches and other software interrupts.

Generating Random Numbers using R

Linear Congruential Generators

lcg.rand <- function(n=10) {
  
  rng <- vector(length = n)
  
  m <- 2 ** 32
  a <- 1103515245
  c <- 12345

  # Set the seed using the current system time in microseconds
  d <- as.numeric(Sys.time()) * 1000
  
  for (i in 1:n) {
    d <- (a * d + c) %% m
    rng[i] <- d / m
  }
  
  return(rng)
}

We can use the function to generate random numbers U(0,1)

# Print 10 random numbers on the half-open interval [0, 1)
lcg.rand()

output:
##  [1] 0.6539917 0.1913481 0.8203220 0.3555346 0.9422340 0.7328100 0.2517834
##  [8] 0.3047419 0.6773148 0.4484053

Multiplicative Congruential Generators (Lehmer RNGs)

lehmer.rng <- function(n=10) {
  
  rng <- vector(length = n)
  
  m <- 2147483647
  a <- 48271
  q <- 44488
  r <- 3399
  
  # Set the seed using the current system time in microseconds. 
  # The initial seed value must be coprime to the modulus m, 
  # which we are not really concerning ourselves with for this example.
  d <- as.numeric(Sys.time())
  
  for (i in 1:n) {
    h <- d / q
    l <- d %% q
    t <- a * l - r * h
    if (t > 0) {
      d <- t
    }
    else {
      d <- t + m
    }
    
    rng[i] <- d / m
  }
  return(rng)
}

# Print the first 10 randomly generated numbers
lehmer.rng()

Output:
##  [1] 0.68360284 0.19261879 0.90183779 0.61194347 0.12303345 0.94781037
##  [7] 0.75432509 0.02637506 0.15072837 0.80928036

References:

Multiplicative Congruential Generators 

Linear Congruential Generators

Wikipedia: Linear congruential generator