Probability¶
Agentic AI · Fundamentals
The discrete probability the course uses: sample space and events, random variables and their distributions, joint, marginal and conditional distributions, independence and conditional independence.
Overview¶
Probability assigns to every possible result of a random experiment a number between 0 and 1 that measures how likely the result is. The course needs it because a language model is a probability distribution over sequences of tokens, the units of text a model reads and writes, and because every evaluation result is an estimate computed from random outcomes.
| Section | The question it answers |
|---|---|
| Outcome, Event & Sample Space | What is a random experiment's set of possible results, and which rules does a probability obey? |
| Random Variables | How is a numerical value attached to each result of an experiment? |
| Discrete Probability Distributions | Which conditions must the probabilities of all values of a random variable satisfy? |
| Joint Distribution | What is the probability of a combination of values of two random variables? |
| Marginal & Independence | How is the distribution of one variable obtained from a joint distribution, and when are two variables independent? |
| Conditional Probability | How does the probability of an event change once another event is known to have occurred, and how does the chain rule factorise a joint distribution? |
| Conditional Independence | When do two variables become independent once a third is known, and how does the Markov assumption of a language model state such an independence? |
Method: derivation first, simulation second. Each rule is derived from the three axioms of probability and the definitions before it; a simulation of die rolls then checks it, by counting how often an event occurs. The code uses only NumPy and Matplotlib, and the fixed random seed makes every run print the same numbers.
What it builds on: the probability course of the first semesters; nothing here is new. The definitions follow Wasserman, 2004, Ch. 1–2. A longer review with exercises is http://christianherta.de/lehre/algorithmic-fundations-of-robotics-and-artifical-intelligence/math/probabilities.html.
Outcome, Event & Sample Space¶
- Outcome (elementary event): a single possible result of a random experiment.
- Die roll: one face, e.g. $3$.
- All outcomes form the sample space $\Omega=\{1,2,3,4,5,6\}$.
- Event: any subset of $\Omega$ — one outcome or a collection.
- e.g. "even" $=\{2,4,6\}$ or
- "greater than 4" $=\{5,6\}$.
Probability is a function $P$ that assigns a number to every event and satisfies three axioms (Wasserman, 2004, §1.2, Def. 1.5):
- $P(A) \ge 0$ for every event $A$;
- $P(\Omega) = 1$;
- for disjoint events $A_1, A_2, \dots$ (no two share an outcome), $P(A_1 \cup A_2 \cup \dots) = P(A_1) + P(A_2) + \dots$
The probability of an event is the sum of its outcome probabilities. An event $A$ is the union of the single-outcome events $\{\omega\}$, $\omega \in A$, and these are disjoint; axiom 3 gives
$$P(A) = P\Big(\bigcup_{\omega\in A}\{\omega\}\Big) = \sum_{\omega\in A} P(\{\omega\}) .$$
Fair die: the six faces have the same probability $q$. By axioms 2 and 3, $1 = P(\Omega) = \sum_{\omega=1}^{6} P(\{\omega\}) = 6q$, so $q = 1/6$ and $P(\text{even}) = P(\{2\}) + P(\{4\}) + P(\{6\}) = 3/6$.
The complement. An event $A$ and its complement $A^c = \Omega \setminus A$ are disjoint, and their union is $\Omega$; axioms 2 and 3 give $1 = P(A) + P(A^c)$, so $P(A^c) = 1 - P(A)$.
Simulation. A fair die is rolled 10 000 times. The relative frequency of each face — the number of rolls showing it divided by the number of rolls — is close to $1/6$, and the running relative frequency of the event even approaches $P(\text{even}) = 0.5$ as the number of rolls grows. The law of large numbers states this: the mean of $n$ independent repetitions approaches the expected value as $n$ grows (Wasserman, 2004, Thm. 5.6).
import numpy as np
from ipynb.fs.defs.plot_probability import plot_die_rolls # the figure; its code is in plot_probability.ipynb
rng = np.random.default_rng(0) # fixed seed: every run gives the same numbers
rolls = rng.integers(1, 7, size=10_000) # 10 000 rolls of a fair die, faces 1..6
faces = np.arange(1, 7)
freq = np.array([np.mean(rolls == f) for f in faces])
even = (rolls % 2 == 0) # the event "even" on each roll
running = np.cumsum(even) / np.arange(1, len(rolls) + 1)
plot_die_rolls(faces, freq, running)
Random Variables¶
A random variable is a function that assigns a numerical value to each outcome in the sample space (Wasserman, 2004, Def. 2.1). Random variables are denoted by capital letters, e.g. $X$ or $Y$; their values by lowercase letters, e.g. $x$.
Its set of possible values is written $\mathrm{Val}(X)$.
A value of a random variable is an event. $\{X = x\}$ is short for the set of outcomes that $X$ maps to $x$, $\{\omega \in \Omega : X(\omega) = x\}$, so $P(X{=}x)$ is the probability of an event and follows from the outcome probabilities.
Die example: let $X=1$ if the face is odd $\{1,3,5\}$, else $X=0$ (even).
- $P(X{=}1)=P(\{1,3,5\})=3/6=0.5$ and
- $P(X{=}0)=0.5$.
Notation ("abuse of notation"): a specific distribution is identified by its argument:
- $P(X)$ denotes the whole distribution of $X$ and
- $P(Y)$ that of $Y$;
$P(X{=}x)$ is a single number.
Short notation: $P(x)$ for $P(X{=}x)$ where it is not ambiguous.
Simulation. $X$ is applied to each simulated roll as a function, and the relative frequency of $X = 1$ is compared with $P(X{=}1) = 0.5$.
X = (rolls % 2 == 1).astype(int) # X(face) = 1 if the face is odd, else 0
print("first 10 faces:", rolls[:10])
print("X of these: ", X[:10])
print(f"relative frequency of X = 1: {X.mean():.4f} (P(X=1) = 0.5)")
Discrete Probability Distributions¶
A discrete probability distribution assigns a probability to every value of a discrete random variable, one that takes finitely or countably many values (Wasserman, 2004, Def. 2.9): $$P(X{=}x)\ge 0 \qquad\text{and}\qquad \sum_{x\in \mathrm{Val}(X)} P(X{=}x)=1.$$
Both properties follow from the axioms. $P(X{=}x) \ge 0$ is axiom 1. For two different values $x \ne x'$ the events $\{X=x\}$ and $\{X=x'\}$ are disjoint, because every outcome has exactly one value, and together they cover $\Omega$; axioms 3 and 2 give
$$\sum_{x\in \mathrm{Val}(X)} P(X{=}x) = P\Big(\bigcup_{x}\{X=x\}\Big) = P(\Omega) = 1 .$$
Example — the Bernoulli distribution. A random variable with the two values $1$ (success) and $0$ (failure) and $P(X{=}1)=p$, $P(X{=}0)=1-p$ is written $X\sim\text{Bernoulli}(p)$ (Wasserman, 2004, §2.3). The die variable of Random Variables is $\text{Bernoulli}(0.5)$.
Joint Distribution¶
A joint distribution gives the probability of combinations of values of two (or more) random variables (Wasserman, 2004, §2.5): $$ P(X=x, Y=y) \ge 0, \qquad \sum_{x}\sum_{y} P(X{=}x,\, Y{=}y) = 1. $$
Die example ($X$ odd/even, $Y=\mathbb{1}[\text{face}>3]$ — the indicator: $1$ if the face is greater than $3$, else $0$):
| $P(X,Y)$ | $Y{=}0\ (\le 3)$ | $Y{=}1\ (>3)$ |
|---|---|---|
| $X{=}1$ (odd) | $2/6$ | $1/6$ |
| $X{=}0$ (even) | $1/6$ | $2/6$ |
Each entry is the probability of an intersection of events. $\{X=x, Y=y\}$ is the event $\{X=x\} \cap \{Y=y\}$; for example $P(X{=}1, Y{=}0) = P(\{1,3,5\} \cap \{1,2,3\}) = P(\{1,3\}) = 2/6$. The four entries sum to 1 by the argument of Discrete Probability Distributions, applied to the pair $(X, Y)$.
It generalises to many variables: $P(X_1,\dots,X_n)$ — e.g. the probability of a whole sequence of outcomes, such as the tokens of a text.
Simulation. The joint distribution is estimated by counting: the share of rolls with each combination $(X{=}x, Y{=}y)$ is compared with the table.
Y = (rolls > 3).astype(int) # Y = 1 if the face is greater than 3
exact = np.array([[1/6, 2/6], # rows: X = 0 (even), X = 1 (odd); columns: Y = 0, Y = 1
[2/6, 1/6]])
joint = np.array([[np.mean((X == x) & (Y == y)) for y in (0, 1)] for x in (0, 1)])
print("estimated P(X=x, Y=y) exact")
for x in (0, 1):
print(f"X={x}: {joint[x, 0]:.4f} {joint[x, 1]:.4f} {exact[x, 0]:.4f} {exact[x, 1]:.4f}")
print(f"sum of the estimates: {joint.sum():.4f}")
Marginal & Independence¶
- Marginal: the distribution of one variable, recovered by summing the joint over the other
(Wasserman, 2004, Def. 2.23)
- $P(X)=\sum_y P(X,Y{=}y)$.
- Derivation: the events $\{X=x, Y=y\}$ for the different values $y$ are disjoint, and their union is $\{X = x\}$; axiom 3 gives $P(X{=}x) = \sum_y P(X{=}x, Y{=}y)$.
- Die example: $P(X{=}1)=2/6+1/6=1/2$.
- Independence: $P(X,Y)=P(X)\,P(Y)$ for all values (Wasserman, 2004, Def. 2.29) — the value of one
variable does not change the distribution of the other.
- Notation: $X \perp Y$
- Die example: $P(X{=}1,Y{=}1)=1/6$, but $P(X{=}1)\,P(Y{=}1)=1/2\cdot 1/2=1/4$, so $X$ and $Y$ are not independent.
Simulation. The marginals are the row and column sums of the estimated joint table. For $X$ and $Y$ of one die, the joint probability differs from the product of the marginals. For two separate dice — $X$ from the first, $Y$ from the second — the joint probability equals the product up to the sampling error.
P_X = joint.sum(axis=1) # marginal of X: sum over y
P_Y = joint.sum(axis=0) # marginal of Y: sum over x
print(f"one die: P(X=1, Y=1) = {joint[1, 1]:.4f} P(X=1) P(Y=1) = {P_X[1] * P_Y[1]:.4f}")
second = rng.integers(1, 7, size=len(rolls)) # a second, separate die
Y2 = (second > 3).astype(int)
print(f"two dice: P(X=1, Y=1) = {np.mean((X == 1) & (Y2 == 1)):.4f} "
f"P(X=1) P(Y=1) = {X.mean() * Y2.mean():.4f}")
Conditional Probability¶
$$ P(X\mid Y) = \frac{P(X, Y)}{P(Y)}, \qquad P(Y)>0 $$
"Probability of $X$ given $Y$" (Wasserman, 2004, Def. 1.12, Def. 2.35).
Conditioning restricts the sample space. Given $Y = y$, only the outcomes with $Y = y$ remain possible; dividing by $P(Y{=}y)$ rescales their probabilities so that they sum to 1 again.
Die example: $P(X{=}1\mid Y{=}1)=\dfrac{1/6}{1/2}=1/3$ — of the faces $4,5,6$ only $5$ is odd.
Independence. If $X \perp Y$, the definition of independence in the numerator gives
$$P(X \mid Y) = \frac{P(X)\,P(Y)}{P(Y)} = P(X)$$
(Wasserman, 2004, Lemma 1.14): knowing $Y$ does not change the distribution of $X$.
Product rule and chain rule. Multiplying the definition by $P(Y)$ gives the product rule $P(X, Y) = P(X \mid Y)\,P(Y)$. Applied to $X_n$ and the group $(X_1, \dots, X_{n-1})$, and then again to the group:
$$ \begin{aligned} P(X_1, \dots, X_n) &= P(X_n \mid X_1, \dots, X_{n-1})\,P(X_1, \dots, X_{n-1}) \\ &= P(X_n \mid X_1, \dots, X_{n-1})\,P(X_{n-1} \mid X_1, \dots, X_{n-2})\,P(X_1, \dots, X_{n-2}) \\ &= \dots = \prod_{i=1}^{n} P(X_i \mid X_1, \dots, X_{i-1}) . \end{aligned} $$
This chain rule holds for every joint distribution; a language model computes the probability of a text in this form, one token $X_i$ at a time given the tokens before it.
Simulation. $P(X{=}1 \mid Y{=}1)$ is estimated by keeping only the rolls with $Y = 1$ and counting the share of odd faces among them; the result is compared with $1/3$ and with the quotient $P(X{=}1, Y{=}1)/P(Y{=}1)$ of the estimated joint table.
kept = rolls[Y == 1] # only the rolls with face > 3
print(f"rolls kept: {len(kept)} of {len(rolls)}, faces {np.unique(kept)}")
print(f"share of odd faces among them: {np.mean(kept % 2 == 1):.4f} (P(X=1 | Y=1) = 1/3 = 0.3333)")
print(f"P(X=1, Y=1) / P(Y=1) from the joint table: {joint[1, 1] / P_Y[1]:.4f}")
Conditional Independence¶
$X$ is independent of $Y$ given $Z$ if $$P(X,Y \mid Z)=P(X \mid Z)\,P(Y\mid Z)$$ or, equivalently, $$P(X \mid Y,Z)=P(X \mid Z).$$
Notation: $X \perp Y \mid Z$ (Wasserman, 2004, Def. 17.1)
The two forms are equivalent. If $P(Y \mid Z) > 0$, the definition of conditional probability, applied twice, and the first form give
$$ \begin{aligned} P(X \mid Y, Z) &= \frac{P(X, Y, Z)}{P(Y, Z)} = \frac{P(X, Y \mid Z)\,P(Z)}{P(Y \mid Z)\,P(Z)} \\ &= \frac{P(X \mid Z)\,P(Y \mid Z)}{P(Y \mid Z)} = P(X \mid Z) . \end{aligned} $$
Read backwards, with the product rule $P(X, Y \mid Z) = P(X \mid Y, Z)\,P(Y \mid Z)$, the second form gives the first.
Once $Z$ is known, $Y$ carries no further information about $X$. The Markov assumption of a language model is a statement of this form: the next token is conditionally independent of the earlier tokens given the most recent ones. For a first-order Markov assumption, $X_i \perp (X_1, \dots, X_{i-2}) \mid X_{i-1}$, and every factor of the chain rule shortens:
$$P(X_1, \dots, X_n) = P(X_1)\prod_{i=2}^{n} P(X_i \mid X_{i-1}) .$$
Dependent, but conditionally independent. A coin $Z$ is chosen at random: with probability $1/2$ a fair coin ($Z = 0$, heads with probability $0.5$), with probability $1/2$ a biased coin ($Z = 1$, heads with probability $0.9$). The chosen coin is tossed twice; $X$ and $Y$ indicate heads on the first and on the second toss. Given $Z$, the two tosses are independent. Without $Z$, by the marginal and the product rule,
$$ \begin{aligned} P(X{=}1) &= \tfrac12\cdot 0.5 + \tfrac12\cdot 0.9 = 0.7 = P(Y{=}1), \\ P(X{=}1, Y{=}1) &= \tfrac12\cdot 0.5^2 + \tfrac12\cdot 0.9^2 = 0.53 \;\ne\; 0.7\cdot 0.7 = 0.49 . \end{aligned} $$
A head on the first toss makes the biased coin more likely and therefore a second head: $P(Y{=}1 \mid X{=}1) = 0.53/0.7 \approx 0.76 > 0.7$. $X$ and $Y$ are dependent, and $X \perp Y \mid Z$.
Simulation. 100 000 repetitions of the experiment estimate $P(X{=}1, Y{=}1)$ with and without conditioning on $Z$, and compare it with the product of the corresponding marginals.
reps = 100_000
Z = rng.integers(0, 2, size=reps) # 0 = fair coin, 1 = biased coin
heads = np.where(Z == 1, 0.9, 0.5) # probability of heads of the chosen coin
Xc = (rng.random(reps) < heads).astype(int) # first toss
Yc = (rng.random(reps) < heads).astype(int) # second toss, same coin
print(f"without Z: P(X=1, Y=1) = {np.mean(Xc & Yc):.4f} P(X=1) P(Y=1) = {Xc.mean() * Yc.mean():.4f}")
for z in (0, 1):
m = Z == z
print(f"given Z={z}: P(X=1, Y=1 | Z) = {np.mean(Xc[m] & Yc[m]):.4f} "
f"P(X=1 | Z) P(Y=1 | Z) = {Xc[m].mean() * Yc[m].mean():.4f}")
print(f"P(Y=1 | X=1) = {Yc[Xc == 1].mean():.4f} (derived: 0.53 / 0.7 = {0.53 / 0.7:.4f})")
References¶
Wasserman, Larry. All of Statistics: A Concise Course in Statistical Inference. Springer, 2004. doi:10.1007/978-0-387-21736-9. — sample space, events and probability (§1.2, Def. 1.5), conditional probability (Def. 1.12, Lemma 1.14), random variables and their distributions (Def. 2.1, Def. 2.9, §2.3, §2.5, Def. 2.23, Def. 2.29, Def. 2.35), conditional independence (Def. 17.1), the weak law of large numbers (Thm. 5.6).