# Algorithms and Simulation

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

-
@J.M. thank you for your edit. I am new here and i do my best in order to present my question as understandable as i can. Thank you all for your concern in advance. – johan paul Nov 14 '11 at 16:31
What is a 'disposal algorithm'? When I google for it I find this question on the first page, which normally indicates non-standard terminology. Is it the same thing as rejection sampling? – Chris Taylor Nov 14 '11 at 16:47
@ChrisTaylor yes, we could say it as a rejection algorithm also. In the bibliography i use, it has both terms. – johan paul Nov 14 '11 at 16:59
Were you given a definition of "optimal"? Or any limitations? (I.e. for (b) it looks like $\sigma^2=1$ should be optimal for the obvious def of optimal) – jwpat7 Nov 14 '11 at 21:47
@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. – johan paul Nov 14 '11 at 22:01

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

-
Chris thank you very very much for your help! You saved my day. – johan paul Nov 15 '11 at 12:37