= Solution
For $0<u<1$ define the generalized inverse, or <quantile function>, by
$$
Q(u)=\inf\{x\in\mathbb R:F(x)\geq u\}.
$$
It is finite because the <cumulative distribution function> tends to zero and one at the two infinities. Monotonicity and right continuity of $F$ give the key equivalence
$$
Q(u)\leq x\quad\Longleftrightarrow\quad u\leq F(x).
$$
For the forward implication, choose points in the defining set approaching its infimum from above. Right continuity gives $F(Q(u))\geq u$, and then monotonicity gives $F(x)\geq u$ whenever $Q(u)\leq x$. The reverse implication follows immediately because $x$ then belongs to the defining set. Consequently, for a continuous <uniform distribution> draw $U$,
$$
\boxed{P(Q(U)\leq x)=P(U\leq F(x))=F(x).}
$$
This proves <inverse transform sampling> for discontinuous as well as continuous distribution functions.
There is a minor endpoint defect in the printed codomain. The true <quantile endpoint at probability one> is $Q(1)=\inf\{x:F(x)=1\}$, which equals $+\infty$ for an unbounded-above <normal distribution>. Thus it need not be real at one. Use the extended-real value there, or assign an arbitrary finite value at this single probability level. Since $P(U=1)=0$, either choice gives the same sampled distribution; the latter supplies a real-valued version on all of $(0,1]$. \b[The endpoint has no effect on the inverse-transform law.]
For <rejection sampling>, choose a proposal <probability density function> $g$ that can be sampled and a finite constant $M$ with $f(y)\leq Mg(y)$ wherever the target has positive mass. Generate independent pairs $(Y_j,U_j)$, with $Y_j$ of density $g$ and $U_j$ uniform. Accept $Y_j$ if $U_j\leq f(Y_j)/(Mg(Y_j))$; otherwise discard the pair and repeat with fresh independent draws. At points where both densities vanish the acceptance rule may be defined arbitrarily. For any measurable set $A$,
$$
P(Y_j\in A,\text{ acceptance})=\int_A g(y)\frac{f(y)}{Mg(y)}dy=\frac1M\int_A f(y)dy.
$$
Thus one trial accepts with probability $1/M$, and the conditional density given acceptance is $f$. More explicitly, summing over the index of the first accepted proposal gives
$$
P(\text{output}\in A)=\sum_{j\geq1}(1-1/M)^{j-1}\frac1M\int_Af(y)dy=\int_Af(y)dy.
$$
The probability of never accepting is zero, since $M<\infty$, and the expected number of proposals is $M$. \b[The algorithm terminates almost surely and samples the target density exactly.]
Back to article page
