SimSpiders
by Felisa J. Vázquez-Abad and Yanick Champoux

Generation of Random Variables



Basic Notions
Methods:
- Inverse Function
- Acceptance-Rejection
- Composition
- Convolution
- Transformations
Distributions:
- Uniform
- General Discrete
- Geometric
- Poisson
- Exponential
- Pareto
- Normal
- Gamma
- Beta

Cross Referencing:
- Topics Index
- SimSpiders Main Page


The Inverse Function Method



METHOD: The Inverse Function Method can be summarized as follows.
  • Generate a random variate U, Uniform in (0,1)
  • Set X(U) = F-1(U)
To see why this works, consider first the continuous case and calculate:

Prob[X(U) < x] = P[F-1(U) < x] = P[U < F(x)] = F(x),

where we have used the property that a uniform (0,1) random variate has probability h of being in a subinterval of (0,1) of size h. It then follows that the method indeed generates a random variable with the desired distribution.
In the discrete case, we have (see diagram above):

Prob[X(U) = k] = P[F(k-1) k

where F(0)=0.

EXAMPLES:

Extreme Values

Here is a non-trivial example of how the Inverse Function Method can be used to decrease the computational effort in generating extreme values. The example is taken from Law and Kelton (reference***).

Let {Yk, 1 < k < n} be independent and identically distributed random variables and suppose that the simulation requires generating the extreme values

R = max {Y1, ..., Yn}, and (or) S = min {Y1, ..., Yn}
Direct simulation would require to generate all n variables and then make a comparison to obtain the values of R and S. However, if we suppose that for each k, Yk= F-1(Uk) then by monotonicity of the inverse function (which is always true for a probability distribution),
R = F-1(max {Uk}), and S = F-1(min {Uk}).
Now to generate the maximum and minimum of i.i.d. UNIFORM random variables U[0,1] we use their distributions:
max {Uk,1 < k < n} ~ W1/n, and min {Uk,1 < k < n} ~ 1 - W1/n.
where W ~ U[0,1] is a uniform random variable on [0,1] also. Thus we only need to generate one random variable.

Continuous Random Variables

The Exponential, Pareto, Weibull and other continuous random variables with easily invertible distribution functions are straightforward to generate with this method, since we can evaluate the inverse function F-1 analytically. But other distributions may require numerical methods to invert the distribution, as is the case for distributions belonging to the Gamma family. In these cases we use other methods that may result in faster and more efficient generators.

Discrete Random Variables

The Geometric distribution can also be easily and efficiently generated. Actually, for a discrete random variable we can always write a generic program to use this method, but it may not always be the most efficient generator.

Methods Distributions


© Copyright 1998 Felisa J. Vázquez-Abad and Yanick Champoux. All rights reserved.