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!
|