In a class lecture, the "Acceptance-rejection algorithm" was presented as follows:

To generate $𝑋 \sim 𝑓(𝑥)$, Find density $g$ satisfying $\frac{f(t)}{g(t)}<=c$ for some constant $c$ for all $t \in domain(f)$ with $f(t)>0$ and from which rv's can be generated. For each rv required,

  1. Generate $Y \sim g $
  2. Generate $U \sim U(0,1)$
  3. If $U \leq \frac{f(t)}{cg(t)}$ accept Y and return $X = Y$ otherwise go back to step 1.

In step 3, we see that $P(accept|Y=y)=P(U \leq \frac{f(y)}{cg(y)}|Y=y)=\frac{f(y)}{cg(y)})$

I do not understand how can we derive the last staement:

$P(accept|Y=y)=P(U \leq \frac{f(y)}{cg(y)}|Y=y)=\frac{f(y)}{cg(y)})$

I understand this is a very basic thing but I am stuck in it. From what I understand, $P(accept|Y=y)$ should be equal to $\frac{P(accept, Y=y)}{P(Y = y)}$ But how are we calculating the $P(accept, Y=y)$? A break down of the derivation will be very helpful for my understanding.

  • $\begingroup$ Apply the definition of "$U\sim U(0,1)$" to compute the chance in (3), after first making sense of what the undefined variable "$t$" might possibly mean in (3). $\endgroup$ – whuber Jun 24 at 19:47
  • $\begingroup$ Thank you! So here we are using $P(U \leq u) = u$, right? If that is the case then is this assumption correct: $P(accept|Y=y)$ should be equal to $\frac{P(accept, Y=y)}{P(Y = y)}$? If that is true then how to calculate P(accept, Y=y)? Is it simply $P(accept) * P(Y = y)$? $\endgroup$ – user26264 Jun 24 at 21:40
  • $\begingroup$ You might be overthinking this: you don't need to apply any definitions of conditional probability. Indeed, the notation probably is getting in your way: in (3), write "$y$" instead of "$t.$" Since you have already observed the event $Y=y,$ the only probability you need to calculate is $\Pr(U \le f(y)/(cg(y))).$ $\endgroup$ – whuber Jun 24 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.