# Rejection sampling for optimal $\lambda$ and $a$

Suppose $f(x) \propto \exp ({-(x-u)^2\over2\sigma^2}) I_{X>=a}$ and we cannot compute the normalizing constant. Consider rejection sampling using proposal density of a shifted exponential distribution, $\text{Exp}(\lambda,\,a)$.

Let $g(x)=\lambda \exp(-\lambda(x-a)) I_{X>=a}\,$ with $I$ an indicator function. For sampling from $f(x)$ with $u=0,\, \sigma^2=1,\, a=2$, how do we find optimal values of $\lambda$ and $a$ for $g(x)$?

I have tried to approach this by maximizing $f(x)/g(x)$ but the solution is not accurate.

• Consider drawing graphs of $f$ and $g$: the picture will readily suggest the correct solution.
– whuber
Commented Sep 19, 2018 at 16:35
• in this case what would is the optimal case ? is it the case whereby g(x) is just above f(x) ? Commented Sep 19, 2018 at 16:45
• wow this method seems pretty advanced. What I learnt is that g(x) should be over f(x) but not too much over to maximize efficiency of rej sampling. In that case I found that lambda=1 and a=0 leads to the g(x) curve just being able to cover the f(x) curve. Am I right ? and yes this is a hw qns which Im trying hard to figure Commented Sep 19, 2018 at 19:10

### Two parameters to optimize

Your rejection criterium can be scaled with an additional constant $b$

$b \frac{f(x)}{g(x,\lambda,a)}$

where $b$ is to be chosen such that the above criteria value is for all $x$ equal to or less than one and ideally you get the maximum equal to one.

So you have two parameters to optimize. Not only $\lambda$, but also $b$.

### Finding parameters $\lambda$ and $b$

• Basically you are trying to find curves like:

$$g(x,\lambda,a,b) = \frac{\lambda}{b} e^{-\lambda (x-a)}$$

that are just touching the curve of $f(x) = e^{-0.5x^2}$.

• For this you want $f(x) = g(x)$ and $f^\prime(x)= g^\prime(x)$. See the image below for examples.

The thick black line is $f(x) = e^{-\frac{x^2}{2}}$. The coloured lines are $g(x,\lambda,a,b)$ for $\lambda=0.5$, $\lambda=1$ and $\lambda=1.5$ and $b$ adjusted such that the lines $f(x)$ and $g(x)$ touch. I plotted also a logarithmic scale for better visibility

• Note that $\frac{f^\prime(x)}{f(x)}=-x$ and $\frac{g^\prime(x)}{g(x)}=-\lambda$, thus a curve $g(x,\lambda,b,a)$ will touch the curve $f(x)$ in $x=\lambda$.

• Then setting $f(\lambda) = g(\lambda,\lambda,b,a)$ you can find $b$ that is associated with $\lambda$ and $a$

$$e^{-0.5 \lambda^2} = \frac{\lambda}{b}e^{-\lambda(\lambda-a)}$$

which leads to $$b = \lambda e^{-0.5 \lambda^2+a \lambda}$$

### Finding optimal parameters

To have the lowest amount of rejections you want the curve $g(x,\lambda,a,b)$ to be as close as possible to $f(x)$. The amount of rejections can be related to the ratio of surface area under $g(x,\lambda,a,b)-f(x)$ and $g(x,\lambda,a,b)$. So you want to find the minimum of:

$$\int_a^\infty g(x,\lambda,a) dx = \frac{1}{b} = \frac{1}{\lambda e^{-0.5 \lambda^2+a \lambda}}$$

which can be found by setting the derivative of the denominator to zero

$$\frac{d}{d\lambda} \lambda e^{-0.5 \lambda^2+a \lambda} = (- \lambda^2+a \lambda+1) e^{-0.5 \lambda^2+a \lambda} = 0$$

which is like solving the quadratic $- \lambda^2+a \lambda+1=0$ that has the solution:

$$\lambda = b e^2 = \frac{a+\sqrt{a^2+4}}{2}$$