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 Exponential Distribution

The Inverse Function Method: The most commonly used generator for an exponential random variable is the Inverse Function Method.

  • Generate U~U(0,1)
  • Set X = - Log(1-U)/lambda

Von Newmann's Method: In the mid fifties, computers were not all capable of accurately evaluating exponentials and logarithms. Von Newmann divised a method for generating an exponential random variable that does not require evaluation of logarithms. Even if today's computers are powerfull, if a simulation uses millions of exponential random variables, it may still be a better alternative not to use the Inverse Function Method.

1. Set k=0.
2. Generate U1 ~ U(0,1) as a uniform variate, set N=1.
3. Do
N = N+1, and
Generate UN ~ U(0,1)
   Until UN > U1
4. if N is pair then set Y = U1
   else set k = k+1 and GO TO 3.
5. Set X = k + Y
Amazingly enough, X has an exponential distribution with parameter lambda=1. It suffices now to multiply by the desired mean, 1/lambda. You are welcome to try and prove that this clever method works fine, the hints are: use the Composition Method to identify k as the integer part of X. The residual, Y, has a constrained exponential distribution and is gnerated by the Acceptance-Rejection Method. Only Von Newmann's method "recycles" the same random variables for generating the geometric random variable k and for the acceptance test. If you can't prove this, give us a call!

Methods Distributions


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