Probability Theory in Computer Science

Learning Objectives

By the end of this page, you should be able to:

• Define sample space, event, and probability, and compute basic probabilities
• Distinguish mutually exclusive events from independent events
• Apply the conditional probability formula and Bayes' theorem to real problems
• Explain how Markov chains model systems that evolve over time
• Connect probability theory to CS applications like spam filtering, medical diagnosis, and PageRank
• Identify common mistakes students make with independence and conditional probability

Quick Answer

Probability theory is the branch of mathematics that quantifies uncertainty — it assigns a number between 0 (impossible) and 1 (certain) to how likely an event is to happen. In computer science, probability underlies machine learning (classifiers output probabilities), spam filters (Bayesian reasoning), search engines (Markov chains behind PageRank), and randomized algorithms. The core building blocks are the sample space (all possible outcomes), events (subsets of outcomes you care about), and rules for combining probabilities when events are independent, mutually exclusive, or conditional on each other. Once you're comfortable with conditional probability and Bayes' theorem, you can reason rigorously about anything from "how reliable is this medical test?" to "how likely is this email actually spam?"

Sample Space and Events

The sample space ($S$) is the set of all possible outcomes of a random experiment. An event is any subset of the sample space — the outcomes you're interested in.

Example: Rolling a fair six-sided die gives sample space $S = \{1, 2, 3, 4, 5, 6\}$. The event "rolling an even number" is the subset $E = \{2, 4, 6\}$.

The probability of an event is:

$P(E) = \frac{\text{number of favorable outcomes}}{\text{number of total outcomes in } S} \quad \text{(when outcomes are equally likely)}$

So $P(E) = 3/6 = 0.5$ for rolling an even number.

Why it matters: Defining the sample space precisely is the single most common source of probability mistakes. If you miscount the outcomes or forget that order matters (or doesn't), every calculation downstream will be wrong.

Common misunderstanding: Students often assume all outcomes are "equally likely" by default. That assumption only holds for fair dice, fair coins, and similarly symmetric setups — it does not hold for real-world events like "will it rain tomorrow," where outcomes must be weighted according to actual data or a model.

Mutually Exclusive vs. Independent Events

These two ideas get confused constantly, but they describe different relationships:

• Mutually exclusive events cannot happen at the same time: $P(A \cap B) = 0$. Example: rolling a 2 and rolling a 5 on the same die roll — you can't do both at once.
• Independent events don't influence each other's probability: $P(A \cap B) = P(A) \cdot P(B)$. Example: flipping a coin and rolling a die are independent — the coin result tells you nothing about the die result.

Worked numeric example: Flip a fair coin twice. What's the probability of getting heads both times?

The flips are independent, so $P(\text{HH}) = P(H) \times P(H) = 0.5 \times 0.5 = 0.25$.

Checking with the full sample space $\{HH, HT, TH, TT\}$: 1 favorable outcome out of 4, so $P(HH) = 1/4 = 0.25$ — matches.

Real-world example: In A/B testing for a website, you typically assume that seeing version A vs. version B doesn't affect a user's baseline likelihood to convert — that independence assumption is what lets you multiply probabilities to compute joint outcomes across many users.

Conditional Probability and Bayes' Theorem

Conditional probability asks: given that event $B$ has already happened, what's the probability of event $A$?

$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$

Bayes' theorem flips a conditional probability around, letting you compute $P(A \mid B)$ from $P(B \mid A)$:

$P(A \mid B) = \frac{P(B \mid A) \, P(A)}{P(B)}$

Worked numeric example — spam filter:

Suppose 20% of all emails are spam ($P(\text{spam}) = 0.2$). The word "free" appears in 60% of spam emails ($P(\text{free} \mid \text{spam}) = 0.6$) but only in 5% of legitimate emails ($P(\text{free} \mid \text{not spam}) = 0.05$). If an email contains "free," what's the probability it's spam?

First compute $P(\text{free})$ using the law of total probability:

$P(\text{free}) = P(\text{free}\mid\text{spam})P(\text{spam}) + P(\text{free}\mid\text{not spam})P(\text{not spam})$ $= (0.6)(0.2) + (0.05)(0.8) = 0.12 + 0.04 = 0.16$

Now apply Bayes' theorem:

$P(\text{spam} \mid \text{free}) = \frac{(0.6)(0.2)}{0.16} = \frac{0.12}{0.16} = 0.75$

So even though "free" seems like a strong spam signal, only 75% of emails containing it are actually spam — not 100%, because legitimate emails occasionally use the word too.

Why it matters: Bayes' theorem is the mathematical foundation of spam filters, medical diagnosis (interpreting test results), and any system that needs to update a belief after seeing new evidence — which is exactly what "learning from data" means in machine learning.

Markov Chains

A Markov chain is a sequence of random states where the probability of moving to the next state depends only on the current state, not on the full history of how you got there (the "memoryless" property).

Worked example: If today is Sunny, what's the probability that tomorrow is Cloudy? Reading directly from the transition diagram: $P(\text{Cloudy} \mid \text{Sunny}) = 0.3$. What about two days from now? You'd multiply along every possible path (Sunny→Sunny→Cloudy, Sunny→Cloudy→Cloudy, Sunny→Rainy→Cloudy) and sum the probabilities — this is exactly how transition matrices are multiplied together in practice.

Why it matters: Markov chains power Google's PageRank algorithm (modeling a "random surfer" clicking links), predictive text on your phone keyboard, and speech recognition systems — anywhere you need to model a sequence of states with probabilistic transitions.

Key Terms

Term	Definition
Sample space ($S$)	The set of all possible outcomes of a random experiment
Event	Any subset of the sample space
Mutually exclusive events	Events that cannot occur at the same time ($P(A \cap B) = 0$)
Independent events	Events where one's occurrence doesn't affect the other's probability
Conditional probability	The probability of an event given that another event has occurred, $P(A \mid B)$
Bayes' theorem	A formula for reversing a conditional probability using prior and evidence probabilities
Complementary event	The event that the original event does not occur; $P(A^c) = 1 - P(A)$
Markov chain	A sequence of states where the next state depends only on the current state
Transition matrix	A matrix listing the probabilities of moving from each state to every other state

Common Mistakes

1. Misconception: "Mutually exclusive and independent mean the same thing." Why it's wrong: They describe opposite relationships in a subtle sense — two mutually exclusive events with nonzero probability are actually maximally dependent, because if one happens, the other definitely cannot. Correct: Mutually exclusive means $P(A \cap B) = 0$; independent means $P(A \cap B) = P(A)P(B)$. Two events with nonzero probability can't be both mutually exclusive and independent at the same time (unless one has probability zero).

2. Misconception: "If a coin has landed on heads 5 times in a row, tails is 'due' next." Why it's wrong: This is the gambler's fallacy — it assumes the coin has memory of past results, but each flip is an independent event. Correct: A fair coin's probability of heads is always 0.5 on the next flip, regardless of what happened before, because independent events don't influence each other's probabilities.

3. Misconception: "$P(A \mid B)$ and $P(B \mid A)$ are basically the same thing." Why it's wrong: These are different quantities that can have very different values — confusing them is called the "prosecutor's fallacy" and leads to serious real-world errors (e.g., in medical testing and legal reasoning). Correct: $P(A \mid B) = \dfrac{P(B \mid A) P(A)}{P(B)}$ (Bayes' theorem) — the two conditionals are related but not equal, and the difference depends on how common $A$ and $B$ are individually (their "priors").

Comparison and Connections

Concept	Mutually Exclusive	Independent	Conditional Probability
Formula	$P(A \cap B) = 0$	$P(A \cap B) = P(A)P(B)$	$P(A\mid B) = P(A\cap B)/P(B)$
Can both happen together?	Never	Yes, but unrelated	Depends on the relationship
Typical CS use	Modeling disjoint categories	Randomized algorithms, A/B testing	Spam filters, diagnosis, Bayesian inference

Practice Questions

Recall

1. What is the range of possible values for a probability? Answer: Between 0 and 1, inclusive, where 0 means impossible and 1 means certain.
2. What condition defines two events as mutually exclusive? Answer: They cannot occur at the same time, meaning $P(A \cap B) = 0$.

Understanding 3. Why can't two events with nonzero probability be both mutually exclusive and independent? Answer guidance: Independence requires $P(A \cap B) = P(A)P(B) > 0$ when both have positive probability, but mutual exclusivity requires $P(A \cap B) = 0$. These can't both be true unless at least one event has probability zero, so the two properties conflict for real, non-trivial events. 4. Why does Bayes' theorem require you to know the overall (prior) probability of the hypothesis, not just how well the evidence matches it? Answer guidance: Because a rare hypothesis needs much stronger evidence to become likely — even a good match to evidence isn't enough if the hypothesis was very unlikely to begin with. This is why the spam example only reaches 75% probability despite "free" being a fairly strong signal: legitimate email is common enough to still explain many "free" occurrences.

Application 5. A factory's rare defect rate is 1%. A test correctly flags defective items 95% of the time but also incorrectly flags 2% of good items. If an item is flagged, what's the probability it's actually defective? (Use Bayes' theorem.) Answer guidance: $P(\text{flag}) = (0.95)(0.01) + (0.02)(0.99) = 0.0095 + 0.0198 = 0.0293$. $P(\text{defective}\mid\text{flag}) = 0.0095/0.0293 \approx 0.324$, so only about 32% of flagged items are truly defective — a strong illustration of why rare conditions need very precise tests. 6. A weather Markov chain says if today is Rainy, tomorrow is Rainy with probability 0.5, Cloudy with 0.3, and Sunny with 0.2. If it's Rainy today, what's the probability it's still Rainy the day after tomorrow, considering only the path Rainy→Rainy→Rainy? Answer: $0.5 \times 0.5 = 0.25$ for that specific path (the true total would also need to sum other paths that return to Rainy).

Analysis 7. Compare using raw counting (favorable outcomes over total outcomes) versus Bayes' theorem to solve probability problems. When is each approach more appropriate? Answer guidance: Raw counting works well when outcomes are equally likely and the sample space is small and enumerable, like dice or cards. Bayes' theorem is necessary when you're updating a belief based on evidence and the relevant probabilities come from data or measurements rather than a symmetric sample space, such as medical tests or spam detection. 8. Explain why the "memoryless" property of Markov chains is both a simplifying assumption and a potential limitation when modeling real systems. Answer guidance: It simplifies computation because you only need the current state to predict the future, making the model tractable (matrix multiplication). But many real systems have genuine memory — for example, weather patterns or user behavior can depend on trends over several days, not just yesterday — so a plain Markov chain may lose predictive accuracy compared to models that consider longer history.

FAQ

Q: Why can probabilities never be negative or greater than 1? A: Probability is defined as a fraction of favorable outcomes over total outcomes (or a measure with the same normalization), and by construction that ratio is always between 0 and 1. A "probability" outside this range would mean something is more certain than certain, which is meaningless.

Q: What's the difference between a prior and a posterior probability in Bayes' theorem? A: The prior, $P(A)$, is your belief before seeing evidence. The posterior, $P(A \mid B)$, is your updated belief after seeing evidence $B$. Bayes' theorem is the formula that converts one into the other.

Q: Why do independence assumptions matter so much in machine learning? A: Many algorithms (like Naive Bayes classifiers) assume features are independent to make the math tractable, multiplying individual probabilities together. When that assumption is false in reality, the model's outputs can be biased, so it's important to know when independence is a simplification rather than a fact.

Q: How is a Markov chain different from ordinary conditional probability? A: Conditional probability describes a single relationship between two events. A Markov chain applies conditional probability repeatedly across a sequence of states, always conditioning only on the immediately preceding state.

Q: Do I need calculus to understand basic probability theory? A: No — for discrete events (dice, coins, categorical data) you only need arithmetic and the formulas covered here. Calculus becomes necessary once you move to continuous random variables and probability density functions.

Quick Revision

• Probability ranges from 0 (impossible) to 1 (certain); probabilities of all outcomes in a sample space sum to 1.
• Sample space = all possible outcomes; event = a subset of the sample space you care about.
• Mutually exclusive: $P(A \cap B) = 0$. Independent: $P(A \cap B) = P(A)P(B)$. These are different, often-confused ideas.
• Conditional probability: $P(A\mid B) = P(A \cap B)/P(B)$.
• Bayes' theorem: $P(A\mid B) = P(B\mid A)P(A)/P(B)$ — used to reverse a conditional probability.
• The gambler's fallacy wrongly assumes independent events "even out" in the short run.
• Bayes' theorem powers spam filters, medical diagnosis interpretation, and Bayesian machine learning.
• A Markov chain's next state depends only on the current state (the memoryless property).
• Transition matrices encode all state-to-state probabilities in a Markov chain.
• Google's PageRank models web navigation as a Markov chain over links.
• Complementary probability: $P(A^c) = 1 - P(A)$.

Related Topics

Prerequisites: Basic set theory, Matrices and Determinants, basic arithmetic with fractions

Related Topics: Combinatorics, statistical inference, machine learning classifiers (Naive Bayes)

Next Topics: Random Variables