Probability & Statistics — Complete Review Notes

Lecture-style revision document | probability, distributions, estimation, testing and regression

Chapter 1 — Foundations
Discrete mathematics studies mathematical objects that are separate or countable rather than
continuously varying. Important objects include sets, propositions, relations, functions, samples, trees,
and integers.

A proposition is a declarative statement that is either true or false. Logical connectives include negation,
conjunction, disjunction, implication, and biconditional. Truth tables provide a systematic way to evaluate
compound propositions.

An implication p → q is false only when p is true and q is false. The contrapositive, ¬q → ¬p, is logically
equivalent to p → q.

Worked examples and review points

Example: If p means 'n is even' and q means 'n² is even', then p → q is true for every integer n. A proof
can be built directly from the definition of an even integer.

Review: distinguish implication from its converse. The converse q → p does not automatically follow from
p → q.
Chapter 2 — Sets
A set is a collection of distinct objects. The notation x ∈ A means x belongs to A. A subset relation A ⊆ B
means every element of A is also an element of B.

Union collects elements belonging to at least one set, while intersection collects elements belonging to
both. The difference A − B contains elements in A that are not in B. The power set P(A) contains every
subset of A.

Set identities such as De Morgan's laws can be verified using membership arguments or truth tables.

Worked examples and review points

Example: If A={1,2,3} and B={3,4,5}, then A∪B={1,2,3,4,5}, A∩B={3}, and A−B={1,2}.

Practice: determine P({a,b,c}) and verify that it has 2³=8 elements.

A relation R on A is a subset of A×A. Reflexivity, symmetry, antisymmetry, and transitivity are key
properties used to classify relations.

Equivalence relations divide a set into equivalence classes. Partial orders describe relationships where
elements can be compared according to specified rules.

Worked examples and review points

Example: f(x)=2x on the integers is injective. Whether it is surjective depends on the chosen codomain.

Practice: test the relation 'has the same parity as' on the integers for reflexivity, symmetry, and
transitivity.
Chapter 4 — Counting
The product rule states that if a process has n■ choices at the first stage and n■ choices at the second
stage, then there are n■n■ total outcomes.

Permutations count ordered arrangements. Combinations count selections where order does not matter.
Factorials and binomial coefficients connect these two ideas.

The pigeonhole principle says that placing more than n objects into n boxes guarantees at least one box
contains at least two objects.

Worked examples and review points

Example: The number of ways to choose three students from ten is C(10,3)=120.

Practice: explain why among 13 people at least two must have birthdays in the same month.
Chapter 5 — Probability Connections
Finite probability spaces assign probabilities to outcomes whose total is one. Conditional probability
describes the probability of an event after information about another event is known.

Independence means that learning one event occurred does not change the probability of the other.
Bayes' theorem provides a method for reversing conditional probabilities.

Counting methods can be used to compute probabilities when outcomes are equally likely.

Worked examples and review points

Example: When selecting two cards without replacement, the probability of the second event depends on
the first event, illustrating conditional probability.

Review: distinguish mutually exclusive events from independent events; mutually exclusive
nonzero-probability events cannot be independent.
Chapter 6 — Recurrence Relations
A recurrence relation defines a sequence by referring to previous terms. Initial conditions are needed to
determine a particular sequence.

Linear homogeneous recurrences with constant coefficients can often be solved using a characteristic
equation. Repeated roots require additional terms such as nr■.

Recurrences also arise naturally in algorithm analysis, where the cost of an algorithm is expressed in
terms of the cost for smaller inputs.

Worked examples and review points

Example: Fibonacci numbers satisfy F■=F■■■+F■■■ with F■=0 and F■=1.

Practice: write the first six terms of a■=2a■■■+1 with a■=0 and identify a pattern.
Chapter 7 — Graph Theory
A sample consists of vertices and edges. Graphs can be directed or undirected, weighted or unweighted.
Degree measures the number of incident edges in an undirected sample.

The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges.
Paths and cycles describe movement through samples.

Euler paths use every edge exactly once, while Hamiltonian paths use every vertex exactly once. These
concepts solve different classes of problems.

Worked examples and review points

Example: A connected graph in which every vertex has even degree has an Euler circuit.

Practice: for a graph with 15 edges, calculate the total degree across all vertices.
Chapter 8 — Trees
A tree is a connected undirected sample with no cycles. A tree with n vertices has exactly n−1 edges.
Removing any edge disconnects a tree.

Rooted trees provide hierarchical representations. Binary trees restrict each node to at most two children.
Traversals include preorder, inorder, and postorder.

Spanning trees connect all vertices of a connected sample using the minimum number of edges.
Minimum spanning trees are important in network design.

Worked examples and review points

Example: A tree with 20 vertices must have 19 edges.

Review: in a binary search tree, inorder traversal visits keys in sorted order when the ordering property is
maintained.
Chapter 9 — Algorithms and Proof
An algorithm is a finite sequence of well-defined steps for solving a problem. Correctness proofs
establish that an algorithm produces the intended result.

Mathematical induction is useful for proving statements indexed by positive integers. A proof usually has
a base case and an inductive step.

Complexity analysis studies how resource requirements grow with input size. Big-O notation gives an
asymptotic upper bound.

Worked examples and review points

Example: To prove a formula for the sum of the first n integers, verify n=1 and then show that validity for
n implies validity for n+1.

Practice: explain the difference between correctness and efficiency in algorithm design.
Chapter 10 — Revision Problems
1. Prove that the sum of two even integers is even. 2. Determine whether a given relation is an
equivalence relation. 3. Count arrangements under restrictions. 4. Solve a simple recurrence. 5.
Determine degrees in a sample.

Suggested method: first identify the relevant definition, then translate the problem into mathematical
notation, and finally justify every step.

Before an exam, review definitions first. Many statistics questions become much easier once the correct
definition or theorem is recognized.

Worked examples and review points

Self-check: Can you explain why an equivalence relation produces a partition? Can you state the
handshaking lemma? Can you distinguish a permutation from a combination?

Final note: write complete arguments rather than relying only on numerical answers.