Communications of the ACM

of the types we deal with in code are discrete and not “measurable” or real number-like.

Because the values we care about are usually not even comparable, we also will avoid cumulative distributions. One reason that mathematicians like standard continuous distributions—such as Gaussian, beta, binomial, and uniform—is because of their nice algebraic properties, called conjugate priors. 2 For example, uniform prior combined with a binomial likelihood results in a beta posterior. This makes 18th- and 19th- century probabilistic computations using pencil and paper feasible, but that is not necessary now that there are powerful computers that can run millions of simulations per second.

In programming examples, distributions typically come from outside data as discrete frequentist collections of data with an unknown distribution, or they are defined explicitly as a Bayesian representation by enumerating a list of value/probability pairs. For example, here is the distribution of weight of adults in the United States, according to the Centers for Disease Control (CDC):

CDC ∈ ℙ (Weight)

CDC = [obese  0.4, skinny  0.6]

Efficiently sampling from com-
posed distributions is, indeed, rocket
science. Just like database query opti-
mizers, advanced sampling methods
leverage properties of the leaf distribu-
tions and the structure of the query9
or program3 that computes the distri-
bution. It leverages deep and complex
mathematical techniques such as im-
portance sampling, Metropolis-Hast-
ings, Markov Chain Monte Carlo, and
Gibbs sampling that are far outside the
scope of this article but are important
for making real-world computations
over probability distributions feasible.
As Bayesian analysis consultant John
D. Cook remarked “... Bayesian statis-
tics goes back over 200 years, but it did
not take off until the 1980s because
that’s when people discovered practi-
cal numerical methods for computing
with it …”
To illustrate the sophistication in-
volved in efficiently sampling known
discrete distributions, imagine con-
verting the example distribution CDC
pling from the collection and count-
ing the frequencies of each element
from a in dist.Take(n) group
by a into g select g.Key a
g.Sum()/n approximates the Bayesian
representation of the distribution.

When converting from the Bayesian
to the frequentist implementation,
the probabilities do not to have to
add up to 1, and the sampling pro-
cess will ensure the ratios are prop-
erly normalized.

Like true mathematicians, we will silently switch between these two representations of distributions whenever convenient. Unlike mathematicians, however, to keep things simple we will not consider continuous distributions. We want our distribution to hold generically any type A, and most