12 A better abstraction for randomness

In this chapter, probability is introduced as a way to reason about uncertainty in programs, starting with the contrast between frequentist and Bayesian interpretations. Frequentism treats probability as long-run observed frequency across repeated trials, while Bayesian thinking treats probability as a degree of confidence that updates when new evidence appears. The chapter uses this distinction to motivate a practical goal: representing random quantities in a way that is more expressive than directly calling a standard random-number generator.

The core abstraction is a pair of generic interfaces for distributions, one for any distribution and one for discrete distributions. A discrete distribution exposes its support and the weight of each possible outcome, letting probabilities be stored as integer weights rather than normalized decimals. This supports simple cases like uniform sampling and Bernoulli coin flips, including fair, unfair, double-headed, and double-tailed coins, while also allowing distributions to be inspected through helper methods that produce infinite sample streams, printed weights, and histograms.

From there, the chapter generalizes random values by adding projection and filtering operations, making distributions behave more like fluent sequence objects. Projection lets a distribution over integers be transformed into one over any type, enabling categorical distributions for arbitrary labels and showing several ways to sample them: a naive big-list approach, a ladder-based search, rejection sampling, and finally the alias method. The alias algorithm is presented as the efficient solution, achieving constant-time sampling with linear storage, and the chapter closes by showing how filtering a distribution removes unwanted outcomes, setting up later use of probability objects for Bayesian reasoning and decision-making.

• The frequentist philosophy sees probabilities as fractions of observed outcomes of experiments. The Bayesian philosophy sees probabilities as quantified opinions about confidence in outcomes based on observed evidence and therefore subject to change.
• A discrete probability distribution is formally a PMF. It assigns a probability to each member of its support. We can represent probabilities as fractions between 0.0 and 1.0 or as integer weights; both options have pros and cons. A distribution produces samples; Bayesians use the weight of a value to quantify the strength of our belief that the next sample will be than as value.
• We can make code that uses randomness read more like what it does. We can reason about distributions as distributions rather than as calls to Random.Next.
• The discrete uniform distribution is like a fair n-sided die; when sampled, it generates equally weighted samples between 0 and n−1. The Bernoulli distribution is like an unfair coin; when sampled, it generates 0 or 1, with a specified weight for each. A categorical distribution generates samples of any desired type from any support with any weights; it’s the most general of the finite discrete distributions.
• We looked at four ways to implement categorical distributions. The quick-­and-dirty algorithm is inefficient if the total weight is large. The ladder algorithm can be optimized to have an O(log n) worst case. The rejection algorithm has an arbitrarily bad worst case. The alias algorithm is more complex to implement but has an O(1) cost for sampling and never rejects a sample.
• A categorical distribution can easily be filtered to remove a category, which will come in handy in chapter 13.

FAQ