Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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
2  
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

1 Answer 1

up vote 2 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.