# Accept reject method to generate random numbers

The method says that having a proposal $g(x)$

1. Sample $X^* \tilde ~ g(x)$ and $U \tilde ~ Unif(0,1)$
2. Accept $X = X^*$ if $U ≤ f(X^*) / M g(X^*)$

Moreover, $M$ is constant that satisfies $Mg(x) ≥ f(x) \forall x$

But how should I choose this $g(x)$? And what about the constant $M$?

Say I have the following function $\displaystyle f(x) = \frac{x^3}{e^{x}+1}$ what does $g(x)$ should look like?

Sorry for my no-math-language I'm not used to it.

-
I think I know what you mean by the accept-reject method, but I had to guess. Could you edit your question so that we know exactly what you're trying to do. –  Tim May 19 '13 at 9:10
Your $f(x)$ isn't a density function. It's always negative and doesn't converge to $0$ as $x\to\infty$. Do you mean $f(x) = \frac {x^3}{1+e^x}$? –  Tim May 19 '13 at 9:41
I am very sorry I was reading other stuff and got confused. I edited the question. –  BRabbit27 May 19 '13 at 9:58
Don't apologise :) I can answer it now. –  Tim May 19 '13 at 10:00

The main idea is to look at the tail of $f(x)$. That is how does $f(x)$ behave when $x$ is very large. Then we need to find something that looks like it, but is easy to integrate.

We want to keep $g$ as close to $f$ as possible If $M$ is high we reject a lot of samples.

In your case the difficult bit is the $\frac 1{1+e^x}$. but for large values of $x$ that's very close to $e^{-x}$ so $g(x)\sim x^3 e^{-x}$ is the right sort of candidate. It's not too far away from $f(x)$ and we can integrate it to get

$$\int_x^\infty t^3 e^{-t} dt = e^{-x}\left( x^3 + 3x^2 + 6x + 6 \right)$$

We have to be careful because $\int_0^\infty t^3 e^-t dt = 6$ so we should set $$g(x) = \frac {x^3}{6 e^{x}}$$ Therefore $$\mathbb P\left (X^*>x\right) = e^{-x}\frac{ x^3 + 3x^2 + 6x + 6}6.$$ So $X^*$ is easy to simulate.

Now we have to find $\max_{x_\in \mathbb R} \frac{f(x)}{g(x)}$

It's easy to calculate $\dfrac{f(x)}{g(x)} = \dfrac{6e^x}{1+e^x}<6$ So we can set $M = 6$

So for high values of $X^*$ we hardly ever reject, because $\dfrac{f(x)}{Mg(x)}\to 1$ for low values we might reject with probability up to $\frac 12$, which isn't bad.

Choosing a good proposal distribution is more of an art than a science, the main thing is to make sure the tails agree, and that you're don't end up rejecting too many.

-
Very nice answer. Can you suggest a reference to read more a little bit of this? I got lost in the last part when you say for high values and low values what would happen, I just need to read more about it I think... –  BRabbit27 May 19 '13 at 11:30
Writing $X^8$ instead of $X^*$ probably didn't help. The acceptance probability is $\dfrac{f(x)}{Mg(x)}$ so we don't want there to be values of $x$ where this is too small because we'd reject lots of values. I can't recommend a book but there are some lecture notes that look quite good. www.maths.bris.ac.uk/~manpw/teaching/notes.pdf –  Tim May 19 '13 at 11:46