Compute probabilities in finite sample spaces - Discrete Math

SECTION 1

Historical Context & Motivation

The formal study of probability began not in university lecture halls but at gaming tables in Renaissance Europe. Gamblers and nobles alike sought reliable methods to evaluate bets on dice, cards, and other games of chance—situations that naturally involve finite sample spaces, where the set of possible outcomes is countable and bounded. The mathematical frameworks that emerged from these questions eventually matured into one of the most powerful branches of modern mathematics, underpinning fields from statistical mechanics to machine learning. Understanding how to compute probabilities over finite sets remains the essential first step toward mastering any probabilistic reasoning, and the intellectual lineage stretches back several centuries.

1494 • Pacioli's Problem of Points

Luca Pacioli posed the problem of points—how to fairly divide stakes in an interrupted game—stimulating systematic thought about finite outcome counting.

1654 • Pascal–Fermat Correspondence

Blaise Pascal and Pierre de Fermat exchanged a series of letters that solved the problem of points, establishing the combinatorial method for computing probabilities by exhaustively enumerating equally likely outcomes.

1713 • Bernoulli's Ars Conjectandi

Jacob Bernoulli's posthumous treatise formalized the classical definition of probability as the ratio of favorable to total equally likely cases, and proved the law of large numbers.

1812 • Laplace's Théorie Analytique

Pierre-Simon Laplace refined Bernoulli's framework and articulated the principle that P(E) = |E| / |S|, cementing the ratio-counting approach as the standard for finite probability.

1933 • Kolmogorov's Axioms

Andrey Kolmogorov published axioms grounding all of probability theory in measure theory, providing the rigorous foundation into which finite sample space computations fit as a special case.

The central question these mathematicians pursued remains our starting point: given a finite collection of possible outcomes, how do we assign a meaningful numerical measure to the likelihood of any particular event? This lesson develops the answer from first principles, equipping you with both the theoretical grounding and the practical techniques to compute probabilities in any finite sample space.

SECTION 2

Core Principles & Definitions

Before computing any probability, we must establish the vocabulary and structural assumptions that make such computation well-defined. A random experiment is any process whose outcome cannot be predicted with certainty before it is performed. Rolling a die, drawing a card, or selecting a committee from a roster are all random experiments. The complete list of all distinct outcomes that can result from such an experiment forms the sample space, typically denoted S (or Ω). When this set is finite—that is, when |S| is a natural number—we say we are working in a finite sample space. An event is any subset E ⊆ S, and the probability of E is a real number P(E) ∈ [0, 1] quantifying how likely E is to occur.

Sample Space (S)

The finite set of all possible, mutually exclusive outcomes of a random experiment. For a standard die, S = {1, 2, 3, 4, 5, 6} with |S| = 6.

Event (E ⊆ S)

Any subset of the sample space. The event "rolling an even number" is E = {2, 4, 6}. The empty set ∅ is the impossible event; S itself is the certain event.

Probability Function P

A function P : 2ˢ → [0, 1] satisfying Kolmogorov's axioms: P(S) = 1, P(∅) = 0, and for disjoint events A and B, P(A ∪ B) = P(A) + P(B).

Equally Likely Outcomes

When symmetry or design ensures every outcome has the same probability, P({sᵢ}) = 1/|S| for each sᵢ ∈ S. This is the classical (Laplacian) model.

Complementary Counting

Often it is easier to compute P(Eᶜ) and use P(E) = 1 − P(Eᶜ). This strategy is especially powerful when Eᶜ has a simpler structure than E.

✦

KEY TAKEAWAY

Think of a finite sample space like a jar of distinctly colored marbles. Each marble is a possible outcome, and the probability of an event is simply the fraction of marbles whose color matches your criterion. If the jar has 20 marbles and 5 are red, the probability of drawing red is 5/20 = 1/4. The entire framework of finite probability reduces to careful counting of favorable outcomes versus total outcomes—provided each marble is equally likely to be drawn.

SECTION 3

Visual Explanation: Anatomy of a Finite Sample Space

The 6 × 6 grid represents all 36 equally likely outcomes when rolling two fair dice. The highlighted cells mark the event E = "sum equals 7," which contains exactly 6 outcomes. Since all outcomes are equally likely, P(E) = 6/36 = 1/6.

The grid above illustrates the most fundamental technique in finite probability: enumerate every element of the sample space S, identify those belonging to the event E, and form the ratio |E|/|S|. Notice that the six highlighted outcomes—(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)—lie along the anti-diagonal of the grid, reflecting the algebraic constraint that the two die values must sum to 7. This geometric regularity is no accident; many probability problems become transparent once the sample space is visualized in a structured way, such as a grid, tree diagram, or Venn diagram.

SECTION 4

Mathematical Framework

We now formalize the computational machinery. The framework rests on a probability function P defined on subsets of a finite sample space S that satisfies the Kolmogorov axioms, specialized to the finite case. From these axioms, several indispensable formulas follow.

CLASSICAL PROBABILITY (EQUALLY LIKELY OUTCOMES)

P(E) = |E| / |S|

Where |E| is the number of outcomes favorable to event E, and |S| is the total number of outcomes in the sample space. This formula applies only when every outcome in S is equally likely.

COMPLEMENT RULE

P(Eᶜ) = 1 − P(E)

The probability of the complement Eᶜ (everything not in E) is one minus the probability of E. This is especially useful when counting favorable outcomes directly is harder than counting unfavorable ones.

INCLUSION–EXCLUSION PRINCIPLE (TWO EVENTS)

P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

For any two events A, B ⊆ S, the probability of their union equals the sum of their individual probabilities minus the probability of their intersection. This corrects for double-counting outcomes that belong to both A and B.

GENERAL WEIGHTED PROBABILITY

P(E) = Σ_{s∈E} p(s) where Σ_{s∈S} p(s) = 1

When outcomes are not equally likely, each outcome s has its own weight p(s) ≥ 0. The probability of event E is the sum of the weights of all outcomes in E. The weights must sum to 1 across the entire sample space.

⚠

When Is the Classical Formula Valid?

The ratio P(E) = |E|/|S| is valid only under the assumption of equally likely outcomes. A fair coin, a well-shuffled deck, or a uniform random number generator all satisfy this condition. A loaded die does not—for such cases, you must use the general weighted formula and know (or estimate) each p(s) individually.

SECTION 5

Counting Methods for Finite Sample Spaces

The classical probability formula P(E) = |E|/|S| reduces the probability problem to a counting problem: determine |E| and |S|. For small sample spaces, direct enumeration suffices. For larger spaces, we rely on systematic counting principles from combinatorics. The three most frequently used tools are the multiplication principle, permutations, and combinations.

This flowchart guides the choice of counting technique. Start by assessing the size of the sample space. For small spaces, list outcomes directly. For larger spaces, determine whether order matters to choose between combinations and permutations. The multiplication principle and complement counting are meta-strategies applicable throughout.

Method	Formula	When to Use	Example
Multiplication Principle	n₁ × n₂ × … × nₖ	Sequential choices where each stage has a fixed number of options	Outcomes of flipping 3 coins: 2 × 2 × 2 = 8
Permutations P(n, k)	n! / (n − k)!	Ordered selections without replacement from n items, choosing k	Arranging 3 of 10 books on a shelf: 10!/7! = 720
Combinations C(n, k)	n! / (k!(n − k)!)	Unordered selections without replacement from n items, choosing k	Choosing a 5-card hand from 52 cards: C(52, 5) = 2,598,960
Complement Counting	\|E\| = \|S\| − \|Eᶜ\|	When the event's complement is simpler to count	P(at least one head in 4 flips) = 1 − P(all tails) = 1 − 1/16

Summary of core counting techniques used to compute |E| and |S|

SECTION 6

Worked Example: Probability of a Full House in Poker

A full house in five-card poker consists of three cards of one rank and two cards of a different rank (e.g., three Kings and two 7s). We wish to compute the probability of being dealt a full house from a standard 52-card deck, assuming all 5-card hands are equally likely.

Computing P(Full House)

1
Step 1 — Determine the sample space size |S|

A 5-card hand is an unordered selection of 5 cards from 52, so the total number of possible hands is the combination C(52, 5). Computing: C(52, 5) = 52! / (5! × 47!) = (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1).

|S| = C(52, 5) = 2,598,960
2
Step 2 — Count favorable outcomes |E| using the multiplication principle

Building a full house requires three sequential choices. First, choose the rank for the three-of-a-kind: there are 13 possible ranks (Ace through King). Second, choose which 3 of the 4 suits will appear for that rank: C(4, 3) = 4 ways. Third, choose the rank for the pair: there are 12 remaining ranks. Fourth, choose which 2 of the 4 suits will appear for the pair: C(4, 2) = 6 ways. By the multiplication principle, the total count is 13 × 4 × 12 × 6.

|E| = 13 × C(4,3) × 12 × C(4,2) = 13 × 4 × 12 × 6 = 3,744
3
Step 3 — Apply the classical probability formula

Since every 5-card hand is equally likely (the deck is well-shuffled), we apply P(E) = |E| / |S|. Substituting our counts: P(Full House) = 3,744 / 2,598,960.

P(Full House) = 3,744 / 2,598,960 ≈ 0.001441, or about 0.144%
4
Step 4 — Interpret the result

The probability is roughly 1 in 694. In practical terms, if you were dealt 694 random 5-card hands, you would expect to see a full house approximately once. This low probability reflects the high specificity of the structural constraint: matching exactly three of one rank and two of another out of the enormous space of 2.6 million possible hands.

Odds ≈ 1 in 694 hands

SECTION 7

Common Pitfalls & Best Practices

Even with the correct formulas at hand, probability computations in finite sample spaces are rife with subtle traps. The table below contrasts frequent errors with their corrections, helping you build disciplined reasoning habits.

Common Pitfall	Why It's Wrong	Correct Approach
Assuming equally likely when outcomes are not	Rolling two dice and treating "sum = 2" and "sum = 7" as equally probable ignores that sum = 7 has 6 constituent outcomes while sum = 2 has only 1.	Always model the experiment at the atomic outcome level where symmetry genuinely holds (e.g., ordered pairs for two dice, not sums).
Double-counting overlapping events	Adding P(A) + P(B) without subtracting P(A ∩ B) overcounts outcomes in the intersection.	Apply inclusion–exclusion: P(A ∪ B) = P(A) + P(B) − P(A ∩ B). For three or more events, extend the formula accordingly.
Confusing permutations and combinations	Using P(n, k) when the selection is unordered inflates the count by a factor of k!, giving an incorrect probability.	Ask: "Does the order in which I choose items affect the outcome?" If not, use C(n, k). If yes, use P(n, k).
Neglecting with/without replacement	Sampling with replacement allows repetitions, changing both \|S\| and \|E\|. Using the wrong model silently corrupts the answer.	Explicitly state the sampling model. With replacement: nᵏ total sequences. Without replacement: P(n, k) ordered or C(n, k) unordered.

Pitfalls in finite probability and their remedies

✦

KEY TAKEAWAY

Think of computing a finite probability like conducting a precise inventory audit. You must first confirm that every item on the shelf is tagged with exactly the same weight (equally likely assumption), then count how many items match your search criteria versus the total stock. If the tags carry different weights—say, some products are bulkier and were packed more densely—you need a weighted tally instead. The single most consequential decision in any finite probability problem is verifying that your sample space is modeled at the right level of granularity where the uniform assumption truly applies.

SECTION 8

Connections to Advanced Probability Theory

Finite sample spaces provide the foundational intuition upon which more general probability theory is built. Understanding how the finite case connects to advanced frameworks prepares you for courses in stochastic processes, statistical inference, and information theory, where the sample space may be countably infinite or uncountable.

Concept	Finite Sample Space Version	General / Advanced Version
Sample space	Finite set S = {s₁, s₂, …, sₙ}	Arbitrary measurable space (Ω, ℱ); may be countably infinite or continuous (e.g., ℝ)
Event algebra	Power set 2ˢ (all subsets are events)	σ-algebra ℱ ⊆ 2^Ω; not all subsets need be measurable
Probability	P(E) = \|E\|/\|S\| (classical) or P(E) = Σ p(sᵢ)	Probability measure μ on (Ω, ℱ); for continuous spaces, P(E) = ∫_E f(x) dx via density functions
Additivity	Finite additivity: P(A ∪ B) = P(A) + P(B) for disjoint A, B	Countable additivity (σ-additivity): P(⋃ᵢ Aᵢ) = Σᵢ P(Aᵢ) for countably many disjoint events
Conditional probability	P(A\|B) = \|A ∩ B\| / \|B\| when outcomes are equally likely	P(A\|B) = P(A ∩ B) / P(B), extended to Radon–Nikodym derivatives for continuous conditioning

From finite to general probability: concept correspondence

The transition from finite to general probability theory is elegant: every finite-sample-space result you learn remains valid as a special case of the measure-theoretic framework. Kolmogorov's axioms were deliberately designed so that the intuitive counting-based probability you practice here generalizes seamlessly. As you progress to topics like random variables, expectation, and stochastic processes, the finite case will continue to serve as a concrete testing ground—a place where you can verify general theorems by direct computation before trusting abstract proofs.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

A sample space S contains 10 outcomes. If the outcomes are not equally likely, can we still use P(E) = |E|/|S| to compute the probability of an event E? Explain why or why not, and state what additional information would be needed.

Show answer

No, the formula P(E) = |E|/|S| is valid only when all outcomes in S are equally likely. When outcomes have different probabilities, we must use the general weighted formula P(E) = Σ_{s∈E} p(s), where p(s) is the probability assigned to each individual outcome. To apply this, we need the complete probability distribution—i.e., the value of p(s) for each s ∈ S, with the constraint that all p(s) ≥ 0 and Σ_{s∈S} p(s) = 1. Without this distribution, the probability of E is indeterminate.

Question 2: BASIC CALCULATION

A standard deck of 52 cards is shuffled and one card is drawn at random. What is the probability that the card is a heart or a face card (Jack, Queen, King)?

Show answer

Let A = "card is a heart" and B = "card is a face card." Then |A| = 13 (one suit), |B| = 12 (3 face cards × 4 suits), and |A ∩ B| = 3 (the Jack, Queen, and King of hearts). By inclusion–exclusion: |A ∪ B| = 13 + 12 − 3 = 22. Since all 52 cards are equally likely, P(A ∪ B) = 22/52 = 11/26 ≈ 0.4231. The key step is subtracting the 3 hearts that are also face cards to avoid double-counting.

Question 3: INTERMEDIATE

A committee of 4 people is to be chosen from a group of 6 men and 5 women. What is the probability that the committee contains at least one woman?

Show answer

The total number of ways to choose a 4-person committee from 11 people is |S| = C(11, 4) = 330. The complement of "at least one woman" is "all men," which requires choosing 4 from the 6 men: |Eᶜ| = C(6, 4) = 15. Therefore P(at least one woman) = 1 − P(all men) = 1 − 15/330 = 1 − 1/22 = 21/22 ≈ 0.9545. Complement counting is the efficient strategy here because directly counting "at least one woman" would require summing over four separate cases (exactly 1, 2, 3, or 4 women).

Question 4: APPLIED

A network router receives packets from 3 servers. Server A sends 50% of all packets, Server B sends 30%, and Server C sends 20%. A quality test is run on a randomly selected sample of 2 packets from a batch of 10 (5 from A, 3 from B, 2 from C), drawn without replacement. What is the probability that both sampled packets come from Server A?

Show answer

Since we draw 2 packets from 10 without replacement and without regard to order, the sample space size is |S| = C(10, 2) = 45. The number of ways to choose both packets from Server A's 5 packets is |E| = C(5, 2) = 10. Therefore P(both from A) = 10/45 = 2/9 ≈ 0.2222. Note that this is a hypergeometric-type calculation: we are sampling from a finite population stratified by source, which is a direct application of the classical probability formula over a finite sample space of unordered pairs.

Question 5: CRITICAL THINKING

Prove that for any finite sample space S with |S| = n and any event E ⊆ S, if we define a non-uniform probability distribution p(sᵢ) = i / T where T = n(n+1)/2 and s₁, s₂, …, sₙ are the outcomes, then P(E) = Σ_{sᵢ ∈ E} i / T. Verify this defines a valid probability distribution and compute P(E) when E = {s₁, sₙ} and n = 10.

Show answer

First, we verify that the distribution is valid. Each p(sᵢ) = i/T ≥ 0 since i ≥ 1 and T > 0. The sum Σᵢ₌₁ⁿ p(sᵢ) = Σᵢ₌₁ⁿ i/T = (1/T) × n(n+1)/2 = T/T = 1, confirming the axioms are satisfied. For n = 10, T = 10 × 11/2 = 55. The event E = {s₁, s₁₀} gives P(E) = p(s₁) + p(s₁₀) = 1/55 + 10/55 = 11/55 = 1/5 = 0.2. This example illustrates that non-uniform distributions over finite spaces are well-defined as long as all weights are non-negative and sum to 1, and that the probability of any event is simply the sum of the weights of its constituent outcomes.

SUMMARY

Lesson Summary

Summary

Computing probabilities in finite sample spaces rests on the elegant principle that probability reduces to counting. When every outcome in S is equally likely, the probability of event E is simply P(E) = |E|/|S|. When outcomes carry different weights, the general weighted formula P(E) = Σ p(s) applies. The key challenge lies in accurately computing |E| and |S|, which requires fluency with the multiplication principle, permutations, combinations, and the complement counting strategy.

Critical pitfalls include assuming equally likely outcomes without justification, confusing ordered and unordered selections, and neglecting the inclusion–exclusion principle when events overlap. The finite framework generalizes naturally to Kolmogorov's measure-theoretic axioms, making this material the essential launchpad for all advanced probability and statistics coursework.