Why does elimination method for random variables work? Why does elimination method for random variables work?
Elimination method:


*

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

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

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

*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.
 A: 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$.
A: 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.
