Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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. – Tim May 19 '13 at 11:46

Your Answer


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.