Probability Theory

A probability space is a triple $(\Omega, \mathcal{F}, P)$ where:

• $\Omega$ is the sample space (set of all possible outcomes).
• $\mathcal{F}$ is a sigma-algebra on $\Omega$.
• $P : \mathcal{F} \to [0, 1]$ is a probability measure.

Definition. A sigma-algebra $\mathcal{F}$ on $\Omega$ is a collection of subsets satisfying:

1. $\Omega \in \mathcal{F}$.
2. If $A \in \mathcal{F}$Then $A^c \in \mathcal{F}$ (closed under complementation).
3. If $A_1, A_2, \ldots \in \mathcal{F}$Then $\bigcup_{i=1}^{\infty} A_i \in \mathcal{F}$ (closed under countable unions).

Definition. A probability measure $P$ satisfies:

1. Non-negativity: $P(A) \geq 0$ for all $A \in \mathcal{F}$.
2. Normalisation: $P(\Omega) = 1$.
3. Countable additivity: If $A_1, A_2, \ldots$ are pairwise disjoint, then $P\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i)$.

Proposition 1.1. For any probability space:

1. $P(\emptyset) = 0$.
2. $P(A^c) = 1 - P(A)$.
3. If $A \subseteq B$Then $P(A) \leq P(B)$.
4. $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ (inclusion-exclusion).
5. Boole”s inequality: $P\left(\bigcup_{i=1}^{n} A_i\right) \leq \sum_{i=1}^{n} P(A_i)$.
6. Bonferroni inequality: $P\left(\bigcap_{i=1}^{n} A_i\right) \geq 1 - \sum_{i=1}^{n} (1 - P(A_i))$.

Proof. (1) Apply countable additivity to the disjoint union $\Omega = \Omega \cup \emptyset \cup \emptyset \cup \cdots$: $1 = 1 + P(\emptyset) + P(\emptyset) + \cdots$So $P(\emptyset) = 0$.

(3) $B = A \cup (B \setminus A)$ is a disjoint union, so $P(B) = P(A) + P(B \setminus A) \geq P(A)$.

(4) $P(A \cup B) = P(A) + P(B \setminus A) = P(A) + P(B) - P(A \cap B)$. $\blacksquare$

Definition. The conditional probability of $A$ given $B$ (with $P(B) > 0$) is

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

Theorem 1.2 (Law of Total Probability). If $B_1, \ldots, B_n$ form a partition of $\Omega$ with $P(B_i) > 0$ for all $i$Then

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

Theorem 1.3 (Bayes’ Theorem). Under the same conditions:

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

Definition. Events $A$ and $B$ are independent if $P(A \cap B) = P(A)\,P(B)$.

Proposition 1.4. If $A$ and $B$ are independent with $P(B) > 0$Then $P(A \mid B) = P(A)$.

Proof. $P(A \mid B) = P(A \cap B)/P(B) = P(A)P(B)/P(B) = P(A)$. $\blacksquare$

Definition. Events $A_1, \ldots, A_n$ are mutually independent if for every subset $J \subseteq \{1, \ldots, n\}$:

$P\left(\bigcap_{j \in J} A_j\right) = \prod_{j \in J} P(A_j)$

Pairwise independence does not imply mutual independence.

Definition. A random variable is a measurable function $X : \Omega \to \mathbb{R}$. The cumulative distribution function (CDF) of $X$ is

$F_X(x) = P(X \leq x)$

Proposition 2.1 (Properties of the CDF).

1. $F$ is non-decreasing: if $a \leq b$Then $F(a) \leq F(b)$.
2. $\lim_{x \to -\infty} F(x) = 0$ and $\lim_{x \to +\infty} F(x) = 1$.
3. $F$ is right-continuous: $\lim_{x \to a^+} F(x) = F(a)$.

Proof. (1) If $a \leq b$Then $\{X \leq a\} \subseteq \{X \leq b\}$So $F(a) = P(X \leq a) \leq P(X \leq b) = F(b)$ by Proposition 1.1(3).

(2) As $x \to -\infty$The events $\{X \leq x\}$ decrease to $\emptyset$So by continuity from above of probability measures, $F(x) \to 0$. As $x \to +\infty$The events increase to $\Omega$So $F(x) \to 1$.

(3) As $x \to a^+$The events $\{X \leq x\}$ decrease to $\{X \leq a\}$Giving right-continuity. $\blacksquare$

A random variable is discrete if its range is countable. The probability mass function (PMF) is $p_X(x) = P(X = x)$.

Definition (Expected Value). For a discrete random variable:

$E[X] = \sum_{x} x\, p_X(x)$

Provided the sum converges absolutely.

Definition (Variance). $\mathrm{Var}(X) = E[(X - \mu)^2] = E[X^2] - (E[X])^2$ where $\mu = E[X]$.

Proposition 2.2 (Linearity of Expectation). $E[aX + bY] = aE[X] + bE[Y]$ for any random variables $X$, $Y$ and constants $a$, $b$.

Proof. Direct computation from the definition of expected value. For the discrete case:

$E[aX + bY] = \sum_{x,y} (ax + by)\, p_{X,Y}(x,y) = a\sum_x x\, p_X(x) + b\sum_y y\, p_Y(y) = aE[X] + bE[Y]$

$\blacksquare$

A random variable is continuous if its CDF is absolutely continuous, i.e., there exists a probability density function (PDF) $f_X$ such that

$F_X(x) = \int_{-\infty}^{x} f_X(t)\, dt$

Key properties:

1. $f_X(x) \geq 0$ for all $x$.
2. $\int_{-\infty}^{\infty} f_X(x)\, dx = 1$.
3. $P(a \leq X \leq b) = \int_a^b f_X(x)\, dx$.
4. $P(X = a) = 0$ for any single point $a$.

Discrete distributions:

Continuous distributions:

Definition. $X \sim N(\mu, \sigma^2)$ if $X$ has PDF $f(x) = \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$.

Theorem 2.3 (Standardisation). If $X \sim N(\mu, \sigma^2)$Then $Z = (X - \mu)/\sigma \sim N(0, 1)$.

Proof. The CDF of $Z$: $P(Z \leq z) = P(X \leq \mu + \sigma z) = \int_{-\infty}^{\mu + \sigma z} \frac{1}{\sigma\sqrt{2\pi}} e^{-t^2/2}\, dt$. Substituting $u = (t - \mu)/\sigma$: $= \int_{-\infty}^{z} \frac{1}{\sqrt{2\pi}} e^{-u^2/2}\, du$Which is the CDF of $N(0, 1)$. $\blacksquare$

Theorem 2.4 (Moment Generating Function). If $X \sim N(\mu, \sigma^2)$Then

$M_X(t) = E[e^{tX}] = \exp\left(\mu t + \frac{\sigma^2 t^2}{2}\right)$

Proof. $M_X(t) = \int_{-\infty}^{\infty} e^{tx} \frac{1}{\sigma\sqrt{2\pi}} e^{-(x-\mu)^2/(2\sigma^2)}\, dx$. Completing the square in the exponent and evaluating the Gaussian integral gives the result. $\blacksquare$

Definition. The moment generating function (MGF) of $X$ is $M_X(t) = E[e^{tX}]$ (when it exists in a neighbourhood of $t = 0$).

Theorem 2.5. If the MGF exists in a neighbourhood of 0, it uniquely determines the distribution. Furthermore, $E[X^n] = M_X^{(n)}(0)$.

Problem. Let $X \sim \mathrm{Poisson}(3)$ and $Y \sim \mathrm{Poisson}(5)$ be independent. Find the distribution of $X + Y$.

Definition. The joint CDF of $(X, Y)$ is $F_{X,Y}(x, y) = P(X \leq x, Y \leq y)$.

Definition. The joint PDF (for continuous random variables) is $f_{X,Y}(x, y) \geq 0$ such that

$F_{X,Y}(x, y) = \int_{-\infty}^{x}\int_{-\infty}^{y} f_{X,Y}(u, v)\, du\, dv$

Definition. The marginal PDF of $X$ is $f_X(x) = \int_{-\infty}^{\infty} f_{X,Y}(x, y)\, dy$.

Definition. The covariance of $X$ and $Y$ is

$\mathrm{Cov}(X, Y) = E[(X - E[X])(Y - E[Y])] = E[XY] - E[X]E[Y]$

Proposition 2.6. $\mathrm{Cov}(X, Y) = \mathrm{Cov}(Y, X)$ and $\mathrm{Cov}(aX + b, cY + d) = ac\,\mathrm{Cov}(X, Y)$.

Definition. The correlation coefficient is

$\rho(X, Y) = \frac{\mathrm{Cov}(X, Y)}{\sqrt{\mathrm{Var}(X)\,\mathrm{Var}(Y)}}$

Theorem 2.7 (Cauchy—Schwarz for Random Variables). $|\rho(X, Y)| \leq 1$With equality if and only if $Y = aX + b$ almost surely for some $a, b$.

Definition. $X$ and $Y$ are independent if $F_{X,Y}(x, y) = F_X(x)\, F_Y(y)$ for all $x, y$.

For continuous random variables, this is equivalent to $f_{X,Y}(x, y) = f_X(x)\, f_Y(y)$.

Proposition 2.8. If $X$ and $Y$ are independent, then $\mathrm{Cov}(X, Y) = 0$. The converse is false.

Theorem 4.1 (Weak Law of Large Numbers). Let $X_1, X_2, \ldots$ be i.i.d. With $E[X_i] = \mu$ and $\mathrm{Var}(X_i) = \sigma^2 < \infty$. Then for every $\varepsilon > 0$:

$\lim_{n \to \infty} P\left(\left|\frac{1}{n}\sum_{i=1}^{n} X_i - \mu\right| \geq \varepsilon\right) = 0$

Proof. Let $S_n = \frac{1}{n}\sum_{i=1}^{n} X_i$. Then $E[S_n] = \mu$ and $\mathrm{Var}(S_n) = \sigma^2/n$. By Chebyshev’s inequality:

$P(|S_n - \mu| \geq \varepsilon) \leq \frac{\mathrm{Var}(S_n)}{\varepsilon^2} = \frac{\sigma^2}{n\varepsilon^2} \to 0 \quad \mathrm{as\ } n \to \infty$

$\blacksquare$

Theorem 4.2 (Strong Law of Large Numbers). Under the same conditions:

$P\left(\lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n} X_i = \mu\right) = 1$

The sample mean converges to the population mean almost surely.

Theorem 4.3 (Central Limit Theorem). Let $X_1, X_2, \ldots$ be i.i.d. With $E[X_i] = \mu$ and $\mathrm{Var}(X_i) = \sigma^2 \in (0, \infty)$. Then

$\frac{S_n - n\mu}{\sigma\sqrt{n}} \xrightarrow{d} N(0, 1)$

Where $S_n = \sum_{i=1}^{n} X_i$ and $\xrightarrow{d}$ denotes convergence in distribution.

Equivalently, for large $n$:

$P\left(\frac{S_n - n\mu}{\sigma\sqrt{n}} \leq z\right) \approx \Phi(z)$

Where $\Phi$ is the CDF of the standard normal.

Proof (using characteristic functions). Let $\varphi_X(t) = E[e^{itX}]$ be the characteristic function of $X_1$. The characteristic function of $(S_n - n\mu)/(\sigma\sqrt{n})$ is:

$\varphi_n(t) = \left[\varphi_X\left(\frac{t}{\sigma\sqrt{n}}\right)\right]^n \cdot e^{-it\sqrt{n}\mu/\sigma}$

Expanding $\varphi_X$ around 0: $\varphi_X(s) = 1 + i\mu s - \frac{(\sigma^2 + \mu^2)s^2}{2} + o(s^2)$. Substituting $s = t/(\sigma\sqrt{n})$:

$\varphi_n(t) = \left[1 + \frac{i\mu t}{\sigma\sqrt{n}} - \frac{(\sigma^2 + \mu^2)t^2}{2\sigma^2 n} + o\left(\frac{1}{n}\right)\right]^n \cdot e^{-it\sqrt{n}\mu/\sigma}$

Using $\lim_{n \to \infty}(1 + a_n/n)^n = e^{\lim a_n}$:

$\lim_{n \to \infty} \varphi_n(t) = \exp\left(\frac{i\mu t}{\sigma} - \frac{(\sigma^2 + \mu^2)t^2}{2\sigma^2}\right) \cdot \exp\left(-\frac{i\mu t}{\sigma}\right) = e^{-t^2/2}$

This is the characteristic function of $N(0, 1)$. By Levy’s continuity theorem, the convergence in distribution follows. $\blacksquare$

Problem. A fair die is rolled 100 times. Approximate the probability that the sum exceeds 370.

• The CLT does not apply to small samples. The CLT is an asymptotic result. For small $n$ ( $n < 30$), the normal approximation can be poor unless the underlying distribution is already close to normal. Use the Berry—Esseen theorem for finite-sample bounds.
• Independence is critical for the LLN and CLT. If the $X_i$ are dependent, the sample mean may not converge to the population mean, or the convergence rate may differ. For stationary sequences with weak dependence, versions of these theorems still hold, but the proofs are more involved.
• Convergence in distribution is weaker than convergence in probability. The CLT gives convergence in distribution of the standardised sum, not convergence of the sum itself. The LLN gives the latter (convergence in probability).

Theorem 5.1 (CDF Method). If $Y = g(X)$ and $g$ is monotone, then

$F_Y(y) = P(g(X) \leq y) = \begin{cases} F_X(g^{-1}(y)) & \text{if} g \text{ is} increasing \\ 1 - F_X(g^{-1}(y)) & \text{if} g \text{ is} decreasing \end{cases}$

Theorem 5.2 (Change of Variables). If $Y = g(X)$ where $g$ is differentiable and strictly monotone, then

$f_Y(y) = f_X(g^{-1}(y)) \cdot \left|\frac{d}{dy} g^{-1}(y)\right|$

Theorem 5.3. If $X$ and $Y$ are independent continuous random variables, the PDF of $Z = X + Y$ is

$f_Z(z) = (f_X * f_Y)(z) = \int_{-\infty}^{\infty} f_X(x)\, f_Y(z - x)\, dx$

Proof. $F_Z(z) = P(X + Y \leq z) = \iint_{x+y \leq z} f_{X,Y}(x, y)\, dx\, dy = \int_{-\infty}^{\infty} f_X(x)\left[\int_{-\infty}^{z-x} f_Y(y)\, dy\right] dx = \int_{-\infty}^{\infty} f_X(x)\, F_Y(z - x)\, dx$.

Differentiating: $f_Z(z) = \int_{-\infty}^{\infty} f_X(x)\, f_Y(z - x)\, dx$. $\blacksquare$

Corollary 5.4. The sum of independent normals is normal: if $X \sim N(\mu_1, \sigma_1^2)$ and $Y \sim N(\mu_2, \sigma_2^2)$ are independent, then $X + Y \sim N(\mu_1 + \mu_2, \sigma_1^2 + \sigma_2^2)$.

Proof. The convolution of two Gaussian PDFs is Gaussian. This follows from the MGF: $M_{X+Y}(t) = M_X(t)M_Y(t) = \exp((\mu_1 + \mu_2)t + (\sigma_1^2 + \sigma_2^2)t^2/2)$Which is the MGF of $N(\mu_1 + \mu_2, \sigma_1^2 + \sigma_2^2)$. $\blacksquare$

1. Dropping negative signs during algebraic manipulation. Substitute back to verify your answer.

2. Misreading the question, particularly with ‘hence’ vs ‘hence or otherwise’. The former requires using previous work.

3. Confusing the domain and range of functions, or not considering restrictions (e.g., denominator cannot be zero).

4. Confusing $P(A|B)$ with $P(B|A)$. These are related by Bayes’ theorem but are not equal in general.

Problem. Factory A produces 60% of items and factory B produces 40%. Defect rates are 2% and 5% respectively. Find the probability a randomly selected item is defective.

Solution. $P(D) = P(D|A)P(A) + P(D|B)P(B) = 0.02 \times 0.6 + 0.05 \times 0.4 = 0.012 + 0.020 = 0.032$.

Given a defective item, $P(A|D) = \frac{0.012}{0.032} = 0.375$ (Bayes’ theorem).

$\blacksquare$

Problem. A fair coin is tossed until the first head appears. Find the expected number of tosses using the probability generating function.

Solution. $X \sim \text{Geo}(p = 0.5)$. $P(X = k) = 0.5^k$ for $k = 1, 2, \ldots$

PGF: $G(s) = \sum_{k=1}^{\infty} 0.5^k s^k = \frac{0.5s}{1 - 0.5s}$.

$E(X) = G'(1) = \frac{0.5}{(1-0.5)^2} = \frac{0.5}{0.25} = 2$.

$\blacksquare$

• Sample spaces, events, and sigma-algebras provide the rigorous foundation for probability theory.
• Random variables: discrete (PMF) and continuous (PDF); CDF $F(x) = P(X \leq x)$.
• Expectation: $E(X) = \sum x \cdot P(X=x)$ or $\int x f(x)\,dx$; linearity $E(aX + bY) = aE(X) + bE(Y)$.
• Variance: $\text{Var}(X) = E(X^2) - [E(X)]^2$; $\text{Var}(aX + b) = a^2\text{Var}(X)$.
• Generating functions (PGF, MGF) encode distribution information; moments obtained by differentiation at specific points.