Probability starts with a simple idea: listing all possible outcomes. This complete list is called the sample space. Think of it as the universe of what could happen in a given situation.

If you flip a coin, there are only two possible outcomes: heads or tails. The sample space, which we can call $S$, is just {$H, T$}.

An event is a specific outcome or a group of outcomes you're interested in. It's a subset of the sample space. For the coin flip, the event "the coin lands on heads" is simply {$H$}.

Let's try a six-sided die. The sample space includes every face of the die: $S = \{1, 2, 3, 4, 5, 6\}$. An event could be "rolling a 4," which corresponds to the set {4}. Or it could be more complex, like "rolling an even number," which is the set $E = \{2, 4, 6\}$.

Probabilities follow three basic rules, or axioms. These rules ensure that our calculations make sense.

First, the probability of any event is a number between 0 and 1. A probability of 0 means the event is impossible. A probability of 1 means it's certain. For any event $E$, its probability $P(E)$ is:

Second, the probability of the entire sample space is 1. This just means that something from the list of all possible outcomes must happen. For the sample space $S$:

Third, if two events are mutually exclusive—meaning they can't both happen at the same time—the probability of one or the other happening is the sum of their individual probabilities. For example, you can't roll a 1 and a 3 on a single die at the same time. Let $E_1$ be the event of rolling a 1, and $E_2$ be the event of rolling a 3. The probability of rolling a 1 or a 3 is:

Sometimes events aren't mutually exclusive. For instance, in an email system, a message might be marked as "spam" and also marked as "important."

This leads to the idea of conditional probability: the likelihood of an event occurring, given that another event has already happened. We write the probability of event $A$ happening given that event $B$ has happened as $P(A|B)$.

Let's go back to our die. Let $A$ be the event "rolling a number less than 5," so $A = \{1, 2, 3, 4\}$. Let $B$ be the event "rolling an even number," so $B = \{2, 4, 6\}$.

What is the probability of rolling a number less than 5, given that we know the roll was even? Since we know the roll was even, our new, smaller sample space is just {$2, 4, 6$}. Within this new space, the outcomes that are also less than 5 are {$2, 4$}. So, there are 2 favorable outcomes out of 3 total possibilities. $P(A|B) = 2/3$.

The formal definition of conditional probability is:

Here, $P(A \cap B)$ is the probability that both $A$ and $B$ happen. In our die example, the outcomes that are both even and less than 5 are {$2, 4$}. So, $P(A \cap B) = 2/6 = 1/3$. The probability of rolling an even number is $P(B) = 3/6 = 1/2$. Plugging these in gives us:

This matches our intuitive result. Conditional probability is a powerful tool for narrowing down possibilities based on new information.

We can rearrange the conditional probability formula to get a very useful result known as Bayes' Theorem. This theorem is the backbone of many systems in machine learning and data science, from spam filters to medical diagnostics. It tells us how to update our belief about something in light of new evidence.

The theorem looks like this:

Each piece has a name:

• $P(A|B)$ is the posterior probability: what we want to know. The probability of $A$ after we see evidence $B$.
• $P(A)$ is the prior probability: our initial belief about $A$ before seeing any evidence.
• $P(B|A)$ is the likelihood: the probability of observing evidence $B$ if our belief $A$ is true.
• $P(B)$ is the marginal probability: the overall probability of observing the evidence $B$.

Imagine a medical test for a rare disease. Let $A$ be the event "a person has the disease," and $B$ be the event "the test is positive."

• $P(A)$ is the prior: the probability someone has the disease, say 1 in 1000 ($0.001$).
• $P(B|A)$ is the likelihood: the probability of a positive test if you have the disease. Let's say the test is 99% accurate, so this is $0.99$.
• $P(B)$ is the overall probability of a positive test. This is a bit trickier, but we can calculate it.

With Bayes' Theorem, we can calculate $P(A|B)$: the probability you actually have the disease given a positive test. Because the disease is rare, this number is often surprisingly low, showing how the theorem helps us avoid jumping to conclusions.

Finally, we have the concept of independence. Two events are independent if the outcome of one has no effect on the outcome of the other. Flipping a coin twice is a classic example. The result of the first flip doesn't change the probabilities for the second flip.

Mathematically, two events $A$ and $B$ are independent if:

This means the probability of both events happening is just the product of their individual probabilities. If you flip a fair coin twice, the probability of getting two heads in a row is:

$P(H_1 \cap H_2) = P(H_1) \cdot P(H_2) = 0.5 \cdot 0.5 = 0.25$

Another way to think about independence is through conditional probability. If $A$ and $B$ are independent, then knowing $B$ happened tells you nothing new about $A$. Therefore:

Understanding independence is critical in computer science, especially in designing algorithms and analyzing systems where you need to know if different components or events can be treated separately.

Let's check your understanding of these core concepts.

These foundational ideas—sample spaces, axioms, conditional probability, and independence—are the building blocks for tackling uncertainty in any computational problem.