Let's say we have a mixture distribution, defined by density $f(x)= w_1 p_1(x) + w_2 p_2(x)$, where $w_i$ is a scalar weight. Furthermore, we have efficient methods to evaluate the pdf and cdf/icdf for the distribution $D_i$ corresponding to density $p_i$. I would like to sample from such a distribution.

The method I currently employ is an implementation of rejection sampling. I construct a proposal function $M*u(x)$, where $u \sim \text{Unif}(lb,ub)$ ($lb,ub$ are constructed such that at least 99% of the cdf of each $D_i$ is contained within, using icdf) and $M$ is constructed by finding the $\max_{x \in [lb,ub],i} p_i(x)$. Because such proposal function envelopes $f$, I am able to sample $f$ by choosing $x \in X \sim \text{Unif}(lb,ub) \times \text{Unif}(0,M)$ and rejecting if $\pi_2 x > f(x)$ [$\pi_2 x$ being the second coordinate of $x$].

However, doing this is quite slow. Not only is the proposal function inopportune (it is scaled uniform, which likely will lead to many rejections), but the construction of $M$ is very slow, as maximizing a function is a non-trivial task. Is there a more efficient way to sample such a distribution? I had considered icdf sampling, but constructing the icdf for $f$ seems non-trivially difficult. Is this impression incorrect? Or perhaps is there some other effective method? If it is helpful, I am implementing this in python and am currently using the scipy and pytorch libraries.

  • 1
    $\begingroup$ Can you draw a random variable with density $p_i$? If yes, then do the following two-stage process. Stage 1. Draw a random variable $X$ (selector, if I remember correctly), such that it draws 1 with probability $w_i$ and 2 with probability $w_2$. Stage 2. If $X=1$ in the previous stage, draw according to $p_1$, else, draw according to $p_2$. $\endgroup$ – kate-melnykova Sep 18 '20 at 19:35
  • $\begingroup$ @kate-melnykova I can't believe I hadn't thought of that — yes that should work, I believe $\endgroup$ – Josh Purtell Sep 18 '20 at 19:51
  • $\begingroup$ I will copy-paste the solution below, so the question will look like answered. $\endgroup$ – kate-melnykova Sep 18 '20 at 20:04

The mixture distribution can be obtained in the following way.

Let $f(x)=w_1p_1(x) + w_2p_2(x) + ... + w_np_n(x)$, where $p_i$ are density functions and $w_i>0$. Note that $f(x)$ is a density function if the sum of all weights is one.

Then, we use the following two-stage process.

Stage 1. Draw a random variable $X$ (selector, if I remember correctly), such that $P(X=i)=w_i$ for $i=1,2,...,n$.

Stage 2. Return a random variable drawn accordingly to $p_X$, where $X$ is the index obtained in the stage 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.