Re: The Acceptance - Rejection Method

The Acceptance - Rejection Method


The all-purpose way to sample from a FD we know its
expression, F (X).

Let be X a continuous random variable and x0 one its
realization .We are seeking p (X=x0) = F (X<=x0), the
probability y that X doesn’t exceed x0.
Problem
Given y belonging to [0, 1] we intend to find exactly
x0 = F^-1 (y). Generally speaking, its evident, this
inversion is impossible to attain ANALITYCALLY.
The Hungarian J. Von Neumann (1903 – 1957) finds out
how to do so point-by-point __THE
ACCEPTANCE-REJECTION METHOD.
___Let be x0 a random number (the probability) and F
(x0) the Distribution Function value at this point.
The criterion is:
_____Accept u=x0 while F (x0) >= u, reject
otherwise.

Example

Let be the Exponential Distribution function
_____F(x) = 1- Exp (- x / m)______(A)
_____x = [ 0 , infinity)
where the mean m=0.
An uniform random number, u = 0.765 , is the
candidate.
We calculate F(0.765) = 1- Exp (- 0.765) = 0.534
Because 0.765 > 0.534 we ACCEPT 0.534.

IN FACT
This example is a * stupid * one because the inverse
can be easily get
____x = -m * Log (1 - F) = Log (1- 0.765) = 1.2649
and belongs to the r. v. DOMAIN : therefore is
ACCEPTED. (in this case there is NO rejected
values).

Luis Amaral Afonso



Afonso's formulas are stupid because by specifying m=0, it follows that F(x) = 1-exp(-x/0) = 1 for x>0.

Jack (moderator)
.

Relevant Pages