# Why does elimination method for random variables work? [duplicate]

Why does elimination method for random variables work?

Elimination method:

1. Let $$f$$ be p.d.f. supported on $$(a,b)$$ with $$0.

2. Pick $$x$$ in $$Unif(a,b)$$, $$y$$ in $$Unif(0,c)$$.

3. If $$y < f(x)$$, accept $$x$$.

4. Else reject $$x$$ and pick new $$x,y$$.

Particularly I don't understand why step 3. suggests that $$x$$ is a random variable, since it seems to compare "is $$Unif(0,c) < f(x)$$" basically, which to me reads like comparing two separate things.

• The likelihood of choosing a particular $x\in (a,b)$ is constant, i.e. proportional to $1$, and the conditional probability of then not rejecting it is $\frac{f(x)}{c}$, i.e. proportional to $f(x)$. So the likelihood of choosing a particular $x$ and then not rejecting it is proportional to the product of these i.e. to $f(x)$. And that is precisely what you are trying to get, since with probability $1$ you will eventually not reject a value Dec 13, 2018 at 22:14
• Are you describing a method for simulating observations according to a density $f$? Dec 13, 2018 at 22:15

Assume C=1 WLOG

$$Pr( X < x ) = \int_{a}^x P(Y < f(s)) ds = \int_{a} ^x f(s) ds = F(x)$$

So $$X$$ is equal in distribution to the random variable having density $$f$$.

By "elimination" you probably mean "rejection".

The intuition is geometric: you're sampling uniformly on the rectangle $$[a,b]\times[0,c]$$. The probability that a random variable $$Z$$ with the distribution specified by this rejection algorithm is less than $$t$$, for some $$t\in[a,b]$$, is the area under $$f$$, inside the corresponding sub rectangle (suggestion: draw a figure).

If you need a quick review of the properties of conditional probability / expectation, read this answer first.

Here is a "formal" proof. Let $$f$$ be a density supported on $$[a,b]$$ such that $$0 (almost surely and bla-bla-bla), for some $$c>0$$. Let $$X\sim U[a,b]$$ and $$Y\sim U[0,c]$$ be independent random variables. $$\Pr\{Z\leq t\} = \Pr\{X\leq t \mid Y\leq f(X)\} = \frac{\Pr\{X\leq t, Y\leq f(X)\}}{\Pr\{Y\leq f(X)\}}.$$ Using the Law of Total Probability, the denominator is $$\Pr\{Y\leq f(X)\} = \int_a^b \Pr\{Y\leq f(X) \mid X = x \}\,\frac{1}{b-a}\,dx,$$ and the numerator is $$\Pr\{X\leq t, Y\leq f(X)\} = \int_a^b \Pr\{X\leq t, Y\leq f(X) \mid X = x \}\,\frac{1}{b-a}\,dx.$$ But $$\Pr\{Y\leq f(X) \mid X = x \} = \Pr\{Y\leq f(x) \mid X = x \} = \Pr\{Y\leq f(x)\} = f(x),$$ in which the second equality follows from the independence of $$X$$ and $$Y$$. Similarly (check it out), $$\Pr\{X\leq t, Y\leq f(X) \mid X = x \} = f(x)\,I_{[a,t]}(x).$$ Hence, doing the integrals, we have $$\Pr\{Z\leq t\} = \int_a^t f(x)\,dx,$$ as desired.