Engineering / Mathematics — Discrete Probability
Finite Probability Distributions
Finite sample spaces, probability distributions, events and the basic laws governing them.
Executive summary
A finite probability distribution assigns weights summing to one over a finite sample space. Everything in the probabilistic analysis of algorithms is built on this modest foundation.
The formalism matters more than it first appears: most errors in probabilistic reasoning about algorithms come from an unstated or inconsistent sample space rather than from arithmetic.
Learning objectives
- Define a finite probability distribution and its events.
- Apply the union bound and inclusion-exclusion.
- Identify the sample space implicit in an algorithmic claim.
01Sample spaces and events
Finite probability distribution
A pair (Ω, P) where Ω is a finite non-empty set and P : Ω → [0,1] satisfies Σ_{ω∈Ω} P(ω) = 1.
An event is a subset A ⊆ Ω, with P(A) = Σ_{ω∈A} P(ω).
The uniform distribution, where every outcome carries weight 1/|Ω|, is the case of most interest here: a randomised algorithm drawing bits uniformly induces exactly this distribution on its coin-flip sequences.
02Basic laws
| Law | Statement | Condition |
|---|---|---|
| Complement | P(Ā) = 1 − P(A) | Always |
| Monotonicity | A ⊆ B ⇒ P(A) ≤ P(B) | Always |
| Union bound | P(∪Aᵢ) ≤ ΣP(Aᵢ) | Always; no independence needed |
| Inclusion–exclusion | P(A∪B) = P(A)+P(B)−P(A∩B) | Always |
| Additivity | P(A∪B) = P(A)+P(B) | A, B disjoint |
The union bound is crude and indispensable. It requires no assumption whatever, which is precisely the situation in most algorithm analyses where the events of interest are correlated in ways too awkward to describe.
03Conditioning and partitions
A partition of the sample space decomposes a probability into cases, which is the standard route through an analysis that branches.
P(A) = Σᵢ P(A ∩ Bᵢ) for any partition {Bᵢ} of ΩApplied to a randomised algorithm, the partition is usually over the value of some intermediate quantity — the pivot chosen, the base selected, the first index where a loop succeeds — and the analysis proceeds by bounding the conditional behaviour in each case.
04Frequently asked questions
Why restrict to finite sample spaces?
Because a terminating randomised algorithm consuming a bounded number of random bits induces a finite distribution, which covers most of what is needed. Algorithms that loop until success require countably infinite spaces, treated separately.
Is the union bound ever too weak to use?
It fails to give a useful result when the events are numerous and individually probable — bounding a sum of many terms each near one yields nothing. In those cases inclusion-exclusion or a concentration inequality is needed.
Does the sample space depend on the input?
For a randomised algorithm, no — the space is the set of coin-flip sequences, and the input is a fixed parameter. This is exactly why worst-case guarantees over inputs are available while still averaging over randomness.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 96-99.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.