From flat uniforms to any shape
The previous guide left us with a pseudorandom number generator that, given a seed, spits out a deterministic stream of numbers spread evenly across the interval (0,1). That is all most generators ever give you: flat, featureless uniform draws, each one equally likely to land anywhere in the unit interval. But nature is not flat. Heights cluster near an average and thin out at the extremes; the time you wait for the next bus follows an exponential decay; a physics simulation may need a lumpy custom density with two humps. So the central question of this guide is simple to state and surprisingly deep to answer: given only a faucet of uniform numbers, how do we produce draws that follow some other prescribed distribution?
Why does this matter so much? Because every Monte Carlo idea downstream rests on it. To do Monte Carlo integration you scatter random points and average a function over them — but the points must follow the right distribution or the average estimates the wrong thing. To run importance sampling you deliberately draw from a cleverly chosen density instead of the natural one. To explore a hard high-dimensional target with the Metropolis-Hastings algorithm you still need to sample simple proposal moves. Sampling is the foundation; the rest of the rung is what you build on top of it.
Inverse-transform: ride the CDF backwards
The cleanest trick is inverse-transform sampling, and the picture behind it is worth fixing in your head. Every distribution has a cumulative distribution function, written F(x): it is the probability that a draw lands at or below x, so it climbs from 0 on the far left up to 1 on the far right, never going down. Now flip your view. Instead of asking "given x, what is the probability F(x)?", ask the reverse: "given a probability level u, what x sits at that height?" That answer is the inverse function, F^{-1}(u). The whole method is one line: draw a uniform u in (0,1), then output x = F^{-1}(u).
Why does riding the CDF backwards work? Picture the curve of F as a staircase you climb. Where the distribution is dense, F rises steeply, so a fat slice of the u-axis maps onto a thin slice of the x-axis — many uniform draws get funneled into that narrow, popular region. Where the distribution is sparse, F is nearly flat, so a thin slice of u spreads across a wide stretch of x, and few draws land there. The flat uniform stream gets squeezed and stretched until its density exactly matches F. As a tiny worked case, the exponential with rate 1 has F(x) = 1 - e^{-x}; inverting gives x = -ln(1 - u), so each uniform u instantly becomes an exponential draw.
u ~ Uniform(0,1) # one flat draw
x = Finv(u) # x = F^{-1}(u), the inverse CDF
# exponential(rate=1): Finv(u) = -ln(1 - u)
# u = 0.5 -> x = 0.693
# u = 0.9 -> x = 2.303 (rarer, deeper into the tail)Rejection sampling: throw darts, keep the good ones
When you cannot invert F — or you only know the density's shape, even up to an unknown scaling constant — rejection sampling saves the day. The idea is gleefully physical. Suppose your target density is some curve p(x) sitting over an interval. Find a simple shape you CAN sample from — often just a uniform box, or a scaled-up easy density called the proposal — that completely covers p(x) like a tent. Now throw darts uniformly under the tent's roof. Some darts land under the curve p(x); some land in the empty gap between the curve and the roof. Keep the darts that land under p(x); throw away (reject) the rest. The kept darts' x-coordinates are exact draws from p.
- Pick a proposal you can sample and a constant M so that the scaled proposal M*q(x) sits entirely above the target p(x) everywhere — the tent must cover the curve.
- Draw a candidate x from the proposal q, and independently draw a uniform u in (0,1) — this u picks a random height under the tent at that x.
- Accept x if u <= p(x) / (M*q(x)) — the dart fell under the real curve; otherwise reject it and loop back to try again.
- The stream of accepted x values is distributed exactly as p, no matter how ugly p is, as long as the tent truly covers it.
Rejection is wonderfully general — it works for densities with no formula for F at all, and it tolerates knowing p only up to a constant, since an unknown scale just rides along inside M. But honesty demands the catch: its efficiency is the fraction of the tent's area that lies under the curve. If your tent fits snugly, you accept most darts; if it is baggy, you reject almost everything and waste enormous effort. And here is the brutal twist that motivates the rest of this rung: in high dimensions a tent that covers a target almost always becomes catastrophically baggy, so the acceptance rate collapses toward zero. That curse is exactly why hard high-dimensional problems abandon plain rejection for the Markov-chain methods of guide 5.
Honesty: what "correct" sampling really means
It is tempting to imagine that a sampler outputs "the" right numbers. It does not. Both methods produce a RANDOM sequence whose long-run histogram converges to the target density — any single batch of draws is one noisy realization, and two different seeds give two different (equally valid) batches. "Correct" means the distribution of the draws is right, not that any particular draw is special. This is the same humility that runs through all of computational mathematics: just as a numerical solution of A x = b is an approximate answer with a backward-stable story behind it, a sample is an approximate stand-in for a distribution, and its quality only shows up when you average many draws.
Two more honest caveats. First, every draw is filtered through floating-point arithmetic: -ln(1 - u) is not the exact real logarithm, and when u is extremely close to 1 the subtraction 1 - u loses precision (a small echo of catastrophic cancellation), so deep tails are sampled less faithfully than the bulk. Second, the whole pipeline inherits the determinism of its source. Your "random" draws are a fixed function of the seed, which is a gift for reproducibility and debugging but a trap if a flawed generator has hidden correlations — then your beautifully shaped samples are subtly wrong in ways no histogram of a single coordinate will reveal.
Choosing a method, and where this leads
So which trick do you reach for? If the CDF and its inverse have clean formulas, use inverse-transform — it is exact, deterministic per draw, and wastes nothing. If you only have the density's shape (perhaps unnormalized) and can build a snug covering tent, use rejection. For the workhorse normal distribution, practitioners use neither in their naive form: a specialized transform turns pairs of uniforms into pairs of Gaussians directly, which is why a good library has a dedicated Gaussian routine rather than inverting F by hand. The lesson is that "sampling" is not one algorithm but a toolbox, and the right tool depends on what you can compute about your target.
Notice the thread that ties this rung together. Both methods here can produce truly independent draws, which is the cleanest possible situation. But both break down in high dimensions: inverse-transform needs a workable inverse CDF you rarely have for a complicated joint distribution, and rejection's acceptance rate plummets as the covering tent grows baggy. When the target is a tangled high-dimensional density that resists both, you give up on independence and instead build a Markov chain that wanders toward the target — the Metropolis-Hastings idea of guide 5. Before that, guides 3 and 4 show what you can DO with the independent draws you now know how to make: estimate integrals at the famous O(1/sqrt(N)) rate, and shrink that error with importance sampling and friends.