Rejection Method for Variable Simulation
Translated by
ScribdTranslationsRejection Method for Variable Simulation
Translated by
ScribdTranslations13/03/2020
Simulation of variables
random
Prof. Mohamed El Merouani
[Link]
e-mail: m_merouani@[Link]
Simulation by the method of
rejection
1
13/03/2020
Introduction
For the inversion method, it is suitable to
know the cumulative distribution function.
But sometimes, we know the function of
density and we do not know the function of
distribution, as happens, for example,
for the normal law.
In these cases, we can apply the method of
rejection, introduced by Von Neumann (1951).
Introduction
Suppose we want to sample at
starting from a v.a.X with density function f.
We don't know how to do it directly, but we
we have a process for sampling at
starting from another density function
quef(x) ≤ cg(x) for all x (with some)
finite constant.
2
13/03/2020
Simulation by the rejection method
The rejection method or algorithm is:
Until U ≤ f(x)/cg(x)
GenerateX→g
Generate U→U(0,1)
SortirX
The rejection method is equivalent to generating
variables Y→U(0,cg(X)) and accept them if
Y ≤ f(X).
5
Simulation by the rejection method
(Proof):
To demonstrate that the process is correct, it
must check that ( ≤ /Xaccepted)=F(x), where
This is the distribution function of X. We have
( ≤ /Xaccepted)= ( , Xaccepted
P(Accepted)
In addition,
P(Xaccepted)= ∫ ≤ / =
=∫ = (3,1)
6
3
13/03/2020
Simulation by the rejection method
(Proof):
( ≤ ,Xaccepted)= ∫ ≤ , ≤ / =
=∫ =
And we get the result.
(3.1) indicates that in each iteration of the algorithm, we accept
a value of an independent form with a probability of 1/c, which
give the effectiveness of the process. The number of iterations or tests
independent before the acceptance of a value follows the law
geometric with parameter 1/c, and c being the average number of
tests. The closer it is to 1 (always c≥1), the more effective the method is.
effective, because the densities f and g will be closer.
7
Example:
•Generation of the beta law B(3,4). Its function of
density is f(x)=60x2(1-x)3, 0<x<1
We take as a function the density of the law
U(0,1). Let us determine a constant such that
f ≤ cg. The maximum of the function f(x)/g(x) is
reaches enx=2/5.
( )
Thus: ≤ 60( ) (1 − ) = ≡
( )
Therefore, = (1 - x)
( )
4
13/03/2020
Example:
The rejection algorithm for this example will be,
so:
Until U2≤ U1(1 − U1)
GenerateU1, U2→U(0,1)
ExitU1
The average number of iterations until
l’acceptation estc=2,07, l’efficience est 1/c=0,48
Exercise:
We wish to sample from a random variable.
Density function Xde
f(x)=3x(2-x)/4, 0≤x≤2
Apply the rejection method to do it and
give the corresponding algorithm.
10
5
13/03/2020
Solution:
We take as function g the density of the
law U(0,2). Let's determine a constant c such
( )
that f≤cg. The maximum of the function is
( )
reach at x=1.
( )
Thus ≤ ≡
( )
( )
Consequently, x(2 - x)
( )
11
Solution:
The corresponding algorithm is therefore:
Until that2≤U1(2- U1)
GenerateU1→U(0,2)
GenerateU2U(0,1)
ExitU1
The average number of iterations until
l’acceptation est c=3/2, l’efficience est 1/c=2/3
12
6
13/03/2020
Remarks:
The acceptance probability is 1/c.
So, the probability of acceptance is high.
when it is close to 1, and that happens, of course,
when g(x) is the same as f(x).
From which, on one hand, we want g(x) to be so much
close def(x) so that it is possible for the
the acceptance probability should be high.
On the other hand, we want g(x) to be so easy
to simulate that it is possible.
13
Efficiency of the rejection algorithm:
When it is large, the efficiency of
the rejection algorithm is low and the
the percentage of rejected values is high.
So, it is necessary to generate a very high number of
random values deg(y) to obtain a small
valid sample def(x).
14