rejection sampling
Suppose you want to scatter points evenly under a strangely shaped hill — a probability density you can compute but cannot invert. Here is a wonderfully simple idea: throw darts uniformly at a big rectangle that fully covers the hill, and KEEP only the darts that land under the hill's curve; throw away (reject) the rest. The points you keep are distributed exactly according to the hill's shape. That is rejection sampling, invented by von Neumann.
Precisely: to sample from a target density f, choose an easy 'proposal' density g you CAN sample from and a constant M with f(x) <= M * g(x) everywhere, so M*g forms an envelope sitting above f. Repeat: draw a candidate x from g, draw a uniform u in [0, 1), and ACCEPT x if u <= f(x) / (M * g(x)); otherwise reject and try again. Accepted x's follow f exactly — no inversion, no integral of f needed, you only have to evaluate f up to a constant. The fraction you accept on average is 1/M, the ratio of the area under f to the area under the envelope; the tighter the envelope hugs f, the fewer darts you waste.
Its charm is that it works for almost any density you can write down and bound, even ones with no closed-form CDF, and it gives EXACT samples (not approximate ones). Its honest weakness is efficiency: if the envelope M*g is much bigger than f — which is easy to happen in high dimensions, where a box dwarfs the region under any peaked density — then 1/M becomes tiny and you reject almost everything, wasting enormous effort per accepted sample. So rejection sampling shines in low dimensions with a snug proposal and degrades badly otherwise, which is one reason MCMC methods took over for hard high-dimensional sampling.
To sample a point uniformly in the unit disk, draw (x, y) uniformly in the square [-1,1] x [-1,1] and accept only if x^2 + y^2 <= 1. The disk's area pi vs the square's area 4 means you accept pi/4 = 78.5% of darts. Counting that acceptance fraction is itself a Monte Carlo estimate of pi.
Throw darts under an envelope, keep the ones beneath the true curve.
The acceptance rate is 1/M, so a loose envelope is wasteful, and in high dimensions M typically grows exponentially — making naive rejection sampling effectively useless there. A poorly chosen proposal that violates f <= M*g anywhere produces a SILENTLY biased sample.