How does inverse-transform sampling turn uniform draws into a target distribution?

## The problem it solves A random number generator hands you Uniform(0,1) values. Simulation needs draws from exponentials, discrete categories, power laws, custom distributions fitted to data. Inverse-transform sampling is the general bridge between the two. ## The theorem Let `X` be a random variable with cumulative distribution function `F(x) = P(X <= x)`. `F` is non-decreasing, runs from 0 to 1, and for a continuous strictly increasing `F` it has an inverse `F^-1`. Claim: if `U` is Uniform(0,1), then `Y = F^-1(U)` has CDF `F`. Proof: `P(Y <= x) = P(F^-1(U) <= x)`. Since `F` is non-decreasing, `F^-1(U) <= x` exactly when `U <= F(x)`. And for a uniform variable, `P(U <= t) = t` for any `t` between 0 and 1. So `P(Y <= x) = F(x)`, which is the definition of having distribution `F`. The companion statement, the probability integral transform, runs the other way: if `X` is continuous with CDF `F`, then `F(X)` is Uniform(0,1). One direction manufactures draws, the other flattens them. ## Worked case: the exponential An exponential with rate lambda has CDF `F(x) = 1 - exp(-lambda*x)` for `x >= 0`. Solve `u = 1 - exp(-lambda*x)` for `x`: exp(-lambda*x) = 1 - u x = -ln(1 - u) / lambda So `X = -ln(1-U)/lambda` is exponential with rate lambda and mean `1/lambda`. Because `1-U` is itself Uniform(0,1) when `U` is, the equivalent `X = -ln(U)/lambda` is used in practice; it saves a subtraction and is the form worth remembering. Note the rate-versus-mean trap: dividing by lambda gives rate lambda, while multiplying by lambda would give rate `1/lambda`. ## Worked case: a discrete variable Suppose outcomes A, B, C have probabilities 0.5, 0.3, 0.2. Build the cumulative ladder 0.5, 0.8, 1.0. Draw `U` and return the first rung that `U` does not exceed: `U = 0.42` gives A, `U = 0.77` gives B, `U = 0.91` gives C. This is inverse transform with the generalised inverse `F^-1(u) = min{x : F(x) >= u}`, which is defined even where `F` jumps or is flat, so the method covers discrete and mixed distributions without modification. A linear scan costs O(k) per draw for `k` categories; a binary search over the cumulative array costs O(log k), which matters when the ladder is long and the draws are many. ## Where it breaks down The method is only as practical as the inverse CDF. The normal distribution has no closed-form inverse CDF, so drawing normals this way needs a numerical approximation of the inverse; alternatives exist that avoid it, notably the Box-Muller transform, which turns two independent uniforms `U1, U2` into two independent standard normals via `sqrt(-2*ln(U1))*cos(2*pi*U2)` and the same expression with sine. Many fitted or empirical distributions have a CDF you can only evaluate numerically, and inverting it per draw can cost more than an alternative sampler. When the inverse is expensive or unavailable, rejection sampling with a convenient envelope is the usual fallback. ## Why practitioners like it anyway Three properties keep inverse transform in constant use. It is exact, with no acceptance step and no tuning. It consumes exactly one uniform per draw, which makes runs reproducible and easy to reason about when a seed is fixed. And it is monotone: larger `U` gives larger `X`. Monotonicity is what makes it compose cleanly with paired-draw tricks, since the pair `U` and `1-U` maps to a matched low-high pair of target draws, and with common random numbers when two competing system designs must be compared on the same underlying randomness. ## What to say out loud State the theorem with its one-line proof, give the exponential as the worked example, give the cumulative ladder as the discrete case, and name the normal as the standard counter-example where the inverse CDF is not available in closed form.