inverse-transform and rejection sampling

Every simulation rests on one humble ability: turning the computer's stream of uniform random numbers between 0 and 1 into draws from whatever distribution you actually need — a normal, an exponential, a custom shape. Two classic recipes do this. Inverse-transform sampling works when you can invert the cumulative distribution function; rejection sampling works when you cannot, by sampling cleverly and throwing some draws away.

Inverse-transform rests on a small miracle called the probability integral transform: if U is uniform on [0, 1] and F is the cumulative distribution function (CDF) you want, then X = F^(-1)(U), the value of the quantile function at U, has exactly the distribution F. The picture: pick a height U uniformly on the vertical axis between 0 and 1, slide across to the CDF curve, and read off the x where the curve reaches that height; do this many times and the x's are distributed as F. For example F(x) = 1 - e^(-lambda x) for the exponential inverts to X = -ln(1 - U)/lambda, a one-line generator. Rejection sampling handles the common case where F^(-1) has no formula: enclose the target density f under a scaled easy-to-sample density g (so c times g(x) >= f(x) everywhere), draw a candidate x from g, draw a uniform u, and ACCEPT x only if u <= f(x) / (c g(x)); otherwise discard and try again. The accepted points are distributed exactly as f — geometrically, you are throwing darts under the envelope c g and keeping only those that also fall under f.

These are the foundations beneath every higher method (Monte Carlo, MCMC, the bootstrap), and each has an honest cost. Inverse-transform is exact and uses exactly one uniform per draw, but needs an invertible CDF, which many distributions lack in closed form. Rejection is wonderfully general and exact, but its efficiency is 1/c — the acceptance probability — so if the envelope fits the target poorly, c is huge and you reject almost everything, wasting enormous effort. The whole edifice also assumes your underlying uniform generator is genuinely uniform and independent; a flawed generator silently corrupts every draw downstream.