Difficulty: Introductory | Prerequisites: Basic set notation, arithmetic with fractions.
Probability theory is the mathematical framework for reasoning about uncertainty. It sits at the foundation of statistics, machine learning, data science and most of computer science. This first set of notes covers the building blocks: sample spaces, how probability is assigned and measured, the inclusion-exclusion principle, complements and the uniform distribution. If you are comfortable with sets and can manipulate fractions, you have everything you need to start here.
Probability assigns a number between 0 and 1 to every possible outcome of an uncertain process. The numbers must be non-negative and must sum to 1 across all outcomes. Events are sets of outcomes, and their probabilities follow rules you can combine, including inclusion-exclusion for unions and a simple subtraction for complements. When every outcome is equally likely, the probability of an event is just the count of favourable outcomes divided by the total.
Sample space (S)
The set of all possible outcomes of an uncertain event. Think of it as the complete menu of things that could happen.
Outcome
A single element of the sample space. In simple terms, one specific result from the experiment.
Probability measure, p(x)
A function that assigns a number between 0 and 1 to each outcome, representing how likely it is. Think of it as the "weight" each outcome carries.
Non-negativity
The rule that every outcome's probability must be zero or positive. You cannot have a negative chance of something happening.
Normalization
The rule that the probabilities of all outcomes in the sample space must add up to exactly 1. In simple terms, something from the sample space is guaranteed to happen.
Event
A subset of the sample space, i.e. a collection of one or more outcomes. Think of it as a question you can ask about the result: "Did an odd number come up?"
Inclusion-exclusion principle
A formula for the probability of the union of two events that corrects for double-counting the overlap. In simple terms, add the two probabilities, then subtract the bit you counted twice.
Complement of an event (A^c)
The set of outcomes in S that are not in A. The probability of the complement is 1 minus the probability of A. Think of it as "everything else."
Uniform distribution
A probability distribution where every outcome in the sample space is equally likely. In simple terms, no outcome is favoured over any other.
The sample space S lists every outcome that could occur.
Rolling a six-sided die: S = {1, 2, 3, 4, 5, 6}.
Flipping a coin twice: S = {HH, HT, TH, TT}.
Generating a random 4-bit string: S contains all 16 strings from 0000 to 1111.
In introductory probability, sample spaces are usually finite, meaning you can count the outcomes.
Non-negativity: for every outcome x in S, p(x) >= 0.
Normalization: the sum of p(x) over all x in S equals 1.
An event A is any subset of S. Its probability is the sum of the probabilities of the outcomes it contains.
Example: "rolling an even number" on a fair die is the event {2, 4, 6}. Its probability is p(2) + p(4) + p(6) = 1/6 + 1/6 + 1/6 = 1/2.
When you want the probability that event A or event B occurs (the union A ∪ B), you cannot simply add p(A) and p(B) because outcomes in both A and B would be counted twice.
The correction: p(A ∪ B) = p(A) + p(B) - p(A ∩ B).
Example: suppose you draw a card from a standard deck. Let A = "the card is a heart" and B = "the card is a face card." p(A) = 13/52, p(B) = 12/52, and the overlap (face cards that are hearts) gives p(A ∩ B) = 3/52. So p(A ∪ B) = 13/52 + 12/52 - 3/52 = 22/52.
The principle generalises to more than two events, but for this course the two-event version is the one to know.
The complement of event A, written A^c, is the set of all outcomes in S that are not in A.
p(A^c) = 1 - p(A).
This is often the fastest route to a probability when the event itself is complicated but its complement is simple.
Example: the probability of getting at least one head in three coin flips. The complement is "no heads at all" (i.e. TTT), which has probability 1/8. So p(at least one head) = 1 - 1/8 = 7/8.
A sample space of size n follows a uniform distribution when every outcome has the same probability, 1/n.
Under a uniform distribution, the probability of any event A is simply: p(A) = |A| / n, where |A| is the number of outcomes in A.
Most "intro probability" exam questions assume a uniform distribution unless stated otherwise.
Example, fair die: the probability of rolling an odd number is |{1, 3, 5}| / 6 = 3/6 = 0.5.
Example, urn problem: an urn contains 4 blue balls and 5 red balls (9 total). The probability of drawing a blue ball is 4/9.
p(A) = \sum_{x \in A} p(x)p(A \cup B) = p(A) + p(B) - p(A \cap B)p(A^c) = 1 - p(A)p(A) = \frac{|A|}{n} \quad \text{(uniform distribution)}Sample spaces and probability measures are how engineers and scientists model anything with uncertain outcomes. A network engineer uses them to model packet loss across a link; a game designer uses them to balance loot-drop rates. The complement rule is the reason your weather app tells you "20% chance of rain" rather than listing every dry scenario individually. The inclusion-exclusion principle shows up whenever overlapping categories need to be counted without duplication, from database queries to survey analysis.
Students often add p(A) + p(B) to get p(A ∪ B) and forget to subtract the intersection. This overcounts every outcome that belongs to both events.
Students sometimes assume every sample space is uniform. It is not. A loaded die, a biased coin, or any weighted random process has a non-uniform distribution. Only use p(A) = |A|/n when the problem states outcomes are equally likely.
Confusing "outcome" with "event." An outcome is a single element of S; an event is a set of outcomes. Rolling a 3 is an outcome. Rolling an odd number is an event containing three outcomes.
Forgetting that probabilities must sum to 1 over the entire sample space. If your assigned probabilities do not add to 1, something is wrong with the model.
⚠️ Expect at least one question that requires the inclusion-exclusion formula. The setup usually gives p(A), p(B) and p(A ∩ B) and asks for p(A ∪ B).
⚠️ The complement rule is a favourite shortcut question: "what is the probability of at least one..." almost always calls for 1 minus the probability of none.
⚠️ Know how to list a sample space explicitly for small experiments (coins, dice, short bit strings). Being able to enumerate S is the first step in many exam problems.
⚠️ Uniform distribution calculations (|A|/n) appear in nearly every introductory probability exam. Double-check that the problem confirms equal likelihood before applying this formula.
True or false: the probability of an event can be negative. (False. Non-negativity requires p(x) >= 0.)
True or false: if S = {a, b, c} and p(a) = 0.5, p(b) = 0.3, p(c) = 0.1, this is a valid probability distribution. (False. The probabilities sum to 0.9, not 1.)
Fill in the blank: p(A ∪ B) = p(A) + p(B) - ____. (p(A ∩ B))
True or false: the complement of "rolling a 6" on a fair die has probability 5/6. (True.)
Fill in the blank: under a uniform distribution with n outcomes, p(A) = ____. (|A| / n)
Q: A bag contains 3 red, 5 green and 2 blue marbles. What is the probability of drawing a green marble?
A: There are 10 marbles in total and 5 are green, so p(green) = 5/10 = 1/2.
Q: Events A and B have p(A) = 0.4, p(B) = 0.5 and p(A ∩ B) = 0.2. What is p(A ∪ B)?
A: By inclusion-exclusion, p(A ∪ B) = 0.4 + 0.5 - 0.2 = 0.7.
Q: You roll a fair die. What is the probability of rolling a number that is not 4?
A: p(not 4) = 1 - p(4) = 1 - 1/6 = 5/6.
Q: A 3-bit string is generated uniformly at random. What is the probability it contains at least one 1?
A: The sample space has 8 strings. The only string with no 1s is 000. So p(at least one 1) = 1 - 1/8 = 7/8.
Q: State the two axioms that any probability measure must satisfy.
A: Non-negativity (p(x) >= 0 for every outcome x) and normalization (the sum of p(x) over all x in S equals 1).
These fundamentals are the prerequisite for conditional probability and Bayes theorem (covered in Part 2). Inclusion-exclusion extends to counting problems in combinatorics. The complement rule reappears in the study of random variables when computing cumulative distribution functions. Uniform distributions connect directly to combinatorics: if every arrangement is equally likely, counting favourable arrangements gives you the probability.
Probability, sample space, outcome, event, probability measure, axioms of probability, non-negativity, normalization, inclusion-exclusion, union of events, complement rule, complement of an event, uniform distribution, equally likely outcomes, finite sample space, probability of union, Purdue CS, foundations of computer science, discrete probability, intro to probability