0
$\begingroup$

Supposing we want to take a sample from a $N(0,1)$ distribution and i can take a sample from a $N(0,σ^2)$.

(a) Construct a disposal/rejection algorithm with function $N(0,σ^2)$, which generates a sample from the $N(0,1)$.

(b) Find the optimal value of $σ^2$.

  • 0
    @jwpat7 there is no specification, just the best value of $σ^2$. Intuitively yes, i agree with you, $σ^2=1$ seems to be the best choice, but i have problem to prove it.2011-11-14

1 Answers 1

2

A rejection sampling algorithm to generate samples from $f$ given the ability to sample from $g$ works by generating a pair $(x,u)$ where $x\sim g$ and $u\sim U(0,1)$ and then accepting the sample iff

$u \leq \frac{f(x)}{Mg(x)}$

where $M$ is an upper bound on $f(x)/g(x)$. The efficiency of the algorithm is the mean number of samples accepted, which is

$\textrm{P}\left(u \leq \frac{f(x)}{Mg(x)}\right) = \textrm{E} \left( \frac{f(x)}{Mg(x)}\right) = \int \frac{f(x)}{Mg(x)}g(x)dx = \frac{1}{M}$

For your case, you are trying to sample from $f=N(0,1)$ by rejection sampling from $g=N(0,\sigma^2)$, which means that for $M$ you need to choose

$M = \max_x \frac{\frac{1}{\sqrt{2\pi}}e^{-x^2/2}}{\frac{1}{\sqrt{2\pi}\sigma}e^{-x^2/(2\sigma^2)}} = \max_x \;\;\sigma e^{-\frac{1}{2}\left(1 - 1/\sigma^2\right)x^2} = \sigma$

under the assumption that $\sigma>1$ (otherwise $f(x)/g(x)$ has no upper bound, and no rejection sampling algorithm exists). This means that the efficiency of your algorithm is

$\frac{1}{M} = \frac{1}{\sigma}$

which is clearly maximized when $\sigma=1$.

  • 0
    Chris thank you very very much for your help! You saved my day.2011-11-15