Counting and Probability Axioms

Counting is the finite foundation of elementary probability. Before assigning probabilities, we need to know how many outcomes an experiment has and how many of them satisfy an event.

Counting principles

TheoremProduct rule

If a procedure consists of two stages, with $m$ possible outcomes at the first stage and $n$ possible outcomes at the second stage for each first-stage outcome, then the procedure has $mn$ possible outcomes.

The same reasoning gives the generalized product rule. If stage $i$ has $n_i$ choices once the previous stages have been fixed, then the total number of outcomes is

$$\prod_{i=1}^{r}n_i.$$

For example, $k$ independent coin tosses have $2^k$ possible outcome strings.

TheoremSum rule

If a procedure can be carried out in one of $m$ mutually exclusive ways or one of $n$ mutually exclusive ways, then it has $m+n$ possible outcomes.

The disjointness condition matters. For arbitrary finite sets $A$ and $B$, inclusion-exclusion corrects the overlap:

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

For three sets,

$$|A\cup B\cup C| =|A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|.$$

TheoremDivision rule

Suppose a set of $N$ objects is partitioned into equivalence classes, each containing exactly $d$ objects. Then the number of classes is $N/d$.

This rule formalizes the instruction to count labelled constructions first and then identify constructions that differ only by an irrelevant ordering. It is valid only when every equivalence class has the same size.

TheoremPigeonhole principle

If $N$ objects are placed into $k$ boxes, some box contains at least $\lceil N/k\rceil$ objects. In particular, placing $k+1$ objects into $k$ boxes forces a box to contain at least two objects.

To prove the generalized form, assume every box contains at most $\lceil N/k\rceil-1$ objects. Then the total would be at most

$$k\left(\left\lceil\frac{N}{k}\right\rceil-1\right)<N,$$

which contradicts the fact that there are $N$ objects.

Finite probability models

DefinitionSample space and event

A finite sample space $\Omega$ is the set of all outcomes of an experiment. An event is a subset $A\subseteq\Omega$.

DefinitionProbability measure

A probability measure on a finite sample space is a function $P:2^\Omega\to[0,1]$ satisfying

$$P(\Omega)=1, \qquad P(A\cup B)=P(A)+P(B)$$

whenever $A\cap B=\varnothing$.

The axioms imply

$$P(\varnothing)=0, \qquad P(A^c)=1-P(A), \qquad P(A\cup B)=P(A)+P(B)-P(A\cap B).$$

They also imply monotonicity: if $A\subseteq B$, then $P(A)\leq P(B)$.

If all outcomes are equally likely, then

$$P(A)=\frac{|A|}{|\Omega|}.$$

This formula is a model-specific consequence, not the definition of probability. It cannot be used when outcomes do not have equal probability.

ExampleTwo coin tosses

For two fair tosses,

$$\Omega=\{HH,HT,TH,TT\}.$$

The event that exactly one head appears is $A=\{HT,TH\}$, so $P(A)=2/4=1/2$.

Random variables and distributions

A random variable is a function $X:\Omega\to\mathbb{R}$. For a discrete random variable, its probability mass function is

$$p_X(x)=P(X=x),$$

and it satisfies $p_X(x)\geq0$ and $\sum_xp_X(x)=1$. The cumulative distribution function is defined for every random variable by

$$F_X(t)=P(X\leq t).$$

The counting principles above are useful when the sample space is finite, but the axiomatic definition continues to apply when outcomes are not equally likely or when the sample space is infinite.