okay so today on numerical methods yes
maybe always to give you an orientation
we are discussing the numerical method
called Monte Carlo method we are
discussing how to generate other
distributions from sequences of uniform
distributed random drawings okay and the
first method we discussed was the
inversion of the distribution function
and for that we had to actually define
what is the inverse of the distribution
function because the distribution
function can be as monotone but not
strictly monotone and for that we define
some generalized version which you see
here in the picture so whenever you have
say some area of non-uniqueness like
here we take just the infimum of this
set huh and we could actually then show
you have this lemma we could prove this
lemma that if you have given the inverse
this generalized inverse of the
distribution function then from a
uniform random variables or from a
sequence of uniform drawings you can
generate an F distributed random
variable X now by applying the inverse
here so now what do we do if we do not
have the inverse of the distribution
function so either we do not know across
formula or we do not have a nice
approximation like the one which we had
for the normal distribution then here I
would like to discuss an alternative
method with you which is called
acceptance rejection also quite
interesting from the way how it is
constructed
and this message makes some other
assumptions so actually first what do we
like to do so let's take the right pen
so what we like to do we like to
generate a sequence generate a sequence
let's call it X I
and this sequence should be joins of an
F distributed random ever say I call it
capital X so this is what we have but
maybe we do not know we do not know F
okay so there is no need to know F
inverse in this method you know or you
even do not need to know F so what we
need to know is
you
we know F prime the density record that
this is for example the situation which
we had for the normal distribution for
the normal distribution density is 1
divided by square root to P times
exponential minus x squared half so we
know the density nice dose formula
know the density nice dose formula do not know F or F inverse in closed
do not know F or F inverse in closed
form but then we need some additional
stuff
actually we know we need to know how to
generate some utility sequence a
sequence Y I and these are toys over GE
distributed
the Bible
why so we need some other sequence and
this sequence should have a relation to
our function f or f time yeah we know
that is a constant C such that the
so a constant C such that C times the
density of G is larger than the density
of F so if you draw the two densities
the density of G should be above F if
there is a if there is some region where
it is not above it's maybe not a problem
you can you can multiply it with the C
and shift it a little bit up as long as
this region has nonzero values so we
have this clique with the constant you
know we can use but actually we need
somehow the property that the density of
G lies above F most importantly in the
azan to asymptotics yeah so f decays
faster than g so if you have something
like this and this is maybe not a very
strong assumption yeah so for maybe
exponential distributed random variable
exponential minus x squared
you know I immediately have exponential
minus X decays slower and so I could use
an exponentially distributed random
variable to dominate the normal
distribution tensity in the other
asymptotics this is our situation
actually the third point the the
requirement is even a little bit
stricter I need two sequences one one
uniform independent one but essentially
these are now the requirements and these
requirements are not so strong and the
claim is that if we have this situation
I can generate a sequence of F
distributed random barber okay maybe I
collect a few typos here F distributed
so yeah this is the situation this is
the corresponding lemma so accept
acceptance rejection sampling let F
denote a distribution function
you
for which we like to generate a sequence
then given a sequence two-dimensional UI
y I so this is a sequence of a
two-dimensional vector being you Y of
random variables U and Y where u is
uniform distributed so U is uniform
distributed on 0 1 and Y is the one
which he had mentioned in the multi
motivation the one that is G distributed
in addition both have to be independent
you
okay but maybe this is not a big
restriction here so you know that if
restriction here so you know that if have one uniform random sequence if it
have one uniform random sequence if it
is episode o number generator we can
just generate a two-dimensional vector
by populating the entries one by the
other so we can generate a uniform
distributed sequence in two dimensions
and maybe if we can apply the inversion
method for G we can generate from the
second component the G and the two may
be independent so G is K so the sequence
YJ which is GG distributed is some kind
of helper sequence actually we will
single out the points from this sequence
so now I need this assumption on the
densities so for the density of G which
I call little G and the density of F
which I call a little F so maybe I check
here the yellow
okay for these we have the relation that
we find a constant C such that the
density of F is smaller than the density
of G with some multiplied with some
constant so some C times G of X okay
so in in maybe I try us more picture
here I answer if you there for example
here a density like say which which
color should I use yeah so maybe like
like the normal distribution yeah so I
have something like this the normal
distribution which goes here oops
like this then maybe you can find some
distribution function G which the case
he is slower huh so this is the G okay
and then you just multiply with the
constant C now to move this here a
little bit up okay and then you have
disc right here yeah okay so this year
is C times G this is G
Saji and this is D F so I need to find a
constant C to dominate this actually
later we will see that it's nice to have
the smallest such constants okay so this
is the situation which I had already
described and then the sequence of the
following numbers so the sequence X i
where from Y I so Y is the sequence I
have which is G distributed where we
just take specific indices so we just
take here specific indices of Y I this
sequence is F distributed so just this
sequence X I pairs distribution F
and what are the specific indices so
here it's take only specific indices so
from the YJ so how are these calculated
so I initialize so actually here my eye
starts in zero so I initialize k zero to
zero and then I take the index ki is the
next index which is larger than the
previous index so this is just that I
take the next guys in the sequence for
which actually the uniform number from
our two-dimensional vector here is
smaller than
the Y the G distributed number why
plucked into the density now
so F of Y divided by C G of Y this
strange expression here so actually here
you have some test criteria and your
test criteria if you take the number or
not
this is your uniform number smaller then
what you get if you pluck the g
distributed number in the two densities
take the ratio and divided by C ok so
you see that we take a few numbers from
the sequence Y so sometimes we accept
the number sometimes we reject the
number and the criteria to accept or
reject the number is this thing here so
this is the criteria if we accept
or rechecked
the yj2 become a number X okay maybe a
small illustration but I believe you
should have the idea yeah so actually we
need to generate two sequences you I are
say you J and YJ so you sequence is here
I always used Queen for you so this is
the sequence you the two dimensional
vector is independent this sequence you
is uniform this sequence Y is G
distributed so this is a G distributed
and this one here is uniform
then on these on this sequence you
compare what do you get for this by
looking at here this criteria you look
at this criteria and you check if the
criteria is too or false
and so maybe here this falls maybe here
it is true and maybe we check a few more
yeah so you check these guys and maybe
this one here is also false false and
that one's maybe - okay then you take X
you take X is equal to Y if the criteria
is - yeah so this year was our Y so we
take this one as the X so let's take
this one here as the X and we take this
one here as the X the other ones are
skipped huh
and this year is then the sequence X I
know sorry there was a rejected one this
one is taken here this one is taken huh
and maybe one more then it's also
accepted so if a few more points so this
one here is also accepted so you see you
get fewer points out of this you know
you have to sample two times the
sequence and then you just single out
one point with a certain probability and
but this one just sequences now F
distributed this is the claim of this
lemma okay so let's prove that this is
an F distributed sequence and maybe
sometime later or you can do it as an
exercise you can maybe check it for a
few examples I have examples some more
examples in the in the script okay so
let's do a proof we generate two
sequences u and y so be here in this
slide I do not talk about sequences I
talk about the random variables and I I
just show you that the random variable X
generated by this condition has F
distribution so the random variables are
called you so on my slide I always had
the queen color for the you and why you
know so this is the random there behind
the you sequence and the Y sequence and
the first thing to note is that the
probability that U is pilotless less or
equal f of Y divided by C G of Y is just
1 divided by C so the probability that
we accept a point no probability that we
accept the point
so here we could maybe write probability
that Y J is accepted this probability is
here our head box our criteria this is
the probability that U is less than F of
Y divided by C G of Y this is the
probability that we accept a point which
comes standpoint for the sequence and
this probability is 1 divided by C okay
so this follows since well how do we do
this so the trick which I'm using here
is coming again later on the slide I
have here the probability of some
condition which depends on two random
variables and actually the probability
is a function which Maps a set of Omega
you know so a set of little omegas to a
number so which said is this this is the
set of all omegas if you plug in the
Omega inside the random variables yeah
that this is 2 so actually if you write
P of U less than F of Y divided by C G
of Y so then actually this is just the
short notation for I would like to have
the probability of the set of all omegas
for which this condition holds that is
to say you of Omega is less than F of y
of Omega divided by CG of y of Omega ok
close to set now so this is the
point-wise the evaluation of this
condition on omega so but in terms of
random variables you can interpret it as
a two dimensional thing all values of
you all possible values of Y and to get
rid of this two-dimensional thing a nice
trick is just to condition on one
variable so we can first calculate the
conditional probability given that we
already know that Y has a certain value
yeah so the probability that you the
random variable U is less than this
expression under the condition that we
know that Y has some value little Y okay
so if your condition you are allowed to
use this condition here in your
expression so I can just replace the
capital y by the little Y so this is
just the probability that U is less than
this number yeah so now this is a number
this is the set of all omegas where u of
Omega is less than this number so this
is like a marginal marginal thing yeah
so this is just the one-dimensional
projection of this tubular
two-dimensional thing now projected
along the line y equals little Y okay so
but now note that U is uniform
so this here's just the distribution
function so this little box here is just
the distribution function of U so the
distribution function of U is just a
constant
yeah so you just have that this is just
this upper bound value sorry the
distribution function is a linear
function so it's just the the
function so it's just the the itself yeah the number on the right hand
itself yeah the number on the right hand
side so you just have this is just f of
Y divided by CG or fine okay
so but actually we were interested here
in the probability that U is less than F
of Capital y but now since I have here
the conditioner I can get the Joint
Distribution by integrating the
conditional one so this the probability
that we are
that you is less than equal F of Y
divided by CG of Y is the integral of
the conditional probability multiplied
with the density integrated over all
possible values of Y no so this is a
standard trick yeah which you have you
will but you can do you know if you like
to do this so let's plug this in so you
see this here is f of Y divided by C G
of Y so this G of Y cancels here and
what is left is just the integral of F
of Y divided by C I integrate the
density over the whole domain so this is
just 1 now so it's just 1 divided by C
ok so that was a first remark so
actually you see that here here we wrote
that this probability is the probability
that we accept a point so the
probability that we accept a point is
actually just 1 divided by this constant
C so we like to have this constant C to
be as close as possible to 1 now so
usually C is larger than 1 but we like
to have it as close as possible to 1
okay now let's prove the result so that
is X the sequence X F distributed
I will use again this trick with the
conditioning okay so
for the condition expectation a
conditioner B I already mentioned this
is the probability a intersected B
relative to the size of the event space
B so the probability of B and we will
use this with actually two sets the
probability or the set Y is smaller than
a given constant X which is two constant
in our distribution function and B is
the set that we accept a point so this
was the red box on our previous side the
set that we accept a point so this is
our condition so my sequence X is
actually equal to the sequence Y
so
X is why if we accept the point so under
the condition that we accept the point
if the point is accepted
you
so the probability that X is below a
little X so this is the distribution
function so we like to calculate the
distribution Virgie the probability that
capital X is less or equal little X is
the probability that y is less or equal
little X under the condition that the
point was accepted so where's the
conditional probability that you so wish
to condition the condition that u is
less than f of Y divided by CG of Y so
now these are here my two sets the
yellow one and the red one and now I use
the definition of the conditional
probability it is the intersection of
the set Y is smaller than X and the
point was accepted divided by the
probability that we accept the point
okay so the probability that we accept
the point it's just 1 divided by C this
is 1 divided by C this was what we first
observed ok so this is just a C times
the probability that we are less than X
raised to Y and the point is accepted
now so the set of where the points are
accepted so now I have again the
situation here that I have a random
variable Y yeah inside this probability
and a random variable you inside this
probability so actually I believe you
was always Queen was you Queen yeah us
on screen so maybe I marked this here
for you so I have here you and why oh
sorry not here so I would like to mark
it here you and why
and
the same trick that we conditioned now
know on some variable so let's condition
on Y so let's fix y equals Z
on Y so let's fix y equals Z integrate over the whole density over
integrate over the whole density over
the whole domain and Marty is so
multiplied with the density okay so all
Y's are then replaced by the driven set
actually I could have used a little Y
okay and we integrate over the set
multiplied with the density and recall
we know the density of this guy which is
y and now you see that what is this set
here this is the probability that little
Z is smaller than X and the uniform
distributed random number u random
variable U is smaller than this constant
F of T divided by CG offset so now I
integrate over set and here in the
probability that is the condition Z is
smaller than X so actually I can replace
here the upper bound and I can get rid
of this first part of the set so and
since you know that this is a uniform so
this guy here is a uniform
you
No so the probability of you smaller
than little you is just little you so I
can't just pluck this here here no and
you have the density G from here and
these two guys cancer now and you have
one divided by C in front which cancers
and this is now integrate F
integrate f up to only X so this is the
distribution function of
this stupid version f of X so we have
proven that X using this method has
distribution function f okay so the
method looks maybe a little bit
complicated but actually it is not here
you can have a very small implementation
very clean you just need the densities
two sequences check the condition accept
or reject the point and you can as I
already gave you some hints use this to
perform a sampling of the normal
distributed random variable yeah without
actually using the distribution function
of the normal distribution you just need
some thing about the density and you can
use the exponential distribution and the
exponential distribution we can use with
the inversion of T distribution function
okay so maybe we have a court session
with this or you can try it as an
exercise that's it for today yeah thank
you see you next time