# How should I sample from a mixture distribution?

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.

• 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$. – kate-melnykova Sep 18 '20 at 19:35
• @kate-melnykova I can't believe I hadn't thought of that — yes that should work, I believe – Josh Purtell Sep 18 '20 at 19:51
• I will copy-paste the solution below, so the question will look like answered. – kate-melnykova Sep 18 '20 at 20:04

## 1 Answer

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.