Given a random number generator to produce random variables with a probability density function $f(x)$, how to generate random variables with probability density function $g(x)?$
$\begingroup$
$\endgroup$
5
asked Feb 8, 2012 at 2:26
-
6$\begingroup$ $G^{-1}(F(X))$ where $F(\cdot)$ is the CDF corresponding to $f(x)$ and $G(\cdot)$ corresponding to $g(x)$. $\endgroup$– Dilip SarwateCommented Feb 8, 2012 at 2:40
-
1$\begingroup$ @DilipSarwate: thanks! But isn't this very inefficient because function inversion is involved? Also one needs to integrate and then calculate inverse. $\endgroup$– littleEinsteinCommented Feb 8, 2012 at 7:00
-
$\begingroup$ There is nothing to integrate, and $G^{-1}$ is a fixed function. Also, usually, a random number generator produces samples from $U(0,1)$ so that $F(X)=X$ which requires no computation. As an example, if $X \sim U(0,1)$, then $-\ln(X)$ is an exponential random variable. Lookit! No integration, no inverse computation, just using a function available in all math libraries to get samples from an exponential distribution. $\endgroup$– Dilip SarwateCommented Feb 8, 2012 at 11:38
-
1$\begingroup$ @DilipSarwate: I was saying if one is given with $f(x)$ and $g(x)$ as pdf. In that case, how do you get $F(x)$ and $G(x)$ (as you said, they are CDF) without integration? Also, you clearly used $G^{-1}$ which is the inverse of $G$, without function inversion, how do you compute $G^{-1}(F(x))?$ $\endgroup$– littleEinsteinCommented Feb 8, 2012 at 15:38
-
$\begingroup$ The point you are missing is that it is only necessary to find the functions $F$ and $G^{-1}$ once, e.g. $F(X)=X$ and $G^{-1}(X) = -\ln(X)$, and then program them into a subroutine that, when given a sample $X$ from your random number generator, will return $G^{-1}(F(X))$, e.g. given $X$, return $-\ln(X)$. It is not necessary to do integrations and function inversions as you call them after generating each random sample $X_i$. There is a one-time cost of figuring out what these functions are; not a per-sample cost of integration and inversion that you seem to be so concerned about. $\endgroup$– Dilip SarwateCommented Feb 8, 2012 at 15:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If you know the pdf's for both, and the distribution from which you can sample, $f(x)$, encloses the distribution from which you want to sample, $g(x)$ (or can be made to do so by multiplying the likelihoods by some constant $c$), you can use an accept-reject algorithm. The gist of this approach is as follows:
- Draw a value from $f(x)$
- At that x-value, form a ratio, $r=g(x)/f(x)$
- Draw a value, $u$, from a uniform distribution on the interval (0,1)
- If $u\le r$, then accept that $x$ and store it
- If $u>r$, then reject that $x$ and start over
- Continue until you have $N$ realized values
Note that accept-reject algorithms are notoriously sluggish, even if you end up accepting all x-values, there are several extra steps for each draw. To optimize the performance of this approach, try to pick an $f(x)$ that is as close to (i.e., as little above) $g(x)$ as possible, so that you accept as high a percentage as you can.
answered Feb 8, 2012 at 4:46