Page 85 - DCAP601_SIMULATION_AND_MODELING

Unit 6: Discrete System Simulation (III)

Using the exponential distribution as an instance: X ~ exp(), with CDF F(x) = 1 – exp(–x) where Notes
 > 0, the draws can be achieved from uniform random numbers u as:
i
–1
x = – log (1 – u ) .
i i
Apart from zero and one from the uniform random numbers make sure that –1and zero are
averted for the exponential distribution.
If a cumulative distribution function and density are obtainable, but no analytical formula for
the inverse, it is easy to execute the quantile function (i.e., the inverse function) using the
Newton-Raphson technique. This could then offer a generator for random numbers. Though,
while this can be a expedient approach, it is typically very much slower than direct methods.
The rejection method, which can be traced back to Von Neumann, often provides an efficient
alternative when inversion is slow. Suppose we wish to sample from a density f(·), and that f is
bounded by another density g: f(·)  cg(·). Sampling from f(·) can then be employed as:
repeat
generate a random examination vi from g(·),

until u cg(v )  f(v ), (1)
i i i
where u is independently U(0, 1) distributed. The potential profit comes when it is hard to
i
sample from f, but simple for g. The closer cg is to f, the better the bound, and the more
competent the rejection method. An instance for the normal distribution is specified below.
The most significant non-uniform distribution is the standard normal, which, unluckily, does
not have a logical inverse. Precise, non-iterative, rough calculations to the normal quantiles
exist, but would lead to a comparatively slow process.

A coarse method for generating e ~ IN[0, 1] depends on the estimated central limit result:
i
 12 
 u    e i (2)
6 

j
 j 1 
Although this is simple, it is twelve times slower than the uniform RNG, and of restricted
correctness.
The method of Box and Muller (1958) converts two uniform random numbers into two
independent standard normals:

1
(e , e ) = h (cos 2u , sin 2u ) where h = (–2 log u ) 2 (3)
i i+1 i i+1 i+1 i i
A well-tested and empirically acceptable generator must be used for input to the Box–Muller
method when (u, u ) are consecutively generated. Particularly, an LCG with poor lattice structure
i i+1
could be difficult. The most well-liked method is the polar–Marsaglia method (Marsaglia and
Bray, 1964), which depends on Box–Muller as below:
repeat

v = 2u - 1, v = 2u — 1
1 1 2 2
d = v + v 2
2
1 2
until d < 1
1/2
e = [“2 log(d)/d] v , e = [—2 log(d)/d] v (4)
1/2
1 1 2 2
This needs, on average, 1.27 as many uniforms as (3) but averts the trigonometric function.

LOVELY PROFESSIONAL UNIVERSITY 79