The Art of Computer Programming, Volume 4B: Combinatorial Algorithms

Mathematical Preliminaries Redux

Many parts of this book deal with discrete probabilities, namely with a finite or countably infinite set Ω of atomic events ω, each of which has a given probability Pr(ω), where

0≤Pr(ω)≤1and∑ω∈Ω⁢Pr(ω)=1.(1)

This set Ω, together with the function Pr, is called a “probability space.” For example, Ω might be the set of all ways to shuffle a pack of 52 playing cards, with Pr(ω)= 1/52! for every such arrangement.

An event is, intuitively, a proposition that can be either true or false with certain probability. It might, for instance, be the statement “the top card is an ace,” with probability 1/13. Formally, an event A is a subset of Ω, namely the set of all atomic events for which the corresponding proposition A ...