Probability, conditional probability and Bayes theorem notes — Unit 1

Probability theory provides a rigorous mathematical framework for quantifying uncertainty, randomness, and incomplete information. In computer science, it forms the absolute bedrock of Machine Learning, Cryptography, and Randomized Algorithms.

⇒1.1 Basic Terminology

• Random Experiment: Any procedure that can be infinitely repeated and has a well-defined set of possible outcomes, but the exact outcome of a specific trial cannot be predicted with absolute certainty before execution. (e.g., Tossing a coin, measuring network latency).
• Sample Space ($S$ or $\Omega$): The set containing absolutely ALL possible outcomes of a random experiment.
  Example: Rolling a 6-sided die, $S = \{1, 2, 3, 4, 5, 6\}$.
• Event ($E$): Any subset of the Sample Space. An event "occurs" if the outcome of the experiment is an element of that subset.
  Example: Rolling an even number, $E = \{2, 4, 6\}$. Notice that $E \subseteq S$.

In 1933, Andrey Kolmogorov formalized probability theory using three fundamental mathematical axioms. Every other rule of probability is derived from these three.

⇒2.1 Kolmogorov's Three Axioms

Let $S$ be a sample space. A probability function $P(E)$ assigns a real number to every event $E \subseteq S$, such that:

• Axiom 1 (Non-negativity): For any event $E$, the probability is a non-negative real number.
  $P(E) \ge 0$
• Axiom 2 (Normalization): The probability of the entire sample space $S$ occurring is exactly 1 (100% certainty).
  $P(S) = 1$
• Axiom 3 (Additivity): If $E_1, E_2, E_3, ...$ are mutually exclusive (disjoint) events (meaning they can absolutely never happen at the same time, $E_i \cap E_j = \emptyset$), then the probability of their union is the sum of their individual probabilities.
  $P(E_1 \cup E_2 \cup ...) = P(E_1) + P(E_2) + ...$

⇒2.2 Derived Rules

From the axioms, we immediately prove:
- $P(\emptyset) = 0$ (The impossible event has 0 probability).
- $P(E^c) = 1 - P(E)$ (Complement Rule: The probability of $E$ NOT happening).
- $0 \le P(E) \le 1$ (Probabilities are strictly bounded between 0 and 1).

For experiments where every outcome in the sample space $S$ is Equally Likely (like rolling a fair die), computing probability reduces to simple counting.

$P(E) = \frac{\text{Number of outcomes in } E}{\text{Total number of outcomes in } S} = \frac{|E|}{|S|}$

To count large sets without manually listing them, we use combinatorics.

⇒3.1 Permutations (Order Matters)

The number of ways to arrange $r$ distinct objects selected from a set of $n$ distinct objects. A PIN code `1234` is different from `4321`.

$^nP_r = \frac{n!}{(n-r)!}$

⇒3.2 Combinations (Order Does NOT Matter)

The number of ways to simply choose a subset of $r$ objects from $n$ objects. A committee with Alice and Bob is the exact same committee as Bob and Alice.

$^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Axiom 3 works only for mutually exclusive events. What if two events can happen at the same time? (e.g., Drawing a card that is both a Heart AND a King).

⇒4.1 The Formula

For ANY two events $A$ and $B$, the probability of $A$ OR $B$ occurring is:

$P(A \cup B) = P(A) + P(B) - P(A \cap B)$

We must mathematically subtract the intersection $P(A \cap B)$ because those specific outcomes were counted twice (once when adding $P(A)$, and again when adding $P(B)$).

⇒4.2 Extension to Three Events

By the Principle of Inclusion-Exclusion:
$P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(B \cap C) - P(A \cap C) + P(A \cap B \cap C)$

Information changes probability. If I ask "What is the probability it will rain tomorrow?", the answer is different if I first tell you "It is currently completely overcast."

⇒5.1 The Definition

The conditional probability of Event $A$ occurring, GIVEN that we mathematically know Event $B$ has already occurred, is denoted as $P(A \mid B)$.

$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$, provided $P(B) > 0$

Intuition: Because we know $B$ occurred, the original massive sample space $S$ collapses. Event $B$ becomes our entirely new "universe" (the new denominator). We are only interested in the fraction of $B$ where $A$ also happens.

⇒5.2 The Multiplication Rule

By algebraically rearranging the formula, we can find the probability of both events happening together (the intersection):

$P(A \cap B) = P(A \mid B) \cdot P(B) = P(B \mid A) \cdot P(A)$

Two events are mathematically Independent if the occurrence (or non-occurrence) of one event has absolutely zero effect on the probability of the other event.

⇒6.1 Mathematical Definitions

Events $A$ and $B$ are independent if and only if:

• $P(A \mid B) = P(A)$ (Knowing B happened didn't change A's chance).
• $P(B \mid A) = P(B)$

Substituting this into the Multiplication Rule gives the ultimate test for independence:

$P(A \cap B) = P(A) \cdot P(B)$

If you multiply their individual probabilities and it equals the intersection probability, they are independent. If it doesn't, they are Dependent.

Example: Flipping a coin twice. The second flip has no physical memory of the first flip. They are independent.

Warning: Do NOT confuse Independent events with Mutually Exclusive events. They are completely different concepts. Mutually Exclusive events are highly dependent: if one happens, the other is 100% guaranteed NOT to happen.

Sometimes, calculating the probability of an event directly is too complex. We must divide and conquer by breaking the sample space into distinct, mutually exclusive scenarios (a Partition).

⇒7.1 The Partition

A set of events $B_1, B_2, ..., B_n$ forms a Partition of the sample space if:
1. They are mutually exclusive ($B_i \cap B_j = \emptyset$).
2. Together, they cover everything ($B_1 \cup B_2 \cup ... \cup B_n = S$).

⇒7.2 The Theorem

If we have a Partition, the total probability of any arbitrary Event $A$ is the weighted sum of its conditional probabilities under each scenario.

$P(A) = \sum_{i=1}^{n} P(A \mid B_i) \cdot P(B_i)$

Example Application: To find the probability a random student fails the course ($A$), we can partition the students into CS Majors ($B_1$) and Math Majors ($B_2$).
$P(\text{Fail}) = P(\text{Fail} \mid \text{CS})P(\text{CS}) + P(\text{Fail} \mid \text{Math})P(\text{Math})$.

Discovered by Reverend Thomas Bayes, this theorem is arguably the most important formula in all of Data Science and modern AI. It provides a mathematical mechanism to update our beliefs when we receive new evidence.

⇒8.1 The Inverse Probability Problem

Often, we know the forward probability $P(\text{Effect} \mid \text{Cause})$. Bayes' Theorem allows us to mathematically reverse this and calculate the backward probability $P(\text{Cause} \mid \text{Effect})$.

Let $H$ be a Hypothesis (e.g., "Patient has cancer").
Let $E$ be Evidence (e.g., "Test result is positive").

$P(H \mid E) = \frac{P(E \mid H) \cdot P(H)}{P(E)}$

Where:
- $P(H)$ (Prior): Our initial belief in the hypothesis before seeing any evidence. - $P(E \mid H)$ (Likelihood): The probability of seeing this exact evidence if the hypothesis is true. - $P(H \mid E)$ (Posterior): Our new, updated belief in the hypothesis *after* seeing the evidence. - $P(E)$ (Marginal): The total probability of seeing this evidence under any circumstances (calculated using the Law of Total Probability).

This classic example demonstrates why human intuition fails at probability.

⇒9.1 The Scenario

A rare disease affects 1% of the population. $P(D) = 0.01$.
A medical test is highly accurate:
- If you have the disease, it correctly tests positive 99% of the time. (True Positive: $P(pos \mid D) = 0.99$).
- If you are completely healthy, it falsely tests positive only 2% of the time. (False Positive: $P(pos \mid H) = 0.02$).

You take the test. It comes back POSITIVE. What is the actual mathematical probability that you have the disease? Most humans guess 90-99%.

⇒9.2 The Bayesian Calculation

We want $P(D \mid pos)$.

By Bayes' Theorem:
$P(D \mid pos) = \frac{P(pos \mid D) \cdot P(D)}{P(pos)}$

First, use Total Probability to find the denominator $P(pos)$:
$P(pos) = P(pos \mid D)P(D) + P(pos \mid H)P(H)$
$P(pos) = (0.99)(0.01) + (0.02)(0.99) = 0.0099 + 0.0198 = 0.0297$

Now apply Bayes:
$P(D \mid pos) = \frac{0.0099}{0.0297} \approx 0.333$

The result is exactly 33.3%. Even with a "99% accurate" test, a positive result means you most likely do NOT have the disease. This happens because the Base Rate (1% rarity) overwhelmingly outweighs the test accuracy. Algorithms must use Bayes' theorem to avoid this "Base Rate Fallacy".

In machine learning, we use Bayes' Theorem to classify data, such as determining if an email is Spam or Ham based on its words.

⇒10.1 The Model

We want to calculate $P(\text{Spam} \mid \text{Word}_1, \text{Word}_2, ...)$.

Applying Bayes':
$P(\text{Spam} \mid W_1, W_2...) \propto P(W_1, W_2... \mid \text{Spam}) \cdot P(\text{Spam})$

⇒10.2 The "Naïve" Assumption

Calculating the joint probability of 100 specific words appearing together is mathematically impossible without infinite training data.

To solve this, we make a "Naïve" assumption: We assume that the occurrence of every word is mathematically Independent of every other word, given the class.

This shatters the complex joint probability into simple multiplication:
$P(W_1, W_2... \mid \text{Spam}) = P(W_1 \mid \text{Spam}) \cdot P(W_2 \mid \text{Spam}) \cdot ...$

Even though this assumption is linguistically false (the word "bank" is obviously dependent on "account"), the resulting algorithm works incredibly well in practice and runs in linear time.

Unit 1 sets the axiomatic foundations. Mastery of Bayes' Theorem is absolute requirement for passing.

⇒11.1 University Exam Checklist

• State Kolmogorov's three axioms of probability.
• Use the General Addition Rule to solve problems involving overlapping events.
• Solve combinatorics problems using Permutations ($^nP_r$) and Combinations ($^nC_r$) to find probability.
• Write the formula for Conditional Probability $P(A \mid B)$.
• State the mathematical definition of Independent Events. Use it to prove whether two given events are independent.
• State the Law of Total Probability and use it to solve multi-stage experiment problems.
• Write the formula for Bayes' Theorem.
• Solve complex "Base Rate Fallacy" problems (like the medical test example or factory defect example) using a combination of Total Probability and Bayes' Theorem.
• Explain the concept and independence assumption behind the Naïve Bayes Classifier algorithm.