Chapter 12: A better abstraction for randomness

Introduction

This chapter introduces a higher-level abstraction for discrete randomness, centered on representing and efficiently sampling unfair die rolls as categorical distributions in preparation for Bayesian reasoning.

• Randomness abstraction motivation: Explain why the chapter seeks a better representation of randomness than ordinary random-number-generating functions, and relate it to manipulating random quantities with high-level, fluent operations.
  Why it matters: A higher-level representation makes probabilistic code more readable and composable than hand-written random-number loops.
• Categorical distribution agenda: Describe the chapter's central discrete-randomness task: representing a categorical distribution as an unfair die roll, sampling it efficiently with several algorithms, and filtering categories out of it.
  Why it matters: Categorical distributions provide a concrete representation of weighted discrete outcomes that later probability operations can build on.
• Bayesian preparation: State how this chapter prepares for chapter 13: its distribution representation and unfair-die simulation are groundwork for automatically applying Bayes' theorem when new real-world evidence affects a program's decision.
  Why it matters: The immediate work on discrete randomness supports the later goal of updating decisions in light of evidence.

Key terms: random number generating functions, random quantities, Where, SelectMany, Join, GroupBy, discrete probability distributions, categorical distribution, unfair die, sampling

12.1 What are probabilities?

This section contrasts frequentist and Bayesian meanings of probability and states how the book will use both perspectives.

• Frequentist probability: Explain the frequentist view that an outcome’s probability is its observed long-run frequency across many repetitions of the same experiment, and therefore lies between zero and one.
  Why it matters: This gives a testable interpretation of probability for repeatable random experiments.
• Bayesian probability: Describe the Bayesian view that probability expresses confidence in an outcome based on available evidence, and that this informed opinion changes when new evidence arrives.
  Why it matters: This perspective lets the book discuss uncertainty even when an event cannot conveniently be repeated.
• Book’s dual probability use: State that the book mainly adopts the Bayesian attitude toward probabilities while using frequentist sampling checks to test whether an algorithm produces expected proportions, such as roughly 30,000 heads in 100,000 samples for a 30% heads process.
  Why it matters: It distinguishes using probability to model uncertainty from using repeated samples to check an implementation.

Key terms: Frequentist, probability, outcome, trials, frequency, Bayesian, confidence, evidence, frequentist philosophy, Bayesian attitude

12.2 What are discrete probability distributions?

This section defines finite discrete probability distributions through probability mass functions and explains sampling outcomes according to their assigned probabilities.

• Discrete distribution components: Explain that a probability distribution assigns probabilities to outcomes, and define its support as the set of possible outcomes. Distinguish a discrete support, such as die faces or coin results, from a continuous range of outcomes.
  Why it matters: These terms specify exactly what kind of random quantity the chapter’s abstractions will represent.
• Probability mass functions: Describe a probability mass function (PMF) as the function, conventionally written P, that gives the probability of each outcome in a discrete distribution. Explain discrete uniform distributions as the special case where every supported outcome has equal probability.
  Why it matters: The PMF is the representation that determines how often each outcome should appear when sampled.
• Sampling finite distributions: Explain that sampling from a distribution produces a random value in its support, with each value occurring according to the PMF. State that this book restricts its discrete distributions to finite support, although discrete support can in principle be infinite.
  Why it matters: Sampling is how a program turns a modeled distribution into random game events, simulation events, and later algorithms.

Key terms: probability distribution, support, discrete, continuous, probability mass function, PMF, P, discrete uniform distribution, sampling, finite support

12.3 Generating uniform samples with Random

This section explains what C# Random.Next(max) samples, why its pseudorandom output is unsuitable for security, and why randomness needs a higher-level generic distribution abstraction.

• Random.Next uniform sampling: Describe the discrete uniform distribution sampled by Random.Next(max), including its integer support from 0 through max minus 1 and its role in a simple fair die simulation.
  Why it matters: This establishes the basic built-in sampling operation that the later distribution abstractions generalize.
• Pseudorandomness security limits: Explain that Random produces deterministic pseudorandom values that are adequate for many ordinary uses but predictable to an attacker with enough samples, so security-sensitive uses require a crypto-strength pseudorandom generator such as RandomNumberGenerator.
  Why it matters: Choosing a convenient random API when unpredictability is required can compromise games of chance and cryptographic keys.
• Distribution abstraction motivation: Explain why one-shot integer sampling with Random.Next(n) is too low-level for richer random programs, and describe the proposed generic distribution abstraction as representing outcomes whose support is drawn from type T, analogous to how IEnumerable<T> represents sequence elements.
  Why it matters: The abstraction makes it possible to work with random cards, songs, compound die rolls, and other typed random quantities rather than only individual integer draws.

Key terms: Random, Next(max), discrete uniform distribution, support, pseudorandom, deterministic algorithm, RandomNumberGenerator, crypto-strength pseudorandom number generator, one-use tool, probability distribution

12.4 IDistribution<T> and IDiscreteDistribution<T>

This section defines generic interfaces for sampling probability distributions and representing discrete distributions with integer weights.

• Distribution sampling interface: Describe IDistribution<T> as a generic interface whose Sample() operation returns a randomly generated value of type T from the distribution's support, and explain its role as the base interface for discrete distributions now and continuous distributions later.
  Why it matters: A common sampling interface lets different kinds of distributions be used through the same abstraction.
• Discrete distribution capabilities: Explain that IDiscreteDistribution<T> extends the sampling abstraction by providing Support() to enumerate possible values and Weight(T) to obtain a value's integer weight, with zero weight for a value outside the support.
  Why it matters: Discrete algorithms need both the ability to draw outcomes and the ability to inspect which outcomes exist and how they are weighted.
• Integer weight probabilities: Explain how a discrete outcome's sampling probability is computed as its positive integer weight divided by the sum of all support members' weights, and distinguish these non-normalized weights from a PMF stored as doubles.
  Why it matters: Integer weights express relative likelihoods without requiring stored probabilities to sum exactly to one.

Key terms: IDistribution<T>, Sample(), support, IDiscreteDistribution<T>, Support(), Weight(T), weight, non-normalized integer weights, PMF, rounding errors

12.5 Flipping an unfair coin with Bernoulli

This section implements Bernoulli coin-flip distributions by combining singleton and discrete-uniform distributions, while reducing outcome weights to lowest terms with the GCD.

• Bernoulli coin-flip model: Describe how a Bernoulli distribution models a coin flip as an integer distribution in which 0 represents tails and 1 represents heads, including fair and unfair coins.
  Why it matters: This gives coin flips a reusable distribution abstraction instead of requiring direct calls to Random.
• Weighted uniform sampling: Explain how integer weights generate an unfair Bernoulli sample: sample uniformly from a range whose size is the total weight, then map ranges of sampled values to tails or heads. Describe how a double-headed or double-tailed coin is represented as a singleton distribution.
  Why it matters: Integer-weighted sampling makes specified coin odds easy to implement and read without hand-writing random-number tests.
• Lowest-term weight reduction: Explain why integer outcome weights are stored in lowest terms and describe using Euclid’s algorithm to find their greatest common divisor, including its base case and recursive remainder rule.
  Why it matters: Reducing equivalent weights avoids carrying unnecessary larger numbers into later distribution algorithms.

Key terms: Bernoulli distribution, tails, heads, coin flip, weight, total weight, discrete uniform distribution, singleton distribution, double-headed coin, double-tailed coin

12.6 Improving the ecosystem with extension methods

This section adds extension methods that expose distributions as infinite sample sequences and quickly visualize discrete distributions.

• Sample sequence bridge: Explain how the Samples() extension turns an IDistribution<T> into an unbounded sequence of generated samples, allowing familiar sequence operations to be used fluently on distribution output.
  Why it matters: This bridge lets distribution code read in terms of the samples you want to generate and process.
• Discrete distribution visualization: Describe the extension methods for inspecting a discrete distribution by printing its weights and displaying a histogram, including how repeated Bernoulli samples can check whether observed outcomes match the intended bias.
  Why it matters: Quick weight displays and histograms make it easier to debug and sanity-check probabilistic code.

Key terms: Samples(), IDistribution<T>, unbounded sequence of samples, extension methods, fluent interface, discrete distributions, weights, histogram, Bernoulli

12.7 Representing unfair die rolls by adding a projection

This section implements projected discrete distributions so an underlying distribution can be mapped to arbitrary categories and combined into an unfair categorical distribution.

• Projected distribution behavior: Describe how a Projected distribution wraps an underlying discrete distribution and a projection function, sampling the underlying value and returning its projected result.
  Why it matters: Projection lets distributions return meaningful values such as colors or heads and tails rather than only their original sample values.
• Projected support and weights: Explain how Support() and Weight(T) for a projected distribution are computed by projecting every underlying support value, grouping equal projected results, and summing their underlying weights, reducing the resulting weights to the smallest values possible.
  Why it matters: Many original outcomes can collapse into one projected category, so correct aggregation is what preserves the intended probabilities.
• Categorical distribution generality: State that the projected colored die is a categorical distribution: a finite discrete distribution that chooses among categories of any type, each with an arbitrary weight, making it the most general finite discrete distribution.
  Why it matters: This abstraction is the common input for the chapter's later algorithms for sampling weighted categories.

Key terms: Projected, projection, underlying discrete distribution, Sample(), Support(), Weight(T), group, total weight, Bernoulli distribution, categorical distribution

12.8 Categorical algorithm 1: Make a big list

This section presents a quick categorical-distribution algorithm that samples from a weight-expanded list and explains why its O(W) setup cost is impractical.

• Weight-expanded categorical sampling: Describe how the quick-and-dirty categorical-distribution algorithm builds a collection containing each category repeated according to its weight, then samples it through a uniform discrete distribution and projection.
  Why it matters: This establishes a correct baseline for categorical sampling before more efficient algorithms replace its large expanded collection.
• Expanded-list setup costs: Explain the performance trade-off of the quick-and-dirty projection algorithm: Sample() is O(1), but building the distribution takes O(W) time and O(W) extra storage, where W is the total weight.
  Why it matters: A fast individual sample does not make an algorithm suitable when its preprocessing time and memory scale with a potentially huge total weight.

Key terms: categorical distribution, support, weight, uniform discrete distribution, projection, Sample(), quick-and-dirty projection algorithm, O(1), O(W), total weight

12.9 Categorical algorithm 2: Climb a ladder

This section presents ladder climbing as a categorical-sampling algorithm, compares its costs with the prior big-list approach, and sketches a binary-search optimization.

• Ladder-climbing categorical sampling: Describe how to sample an integer categorical distribution by treating cumulative weights as uneven ladder-rung heights. Explain that a uniform height from 0 through W−1 selects the lowest rung whose cumulative weight is greater than that height.
  Why it matters: This method samples weighted categories without constructing one list entry for every unit of weight.
• Support projection: Explain how an integer categorical distribution over 0 through n−1 can be converted into a distribution over arbitrary category values by applying a projection.
  Why it matters: Keeping the sampling machinery indexed by integers lets the same algorithm serve any kind of category.
• Cost tradeoffs and binary search: Compare the big-list algorithm with ladder climbing in terms of space, construction, and sample time, and describe the proposed binary-search improvement. State why repeated cumulative heights from zero-weight categories require careful handling in the binary-search version.
  Why it matters: The comparison shows why a representation that is cheaper to build may need a different search strategy to remain fast at sampling.

Key terms: total weight, support, ladder, rungs, uniform distribution, cumulative weights, projection, categorical distribution, Algorithm 1, Algorithm 2

12.10 Categorical algorithm 3: Rejecting rejection sampling

This section introduces categorical rejection sampling as dart throwing on a weighted histogram, then explains why its unbounded retries make it a poor categorical sampler.

• Categorical rejection-sampling model: Describe how rejection sampling represents weighted categories as rows of a rectangular dartboard whose width is the largest weight. Explain that a row is chosen uniformly, a column is chosen uniformly, and an attempt is retried when it lands on an X rather than a category.
  Why it matters: This gives you a concrete way to see how rejection sampling turns uniform random choices into weighted categorical samples.
• Weight-proportional sample probabilities: Explain why accepted samples occur in proportions matching the category weights. State that each category occupies a number of non-X squares equal to its weight, so conditioning on hitting a non-X square preserves those relative proportions.
  Why it matters: The point of the algorithm is not merely to return a category, but to return categories with the intended weighted probabilities.
• Unbounded rejection cost: Explain why rejection sampling can have arbitrarily bad worst-case sampling time for categorical distributions. Distinguish the O(n) Max() calculation, which can be cached, from the real problem: an unbounded retry loop when a large fraction of the dartboard consists of Xs.
  Why it matters: Recognizing the rejection bottleneck explains why a different categorical algorithm is needed despite this method's simple implementation.

Key terms: rejection sampling, categories, weights, largest weight, dartboard, X, non-X portions, proportional, generated samples, Max()

12.11 Categorical algorithm 4: The alias algorithm

This section explains how the alias algorithm preprocesses integer-weighted categorical distributions into row distributions that sample in constant time without rejection.

• Alias-table construction: Describe how the alias algorithm turns nonzero integer category weights into a rectangular n-by-W dartboard by filling each row to width W with values moved from long rows to short rows.
  Why it matters: This construction preserves each category's weighted area while ensuring that every possible dart hit produces a sample.
• Row-distribution sampling: Explain that the completed rectangle is represented as one singleton or projected Bernoulli distribution per row, and that sampling chooses a row uniformly and then samples that row's distribution.
  Why it matters: Representing each row as a tiny distribution is what converts the conceptual dartboard into executable constant-time sampling.
• Alias algorithm complexity: State that preprocessing uses O(n) extra storage and at most O(n) balancing iterations, while each Sample() call is O(1) because it makes two constant-time samples.
  Why it matters: The alias algorithm achieves the chapter's target of linear extra storage with constant-time samples from arbitrary discrete distributions.
• Zero weights and doubles: Distinguish the alias algorithm's immunity to zero-weight-category problems from its implementation difficulty with double weights, where floating-point rounding can misclassify row widths.
  Why it matters: This clarifies why integer weights make the algorithm straightforward and why numerical representation affects algorithm correctness.

Key terms: alias algorithm, categorical distribution, weights, short row, long row, just-right row, singleton, Bernoulli, projection, uniformly distributed

12.12 Filtering out a category

This section shows how to filter a categorical distribution by excluding outcomes and renormalizing the remaining sampling probabilities, setting up Bayesian reasoning.

• Categorical distribution filtering: Describe how to construct a filtered categorical distribution from an existing distribution and a predicate: an outcome remains in the support only when the predicate accepts it.
  Why it matters: Filtering lets a program express the distribution that results when certain possible outcomes are ruled out.
• Green-roll rejection model: Explain that repeatedly rerolling an unfair die whenever green appears has the same distributional result as making a new categorical distribution with green assigned weight zero, so green no longer appears in its samples.
  Why it matters: This replaces an operational reroll loop with a direct representation of the conditional set of acceptable outcomes.
• Bayesian reasoning motivation: State that arbitrary categorical distributions and category filtering provide the tools needed to reason backward from observed effects to deduced causes with Bayes’ theorem in the next chapter.
  Why it matters: The filtering example is a bridge from sampling distributions to making principled inferences from evidence.

Key terms: categorical distribution, predicate, support, filtered distribution, unfair die, green, weight, re-roll, histogram, Bayes’ theorem

12.13 Summary

This summary recaps discrete probability distributions, their programming abstractions and sampling algorithms, and filtering categories for later probabilistic reasoning.