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

Question

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.

Answer 1

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}$$