Congruential methods; rejection method

Congruential methods

Congruential generators produce integers X1, X2, ... by modular arithmetic, and the random numbers are R = X/m.

1. Mixed (linear) congruential method

X(n+1) = (a X(n) + c) mod m, with seed X0, multiplier a, increment c and modulus m. Parameters must give a long period; the maximum period is m.

Example: a = 5, c = 3, m = 16, X0 = 7: X1 = (5 x 7 + 3) mod 16 = 38 mod 16 = 6, so R1 = 6/16 = 0.375 X2 = (5 x 6 + 3) mod 16 = 33 mod 16 = 1, so R2 = 0.0625 X3 = (5 x 1 + 3) mod 16 = 8, so R3 = 0.5 X4 = 11, X5 = 10, X6 = 5 ... and it returns to 7 after 16 steps (full period).

2. Multiplicative congruential method (c = 0)

X(n+1) = a X(n) mod m. It is faster, but the maximum period is smaller (for m = 2^b, at most m/4, and the seed must be odd). Example: a = 13, m = 64, X0 = 1 gives 13, 41, 21, 17, 29, 57, 37, 33 (R = 0.203, 0.641 ...).

3. Additive congruential method

X(n) = (X(n-1) + X(n-k)) mod m, using earlier values of the sequence. Example with k = 2, m = 100, seeds 65 and 89: 54, 43, 97, 40, 37, 77.

Rejection (acceptance-rejection) method

Rejection method generates random variates from a distribution by generating candidates and discarding those that do not satisfy a condition. The values that survive follow the wanted distribution.

Steps for a density f(x) on [a, b] with maximum value M:

1. Generate R1 uniform on (0, 1) and set x = a + (b - a) R1.
2. Generate R2 uniform on (0, 1) and set y = M R2.
3. If y <= f(x), accept x as the variate; otherwise reject it and go to step 1.

Example: f(x) = 2x on [0, 1], M = 2. If R1 = 0.6, R2 = 0.5: x = 0.6, y = 1.0, f(x) = 1.2, y <= f(x) so accept 0.6. If R1 = 0.2, R2 = 0.9: x = 0.2, y = 1.8, f(x) = 0.4, so reject. On average half of the pairs are accepted here.

A simpler example: to get uniform values on (1/4, 1) from U(0, 1), generate R and reject it if R < 1/4. The rejection method is also used to generate Poisson variates (multiply uniform random numbers until the product is below e^(-lambda)). Its efficiency is the fraction of accepted candidates.