Foundations of Probability

Motivation: why uncertainty needs a formal model

Uncertainty runs through engineering and everyday life:

staffing call centers against uncertain demand;
low-power circuits built from individually unreliable elements;
wireless links with fading, interference and varying load;
medicine, epidemics, security (backups, firewalls against unknown threats), finance and insurance;
reservation systems, online auctions and search advertising;
complex systems such as brains, climate and CAT scans, where there are too many variables to model individually, so aggregate probabilistic models are needed.

Probability theory does three jobs:

Role	What it provides
language	a common vocabulary for sharing, decomposing and recombining knowledge about uncertainty
decision guidance	concrete rules for statistical decisions, estimation and inference
complexity management	approximations and bounds that make large systems tractable

IntuitionThe central question

What exactly is a probability model — which objects must exist, and which few rules must they obey — so that every intuitive fact about chance (complements, unions, “equally likely”, infinite sequences of trials) follows as a theorem rather than an assumption?

What does “probability” mean?

View	Probability of $E$ is…	Problem
relative frequency	$\displaystyle\lim_{n\to\infty}\frac{n(E)}{n}$ over repeated trials	assumes the limit exists and is the same for every run: a complicated hidden axiom
axiomatic (adopted here)	any number assigned by a set function obeying a few simple axioms	only says what probabilities must satisfy; the frequency limit becomes a theorem (strong law of large numbers)
subjective	a coherent degree of belief (“90% sure Shakespeare wrote Hamlet”)	real people’s beliefs can violate the axioms

ImportantWhy the axiomatic approach

Ross’s argument: rather than assume that relative frequencies converge, assume a few self-evident rules, and then prove that frequencies converge with probability 1. The mathematics is the same under every interpretation. Only the reading differs.

ExampleMaking a forecaster honest (Hajek)

A forecaster who announces “probability $p$ of rain” is paid $p$ up front. If it does not rain, she must pay back $-\ln(1-p)$ . If her true belief is $q$ , her expected payoff is $p + (1-q)\ln(1-p).$ This is maximized at $p = q$ , so reporting her true belief is optimal, and “30%” acquires an operational meaning.

DerivationWhy

p = q

maximizes the payoff

$\frac{d}{dp}\big[p + (1-q)\ln(1-p)\big] = 1 - \frac{1-q}{1-p}$ . This is zero iff $p = q$ . The second derivative is $-\frac{1-q}{(1-p)^2} < 0$ , so $p = q$ is the maximum.

RemarkProper scoring rules

This is a proper scoring rule, a close relative of the log rule behind market scoring rules and peer prediction (prediction-markets).

Sample spaces, events and set algebra

DefinitionSample space, outcome, event

The sample space $\Omega$ (Ross writes $S$ ) is the set of all possible outcomes of an experiment.
An outcome $\omega\in\Omega$ is what the experiment produces.
An event is a subset $A\subseteq\Omega$ . It occurs if the outcome lies in $A$ .

Running example: one fair die, $\Omega = \{1,\dots,6\}$ .

Event	Description	Set
$B$	shows 2 or less	$\{1,2\}$
$E$	even	$\{2,4,6\}$
$O$	odd	$\{1,3,5\}$
$BE$	2 or less and even	$\{2\}$
$B\cup E$	2 or less or even	$\{1,2,4,6\}$
$EO$	even and odd	$\emptyset$
$E\cup O$	even or odd	$\Omega$
$B^c$	not 2 or less	$\{3,4,5,6\}$

ConventionNotation

$AB = A\cap B$ (intersection, “and”). $A\cup B$ is union (“or”). $A^c$ is the complement (“not”). $\emptyset$ is the null event. $A\subset B$ means $A$ implies $B$ .

DefinitionMutually exclusive events and partitions

Events $E_1,\dots,E_n$ are mutually exclusive if at most one can occur, i.e. $E_iE_j = \emptyset$ for $i\ne j$ . They form a partition of $\Omega$ if they are mutually exclusive and $\bigcup_iE_i = \Omega$ . For example, $A$ and $A^c$ always partition $\Omega$ .

FormulaAlgebra of events

Law	Statement
commutative	$E\cup F = F\cup E$ , $\quad EF = FE$
associative	$(E\cup F)\cup G = E\cup(F\cup G)$ , $\quad (EF)G = E(FG)$
distributive	$(E\cup F)G = EG\cup FG$ , $\quad EF\cup G = (E\cup G)(F\cup G)$
De Morgan	$\Big(\bigcup_{i=1}^nE_i\Big)^c = \bigcap_{i=1}^nE_i^c$ , $\quad \Big(\bigcap_{i=1}^nE_i\Big)^c = \bigcup_{i=1}^nE_i^c$

IntuitionKarnaugh map for two events

The four cells $AB$ , $AB^c$ , $A^cB$ , $A^cB^c$ partition $\Omega$ :

	$B$	$B^c$
$A$	$AB$	$AB^c$
$A^c$	$A^cB$	$A^cB^c$

$A\cup B$ covers every cell except $A^cB^c$ . That is De Morgan’s first law, $(A\cup B)^c = A^cB^c$ , read straight off the map.

ProofDe Morgan’s laws for

n

events (Ross)

Step 1: First law, ⊆. If $x\in(\bigcup_iE_i)^c$ , then $x$ is in no $E_i$ , so $x\in E_i^c$ for every $i$ , i.e. $x\in\bigcap_iE_i^c$ .

Step 2: First law, ⊇. If $x\in\bigcap_iE_i^c$ , then $x$ is in no $E_i$ , so $x\notin\bigcup_iE_i$ .

Step 3: Second law from the first. Apply the first law to the complements $E_i^c$ and use $(E^c)^c = E$ : $(\bigcup_iE_i^c)^c = \bigcap_iE_i$ . Take complements of both sides.

∎

NoteSet identities are theorems, not axioms

De Morgan’s laws hold for any sets; nothing needs to be assumed. The axioms below are different: they are requirements on a probability model.

The axioms of probability

The problem. We want to assign a number $P(A)$ to events, and we need rules strong enough to derive everything else, but no stronger than intuition supports.

DefinitionProbability space

A probability space is a triple $(\Omega,\mathcal F,P)$ (“Omega, script F, P”):

$\Omega$ : a nonempty sample space;
$\mathcal F$ : the collection of events, a set of subsets of $\Omega$ ;
$P$ : a probability measure assigning $P(A)$ to each $A\in\mathcal F$ .

Component	Detail
Signature	$P : \mathcal F\to[0,1]$
Domain	events, i.e. sets of outcomes, not individual outcomes
Codomain	a number in $[0,1]$
Not an input	the outcome itself; $P$ scores whole sets

Event axioms

DefinitionAxioms E.1–E.3 (Hajek)

E.1 $\Omega\in\mathcal F$ .
E.2 If $A\in\mathcal F$ , then $A^c\in\mathcal F$ .
E.3 If $A_1, A_2, \dots\in\mathcal F$ (a finite or countably infinite list), then $A_1\cup A_2\cup\cdots\in\mathcal F$ .

NoteTerminology

A collection satisfying E.1–E.3 is usually called a σ-algebra (or σ-field). Neither source uses the term.

IntuitionWhy these three

Starting from the events we care about, “not,” “or” and “and” must keep us inside the collection. Otherwise we couldn’t even ask for the probability of a complement or a union. Countable unions are needed for infinite experiments, e.g. “the first head occurs on an odd flip.”

PropositionDerived event properties

e.4 $\emptyset\in\mathcal F$ , since $\emptyset = \Omega^c$ (E.1 + E.2).
e.5 $A, B\in\mathcal F\Rightarrow AB\in\mathcal F$ , since $AB = (A^c\cup B^c)^c$ (De Morgan + E.2 + E.3 + E.2).
e.6 Countable intersections are events: $B_1B_2\cdots = (B_1^c\cup B_2^c\cup\cdots)^c$ .

WarningWhy not let every subset be an event?

For finite or countably infinite $\Omega$ , take $\mathcal F$ = all subsets. There is no problem.
For uncountable $\Omega$ (e.g. $[0,1]$ ), it can be mathematically impossible to define $P$ on all subsets consistently with the probability axioms. So $\mathcal F$ is restricted to a rich collection containing every set met in practice. Ross calls these the measurable sets. See measure-theory for why, and for how $\mathcal F$ and $P$ are actually constructed on $[0,1]$ .

RemarkWhich properties are axioms is a choice

One could make e.4 an axiom in place of E.1.

Probability axioms

DefinitionAxioms P.1–P.3

P.1 (nonnegativity) $P(A)\ge0$ for every event $A$ .
P.2 (countable additivity) If $E_1, E_2, \dots$ are mutually exclusive, then $P(E_1\cup E_2\cup\cdots) = P(E_1) + P(E_2) + \cdots.$ The finite version is $P(A\cup B) = P(A) + P(B)$ for disjoint $A, B$ .
P.3 (normalization) $P(\Omega) = 1$ .

NoteRoss’s version

Ross states Axiom 1 as $0\le P(E)\le1$ . The upper bound is not needed as an axiom: it follows from P.1–P.3 (property p.5 below).

ImportantWhy countable, not just finite, additivity

For finite $\Omega$ , finite additivity is enough. Infinite sample spaces need the countable version to compute probabilities like “the first head comes on an odd flip” (Repeated coin flips), and to get continuity of probability (Continuity of probability).

ExampleTwo coins and a die

Fair coin: $\Omega = \{H,T\}$ , $\mathcal F = \{\emptyset,\{H\},\{T\},\Omega\}$ , with $P\{H\} = P\{T\} = \frac12$ .
Biased coin: $P\{H\} = \frac23$ , $P\{T\} = \frac13$ . The axioms don’t force symmetry.
Fair die: $P\{i\} = \frac16$ , so $P(\text{even}) = P\{2\} + P\{4\} + P\{6\} = \frac12$ by additivity.

ExampleTraffic light (Hajek) — equally likely is a modeling choice

$\Omega = \{\text{green},\text{yellow},\text{red}\}$ . Declaring each $\frac13$ is naive. The signal cycles through 30 s green, 5 s yellow, 40 s red (75 s total). If arrival time is unrelated to the cycle, probabilities should be proportional to dwell times:

P\{\text{green}\} = \tfrac25,\qquad P\{\text{yellow}\} = \tfrac1{15}, \qquad P\{\text{red}\} = \tfrac8{15}.

Consequences of the axioms

PropositionDerived properties p.4–p.9

Property	Statement
p.4 complement	$P(A^c) = 1 - P(A)$
p.5 upper bound	$P(A)\le1$
p.6 null event	$P(\emptyset) = 0$
p.7 monotonicity	$A\subset B\Rightarrow P(A)\le P(B)$
p.8 union of two	$P(A\cup B) = P(A) + P(B) - P(AB)$
p.9 union of three	$P(A\cup B\cup C) = P(A)+P(B)+P(C) - P(AB)-P(AC)-P(BC) + P(ABC)$

Proofp.4–p.8 from the axioms

p.4: $A$ and $A^c$ are disjoint with union $\Omega$ , so $P(A) + P(A^c) = P(\Omega) = 1$ (P.2, P.3).

p.5: $P(A) = 1 - P(A^c)\le1$ , since $P(A^c)\ge0$ (P.1).

p.6: $P(\emptyset) = 1 - P(\Omega) = 0$ (p.4, P.3).

Ross’s alternative: take $E_1 = \Omega$ and $E_i = \emptyset$ for $i > 1$ . These are disjoint, so P.2 gives $P(\Omega) = P(\Omega) + \sum_{i\ge2}P(\emptyset)$ , which forces $P(\emptyset) = 0$ .

p.7: Write $B = A\cup(A^cB)$ as a disjoint union. Then $P(B) = P(A) + P(A^cB)\ge P(A)$ .

p.8: $A\cup B = AB^c\cup A^cB\cup AB$ (Karnaugh cells), all disjoint:

P(A\cup B) = \big[P(AB^c) + P(AB)\big] + \big[P(A^cB) + P(AB)\big] - P(AB) = P(A) + P(B) - P(AB).

The key step: every proof decomposes the event into disjoint pieces and applies additivity. This is the only tool the axioms provide.

∎

graph TD
  AX["Axioms P.1 nonnegative, P.2 additive, P.3 total one"] --> C["p.4 complement rule"]
  C --> U["p.5 at most one"]
  C --> N["p.6 null event has probability zero"]
  AX --> M["p.7 monotonicity"]
  AX --> UN["p.8 union of two events"]
  UN --> IE["inclusion-exclusion for n events"]
  IE --> BO["Bonferroni bounds and Boole's inequality"]

ExampleTwo books (Ross)

J likes book 1 with probability .5, book 2 with probability .4, and both with probability .3. Then $P(\text{at least one}) = .5 + .4 - .3 = .6$ , so $P(\text{neither}) = 1 - .6 = .4$ (De Morgan + complement).

Inclusion–exclusion

TheoremInclusion–exclusion identity (Ross, Prop 4.4)

P\Big(\bigcup_{i=1}^nE_i\Big) = \sum_{r=1}^n(-1)^{r+1} \sum_{i_1<\cdots<i_r}P(E_{i_1}\cdots E_{i_r}).

The inner sum runs over all $\binom nr$ subsets of size $r$ .

IntuitionCorrecting overcounts

Add single events, subtract pairs (counted twice), add back triples (subtracted once too often), and so on. The signs alternate because each correction overshoots.

ProofEach outcome is counted exactly once

Step 1: Outcomes in no $E_i$ contribute 0 to both sides.

Step 2: An outcome in exactly $m > 0$ of the events counts once on the left. On the right it appears in $\binom mk$ of the $k$ -fold intersections, contributing $\binom m1 - \binom m2 + \binom m3 - \cdots\pm\binom mm.$

The key step: by the binomial theorem, $0 = (-1+1)^m = \sum_{i=0}^m\binom mi(-1)^i$ . So the alternating sum from $i = 1$ equals $\binom m0 = 1$ . Every outcome is counted exactly once. (Induction on $n$ also works.)

∎

TheoremBonferroni bounds

Truncating inclusion–exclusion alternately over- and under-estimates: $P\Big(\bigcup_iE_i\Big)\le\sum_iP(E_i), \tag{4.1}$

P\Big(\bigcup_iE_i\Big)\ge\sum_iP(E_i) - \sum_{j<i}P(E_iE_j), \tag{4.2}

P\Big(\bigcup_iE_i\Big)\le\sum_iP(E_i) - \sum_{j<i}P(E_iE_j) + \sum_{k<j<i}P(E_iE_jE_k), \tag{4.3}

and so on. The first, (4.1), is Boole’s inequality (the union bound).

Proof“First occurrence” decomposition, then recursion

Step 1: Disjoint decomposition. $\bigcup_iE_i = E_1\cup E_1^cE_2\cup E_1^cE_2^cE_3\cup\cdots$ (the first event to occur). So

P\Big(\bigcup_iE_i\Big) = \sum_iP(E_1^c\cdots E_{i-1}^cE_i). \tag{4.4}

Step 2: Rewrite each term. $E_i$ splits into ” $E_i$ with none of $E_1..E_{i-1}$ ” and ” $E_i$ with at least one,” so $P(E_1^c\cdots E_{i-1}^cE_i) = P(E_i) - P\Big(\bigcup_{j<i}E_iE_j\Big).$ Substituting,

P\Big(\bigcup_iE_i\Big) = \sum_iP(E_i) - \sum_iP\Big(\bigcup_{j<i} E_iE_j\Big). \tag{4.5}

Step 3: Recurse. Nonnegativity of the subtracted term gives (4.1). Applying (4.1) to $P(\bigcup_{j<i}E_iE_j)$ gives (4.2), applying (4.2) to it gives (4.3), and so on.

∎

Counting: computing the size of sets

Why count. When outcomes are equally likely, $P(A) = |A|/|\Omega|$ , so probability becomes counting (Equally likely outcomes). Combinatorial analysis is the mathematics of counting.

TheoremBasic principle of counting

If stage 1 has $m$ possible outcomes and, for each of them, stage 2 has $n$ possible outcomes, there are $mn$ joint outcomes. Generalized: $r$ stages with $n_1, n_2, \dots, n_r$ options (each count holding whatever happened earlier) give $n_1n_2\cdots n_r$ outcomes.

ProofEnumerate as a grid

List the pairs $(i,j)$ as $m$ rows of $n$ entries each: $mn$ in total.

∎

WarningThe choices need not be independent, only the counts

The second stage’s options may depend on the first stage (no repeated letters, for instance). The principle still applies as long as the number of options doesn’t depend on which earlier choice was made.

ExampleDirect applications

Count	Answer
8-bit bytes	$2^8 = 256$
7-place plates, 3 letters then 4 digits	$26^3\cdot10^4 = 175{,}760{,}000$
…no repeats	$26\cdot25\cdot24\cdot10\cdot9\cdot8\cdot7 = 78{,}624{,}000$
functions $\{1..n\}\to\{0,1\}$	$2^n$
subcommittee, 1 of each of 3/4/5/2 class members	$3\cdot4\cdot5\cdot2 = 120$
mother and child of the year, 10 mothers × 3 children	$30$

Permutations

DefinitionPermutation

An ordering of $n$ distinct objects. There are $n! = n(n-1)\cdots2\cdot1$ of them, with the convention $0! = 1$ .

ExampleGrouped orderings

Batting orders for 9 players: $9! = 362{,}880$ .
Rankings of 6 men and 4 women, each ranked only among themselves: $6!\,4! = 17{,}280$ .
4 math, 3 chemistry, 2 history and 1 language book, with each subject kept together: $4!\cdot(4!\,3!\,2!\,1!) = 6912$ . There are $4!$ subject orders times the within-subject orders.

TheoremPermutations with repeated objects

The number of distinct orderings of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, …, $n_r$ are alike, is $\frac{n!}{n_1!\,n_2!\cdots n_r!}.$

DefinitionPrinciple of over-counting

If every element of a set is counted exactly $K$ times, the set’s size is (total count) $/K$ .

ExampleILLINI and PEPPER

ILLINI: label the letters so all 6 are distinct: $6! = 720$ orderings. Each unlabelled word arises from $3!$ labellings of the I’s times $2!$ of the L’s, which is 12. So $720/12 = 60$ .
PEPPER: $6!/(3!\,2!) = 60$ .
10 chess players by nationality (4 Russian, 3 US, 2 GB, 1 Brazil): $10!/(4!\,3!\,2!\,1!) = 12{,}600$ .
9 flags (4 white, 3 red, 2 blue): $9!/(4!\,3!\,2!) = 1260$ .

Combinations

DefinitionBinomial coefficient

For $0\le k\le n$ , the number of $k$ -element subsets of an $n$ -set is

\binom nk = \frac{n!}{k!\,(n-k)!} = \frac{\overbrace{n(n-1)\cdots (n-k+1)}^{k\text{ terms}}}{k!},

and $\binom nk = 0$ if $k < 0$ or $k > n$ .

DerivationOver-counting ordered selections

Choose $k$ objects in order: $n(n-1)\cdots(n-k+1)$ ways. Each set of $k$ appears $k!$ times (once per ordering). Divide by $k!$ .

ExampleLineups and binary strings (Hajek)

Lineups of 5 from 9 players: $\frac{9\cdot8\cdot7\cdot6\cdot5}{5!} = 126$ .
Binary strings of length 9 with exactly 5 ones: $\frac{9!}{5!\,4!} = 126$ .

They are equal because of a bijection: the positions of the 1s name the players chosen. 110110010 ↔ $\{A,B,D,E,H\}$ .

ExampleCommittees with a constraint (Ross)

2 of 5 women and 3 of 7 men: $\binom52\binom73 = 10\cdot35 = 350$ . If two men refuse to serve together, subtract the $\binom22\binom51 = 5$ male-triples containing both: $10\cdot(35-5) = 300$ .

FormulaUseful identities

\binom nk = \binom n{n-k},\qquad \binom nr = \binom{n-1}{r-1} + \binom{n-1}r\ \ (\text{Pascal}),\qquad \sum_{k=0}^n\binom nk = 2^n.

ProofPascal’s identity, combinatorially

Fix one object. The $r$ -subsets containing it number $\binom{n-1}{r-1}$ (choose the other $r-1$ from the rest). Those not containing it number $\binom{n-1}r$ . Together they are all $\binom nr$ subsets.

∎

TheoremBinomial theorem

$(x+y)^n = \sum_{k=0}^n\binom nkx^ky^{n-k}. \tag{4.2}$

ProofTwo proofs

Combinatorial. Expand $(x_1+y_1)\cdots(x_n+y_n)$ into $2^n$ terms, each choosing $x_i$ or $y_i$ from every factor. Terms with exactly $k$ $x$ ‘s correspond to $k$ -subsets of factors, so there are $\binom nk$ of them. Set $x_i = x$ , $y_i = y$ .

Induction. $n = 1$ is trivial. Assume it for $n - 1$ and multiply by $(x+y)$ :

(x+y)^n = \sum_{k}\binom{n-1}kx^{k+1}y^{n-1-k} + \sum_k\binom{n-1}k x^ky^{n-k}.

Reindex the first sum ( $i = k+1$ ) and collect the coefficient of $x^iy^{n-i}$ : $\binom{n-1}{i-1} + \binom{n-1}i = \binom ni$ by Pascal.

∎

ExampleNumber of subsets

$\sum_k\binom nk = (1+1)^n = 2^n$ . Equivalently, assign 0 or 1 to each element. There are $2^n - 1$ nonempty subsets.

ExampleAntennas with no two defectives adjacent (Ross)

$n$ antennas, $m$ defective, with identical items indistinguishable. Line up the $n-m$ working ones. That leaves $n - m + 1$ gaps (including both ends), and at most one defective goes in each gap: $\binom{n-m+1}m\text{ orderings}.$ Check: $n = 4$ , $m = 2$ gives $\binom32 = 3$ of the 6 configurations (0110, 0101, 1010 are functional).

NoteExercise identities

Ross’s exercises include $\binom n2 = \binom k2 + k(n-k) + \binom{n-k}2$ (split pairs by which side each element is on) and $\sum_{x_1+\dots+x_r=n}\frac{n!}{x_1!\cdots x_r!} = r^n$ (count length- $n$ words over an $r$ -letter alphabet). Both are left as exercises.

Multinomial coefficients

DefinitionMultinomial coefficient

For $n_1 + \cdots + n_r = n$ , $\binom n{n_1,n_2,\dots,n_r} = \frac{n!}{n_1!\,n_2!\cdots n_r!}$ is the number of ways to split $n$ distinct items into $r$ distinct (labelled) groups of sizes $n_1,\dots,n_r$ .

DerivationTwo derivations

Sequential choice. $\binom n{n_1}\binom{n-n_1}{n_2}\cdots$ telescopes to $\frac{n!}{n_1!\cdots n_r!}$ .

Permutation bijection. A division corresponds to a word containing $n_1$ copies of “1”, …, $n_r$ copies of " $r$ ". Item $j$ goes to group $i_j$ . Counting these words is the repeated-objects formula.

WarningLabelled vs unlabelled groups

10 officers into 5 patrol / 2 station / 3 reserve: $\frac{10!}{5!\,2!\,3!} = 2520$ .
10 children into team A and team B of 5: $\frac{10!}{5!\,5!} = 252$ .
10 children into two teams of 5 with no labels: $252/2! = 126$ .

When the groups are interchangeable, divide by the number of ways to permute equal-sized groups.

TheoremMultinomial theorem

(x_1 + \cdots + x_r)^n = \sum_{n_1+\cdots+n_r = n}\binom n{n_1,\dots, n_r}x_1^{n_1}\cdots x_r^{n_r},

summing over nonnegative integer vectors. The proof is left as an exercise.

ExampleKnockout tournament with

2^m

players has

n!

outcomes (Ross)

Round 1 with 8 players: pairings into ordered pairs number $\binom8{2,2,2,2} = 8!/2^4$ , and unordered $8!/(2^4\,4!)$ . Times $2^4$ winners gives $8!/4!$ round-1 results. Similarly round 2 has $4!/2!$ and round 3 has $2!/1!$ . The product is $8!$ .

Bijection: rank the winner 1 and the final loser 2. Each loser of a round with $2^k$ matches gets rank $2^k$ plus the rank of the player who beat them. Every tournament result corresponds to exactly one permutation of the players.

Integer solutions of equations (stars and bars)

TheoremRoss, Prop 1.6.1 — positive solutions

The number of positive integer vectors $(x_1,\dots,x_r)$ with $x_1 + \cdots + x_r = n$ is $\binom{n-1}{r-1}.$

ProofChoose dividers among the gaps

Line up $n$ zeros. There are $n-1$ gaps between adjacent zeros. Choosing $r-1$ of them as dividers splits the zeros into $r$ nonempty blocks, whose sizes are the $x_i$ . This is a one-to-one correspondence. For example, $n = 8$ , $r = 3$ : $0|0000|000\leftrightarrow(1,4,3)$ .

∎

TheoremRoss, Prop 1.6.2 — nonnegative solutions

The number of nonnegative integer vectors with $x_1 + \cdots + x_r = n$ is $\binom{n+r-1}{r-1}.$

ProofShift by one

Set $y_i = x_i + 1 > 0$ . Then $\sum y_i = n + r$ , so by Prop 1.6.1 the count is $\binom{n+r-1}{r-1}$ .

∎

ExampleApplications

Problem	Count
$x_1 + x_2 = 3$ , $x_i\ge0$	$\binom41 = 4$
10 fish of 4 types caught	$\binom{13}3 = 286$
$20k in $1k units over 4 investments, all invested	$\binom{23}3 = 1771$
…not all invested (add a reserve variable)	$\binom{24}4 = 10{,}626$
terms in $(x_1 + \cdots + x_r)^n$	$\binom{n+r-1}{r-1}$

ExampleAntennas revisited, with a stronger gap

Let $x_1$ be the number of working items before the first defective, $x_2,\dots,x_m$ the numbers between defectives, and $x_{m+1}$ the number after the last.

At least one working item between defectives: $x_1, x_{m+1}\ge0$ and $x_i\ge1$ . Shifting gives $\binom{n-m+1}m$ , agreeing with the gap argument.
At least two between defectives: shift $y_1 = x_1 + 1$ , $y_i = x_i - 1$ , $y_{m+1} = x_{m+1} + 1$ , giving $\sum y_i = n - 2m + 3$ with positive terms, i.e. $\binom{n-2m+2}m$ .

What you’re counting	Formula
ordered, with repetition ( $r$ slots, $n$ choices)	$n^r$
ordered, no repetition	$n(n-1)\cdots(n-r+1) = n!/(n-r)!$
unordered, no repetition	$\binom nr$
arrangements with repeated objects	$n!/(n_1!\cdots n_r!)$
unordered, with repetition (multisets)	$\binom{n+r-1}{r-1}$

Equally likely outcomes

FormulaClassical probability

If $\Omega$ is finite and all outcomes are equally likely, then $P\{\omega\} = 1/|\Omega|$ (from P.2, P.3), and for any event $A$ , $P(A) = \frac{|A|}{|\Omega|}.$ Here $|A|$ is the cardinality of $A$ .

Warning“Equally likely” is a modeling assumption

It comes from symmetry (a fair die, a well-shuffled deck), not from the axioms. The traffic light shows it can be wrong.

ImportantOrdered or unordered: pick one and be consistent

When drawing $k$ of $n$ items, the outcome can be the ordered sequence or the unordered set. If all ordered outcomes are equally likely, so are all unordered ones, because each set corresponds to exactly $k!$ sequences. Both give the same answer, provided numerator and denominator use the same view.

Example3 balls from 6 white + 5 black: P(1 white, 2 black) (Ross)

Ordered: $|\Omega| = 11\cdot10\cdot9 = 990$ . The white ball can be in position 1, 2 or 3, giving $6\cdot5\cdot4 + 5\cdot6\cdot4 + 5\cdot4\cdot6 = 360$ . $P = 360/990 = 4/11$ .
Unordered: $\binom61\binom52/\binom{11}3 = 60/165 = 4/11$ .

ExampleSocks and dice (Hajek)

Two socks from 6 orange + 3 blue: $P(\text{same color}) = \frac{\binom62 + \binom32}{\binom92} = \frac{15+3}{36} = \frac12$ . With three socks, two must match: probability 1 (pigeonhole).
Two dice, with $A$ = even sum, $B$ = sum divisible by 3, $C$ = doubles: $ABC = \{33, 66\}$ , so $P(ABC) = 2/36 = 1/18$ . A three-event Karnaugh map organizes all 36 outcomes, and checking each row and column verifies it.

Cards

ExamplePoker hands (5 of 52, $\binom{52}5 = 2{,}598{,}960$ )

Full house (three of one rank, two of another): choose the triple rank (13) and the pair rank (12), then suits $\binom43\binom42$ :

P = \frac{13\cdot12\cdot4\cdot6}{\binom{52}5} = \frac{6}{4165}\approx 0.0014.

Straight (five consecutive ranks, ace high or low, so 10 rank sets):

\text{Hajek: } \frac{10\cdot4^5}{\binom{52}5}\approx0.0039,\qquad \text{Ross: } \frac{10(4^5 - 4)}{\binom{52}5}\approx0.0039.

Ross excludes the 4 same-suit straight flushes per rank set; Hajek includes them.

ExampleBridge (Ross)

One player gets all 13 spades: $4/\binom{52}{13}\approx6.3\times10^{-12}$ (four mutually exclusive events).
Each player gets exactly one ace: $\frac{4!\binom{48}{12,12,12,12}}{\binom{52}{13,13,13,13}}\approx0.1055.$

ExampleThe card after the first ace (Ross)

Is the card following the first ace more likely to be the ace of spades or the two of clubs? Equally likely: $1/52$ each.

Argument: order the other 51 cards ( $51!$ ways). There is exactly one place to insert the ace of spades immediately after the first ace. So the probability is $51!/52! = 1/52$ , and the same argument works for any card.

WarningWhy intuition misleads here

“The ace of spades might itself be the first ace” (chance 1/4) seems to favour the two of clubs. But the two of clubs might come before the first ace (chance 1/5), which rules it out. The effects exactly cancel.

Surprising classics

ExampleBirthday problem (Ross)

P(\text{no shared birthday among }n) = \frac{365\cdot364\cdots(365 - n + 1)}{365^n}.

This drops below $\frac12$ at $n = 23$ . At $n = 50$ a match has probability about $0.970$ . At $n = 100$ the odds exceed 3,000,000 : 1.

IntuitionWhy 23 is not surprising

Each pair matches with probability only $1/365$ , but 23 people form $\binom{23}2 = 253$ pairs.

ExampleCommittee and the special ball (Ross)

5 from 6 men + 9 women, exactly 3 men: $\binom63\binom92/\binom{15}5 = 240/1001$ .
$k$ of $n$ balls drawn, one of them special: $P(\text{special chosen}) = \binom11\binom{n-1}{k-1}/\binom nk = k/n$ . Equivalently, the events “special ball is the $i$ -th drawn” are disjoint, each with probability $1/n$ .

ExampleColor sequences remain equally likely (Ross)

$n$ red and $m$ blue balls in random order. Each color pattern arises from $n!\,m!$ of the $(n+m)!$ orderings, so every color pattern has probability $\frac{n!\,m!}{(n+m)!}$ . For example, 2 red and 2 blue: each of the 6 patterns has probability $4/24 = 1/6$ .

ExampleCounting via probability: club sports (Ross)

36 tennis, 28 squash, 18 badminton; 22 T&S, 12 T&B, 9 S&B; 4 all three. Pick a member at random and apply inclusion–exclusion: $N\cdot P(T\cup S\cup B) = 36 + 28 + 18 - 22 - 12 - 9 + 4 = 43.$

ExampleThe matching (hat-check) problem (Ross)

$N$ men draw hats at random. Let $E_i$ = man $i$ gets his own hat. Any $n$ specified men all matching has probability $(N-n)!/N!$ , and there are $\binom Nn$ such sets, so each inclusion–exclusion term is $1/n!$ :

P(\text{no match}) = \sum_{i=0}^N\frac{(-1)^i}{i!}\;\longrightarrow\; e^{-1}\approx0.3679.

WarningIt doesn’t go to 1

One might guess “no match” becomes likely as $N$ grows (more hats, less chance of getting yours) or impossible (more men, more chances for someone to match). Both effects balance, and the limit is about 0.37 regardless of $N$ .

ExampleCouples at a round table (Ross)

10 couples seated at random around a round table ( $19!$ arrangements). For any specified $n$ couples each sitting together, glue each couple into a unit: $2^n(19-n)!$ arrangements. Inclusion–exclusion gives

P(\text{some couple adjacent}) = \sum_{n=1}^{10}(-1)^{n+1} \binom{10}n\frac{2^n(19-n)!}{19!}\approx0.6605,

so $P(\text{no wife next to her husband})\approx0.3395$ .

ExampleRuns of wins (Ross)

A season of $n$ wins and $m$ losses, all $\binom{n+m}n$ orders equally likely. Place the $r$ win-runs in the $m+1$ gaps around the losses ( $\binom{m+1}r$ ways) and split $n$ wins into $r$ positive runs ( $\binom{n-1}{r-1}$ ways):

P(r\text{ runs of wins}) = \frac{\binom{m+1}r\binom{n-1}{r-1}} {\binom{n+m}n}.

For $n = 8$ , $m = 6$ , both 7 runs (strict alternation) and 1 run have probability $1/429$ . Either would suggest the win probability changed over the season.

ExampleRoommates and five unrelated people (Ross)

Roommates: 20 offense + 20 defense players, paired at random. The number of unordered pairings of 40 is $\frac{40!}{2^{20}\,20!}$ . $P(\text{no mixed pairs}) = \frac{[20!/(2^{10}10!)]^2}{40!/(2^{20}20!)} \approx1.34\times10^{-6}$ . $P(20\text{ mixed pairs})$ is about 0.346. The values come from Stirling’s approximation $n!\approx n^{n+1/2}e^{-n}\sqrt{2\pi}$ .

Five people from 10 married couples, no couple chosen: unordered, $\binom{10}5\,2^5/\binom{20}5$ . Ordered, $\frac{20\cdot18\cdot16\cdot14\cdot12}{20\cdot19\cdot18\cdot17\cdot16}$ . They are equal (exercise).

Sample spaces with infinite cardinality

Countable vs uncountable

DefinitionCountably infinite

A set is countably infinite if its elements can be arranged in an infinite list indexed by the positive integers. Examples: $\mathbb Z_+$ , $\mathbb Z = \{0,1,-1,2,-2,\dots\}$ , and the positive rationals, listed by a zig-zag through the array of $i/j$ .

TheoremProposition 1.5.1 — the reals are uncountable

Even $[0,1]$ cannot be listed.

ProofCantor’s diagonal argument

Step 1: Take any list $a_1, a_2, \dots$ of numbers in $[0,1]$ and write their decimal expansions.

Step 2: Build $a^*$ whose $k$ -th digit is the $k$ -th digit of $a_k$ plus 2 (mod 10).

Step 3: $a^*$ is missing from the list. For every $k$ , $a^*$ differs from $a_k$ in digit $k$ by at least 2.

The key step: differing by at least 2 (not just 1) rules out the case where $a^*$ and $a_k$ are two representations of the same number, like $0.1999\ldots = 0.2000\ldots$ .

∎

IntuitionEngineering reading

Countable means every element has a finite bit-string name (a variable-length code: the binary index in the list). The reals admit no such naming.

Countably infinite sample spaces

ExampleChoosing a positive integer (Hajek)

$\Omega = \{1,2,\dots\}$ , $\mathcal F$ = all subsets, and

p_i = \frac1i - \frac1{i+1} = \frac1{i(i+1)},\qquad \sum_{k\le i}p_k = 1 - \frac1{i+1}\to1.

Countable additivity forces $P(A) = \sum_{i\in A}p_i$ for every event $A$ :

$P\{1,4,5\} = \frac12 + \frac1{20} + \frac1{30}\approx0.5833$ ;
$P(\text{multiple of }5) = \sum_{k\ge1}\frac1{5k(5k+1)}\approx0.05763$ .

FormulaGeometric series

\sum_{k=0}^nx^k = \frac{1 - x^{n+1}}{1 - x}\ \ (x\ne1),\qquad \sum_{k=0}^\infty x^k = \frac1{1-x}\ \ (|x| < 1). \tag{1.4–1.5}

From $(1-x)(1 + x + \cdots + x^n) = 1 - x^{n+1}$ : the middle terms cancel.

Repeated coin flips

ExampleWho flips the first head? (Hajek)

Outcomes are infinite 0/1 sequences. Any event fixing the first $k$ flips has probability $2^{-k}$ . Two players alternate, and the first head wins. Let $E_k$ = first head on flip $k$ , so $P(E_k) = 2^{-k}$ . The first player wins on $F = E_1\cup E_3\cup E_5\cup\cdots$ , which is an event by E.3. The union is disjoint, so

P(F) = \frac12\Big(1 + \frac14 + \frac1{4^2} + \cdots\Big) = \frac{1/2} {1 - 1/4} = \frac23.

The first player is twice as likely to win.

ImportantEvents that no finite horizon determines

“First player wins” isn’t determined by any fixed finite number of flips. Only countable unions (E.3) and countable additivity (P.2) reach it.

Continuous sample spaces

DefinitionStandard unit-interval probability space (Hajek)

$\Omega = [0,1]$ , with “no preference” among intervals of equal length: $P([a,b]) = b - a. \tag{1.3}$ So singletons are events with $P\{a\} = 0$ , and open intervals have $P((a,b)) = b - a$ . $\mathcal F$ must contain all open sets (countable unions of intervals), all closed sets (their complements), countable intersections of open sets, and so on.

CautionEvery point has probability 0, but the total is 1

$[0,1] = \bigcup_x\{x\}$ is a disjoint union of zero-probability events. Why doesn’t additivity give $P(\Omega) = 0$ ? Because P.2 covers only countable collections, and $[0,1]$ is uncountable. Countable additivity is exactly strong enough, and no stronger.

ExampleA triangle in the unit square (Hajek)

On $[0,1)^2$ with $P(\text{rectangle}) = \text{area}$ , is $T = \{x,y\ge0,\ x+y<1\}$ an event, and what is $P(T)$ ?

Tile $T$ with disjoint squares: 1 of area $\frac14$ , 2 of area $\frac1{16}$ , 4 of area $\frac1{64}$ , and so on. Countably many, so $T$ is an event (E.3), and by P.2

P(T) = \frac14\Big(1 + \frac12 + \frac14 + \cdots\Big) = \frac14\cdot2 = \frac12.

This matches the area, as it should.

Continuity of probability

DefinitionMonotone sequences and their limits

Increasing: $E_1\subset E_2\subset\cdots$ , with $\lim_nE_n = \bigcup_iE_i$ .
Decreasing: $E_1\supset E_2\supset\cdots$ , with $\lim_nE_n = \bigcap_iE_i$ .

TheoremContinuity of probability (Ross, Prop 2.6.1)

For any increasing or decreasing sequence of events, $\lim_{n\to\infty}P(E_n) = P\Big(\lim_{n\to\infty}E_n\Big).$

ProofDisjoint “new parts” for increasing sequences; complements for decreasing

Step 1: Increasing case, peel off new parts. Let $F_1 = E_1$ and $F_n = E_nE_{n-1}^c$ : the outcomes new at stage $n$ . The $F_n$ are disjoint, with $\bigcup_{i\le n}F_i = E_n$ and $\bigcup_iF_i = \bigcup_iE_i$ .

Step 2: Apply countable additivity.

P\Big(\bigcup_iE_i\Big) = \sum_{i=1}^\infty P(F_i) = \lim_n\sum_{i=1}^n P(F_i) = \lim_nP(E_n).

Step 3: Decreasing case. $E_n^c$ is increasing, and $\bigcup_iE_i^c = (\bigcap_iE_i)^c$ (De Morgan). So $1 - P(\bigcap_iE_i) = \lim_n(1 - P(E_n))$ .

The key step: continuity is equivalent to countable additivity, repackaged: a countable sum is a limit of partial sums.

∎

ExampleThe Ross–Littlewood urn “paradox”

At $1, \frac12, \frac14, \dots$ minutes before noon, add the next 10 numbered balls to the urn and withdraw one.

Rule for the withdrawal	Urn at noon
withdraw ball $10n$ at step $n$	infinitely many balls (any ball not a multiple of 10 stays)
withdraw ball $n$ at step $n$	empty (ball $n$ leaves at step $n$ )
withdraw a uniformly random ball	empty with probability 1

After every finite step, both deterministic versions hold the same number of balls ( $9n$ ). The limits still differ. There is no contradiction, only intuition about infinity failing.

ProofRandom withdrawals empty the urn almost surely

Step 1: Ball 1 survives the first $n$ withdrawals with probability $P(E_n) = \frac{9\cdot18\cdots(9n)}{10\cdot19\cdots(9n+1)}.$ At draw $k$ there are $9k+1$ balls, and $9k$ of them are not ball 1.

Step 2: Continuity. The $E_n$ are decreasing, so $P(\text{ball 1 at noon}) = \prod_{n\ge1}\frac{9n}{9n+1}$ .

Step 3: The product is 0. Its reciprocal $\prod_n\big(1 + \frac1{9n}\big)\ge1 + \sum_{n\le m}\frac1{9n}$ for every $m$ (expand the product and keep only the linear terms). The harmonic series diverges, so the product diverges and $P(F_1) = 0$ . The same argument gives $P(F_i) = 0$ for every ball $i$ (starting from the step at which it enters).

Step 4: Boole’s inequality. $P(\text{urn nonempty}) = P(\bigcup_iF_i)\le\sum_iP(F_i) = 0$ .

∎

Probability as degree of belief

DefinitionSubjective (personal) probability

$P(E)$ is an individual’s degree of belief in $E$ . It should still obey the axioms. If you are 70% sure Shakespeare wrote Julius Caesar and 10% sure Marlowe did, you should be 80% sure it was one of them.

ExampleChoosing a bet (Ross)

In a 7-horse race you believe horses 1–2 each win with probability .20, horses 3–4 with .15 each, and horses 5–7 with .10 each. Compare the even-money bets “one of horses 1, 2, 3” ( $= .55$ ) and “one of 1, 5, 6, 7” ( $= .50$ ). The first is better.

WarningReal beliefs can be incoherent

Answers of 30% (rain today), 40% (tomorrow), 20% (both) and 60% (either) are inconsistent. The union rule forces $.3 + .4 - .2 = .5\ne.6$ . A coherent revision is 30%, 40%, 10%, 60%. The axioms describe an idealized reasoner.

Quick reference

Object	Statement	Note
Probability space	$(\Omega,\mathcal F,P)$	outcomes, events, measure
E.1–E.3	$\Omega\in\mathcal F$ ; closed under complement and countable union	a σ-algebra
e.4–e.6	$\emptyset$ , finite and countable intersections are events	via De Morgan
P.1–P.3	$P\ge0$ ; countably additive; $P(\Omega) = 1$
p.4	$P(A^c) = 1 - P(A)$
p.5–p.6	$P(A)\le1$ ; $P(\emptyset) = 0$
p.7	$A\subset B\Rightarrow P(A)\le P(B)$
p.8	$P(A\cup B) = P(A) + P(B) - P(AB)$	Karnaugh cells
Inclusion–exclusion	$P(\bigcup E_i) = \sum_r(-1)^{r+1}\sum P(E_{i_1}\cdots E_{i_r})$	proof via $(1-1)^m = 0$
Bonferroni	truncations alternately bound above and below	Boole: $P(\bigcup E_i)\le\sum P(E_i)$
Counting principle	$n_1n_2\cdots n_r$	counts, not choices, must be fixed
Permutations	$n!$ ; with repeats $n!/(n_1!\cdots n_r!)$	ILLINI = 60
Combinations	$\binom nk = n!/(k!(n-k)!)$	lineups ↔ binary strings
Pascal	$\binom nr = \binom{n-1}{r-1} + \binom{n-1}r$	contains object 1 or not
Binomial theorem	$(x+y)^n = \sum\binom nkx^ky^{n-k}$	$2^n$ subsets
Multinomial	$\binom n{n_1..n_r}$ = labelled divisions	unlabelled: divide by $k!$
Stars and bars	positive $\binom{n-1}{r-1}$ , nonnegative $\binom{n+r-1}{r-1}$
Equally likely	$P(A) = \lvert A\rvert/\lvert\Omega\rvert$	ordered or unordered, consistently
Full house / straight	$6/4165\approx.0014$ ; $\approx.0039$	straight flushes in or out
Birthday	$< \frac12$ at $n = 23$	253 pairs
Card after first ace	$1/52$ for every card
Matching	$\sum_{i\le N}(-1)^i/i!\to e^{-1}$
Couples at a table	$P(\text{none adjacent})\approx.3395$	glue couples
Runs	$\binom{m+1}r\binom{n-1}{r-1}/\binom{n+m}n$
Diagonal argument	$[0,1]$ uncountable	shift digits by 2
Unit interval	$P([a,b]) = b - a$ ; points have probability 0	only countable additivity
First head wins	$2/3$ for the first player	geometric series
Continuity	monotone $E_n$ : $P(\lim E_n) = \lim P(E_n)$	equivalent to countable additivity
Random-withdrawal urn	empty w.p. 1	$\prod\frac{9n}{9n+1} = 0$ + Boole

Facts to keep to hand

Every derived property is “split into disjoint pieces, then add.” The complement rule, monotonicity, the union rule, inclusion–exclusion, the Bonferroni bounds and continuity all come from one move: rewrite the event as a disjoint union and apply P.2.
Countable additivity is the load-bearing axiom. It makes “first head on an odd flip” computable, gives continuity of probability, and is exactly weak enough to let uncountably many zero-probability points make up a set of probability 1.
Why events are restricted. On uncountable $\Omega$ , not every subset can be assigned a probability consistently, so $\mathcal F$ is a σ-algebra rich enough for practice, not the full power set.
Most counting is one of three moves. (1) Multiply stage counts. (2) Over-count and divide by the symmetry factor ( $k!$ , $n_1!\cdots n_r!$ , $2^n$ for couples, $r!$ for unlabelled groups). (3) Biject to something easier (lineups ↔ bit strings, solutions ↔ divider positions, tournaments ↔ permutations).
The alternating binomial sum is the engine of inclusion–exclusion. $\sum_i(-1)^i\binom mi = 0$ is why each outcome counts once, and why matching and couple-seating probabilities come out as clean alternating series.
“Equally likely” is a modeling assumption to check, not a default. Symmetric dice and cards justify it; the traffic light refutes it. Once assumed, ordered and unordered sample spaces agree when used consistently.
Infinity breaks intuition, not the axioms. Cantor’s diagonal argument, zero-probability points in $[0,1]$ , the urn emptying by noon, and matching staying at $1/e$ all feel paradoxical. Each follows directly from the definitions.

References

Hajek, Probability with Engineering Applications (ECE 313 notes) — chapter 1
Ross, A First Course in Probability — chapters 1–2

Related