Probability Basics

TL;DR

1. Conditional: $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$: restrict the world to $B$ and renormalize.
2. Joint → marginal → conditional: from a joint table $P(X=x,Y=y)$, the marginal is a row or column sum, the conditional is a cell divided by its row or column sum.
3. Product rule: $P(X=x,Y=y)=P(Y=y)P(X=x\mid Y=y)$ (prior times class conditional).
4. Total probability: $P(X=x)={\sum }_{y}P(X=x\mid Y=y)P(Y=y)$. Bayes: $P(Y=1\mid X=x)=\frac{P(X=x\mid Y=1)P(Y=1)}{P(X=x)}$.
5. Independence: $P(A\cap B)=P(A)P(B)$. Conditional independence $A\perp B\mid C$: independent once $C$ is known.
6. Union bound: $P(A_1\cup \cdots \cup A_k)\le {\sum }_{i}P(A_i)$, always true, no independence needed.

The course uses these rules from Lecture 1.1 on: the regression function $\eta (x)=P(Y=1\mid X=x)$ is a conditional probability, the Bayes classifier compares joint probabilities, and fairness criteria are conditional independence statements. (Source of the definitions: the course’s mathematical appendix.)

Events and the rules of probability

Probability space

• $\Omega$: the set of all elementary outcomes (“sample space”), e.g. $\{1,\dots ,6\}$ for a die.
• An event $A\subseteq \Omega$ is a set of outcomes, e.g. “even” $=\{2,4,6\}$.
• A probability measure $P$ assigns each event a number with $P(A)\ge 0$, $P(\Omega )=1$, and $P(A_1\cup A_2\cup \dots )={\sum }_{i}P(A_i)$ for disjoint events (Kolmogorov’s axioms).

Consequences you use all the time:

• $P(\text{not }A)=1-P(A)$.
• $P(A\cup B)=P(A)+P(B)-P(A\cap B)$.
• Die: $P(\{1,2,5\})=\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{1}{2}$.

Conditional probability

Conditional probability

The probability of $A$ given that $B$ has happened ($P(B)>0$):

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

Die: $P(\{3\}\mid \text{odd})=\frac{P(\{3\})}{P(\{1,3,5\})}=\frac{1/6}{1/2}=\frac{1}{3}$.

Memory aid

“Given $B$” means: throw away everything outside $B$, then rescale so that $B$ has probability 1. The bar $\mid$ is a “zoom in” on $B$.

Joint, marginal and conditional distributions

For two random variables $X$ and $Y$ (see Random Variables and Expectation):

Joint, marginal, conditional

• Joint: $P(X=x,Y=y)$, the probability that both happen. All joint probabilities sum to 1.
• Marginal: $P(X=x)={\sum }_{y}P(X=x,Y=y)$ (“sum out” the other variable). In the course the marginal of $X$ is often written $\mu (x)$.
• Conditional: $P(Y=y\mid X=x)=\frac{P(X=x,Y=y)}{P(X=x)}$.
• Product rule (the same formula read backwards): $P(X=x,Y=y)=P(X=x\mid Y=y)P(Y=y)$.

Worked example: from prior and class conditionals to the posterior

This is exactly the computation of the discrete-input Bayes task and of the mock exam. Given: $X\in \{0,1\}$, prior $P(Y=1)=0.4$ (so $P(Y=0)=0.6$), class conditionals $P(X=1\mid Y=1)=0.75$ and $P(X=1\mid Y=0)=0.25$.

Step 1: joint table with the product rule (prior times class conditional):

	$X=0$	$X=1$	row sum = prior
$Y=1$	$0.4\cdot 0.25=0.10$	$0.4\cdot 0.75=0.30$	$0.4$
$Y=0$	$0.6\cdot 0.75=0.45$	$0.6\cdot 0.25=0.15$	$0.6$
column sum = marginal $\mu (x)$	$0.55$	$0.45$	$1$

Step 2: marginal $\mu (x)=P(X=x)$: the column sums, $\mu (0)=0.55$, $\mu (1)=0.45$.

Step 3: conditional $\eta (x)=P(Y=1\mid X=x)$: the $Y=1$ cell divided by the column sum: $\eta (0)=0.10/0.55\approx 0.18$, $\eta (1)=0.30/0.45\approx 0.67$.

Step 4: use it. Bayes classifier for the 0-1 loss: predict 1 iff $\eta (x)\ge \frac{1}{2}$, so $f^{\ast }(0)=0$, $f^{\ast }(1)=1$. Bayes error: in every column take the smaller cell: $0.10+0.15=0.25$.

Memory aid: the table recipe

Rows = true class, columns = observed $x$. Fill the cells with prior × class conditional. Column sums are $\mu (x)$. $\eta (x)$ = upper cell / column sum. The Bayes classifier picks the larger cell in each column, and the Bayes error is the sum of the smaller cells.

Law of total probability and Bayes’ formula

Law of total probability

If $B_1,\dots ,B_k$ are disjoint and together cover $\Omega$:

$$P(A)=\sum _{i=1}^{k}P(A\cap B_i)=\sum _{i=1}^{k}P(A\mid B_i)P(B_i).$$

With $Y\in \{0,1\}$: $P(X=x)=P(X=x\mid Y=1){\pi }_1+P(X=x\mid Y=0){\pi }_0$. This is the denominator of Bayes’ formula.

Bayes' formula

$$P(B\mid A)=\frac{P(A\mid B)P(B)}{P(A)},$$ $$\eta (x)=P(Y=1\mid X=x)=\frac{{\pi }_{1}p(x\mid 1)}{{\pi }_{0}p(x\mid 0)+{\pi }_{1}p(x\mid 1)}.$$

With densities $p(x\mid y)$ instead of probabilities it works the same way. Prior $P(Y=1)$, likelihood $p(x\mid 1)$, posterior $P(Y=1\mid X=x)$.

Test for a rare disease (numbers from the math appendix)

1% of women have breast cancer ($B$). A mammography detects it with probability 0.8 ($P(A\mid B)$, true positive rate) and gives a false alarm with probability 0.096 ($P(A\mid \neg B)$). Total probability: $P(A)=0.8\cdot 0.01+0.096\cdot 0.99=0.103$. Bayes: $P(B\mid A)=\frac{0.8\cdot 0.01}{0.103}\approx 0.078$. A positive test means only about 8%: the prior is tiny.

Memory aid

Posterior ∝ prior × likelihood. Compare ${\pi }_{1}p(x\mid 1)$ with ${\pi }_{0}p(x\mid 0)$; the denominator is the same for both classes, so you only need it for the actual value of $\eta$, not for the decision. That is why the Bayes boundary is “where the weighted curves cross” (L1.1).

Independence and conditional independence

Independence

Events: $P(A\cap B)=P(A)P(B)$, equivalently $P(A\mid B)=P(A)$. Random variables: $P(X\in A,Y\in B)=P(X\in A)P(Y\in B)$ for all $A,B$; written $X\perp Y$.

Two coin tosses $X,Y$ are independent; the first toss $X$ and the sum $X+Y$ are not.

Conditional independence

$X$ and $Y$ are independent given $Z$, $X\perp Y\mid Z$, if

$$P(X\in A,Y\in B\mid Z\in C)=P(X\in A\mid Z\in C)\cdot P(Y\in B\mid Z\in C),$$

equivalently $P(X=x\mid Y=y,Z=z)=P(X=x\mid Z=z)$: once $Z$ is known, $Y$ tells nothing more about $X$.

Where it appears: i.i.d. training data (independent and identically distributed, L1.2); the fairness criteria $\hat{Y}\perp A$ (demographic parity), $\hat{Y}\perp A\mid Y$ (equalized odds), $Y\perp A\mid \hat{Y}$ (predictive parity) in L9.1; observational vs. interventional SHAP in L9.2.

Memory aid

Read "$\perp \mid Y$" as “within each group of $Y$“. $\hat{Y}\perp A\mid Y$: among the people with the same true label, the prediction does not depend on the group. That is why the TPR and FPR are computed inside the columns $Y=1$ and $Y=0$.

The union bound

Union bound

For any events $A_1,\dots ,A_k$:

$$P(A_1\cup \cdots \cup A_k)\le \sum _{i=1}^{k}P(A_i).$$

No independence needed. It is exact for disjoint events and loose when the events overlap (the overlap is counted several times).

Where it appears: the bound for finite function classes (“some $f$ out of $m$ is bad” has probability at most $m$ times the probability for one $f$, L3); the spikes of the minimum norm interpolator ($P(x\text{ in some spike})\le n\cdot P(\text{one spike})$, L8).

Memory aid

“At least one of them happens” → union bound: add up the single probabilities. The price is a factor $m$ (or $n$), which becomes $\log m$ after solving for $\epsilon$.

Self-check

Question cards (4)

$P(Y=1)=0.2$, $P(X=1\mid Y=1)=0.9$, $P(X=1\mid Y=0)=0.3$. Compute $P(X=1)$ and $\eta (1)$.

Answer

Joint cells: $0.2\cdot 0.9=0.18$ and $0.8\cdot 0.3=0.24$. $P(X=1)=0.42$, $\eta (1)=0.18/0.42\approx 0.43<0.5$: predict 0 at $x=1$.

In a joint table, how do you get a marginal and a conditional probability?

Answer

Marginal: sum over the other variable (row or column sum). Conditional: a cell divided by the sum of its row or column (the one you condition on).

What is the difference between $P(\hat{Y}=1\mid Y=1)$ and $P(Y=1\mid \hat{Y}=1)$?

Answer

The first conditions on the true label (TPR, within the column $Y=1$), the second on the prediction (PPV, within the row $\hat{Y}=1$). Bayes’ formula links them via the base rate.

Ten events each have probability 0.01. What can you say about the probability that at least one happens?

Answer

At most $10\cdot 0.01=0.1$ (union bound), whatever the dependence. If they were independent it would be $1-0.99^{10}\approx 0.096$.

Related

• Math overview · Random Variables and Expectation · Inequalities and Convergence