Summary Probability theory

1. Combinatorics
So you think you can count?
The factorial
n! := (n)(n − 1)(n − 2) . . . (2)(1)

and can be used to describe how many ways there are to put n numbers in a sequence. Such an ordering is
called a permutation.
If we want to find how many ways there are to pick a sequence of k distinct numbers (without replacement)
chosen out of n distinct numbers, we use the falling factorial:

n!
(n)k :=
(n − k)!

If we just want a sequence of k not necessarily distinct (with replacement) numbers chosen from n numbers,
that is simply nk .
If we want to draw without replacement and without order (finding the number of subsets of size k), we
need the binomial coefficient. This is pronounced n choose k:
!
n n!
:=
k k!(n − k)!


Inclusion-exclusion (counting version)
If there are N people and r properties (p1 , . . . , pr ) of interest, the amount of people who possess none of the
properties are given by
r
X X X
N− N (pj ) + N (pj1 , pj2 ) − N (pj1 , pj2 , pj3 ) + · · · + (−1)r N (p1 , . . . , pr )
j=1 1≤j1 <j2 ≤r 1≤j1 <j2 <j3 ≤r


Dn , the number of derangements of n numbers:

n
!
X 1r n!
Dn = n! · (−1) ≈
r=0
r! e




1

,2. Basics of set theory
Set theory
A sample space is a set Ω. Any element ω ∈ Ω is called an outcome. Any subset A ⊆ Ω is called an event.
Theorem 2.1.1 For any A, B, C ⊆ Ω and ω ∈ Ω:

• if ω ∈ A and A ⊆ B, then • A ∩ B ⊆ A, B • A∪(B∩C) = (A∪B)∩(A∪C)
ω∈B
• A ∪ (B ∪ C) = (A ∪ B) ∪ C • (A ∪ B)c = Ac ∩ B c
• A∩B =B∩A

• A∪B =B∪A • A ∩ (B ∩ C) = (A ∩ B) ∩ C • (A ∩ B)c = Ac ∪ B c

• A, B ⊆ A ∪ B • A∩(B∪C) = (A∩B)∪(A∩C) • A\B = A ∩ B c


Definition 2.1.2A, B are disjoint if A ∩ B = ∅. A1 , A2 , . . . are pairwise disjoint if Ai ∩ Aj = ∅ for all i ̸= j


The axioms of probability
Definition 2.2.1 A probability space is a triple (Ω, A, P) where ω is a set as above,

Set of all subsets of Ω if Ω is countable
A=
A certain set of subsets of Ω if Ω is uncountable

And P is the probability function on S: that is a function P : A → [0, 1] satisfying the axioms of probability:

1. P(Ω) = 1
S  P
2. if A1 , A2 , . . . are pairwise disjoint, then P Ai = i=1 P(Ai ) (sigma additivity)
i≥1
P
Theorem 2.2.1 Suppose Ω = {ω1 , ω2 , . . . } an p1 , p2 , . . . are non-negative numbers with pi = 1. Defining,
P
for all A ⊆ Ω, P(A) = i:wi ∈A pi . The function P thus obtained is a probability.
Theorem 2.2.2 First properties of probabilities

• P(∅) = 0 • P(A) ≤ 1

• If  B1 , . . . , 
Bn are pairwise disjoint, then
S P • P(A ∪ B) = P(A) + P(B) − P(A ∩ B)
P i≤n i =B i≤n P(Bi )

• P(Ac ) = 1 − P(A) • If A ⊆ B, then P(A) ≤ P(B)


Theorem 2.2.3 Sigma sub-additivity
S  P
For any A1 , A2 , . . . , P i≥1 Ai ≤ i≥1 P(Ai )
Theorem 2.2.4 If (Ω, A, P) is a probability space, Ω is finite and the outcomes ω ∈ Ω all have the same
probability, then, for any A ∈ A,

#A number of elements of A
P(A) = =
#Ω number of elements of Ω

2

, 3.Bayes’ formula
Conditional probability and independence
Definition 3.2.1 Conditional probability. Let (Ω, A, P) be a probability space and A, B be events. Assume
P(B) > 0. Then, the probability of A given B is defined by

P(A ∩ B) P(A) · P(B|A)
P(A|B) = =
P(B) P(B)
S
Theorem 3.2.1 Assume B is an event with P(B) > 0. Assume A1 , . . . are pairwise disjoint and Ai = Ω.
Then:
X
P(B) = P(B|Ai ) · P(Ai ) (Law of total probability)
i≥1

P(B|Ai ) · P(Ai )
P(Ai |B) = P (Bayes’ formula)
j≥1 P(B|Aj ) · P(Aj )

Definition 3.2.2 Events A, B are independent if P(A ∩ B) = P(A) · P(B)
Common thinking mistake: A and B are disjoint is not the same as A and B are independent.
Definition 3.2.3 Events A1 , . . . , An are:

• Pairwise independent if P(Ai ∩ Aj ) = P(Ai ) · P(Aj ) for all i ̸= j

• Mutually independent if, for any subcollection Ai1 , . . . , Aik , it holds that

P(Ai1 ∩ · · · ∩ Aik ) = P(Ai1 ) · · · · · P(Aik )


• If A1 , . . . , An are mutually independent, then they are also pairwise independent. The converse does
not necessarily hold.




3