Cumulative distribution function

Level UniversityDifficulty ★★★★★Concept⌖ Open in the map

What is it?

$F(x) = P(X \le x) = \int_{-\infty}^x p(t)\,\dd t$ . By the fundamental theorem, $F' = p$ . Its inverse (the quantile function) turns uniform random numbers into samples of any distribution.

Formulas

$F(x) = \int_{-\infty}^{x} p(t)\,\dd t, \qquad F'(x) = p(x)$; $U \sim \mathcal U(0,1) \implies F^{-1}(U) \sim F$
inverse transform sampling

Where it shows up in computing

Monte Carlo methods★★★★★fundamentalScientific computing and algorithms
Inverse transform sampling: e.g. $-\ln(1 - U)/\lambda$ is exponential with rate $\lambda$ .
Queueing theory and performance★★★★★frequentOptimization and systems
Latency percentiles (p99) are quantiles of the response-time distribution.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

What is it?

Formulas

Where it shows up in computing

Where is it used?

λ Scientific computing and algorithms

3D Computer graphics

⇄ Optimization and systems