1
$\begingroup$

Why does elimination method for random variables work?

Elimination method:

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

  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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Henry
    Dec 13, 2018 at 22:14
  • 1
    $\begingroup$ Are you describing a method for simulating observations according to a density $f$? $\endgroup$
    – AdamO
    Dec 13, 2018 at 22:15

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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<f<c$ (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.

Improve this answer
$\endgroup$

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