Hey guys, in this video I wanted to do another example of inverse transform sampling. I have a
video on inverse transform sampling already and I will put a link to it in the description box below
but this is just a second example that's a little bit more complicated than the first one I showed.
This one says suppose U is uniformly distributed 0,1. Describe how to use the inversion method to
generate a sample from a distribution with the following pdf and it has a stepwise pdf given as
follows. You don't have to know this, but this type of pdf is called a triangular distribution because
when you plot the pdf, it basically takes the shape of a triangle. I'm going to do this example
in this video. And I go over the basics of the inversion method in the first video, but basically
the steps are you convert your given pdf into a cdf; for the second step, you find the inverse
cdf; and then in the third step you just plug in the uniform random variable into your inverse cdf.
And then when you sample from this distribution, you will get the target distribution that you're
trying to sample from. Let's go ahead and get started with this example. Like I just said, the
first step I'm going to do is I'm going to find the cdf from the pdf. We're given the pdf that has
two steps in it. I'm just going to find the cdf, which is F of X. For the first part, that's going
to be the integral from 0 to X of X dx, which is just going to give me X squared over 2 and this is
going to be from--X is from zero to one. That's the first part of the cdf. Then for the second part,
we're going to start at where X is equal to one. At X is equal to one, F of X is equal to--if
we plug in one here--that's going to be one half and then the rest of the cdf is going to be
from one to X of the integral of two minus X dx. When we integrate that, that's going to give us
one half plus 2X minus X squared over 2 from 1 to X. And if I skip the steps of solving this,
this is going to give us 2X minus X squared over 2 minus 1. This is the cdf at the second step and
this is from--X is from 1 to less than or equal to 2. Combining the two steps that we just solved,
the cdf is going to be X squared over 2 from X is greater than 0 to less than or equal to 1
and then 2X minus X squared over 2 minus 1 when X is greater than 1 and less than or equal to 2.
We're done with the first step, which is finding the cdf. At the next step, we have to take the
inverse of our cdf. We have to find F inverse. The inverse again is going to have two parts
since our cdf has two parts as well. I'm going to find the inverse of the first part first.
I'm going to solve that as Y is equal to X squared over 2 from 0 to 1 and then I'm going to solve for
X. That's going to be 2Y is equal to X squared, then I have to take the square root on both sides.
That's going to be plus or minus the square root of 2Y is equal to X. Because a cdf has to always
be greater than 0, we're going to have that our final solution is positive square root of 2Y is
equal to X. And then we also have to convert the X into the inverse Y. I'm going to use this equation
to solve for the new limits of Y. When X is zero, Y will still be zero. And then when we plug in
one we're going to get Y is equal to one half. Our new limits are going to be from zero to one half
and then the inverse is going to be the square root of 2Y for the first part. Then we have to find
the inverse for the second part. I'm going to do the same thing. I'm going to set Y is equal to 2X
minus X squared over 2 minus 1 and then I'm going to solve for X. I'm going to do 2Y is equal to 4X
minus X squared minus 2. Then I'm basically going to solve this as a quadratic equation. I'm going to
set the left hand side to 0 by subtracting 2Y on both sides. That's going to give us 4X minus X
squared minus 2 minus 2Y. And then I'm basically going to treat this term here as the c and use
the quadratic equation to solve. When I do that, that's going to give me 4 plus or minus the square
root of 16 minus 4 times 2 plus 2Y divided by 2. And when I simplify that, that would be 4 plus or
minus the square root of 8 minus 8Y divided by 2 and then I also have to change the limits of X. We
originally have X is greater than 1 and less than or equal to 2. When I plug that into this equation
here, when I plug in 1 we're going to get 2 minus one half minus 1. That's going to give us that Y has
to be greater than one half. And then when I plug in X, that's going to give me 4 minus 2 minus 1.
That's going to give me 1. The new limits are that Y has to be greater than one half and less than or
equal to 1. For the second step solution, this is not a unique solution because of the plus or minus.
I have to use the equation that we went over in the first video to find a unique inverse cdf,
which was the following. The inverse cdf of U has to be equal to the infimum of X such that F of X
is greater than or equal to U where U is uniformly distributed 0,1. Basically it can take on the
value between zero or one. And we're going to use this definition of the infimum to find
a unique solution to this inverse cdf. I'm just going to, for example, plug in Y is equal to one
half into this equation and if I do that I'm going to get 4 plus or minus 8 minus 8
times one half divided by 2. That solution would basically give me 4 is equal to plus or minus
2 divided by 2, which could either give me a result of 3 or 1. If I do 4 plus 2 divided by
2 that would be 6 divided by 2, which is 3 or 4 minus 2 is 2 divided by 2 would give me 1.
Since both of those are valid solutions, I'm going to pick the one that gives me the smaller number
for the infimum. That would be minus, so the final version that's going to give me a unique solution
is 4 minus the square root of 8 minus 8Y divided by 2 and we have finished the second step.
So the inverse cdf is going to be equal to the square root of 2Y when Y is greater than 0 and
less than or equal to one half. And it's going to be 4 minus the square root of 8 minus 8Y
divided by 2 when Y is greater than one half and less than or equal to 1. And for the final step in
your solution, you would just plug in U, which is a uniform 0, 1 random variable into your inverse
cdf. And then if you sample from this distribution, you will get samples from your target distribution,
which was the triangular distribution. And that's it for this video.
*chiptune music*