Distributions and How to Sample Them

A computer usually supplies uniform pseudorandom numbers. Sampling a waiting time, a Gaussian or a categorical choice requires transforming that starting noise. The Gumbel-max trick turns independent continuous noise into a discrete draw.

Mass, density and cumulative probability

A discrete probability mass function gives $p(k)=P(X=k)$, with $\sum_kp(k)=1$. A continuous density instead gives interval probabilities by integration: $P(a<X\le b)=\int_a^bp(x)dx$. At a single point the probability is zero, and a density may exceed one.

The cumulative distribution function $F(x)=P(X\le x)$ works in both settings. It is nondecreasing and right-continuous, tending to zero and one at the two extremes. A discrete CDF jumps by the probability mass; a continuous differentiable CDF has derivative p.

Distributions to recognise

Binomial probabilities count which k trials succeed, then multiply the probability of each ordered outcome. A geometric waiting time requires k−1 failures before success. Taking the binomial limit with n large and np fixed yields the Poisson model. For a constant event rate λ, the chance of no event by time x is $e^{-\lambda x}$, giving the exponential CDF $1-e^{-\lambda x}$.

Always state whether a geometric variable counts trials or failures. The two conventions differ by one.

Invert the CDF

For a continuous strictly increasing CDF and $U\sim\operatorname{Uniform}(0,1)$, define $X=F^{-1}(U)$. Then

$P(X\le x)=P(U\le F(x))=F(x).$

For distributions with jumps use the generalised inverse $F^{-1}(u)=\inf\{x:F(x)\ge u\}$. This produces discrete categories too.

An exponential draw is $X=-\log(1-U)/\lambda$. The equally distributed $-\log U/\lambda$ is valid as well. Avoid endpoints that make a logarithm undefined in numerical code. A categorical draw selects the first cumulative probability at least U.

Transform a density

For a differentiable one-to-one transformation $Y=g(X)$ with nonzero derivative on its domain,

$p_Y(y)=p_X(g^{-1}(y))\left|\frac{d}{dy}g^{-1}(y)\right|.$

Probability is preserved while interval widths change. For X uniform on [0,1] and Y=X², the CDF is $\sqrt y$ on [0,1], so the density is $1/(2\sqrt y)$ in the interior. It exceeds one near zero but still integrates to one.

A many-to-one transformation requires adding contributions from all inverse branches. Squaring a variable that can be positive or negative is one such case. In several dimensions the inverse derivative becomes an absolute Jacobian determinant.

Read beyond

Read the equation in context

The paper begins with categorical sampling by adding Gumbel noise to log probabilities, then replaces argmax with a temperature-controlled softmax. The hard draw is discrete; the relaxed vector is differentiable but is not an exact one-hot draw at positive temperature.

Your turn

Use the CDF to map a probability level to a quantile. Change the distribution and observe how uniformly spaced probability levels produce unevenly spaced samples.

Coding problems