1.4 Cumulative Distribution Function (CDF)

While the Probability Mass Function (PMF) gives the probability of a random variable being exactly a certain value, the Cumulative Distribution Function (CDF) gives the probability that the random variable is less than or equal to a certain value.

Definition

For a discrete random variable X, the CDF, denoted as F(x), is defined as:

$ F(x) = P(X \le x) = \sum_{t \le x} P(X=t) $

The CDF is a "cumulative" sum of probabilities. For discrete variables, this results in a step function that is non-decreasing and ranges from 0 to 1.

Properties of a CDF:

• $ 0 \le F(x) \le 1 $
• $ F(x) $ is non-decreasing: if $ a < b $, then $ F(a) \le F(b) $.
• $ \lim_{x \to -\infty} F(x) = 0 $ and $ \lim_{x \to +\infty} F(x) = 1 $.

Visualization: PMF and CDF

The following visualization shows the PMF of a 6-sided die (as bars) and its corresponding CDF (as a step line). Notice how each step in the CDF corresponds to the probability of that outcome in the PMF.

Parametric Visualization

Adjust the weights of the outcomes for a 4-sided die. The PMF and CDF will update automatically. This demonstrates the direct relationship between the individual probabilities (PMF) and the cumulative probability (CDF).

Connection to LLMs: Nucleus Sampling

The CDF is extremely important in modern LLMs for a technique called Nucleus Sampling (or top-p sampling).

Instead of considering all 50,000 words in the vocabulary (many of which have near-zero probability), nucleus sampling provides a way to narrow down the choices to a smaller, more reasonable set.

Here's how it works:

1. The LLM calculates the PMF for the next word.
2. The words are sorted by their probability in descending order.
3. The CDF is calculated for this sorted list.
4. A probability threshold, p (e.g., 0.9), is chosen.
5. The model considers only the top words whose cumulative probability is less than or equal to p. This set of words is the "nucleus".
6. The model then samples a word from this nucleus, after renormalizing their probabilities.

This method avoids the risk of picking strange or nonsensical words from the long tail of the probability distribution, leading to more coherent and high-quality text generation. It's a perfect example of how a fundamental concept like the CDF is applied to solve a practical problem in state-of-the-art AI.