Introduction to Probability

Overview

This lecture introduces the fundamental concepts of probability theory and their applications in computer science.

Prerequisites Note

Prerequisites

This course builds on concepts from ECS 020: Discrete Mathematics for Computer Science. We'll be using set theory throughout the course—concepts like sets, subsets, unions ($\cup$), intersections ($\cap$), and complements. If these ideas feel unfamiliar, we encourage you to review your ECS 020 notes or the set theory sections in your discrete math textbook.

Topics

• What is probability?
• Sample spaces and events
• Probability axioms (Kolmogorov axioms)
• Basic probability calculations

Key Definitions

Def. (Experiment)

A procedure or process that yields observations or outcomes.

Def. (Sample Space)

The set of all possible outcomes of an experiment. Denoted by $S$ or $\Omega$.

Def. (Event)

A subset of the sample space. An event $A \subseteq S$ is a collection of possible outcomes.

Def. (Outcome)

A single result from an experiment. Each outcome is an element of the sample space.

Def. (Probability Measure)

A probability measure $P$ is a function that assigns a real number to each event in the sample space, satisfying the Kolmogorov Axioms:

1. Non-negativity: $P(A) \geq 0$ for all events $A$
2. Normalization: $P(S) = 1$ where $S$ is the sample space
3. Additivity (Countable Additivity): For mutually exclusive events $A$ and $B$ (i.e., $A \cap B = \emptyset$), we have $P(A \cup B) = P(A) + P(B)$

More generally, for any countable collection of mutually exclusive events $A_1, A_2, \ldots$: $P\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i)$

These axioms, formulated by Andrey Kolmogorov in 1933, form the foundation of modern probability theory.

Set Operations for Events

Def. (Union of Events)

The union of events $A$ and $B$, denoted $A \cup B$, is the event that occurs when either $A$ or $B$ (or both) occur. In set notation: $A \cup B = \{s \in S : s \in A \text{ or } s \in B\}$.

Def. (Intersection of Events)

The intersection of events $A$ and $B$, denoted $A \cap B$, is the event that occurs when both $A$ and $B$ occur. In set notation: $A \cap B = \{s \in S : s \in A \text{ and } s \in B\}$.

Def. (Complement of an Event)

The complement of event $A$, denoted $A^c$ or $\bar{A}$, is the event that $A$ does not occur. In set notation: $A^c = \{s \in S : s \notin A\}$.

Property: $P(A^c) = 1 - P(A)$

Def. (Mutually Exclusive Events)

Events $A$ and $B$ are mutually exclusive (or disjoint) if they cannot both occur simultaneously. Formally: $A \cap B = \emptyset$.

For mutually exclusive events: $P(A \cup B) = P(A) + P(B)$

Applications in Computer Science

• Algorithm analysis (average-case complexity)
• Machine learning (probabilistic models)
• Network protocols (packet delivery)
• Cryptography (security guarantees)
• Data science (statistical inference)

Lecture slides and additional materials will be posted on Canvas.