## Rejection sampling

Suppose we want to sample from a distribution that is not a simple one. Let's call this distribution *p(x)* and let's assume we can evaluate *p(x) *for any given value *x*, up to a normalizing constant *Z*, that is:

In this context, *p(x)* is too complex to sample from but we have another simpler distribution *q(x)* from which we can draw samples. Next, we assume there exists a constant *k* such that for all values of *x*. The function *kq(x)* is the comparison function as shown in the following figure:

The distribution *p(x)* has been generated with a simple plot:

**0.6*dnorm(x,1)+0.4*dnorm(x,5)**

The rejection sampling algorithm is based on the following idea:

Draw a sample

*z*from_{0}*q(z)*, the proposal distribution-
Draw a second
*u*sample from a uniform distribution on_{0}*[0, kq(z*_{0}*)]* -
If then the sample is rejected otherwise
*u*is accepted_{0}

In the following figure, the pair *(z _{0}*

*, u*

_{0}*)*is rejected if it lies in the gray area. The accepted pairs are a uniform distribution under the curve of

*p(z)*and therefore...