KindiakMath

Category: Probability

The Real Standard Deviation
In high school, the standard deviation $\sigma$ of a dataset $(x_1,\dots, x_n)$ is usually introduced informally as information about the spread of the dataset, quantified through the unwieldy formula

$\displaystyle \sigma = \sqrt{\frac{\Sigma fx^2}{\Sigma f} - \left( \frac{\Sigma fx}{\Sigma f} \right)^2} = \frac 1n \cdot \sqrt{\Sigma x^2 - \frac{\left( \Sigma x \right)^2}{n}}.$

Today, we will approach the standard deviation from far more intuitive perspective, and recover the above formula as a special case. Its cousin $\sigma^2$ is called the variance and is of greater mathematical interest.

We first define the covariance between two random variables $X, Y$ , assuming all quantities exist. Intuitively, it should measure the overall deviation of some kind between $X$ and its expectation $\mathbb E[X]$ ,

Definition 1. The covariance of $X, Y$ , denoted $\mathrm{Cov}(X,Y)$ , is defined by

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

Lemma 1. By expectation properties, we obtain

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

Proof. Expanding within the expectation,

$\begin{aligned}(X - \mathbb E[X]) \cdot (Y - \mathbb E[Y]) &= XY - \mathbb E[X] \cdot Y - \mathbb E[Y] \cdot X + \mathbb E[X] \cdot \mathbb E[Y].\end{aligned}$

Applying the linearity of $\mathbb E[\cdot]$ (we will formally justify this in measure theory),

$\begin{aligned} \mathrm{Cov}(X, Y) &= \mathbb E[(X - \mathbb E[X]) \cdot (Y - \mathbb E[Y])] \\ &=\mathbb E[XY - \mathbb E[X] \cdot Y - \mathbb E[Y] \cdot X + \mathbb E[X] \cdot \mathbb E[Y]] \\ &= \mathbb E[XY] - \mathbb E[\mathbb E[X] \cdot Y] - \mathbb E[\mathbb E[Y] \cdot X] + \mathbb E[\mathbb E[X] \cdot \mathbb E[Y]] \\ &= \mathbb E[XY] - \mathbb E[X] \cdot \mathbb E[Y] - \mathbb E[Y] \cdot \mathbb E[X] + \mathbb E[X] \cdot \mathbb E[Y] \cdot \mathbb E[1] \\ &= \mathbb E[XY] - \mathbb E[X] \cdot \mathbb E[Y]. \end{aligned}$

Lemma 2. The covariance satisfies the following properties:
- $\mathrm{Cov}(X, X) \geq 0$ ,
- $\mathrm{Cov}(X, X) = 0$ if and only if $X = \mathbb E[X]$ ,
- $\mathrm{Cov}(X, Y) = \mathrm{Cov}(Y,X)$ ,
- $\mathrm{Cov}(kX, Y) = k \cdot \mathrm{Cov}(Y,X)$ for $k \in \mathbb Z$ ,
- $\mathrm{Cov}(W+X, Y) = \mathrm{Cov}(W,X) + \mathrm{Cov}(W, Y)$ .
Proof. We prove the fourth property to illustrate:

$\begin{aligned}\mathrm{Cov}(W+X, Y) &= \mathbb E[(W+X)Y] - \mathbb E[W+X] \cdot \mathbb E[Y] \\ &= \mathbb E[WY+XY] - (\mathbb E[W]+\mathbb E[X]) \cdot \mathbb E[Y] \\ &= \mathbb E[WY]+\mathbb E[XY] - (\mathbb E[W] \cdot \mathbb E[Y]+\mathbb E[X] \cdot \mathbb E[Y]) \\ &= \mathbb E[WY] - \mathbb E[W] \cdot \mathbb E[Y] +\mathbb E[XY] - \mathbb E[X] \cdot \mathbb E[Y] \\ &= \mathrm{Cov}(W,Y) + \mathrm{Cov}(X,Y). \end{aligned}$

It is similar to the properties of an inner product, but not exactly, since the second property should require $X = 0$ , rather than just $X$ being a constant. To make such an assertion and more requires technical qualifiers addressed in measure theory. Lemma 2 outlines the main (practical) properties that we need from the covariance.

Lemma 3. Given any constant $k$ , $\mathrm{Cov}(X + k, Y) = \mathrm{Cov}(X, Y)$ .

Proof. By Lemma 2, it suffices to prove that $\mathrm{Cov}(k, Y) = 0$ :

$\mathrm{Cov}(k, Y) = \mathbb E[k Y] - \mathbb E[k] \cdot \mathbb E[Y] = k \cdot \mathbb E[Y] - k \cdot \mathbb E[Y] = 0.$

Lemma 4. For any random variable $X$ , define its variance

$\mathrm{Var}(X) := \mathrm{Cov}(X,X) = \mathbb E[X^2] - \mathbb E[X]^2$

whenever the right-hand side exists. Then $\mathrm{Var}(kX) = k^2 \cdot \mathrm{Var}(X)$ for $k \in \mathbb Z$ .

Proof. We have

$\begin{aligned}\mathrm{Var}(kX) &= \mathrm{Cov}(kX,kX) = k \cdot k \cdot \mathrm{Cov}(X,X) = k^2 \cdot \mathrm{Var}(X). \end{aligned}$

Lemma 5. Denote $\mu_X := \mathbb E[X]$ . Define the standard deviation of $X$ by $\sigma_X := \sqrt{\mathrm{Var}(X)}$ . Define the centered random variable $\hat X := (X - \mu_X)/\sigma_X$ whenever $\sigma_X \neq 0$ . Then $\mathrm{Var}(\hat X) = 1$ .

Proof. By Lemma 2,

$\begin{aligned} \mathrm{Var}(\hat X) &= \mathrm{Cov}(\hat X, \hat X) \\ &= \mathrm{Cov}\left( \frac{ X - \mu_X }{\sigma_X}, \frac{ X - \mu_X }{\sigma_X} \right) \\ &= \frac{1}{\sigma_X^2} \cdot \mathrm{Cov}(X- \mu_X, X- \mu_X) \\ &= \frac{1}{\sigma_X^2} \cdot \mathrm{Cov}(X, X) = \frac{1}{\mathrm{Var}(X)} \cdot \mathrm{Var}(X) = 1.\end{aligned}$

The covariance helps us measure the correlation between the random variables, which we formally define below.

Definition 2. The correlation between $X, Y$ with nonzero variances is defined by

$\displaystyle \rho(X, Y) := \mathrm{Cov}(\hat X, \hat Y) \equiv \frac{\mathrm{Cov}(X, Y)}{\sqrt{\mathrm{Var}(X)} \cdot \sqrt{\mathrm{Var}(Y)}}.$

Corollary 1. Given the dataset $( (x_1,y_1),\dots,(x_n,y_n))$ equipped with the uniform distribution, define the discrete random variables $X$ and $Y$ by $X((x_i,y_i)) = x_i$ and $Y((x_i,y_i)) = y_i$ . Then $X,Y$ follow uniform distributions on the datasets $(x_1,\dots,x_n)$ and $(y_1,\dots,y_n)$ respectively, and

$\displaystyle \mathrm{Cov}(X,Y) = \frac{ 1 }{n} \cdot \sum_{i=1}^n (x_i - \bar x)(y_i - \bar y) = \frac{ 1 }{n} \cdot \sum_{i=1}^n x_i y_i - \frac{ 1 }{n^2} \cdot \sum_{i=1}^n x_i \cdot \sum_{i=1}^n y_i,$

where $\bar x := (x_1+\dots+x_n)/n$ . When there is no confusion, we suppress the indices and write

$\displaystyle \mathrm{Cov}(X,Y) = \frac 1n \cdot \Sigma (x - \bar x)(y - \bar y) = \frac{\Sigma x y}{n} - \frac{ \Sigma x \Sigma y }{n^2} .$

for brevity.

Proof. By an equivalent definition for expectation,

$\begin{aligned} \mathbb E[XY] &= \sum_{\omega \in \Omega} X(\omega) \cdot Y(\omega) \cdot \mathbb P(\{\omega\}) \\ &= \sum_{i=1}^n x_i \cdot y_i \cdot \frac 1n = \frac{ 1 }{n} \sum_{i=1}^n x_i y_i. \end{aligned}$

The other quantities can be computed in a similar manner.

Corollary 2. Setting $Y=X$ in Corollary 1, we obtain

$\displaystyle \mathrm{Var}(X) = \frac{ \Sigma (x - \bar x)^2 }{n} = \frac{\Sigma x^2}{n} - \left( \frac{ \Sigma x }{n} \right)^2.$

Furthermore, combining Definition 2 and Corollaries 1 and 2, the product moment correlation coefficient $r := \rho(X, Y)$ is computed via

$\begin{aligned} r &= \frac{\Sigma (x - \bar x)(y - \bar y)}{\sqrt{ \Sigma (x - \bar x)^2 } \sqrt{ \Sigma (y - \bar y)^2 } } = \frac{ \Sigma x y - \frac{ \Sigma x \Sigma y }{ n }}{\sqrt{ \Sigma x^2 - \frac{ (\Sigma x)^2 }{n} } \sqrt{ \Sigma y^2 - \frac{ (\Sigma y)^2 }{n} }}. \end{aligned}$

Finally,

$\displaystyle \sigma_X = \sqrt{\frac{\Sigma x^2}{n} - \left( \frac{ \Sigma x }{n} \right)^2} = \frac 1n \cdot \sqrt{ \Sigma x^2 - \frac{ ( \Sigma x )^2 }{n} }.$

Given two random variables $X, Y$ , we know that $\mathbb E[X+Y] = \mathbb E[X] + \mathbb E[Y]$ . What can we deduce about $\mathrm{Var}(X + Y)$ ? Interpreting the variance as the covariance with itself and applying covariance properties (where most of the action happens),

$\begin{aligned}\mathrm{Var}(X+Y) &= \mathrm{Cov}(X+Y, X+Y) \\ &= \mathrm{Cov}(X,X) + \mathrm{Cov}(X,Y) + \mathrm{Cov}(Y,X) + \mathrm{Cov}(Y,Y) \\ &= \mathrm{Cov}(X,X) + \mathrm{Cov}(Y,Y) + 2\cdot \mathrm{Cov}(X,Y) \\ &= \mathrm{Var}(X) + \mathrm{Var}(Y) + 2 \cdot \mathrm{Cov}(X,Y).\end{aligned}$

So it’s not as simple as $\mathrm{Var}(X + Y) = \mathrm{Var}(X) + \mathrm{Var}(Y)$ ; there’s an extra term involving $\mathrm{Cov}(X,Y)$ . However, the equality does hold if $\mathrm{Cov}(X,Y) = 0$ . In this case, we call $X$ and $Y$ uncorrelated. Equivalently,

$\mathbb E[XY] = \mathbb E[X] \cdot \mathbb E[Y].$

Lemma 6. If $X, Y$ are independent, then $X$ and $Y$ are uncorrelated. In particular,

$\mathrm{Var}(X + Y) = \mathrm{Var}(X) + \mathrm{Var}(Y).$

Proof. By definition, since $X,Y$ are independent,

$\begin{aligned} \mathbb E[XY] &= \sum_{x \in \mathbb Z} \sum_{y \in \mathbb Z} xy \cdot \mathbb P_{X,Y}(x,y) \\ &= \sum_{x \in \mathbb Z} \sum_{y \in \mathbb Z} x \cdot y \cdot \mathbb P_X(x) \cdot \mathbb P_Y(y) \\ &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) \cdot \sum_{y \in \mathbb Z} y \cdot \mathbb P_Y(y) = \mathbb E[X] \cdot \mathbb E[Y]. \end{aligned}$

Therefore, we recover the core variance properties of interest.

Theorem 1. If $X, Y$ are independent random variables, then

$\mathrm{Var}(X \pm Y) = \mathrm{Var}(X) + \mathrm{Var}(Y).$

Proof. For the minus case,

$\begin{aligned} \mathrm{Var}(X - Y) &= \mathrm{Var}(X + (-Y)) \\ &= \mathrm{Var}(X) + \mathrm{Var}(-Y) \\ &= \mathrm{Var}(X) + (-1)^2 \cdot \mathrm{Var}(Y) \\ &= \mathrm{Var}(X) + \mathrm{Var}(Y). \end{aligned}$

Example 1. For any $\xi \sim \mathrm{Ber}(p)$ , $\mathrm{Var}( \xi) = p(1-p)$ . Likewise, for $X \sim \mathrm{Bin}(p)$ , $\mathrm{Var}(X) = np(1-p)$ .

Proof. We observe that $\xi^2 \sim \mathrm{Ber}(p)$ so that

$\mathrm{Var}( \xi) = \mathbb E[ \xi^2] - \mathbb E[ \xi]^2 = p - p^2 = p(1-p).$

Writing $X = \sum_{i=1}^n \xi_i$ for i.i.d. $\xi_i \sim \mathrm{Ber}(p)$ ,

$\displaystyle \mathrm{Var}(X) = \mathrm{Var}\left( \sum_{i=1}^n \xi_i \right) = \sum_{i=1}^n \mathrm{Var}(\xi_i) = \sum_{i=1}^n p(1-p) = np(1-p).$

Example 2. Let $X_1,\dots, X_n$ be i.i.d. with mean $\mu$ and variance $\sigma^2$ . Define the sample mean by

$\displaystyle \bar X_n := \frac{X_1+ \cdots + X_n}{n}.$

Then $\mathbb E[\bar X_n] = \mu$ and $\mathrm{Var}(\bar X_n) = \sigma^2/n$ .

Thus, at least intuitively, we should get $\mathrm{Var}(\bar X_n) \to 0$ as $n \to \infty$ , so that $\bar X_n \to \mu$ . We can formalise this idea as follows.

Lemma 7. For any $Y \geq 0$ and $\delta > 0$ ,

$\displaystyle \mathbb P(Y \geq \delta) \leq \frac{ \mathbb E[Y] }{ \delta }.$

This result is known as Markov’s inequality.

Proof. For any $Y \geq 0$ , we first note that for $\delta > 0$ ,

$\begin{aligned} \mathbb E[Y] &= \sum_{y \in \mathbb Z} y \cdot \mathbb P_Y(y) \\ &= \sum_{y < \delta} y \cdot \mathbb P_Y(y) + \sum_{y \geq \delta} y \cdot \mathbb P_Y(y) \\ &\geq \sum_{y < \delta} 0 \cdot \mathbb P_Y(y) + \sum_{y \geq \delta} \delta \cdot \mathbb P_Y(y) \\ &= \delta \cdot \sum_{y \geq \delta} \mathbb P_Y(y) = \delta \cdot \mathbb P(Y \geq \delta). \end{aligned}$

Hence, $\mathbb P(Y \geq \delta) \leq \mathbb E[Y]/\delta$ .

Lemma 8. For any random variable $X$ with mean $\mu$ and variance $\sigma^2$ and $\delta > 0$ ,

$\displaystyle \mathbb P(|X - \mu| \geq \delta) \leq \frac{ \sigma^2 }{ \delta^2 }.$

This result is known as Chebychev’s inequality.

Proof. Setting $Y := |X - \mu|^2 \geq 0$ and applying Markov’s inequality, since $\mathbb E[Y] = \mathrm{Var}(X) = \sigma^2$ ,

$\begin{aligned}\mathbb P(|X - \mu| \geq \delta) &= \mathbb P(|X - \mu|^2 \geq \delta^2) = \mathbb P(Y \geq \delta^2) \leq \frac{\mathbb E[Y]}{\delta^2} = \frac{\sigma^2}{\delta^2}.\end{aligned}$

Theorem 2. Fix $\epsilon > 0$ and a distribution $\nu$ with mean $\mu$ and variance $\sigma^2$ . Then for i.i.d. random variables $X_1,\dots, X_n \sim \nu$ ,

$\displaystyle \mathbb P(|\bar X_n - \mu| > \epsilon) \leq \frac{\sigma^2}{n \cdot \epsilon^2}.$

Hence, with more technical caveats, we can conclude that

$\displaystyle \lim_{n \to \infty} \mathbb P(|\bar X_n - \mu| > \epsilon) = 0.$

This result is known as the weak law of large numbers.

Proof. Applying Chebychev’s inequality.,

$\begin{aligned}\mathbb P(|\bar X_n - \mu| > \epsilon) &\leq \frac{\mathrm{Var}(\bar X)}{\epsilon^2} = \frac{\sigma^2}{n \cdot \epsilon^2}.\end{aligned}$

This writeup brings us to the limit, pun not intended, of our intuitive ideas of probability. Up till now, we assumed that $X$ is discrete (i.e. $X(\Omega)$ is at most countably infinite). But for a more serious discussion, we will need $X$ to be continuous of some kind, so that $X(\Omega) \subseteq \mathbb R$ in a meaningful sense. We’ll take an even more general direction—the measure-theoretic formation of probability theory.

—Joel Kindiak, 3 Jul 25, 0019H
September 23, 2025
The Mathematical Average
Given a discrete random variable $X$ taking values in $\mathbb Z$ , what is its expectation, if it exists?

Let’s suppose $X$ takes on finitely many values, i.e. the set

$\mathrm{supp}(X) := \{x \in \mathbb Z : \mathbb P(X = x) > 0\}$

is finite. Denote $\mathrm{supp}(X) = \{x_1,\dots,x_n\}$ . The expectation of $X$ is the value that we expect $X$ to take. In a sense, we want to obtain the “center value” $\mu$ that the random variable $X$ will take.

We can think of the center value $\mu$ as a “pivot” on a “balance beam”. Each $x_i < \mu$ will induce a “weight” of $\mathbb P(X = x_i)$ that tilts the beam anticlockwise, and similarly, each $x_i > \mu$ will induce a “weight” of $\mathbb P(X = x_i)$ that tilts the beam clockwise. Intuitively, the total contributions ought to cancel out, yielding the equality

$\displaystyle \sum_{x \in \mathrm{supp}(X)} (x - \mu) \cdot \mathbb P(X = x) = 0.$

Expanding the left-hand side,

$\begin{aligned} \sum_{x \in \mathrm{supp}(X)} (x - \mu) \cdot \mathbb P(X = x) &= \sum_{x \in \mathrm{supp}(X)} x \cdot \mathbb P(X = x) - \mu \cdot \sum_{x \in \mathrm{supp}(X)} \mathbb P(X = x) \\ &= \sum_{x \in \mathrm{supp}(X)} x \cdot \mathbb P(X = x) - \mu \cdot 1 \\ &= \sum_{x \in \mathrm{supp}(X)} x \cdot \mathbb P(X = x) - \mu. \end{aligned}$

Therefore,

$\displaystyle \sum_{x \in \mathrm{supp}(X)} x \cdot \mathbb P(X = x) = \mu.$

Using measure notation $\mathbb P_X \equiv \mathbb P(X \in \cdot)$ and $\mathbb P_X(x) \equiv \mathbb P_X(\{x\})$ for brevity,

$\displaystyle \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) = \mu,$

where the left-hand side is well-defined if $\mathrm{supp}(X)$ is finite. This quantity we will formally define as the expectation, if the sum exists (even if the sum is infinite).

Let $X$ be a $\mathbb Z$ -valued random variable.

Definition 1. The expectation of $X$ , denoted $\mathbb E[X]$ , is defined by

$\displaystyle \mathbb E[X] := \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x)$

whenever the right-hand side exists.

Example 1. For $p \in [0, 1]$ , if $X \sim \mathrm{Ber}(p)$ , then

$\begin{aligned} \mathbb E[X] &= 0 \cdot \mathbb P_X(0) + 1 \cdot \mathbb P_X(1) \\ &= 0 \cdot (1-p) + 1 \cdot p = p. \end{aligned}$

Lemma 1. Let $(\Omega, \mathcal F, \mathbb P)$ be a probability space and $X : \Omega \to \mathbb Z$ be a random variable. Then

$\displaystyle \mathbb P_X(x) = \sum_{\omega \in \Omega} \mathbb I\{X(\omega) = x\} \cdot \mathbb P(\{\omega\}).$

Whenever both sides are well-defined,

$\displaystyle \mathbb E[X] = \sum_{\omega \in \Omega} X(\omega) \cdot \mathbb P(\{ \omega \}).$

Proof. We first observe that

$\displaystyle \mathbb P_X(x) = \mathbb P(X(\omega) = x) = \sum_{\omega : X(\omega)=x} \mathbb P(\{ \omega \}) = \sum_{\omega \in \Omega} \mathbb I\{X(\omega)=x\} \cdot \mathbb P(\{ \omega \}).$

Hence,

$\begin{aligned} \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) &= \sum_{x \in \mathbb Z} x \cdot \sum_{\omega \in \Omega} \mathbb I\{X(\omega)=x\} \cdot \mathbb P(\{ \omega \}) \\ &=\sum_{x \in \mathbb Z} \sum_{\omega \in \Omega} x \cdot \mathbb I\{X(\omega)=x\} \cdot \mathbb P(\{ \omega \}) \\ &= \sum_{\omega \in \Omega} \sum_{x \in \mathbb Z} x \cdot \mathbb I\{X(\omega)=x\} \cdot \mathbb P(\{ \omega \}) \\ &= \sum_{\omega \in \Omega} X(\omega) \cdot \mathbb P(\{ \omega \}) . \end{aligned}$

Lemma 2. For any map $g : \mathbb Z \to \mathbb Z$ , $g(X) := g \circ X$ is a $\mathbb Z$ -valued random variable.

Theorem 1. If $\mathbb E[g(X)]$ exists, then

$\displaystyle \mathbb E[g(X)] = \sum_{x \in \mathbb Z} g(x) \cdot \mathbb P_X(x),$

whenever both sides are well-defined.

Proof. Defining $Y := g(X)$ by Lemma 2, the proof and result in Lemma 1 yields

$\begin{aligned} \mathbb E[g(X)] = \mathbb E[Y] &= \sum_{\omega \in \Omega} Y(\omega) \cdot \mathbb P(\{\omega\}) \\ &= \sum_{\omega \in \Omega} g(X(\omega)) \cdot \mathbb P(\{\omega\}) \\ &= \sum_{\omega \in \Omega} \sum_{x \in \mathbb Z} g(X(\omega)) \cdot \mathbb I\{X(\omega) = x\} \cdot \mathbb P(\{\omega\}) \\ &= \sum_{x \in \mathbb Z} \sum_{\omega \in \Omega} g(X(\omega)) \cdot \mathbb I\{X(\omega) = x\} \cdot \mathbb P(\{\omega\}) \\ &= \sum_{x \in \mathbb Z} g(x) \cdot \sum_{\omega \in \Omega} \mathbb I\{X(\omega) = x\} \cdot \mathbb P(\{\omega\}) \\ &= \sum_{x \in \mathbb Z} g(x) \cdot \mathbb P_X(x). \end{aligned}$

Corollary 1. Let $Y$ be a $\mathbb Z$ -valued random variable. For any map $g : \mathbb Z^2 \to \mathbb Z$ , $g(X,Y) := g \circ (X,Y)$ is a $\mathbb Z$ -valued random variable. Furthermore,

$\displaystyle \mathbb E[g(X,Y)] = \sum_{(x, y) \in \mathbb Z^2} g(x,y) \cdot \mathbb P_{X,Y}(x,y).$

Furthermore, if $\mathbb E[X], \mathbb E[Y]$ exist, then the following hold:
- $\mathbb E[X + Y] = \mathbb E[X] + \mathbb E[Y]$ ,
- $\mathbb E[\alpha X] = \alpha \cdot \mathbb E[X]$ for any $\alpha \in \mathbb Z$ ,
- $\mathbb E[X - \mathbb E[X]] = 0$ .
Proof. We prove the first identity for simplicity. Define $g(x,y) = x+y$ . Then

$\begin{aligned} \mathbb E[g(X,Y)] &= \sum_{(x, y) \in \mathbb Z^2} g(x,y) \cdot \mathbb P_{X,Y}(x,y) \\ \mathbb E[X+Y]&= \sum_{(x, y) \in \mathbb Z^2} (x+y) \cdot \mathbb P_{X,Y}(x,y) \\ &= \sum_{(x, y) \in \mathbb Z^2} x \cdot \mathbb P_{X,Y}(x,y) + \sum_{(x, y) \in \mathbb Z^2} y \cdot \mathbb P_{X,Y}(x,y) \\ &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_{X}(x) + \sum_{y \in \mathbb Z} y \cdot \mathbb P_{Y}(y) \\ &= \mathbb E[X] + \mathbb E[Y], \end{aligned}$

where the simplifications arise from

$\begin{aligned} \sum_{(x, y) \in \mathbb Z^2} x \cdot \mathbb P_{X,Y}(x,y) &= \sum_{x \in \mathbb Z} \sum_{y \in \mathbb Z} x \cdot \mathbb P_{X,Y}(x,y) \\ &= \sum_{x \in \mathbb Z} \sum_{y \in \mathbb Z} x \cdot \mathbb P(Y = y \mid X = x) \cdot \mathbb P_X(x) \\ &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) \cdot \sum_{y \in \mathbb Z} \mathbb P(Y = y \mid X = x) \\ &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) \cdot 1 \\ &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x).\end{aligned}$

Thankfully, all series here are valid due to linearity.

Example 2. For $n \in \mathbb N$ and $p \in [0, 1]$ , if $X \sim \mathrm{Bin}(n, p)$ , then $\mathbb E[X] = np$ .

Proof. Find independent identically distributed (i.i.d.) Bernoulli random variables $\xi_1, \dots, \xi_n \sim \mathrm{Ber}(p)$ such that

$\displaystyle X = \sum_{i=1}^n \xi_i.$

By Corollary 1,

$\displaystyle \mathbb E[X] = \mathbb E\left[ \sum_{i=1}^n \xi_i \right] = \sum_{i=1}^n \mathbb E[\xi_i] = \sum_{i=1}^n p = np.$

Example 3. Equip the finite sample $(x_1,\dots,x_n) \subseteq \mathbb Z$ with the uniform probability measure and induced random variable $X := \mathrm{id}$ . Then

$\begin{aligned} \mathbb E[X] &= \sum_{x \in \mathbb Z} x \cdot \mathbb P_X(x) \\ &= \sum_{i=1}^n x_i \cdot \mathbb P_X(x_i) \\ &= \sum_{i=1}^n x_i \cdot \frac 1n = \frac 1n \cdot \sum_{i=1}^n x_i =: \bar x. \end{aligned}$

Thus, the right-hand side is called the mean of the sample $(x_1,\dots,x_n)$ .

The expectation has a cousin—the covariance and its child the variance. We will discuss these ideas more in the next post.

—Joel Kindiak, 1 Jul 25, 1915H
September 16, 2025
Adding Random Variables

Given two random variables $X, Y$ with known distributions (for example, $X \sim \mathrm{Ber}(p)$ and $Y \sim \mathrm{Ber}(q)$ ), what is the distribution of their sum $X + Y$ ? This question is highly nontrivial, and is worth some elementary experimentation.

Let’s work with the Bernoulli example and see what we can get. The first case is, in a sense, the “easiest” case to work with: $X = 1$ and $Y = 1$ . Using ordered-pair notation, $(X, Y) = (1, 1)$ . In this case, $X + Y = 2$ . Furthermore, if $X = 0$ , then $X + Y \leq 1 < 2$ , so that there is, in a sense, only one possible case to handle. Therefore, at least informally,

$\mathbb P(X + Y = 2) = \mathbb P((X, Y) = (1, 1)).$

However, the probability on the right side raises a new question: what do we mean by $\mathbb P((X, Y) = ( 1, 1))$ ? If we insist (rather intuitively) that

$\mathbb P((X, Y) = ( 1, 1)) = \mathbb P(X = 1) \cdot \mathbb P(Y = 1),$

we are implicitly assuming that $X,Y$ are independent in some sense (but we need to formalise this notion later on), which may not always be the case! Our first task therefore isn’t even to compute $X + Y$ , but to examine what we mean by $\mathbb P((X, Y) = \cdot )$ , i.e. the joint distribution of $X$ and $Y$ .

Lemma 1. Let $(\Omega, \mathcal F, \mathbb P)$ be a probability space and $X_1, \dots, X_n : \Omega \to \mathbb Z$ be discrete random variables. The product map $\mathbf X_n := (X_1, \dots, X_n) : \Omega \to \mathbb Z^n$ defined by

$\mathbf X_n(\omega) := (X_1(\omega), \dots, X_n(\omega)),\quad \omega \in \Omega$

is measurable, when $\mathbb Z$ is equipped with the usual $\sigma$ -algebra $\mathcal P(\mathbb Z^n)$ , and induces a push-forward measure $\mathbb P_{\mathbf X_n} : \mathcal P(\mathbb Z^n) \to [0, 1]$ defined by

$\begin{aligned} \mathbb P_{\mathbf X_n}(K) &:= \mathbb P(\mathbf X_n \in K) = \mathbb P(\mathbf X_n^{-1}(K)),\quad K \in \mathcal P(\mathbb Z^n).\end{aligned}$

While $\mathbf X_n$ shares many properties of discrete random variables, its range is not a subset of $\mathbb Z$ , and to reduce confusion we restrict the term “discrete random variables” to the original definition.

But what would be the joint distribution of $(X,Y)$ ? That is, what is the value of

$\begin{aligned} \mathbb P_{X,Y}(\{ (x, y) \}) &= \mathbb P(\{ X = x \} \cap \{Y = y\}) \equiv \mathbb P( X = x , Y = y ) \end{aligned}$

for any $x, y \in \mathbb Z$ ? Perhaps $\mathbb P_{X,Y}$ could be defined arbitrarily, as long as we have each value in $[0, 1]$ and

$\displaystyle \sum_{ (x, y) \in \mathbb Z^2 } \mathbb P( X = x , Y = y ) = 1.$

However, there are two more sneaky conditions.

Lemma 2. For any $y \in \mathbb Z$ with $\mathbb P(Y = y) > 0$ ,

$\displaystyle \sum_{x \in \mathbb Z} \mathbb P( X =x , Y = y ) = \mathbb P(Y = y).$

Similarly, for any $x \in \mathbb Z$ with $\mathbb P(X = x) > 0$ ,

$\displaystyle \sum_{y \in \mathbb Z} \mathbb P( X = x , Y = y ) = \mathbb P(X = x).$

Proof. Recall that for any $y \in \mathbb Z$ such that $\mathbb P(Y = y) \equiv \mathbb P_Y(\{y\}) > 0$ , the conditional probability

$\displaystyle \mathbb P( \cdot \mid Y = y ) : \mathcal F \to [0, 1]$

is a probability measure, which induces a probability measure

$\mathbb P( X \in \cdot \mid Y = y ) : \mathcal P(\mathbb Z) \to [0, 1].$

Thus, we must require that

$\displaystyle \sum_{x \in \mathbb Z} \mathbb P( X \in x \mid Y = y ) = 1.$

Hence,

$\begin{aligned} \sum_{x \in \mathbb Z} \mathbb P( X =x , Y = y ) &= \sum_{x \in \mathbb Z} \mathbb P( X =x \mid Y = y ) \cdot \mathbb P(Y = y) \\ &= \mathbb P(Y = y) \cdot \sum_{x \in \mathbb Z} \mathbb P( X =x \mid Y = y ) \\ & = \mathbb P(Y = y) \cdot 1 \\ &= \mathbb P(Y = y). \end{aligned}$

Thankfully, convergence issues resolve themselves here.

Still, do we have an algorithmic way to compute the joint distribution? If the events $X^{-1}(\{ x \}) \equiv X^{-1}(x), Y^{-1}(y) \in \mathcal F$ are independent for any $x, y \in \mathbb N$ , then

$\begin{aligned} \mathbb P(X = x, Y = y) &= \mathbb P(\{X = x \} \cap \{ Y = y\}) \\ &= \mathbb P(X^{-1}(x) \cap Y^{-1}(y)) \\ &= \mathbb P(X^{-1}(x)) \cdot \mathbb P(Y^{-1}(y)) \\ &= \mathbb P(X = x) \cdot \mathbb P (Y = y).\end{aligned}$

Hence, we define the independence of the random variables in this manner.

Definition 1. The discrete random variables $X_1,\dots , X_n : \Omega \to \mathbb N$ are independent if for any $x_1,\dots,x_n \in \mathbb N$ , the events $X_1^{-1}(x_1),\dots, X_n^{-1}(x_n)$ are independent. In this case,

$\mathbb P((X_1,\dots,X_n) = (x_1,\dots,x_n)) = \mathbb P(X_1 = x_1) \cdot \cdots \cdot \mathbb P(X_n = x_n).$

Using p.m.f. notation,

$f_{X_1,\dots,X_n}(x_1,\dots, x_n) = f_{X_1}(x_1) \cdot \cdots \cdot f_{X_n}(y),\quad (x_1,\dots,x_n) \in \mathbb Z^n.$

Example 1. Suppose $X \sim \mathrm{Ber}(p)$ and $Y \sim \mathrm{Ber}(q)$ are independent random variables. Evaluate the distribution of $X + Y : \Omega \to \mathbb Z$ .

Solution. We note that the joint distribution $f_{X,Y}$ is given by

$\begin{aligned} f_{X,Y}(0, 0) &= (1-p) \cdot (1-q),\\ f_{X,Y}(0, 1) &= (1-p) \cdot q,\\ f_{X,Y}(1, 0) &= p \cdot (1-q), \\ f_{X,Y}(1, 1) &= p \cdot q.\end{aligned}$

We observe that $X + Y \in \{0, 1, 2\}$ . Hence,

$\begin{aligned} f_{X+Y}(0) &= f_{X,Y}(0, 0) = (1-p) \cdot (1-q), \\ f_{X+Y}(1) &= f_{X,Y}(0, 1) + f_{X,Y}(1, 0) \\ &= (1-p) \cdot q + p \cdot (1-q), \\ f_{X+Y}(2) &= f_{X,Y}(1, 1) = p \cdot q. \end{aligned}$

Notice that $f_{X+Y}(1)$ is evaluated by summing the cases of $(0, 1)$ and $(1, 0)$ . More generally, we have

$\begin{aligned} f_{X+Y}(k) &= \sum_{x + y = k} f_{X,Y}(x, y) \\ &= \sum_{x + y = k} f_{X}(x) \cdot f_Y(y) \\ &= \sum_{x \in \mathbb Z} f_X(x) \cdot f_Y(k-x) \\ &=: (f_X * f_Y)(k), \end{aligned}$

where the quantity on the right is called the discrete convolution of $f_X$ and $f_Y$ . Time to generalise!

Theorem 1. Let $X, Y : \Omega \to \mathbb Z$ be discrete random variables. Given any function $g : \mathbb Z^2 \to \mathbb Z$ , the random variable $g(X,Y) : \Omega \to \mathbb Z$ exists and is given by the distribution

$\displaystyle \mathbb P_{g(X,Y)}(k) = \sum_{g(x,y) = k} f_{X,Y}(x,y) = \sum_{(x,y) \in g^{-1}(k)} f_{X,Y}(x,y).$

If $X, Y$ are independent, then the distribution is given by

$\displaystyle \mathbb P_{g(X,Y)}(k) = \sum_{(x,y) \in g^{-1}(k)} f_{X}(x) \cdot f_Y(y).$

In particular,

$\displaystyle \mathbb P_{X+Y}(k) = \sum_{x\in \mathbb Z} f_{X}(x) \cdot f_Y(k-x).$

Example 2. Fix $p \in [0, 1]$ . Given that $X_i \sim \mathrm{Ber}(p)$ are independent, $X_1 + X_2$ has a distribution given by

$\displaystyle \mathbb P_{X_1+X_2}(k) = \begin{cases} (1-p)^2, & k = 0, \\ 2p(1-p), & k = 1, \\ p^2, & k = 2. \end{cases}$

Furthermore, for any $n \in \mathbb N^+$ , the distribution of $S_n := X_1 + \cdots + X_n$ is given by

$\displaystyle \mathbb P_{S_n}(k) = {n \choose k} p^k(1-p)^{n-k}.$

Proof. The case $n = 1$ is trivial. Example 1 establishes the case $n = 2$ . For the general case, we prove by induction. Suppose for any $m$ ,

$\displaystyle \mathbb P_{S_m}(k) = {m \choose k} p^k(1-p)^{m-k},\quad 0 \leq k \leq m.$

Suppose $X_{m+1} \sim \mathrm{Ber}(p)$ . Then $S_{m+1} = S_m + X_{m+1}$ . By the discrete convolution and Pascal’s identity,

$\begin{aligned} \mathbb P_{S_{m+1}}(k) &= \mathbb P_{S_m + X_{m+1}}(k) \\ &= \sum_{x\in \mathbb Z} \mathbb P_{S_m}(x) \cdot \mathbb P_{X_{m+1}}(k-x) \\ &= \mathbb P_{S_m}(k) \cdot \mathbb P_{X_{m+1}}(0) + \mathbb P_{S_m}(k-1) \cdot \mathbb P_{X_{m+1}}(1) \\ &= {m \choose k} p^k(1-p)^{m-k} \cdot (1-p) + {m \choose k-1} p^{k-1}(1-p)^{m-(k-1)} \cdot p \\ &=\left( {m \choose k} + {m \choose k-1} \right) \cdot p^k(1-p)^{(m+1)-k} \\ &= {m+1 \choose k} p^k(1-p)^{(m+1)-k}.\end{aligned}$

Example 2 is basically the definition of the Binomial distribution.

Definition 2. Fix $n \in \mathbb N$ and $p \in [0, 1]$ . We say that the random variable $X$ follows a Binomial distribution with parameters $n, p$ , denoted $X \sim \mathrm{Bin}(n, p)$ , if there exists independent Bernoulli random variables $\xi_n \sim \mathrm{Ber}(p)$ such that

$\displaystyle X = \xi_1 + \cdots + \xi_n.$

Trivially, $\mathrm{Bin}(1, p) = \mathrm{Ber}(p)$ .

Corollary 1. If $X \sim \mathrm{Bin}(m, p)$ and $Y \sim \mathrm{Bin}(n, p)$ are independent, then $X + Y \sim \mathrm{Bin}(m+n, p)$ .

Proof. Find independent random variables $\xi_i$ such that

$X = \xi_1 + \cdots + \xi_m,\quad Y = \xi_{m+1} + \dots + \xi_{m+n}.$

Then

$X + Y = \xi_1 + \cdots + \xi_m + \xi_{m+1} + \dots + \xi_{m+n} \sim \mathrm{Bin}(m+n, p).$

With some distributions at hand, we ask a reasonable question: how do we calculate the averages of these distributions? We will answer this question using expectations next time.

—Joel Kindiak, 29 Jun 25, 2229H

September 9, 2025
Neither Random Nor Variable

A random variable is neither random nor a variable. Let me explain.

Flip a fair coin twice. Let $X$ denote the number of Heads that you obtain. What is the value of $X$ ? Well, it depends on each outcome in the sample space $\Omega$ :

$\Omega := \{(\mathrm H, \mathrm H), (\mathrm H, \mathrm T), (\mathrm T, \mathrm H), (\mathrm T, \mathrm T)\}.$

Denote $\mathcal F = \mathcal P(\Omega)$ and the uniform probability measure on $\mathcal F$ by $\mathbb P(\cdot)$ . Since $X$ denotes the number of Heads, we have

$X((\mathrm H, \mathrm H)) = 2, \quad X((\mathrm H, \mathrm T)) = X ((\mathrm T, \mathrm H)) = 1,\quad X((\mathrm T, \mathrm T)) = 0.$

Notice then the randomness arises in selecting the outcome $\omega \in \Omega$ , not in the measurement $X(\omega)$ (though the former inevitably influences the latter). The quantity $X(\omega)$ just records the number of Heads, and each occurs with some probability (which we will explore later on).

Thus, while we call $X$ a random variable, it is neither random (though that is captured by the randomness of $\omega$ ), nor a variable (though that is captured by $X(\Omega)$ ).

Let $(\Omega, \mathcal F)$ and $(\Psi, \mathcal G)$ be measurable spaces.

Definition 1. A map $f : \Omega \to \Psi$ is $\mathcal F/\mathcal G$ –measurable if for any $K \in \mathcal G$ , $f^{-1}(K) \in \mathcal F$ . We omit the prefix $\mathcal F/\mathcal G$ when the context is clear.

Lemma 1. Suppose $\mathcal F = \mathcal P(\Omega)$ . Any map $f : \Omega \to \Psi$ is measurable, where $\Psi$ is equipped with the $\sigma$ -algebra $\mathcal P(\Psi)$ .

Proof. For any $K \in \mathcal P(\Psi)$ ,

$K \subseteq \Psi \quad \Rightarrow \quad f^{-1}(K) \subseteq \Omega \quad \Rightarrow \quad f^{-1}(K) \in \mathcal P(\Omega) = \mathcal F.$

Lemma 2. Suppose furthermore there exists a probability measure $\mathbb P$ on $(\Omega, \mathcal F)$ . Then the map $\mathbb P_X := \mathbb P \circ X^{-1} : \mathcal G \to [0, 1]$ is a probability measure on the measurable space $( \Psi, \mathcal G )$ , called the push-forward measure of $X$ .

Lemmas 1 and 2 are crucial for this purpose: they illustrate that, all things considered, the underlying sample space $(\Omega, \mathcal F, \mathbb P)$ is not as nearly as relevant as the measures induced on $\mathbb N$ . Eventually, we will want to develop measures on $\mathbb R$ too, though that will take substantially more effort.

Equip $\mathbb N$ with the $\sigma$ -algebra $\mathcal P(\mathbb N)$

Definition 2. Let $(\Omega, \mathcal F, \mathbb P)$ be any probability space. A discrete random variable is a map $X : \Omega \to \mathbb N$ . Since we equipped $\mathbb N$ with the $\sigma$ -algebra $\mathcal P(\mathbb N)$ , $X$ is automatically measurable. We call its pushforward measure $\mathbb P_X$ the distribution of $X$ , and for convenience denote, for $x \in \mathbb N$ ,

$\mathbb P_X(x) = \mathbb P(X^{-1}(x)) = \mathbb P(\{\omega \in \Omega : X(\omega) = x \} ) \equiv \mathbb P(X=x).$

Without loss of generality, given that a discrete random variable $X$ has distribution $\mathbb P_X$ , we assume that $(\Omega, \mathcal F, \mathbb P) = (\mathbb N, \mathcal P(\mathbb N), \mathbb P_X)$ and that with respect to this choice, $X = \mathrm{id}$ .

Lemma 3. For any discrete random variable $X$ , $\displaystyle \sum_{x = 0}^\infty \mathbb P(X = x) = 1$ .

The support of a discrete random variable is $\mathbb P_X^{-1}((0, 1])$ . The probability mass function or p.m.f. of $X$ is defined by $f_X := \mathbb P(X = \cdot) : \mathbb R \to [0, \infty)$ . The cumulative distribution function or c.d.f. of $X$ is defined by

$\displaystyle F_X : \mathbb R \to [0, 1],\quad F_X(x) := \mathbb P(X \leq x) \equiv \sum_{t = 0}^{\lfloor x \rfloor} f_X(t).$

To illustrate meaningful examples, let’s consider the flipping of a biased coin with parameter $p \in [0, 1]$ . This means the probability of getting ‘Head’ is some fixed value $p$ , which may or may not be $1/2$ .

Example 1. Consider the usual sample space $\Omega := \{ \mathrm H, \mathrm T\}$ equipped with the $\sigma$ -algebra $\mathcal F := \mathcal P(\Omega)$ . Define the probability measure $\mathbb P : \mathcal F \to [0, 1]$ by $\mathbb P(\{\mathrm H\}) = p$ , which implies that

$\mathbb P(\{\mathrm T\}) = \mathbb P(\Omega \backslash \{\mathrm H\}) = 1 - p.$

Define the random variable $X : \Omega \to \mathbb N$ defined by $X(\mathrm H) = 1$ and $X(\mathrm T) = 0$ . Then

$\mathbb P(X = 1) = \mathbb P(X^{-1}(\{1\}) = \mathbb P(\{\mathrm H\}) = p,\quad \mathbb P(X = 0) = 1- p,$

so that $\mathbb P(X = x) = 0$ for $x \notin \{0, 1\}$ .

Definition 3. Let $(\Omega, \mathcal F, \mathbb P)$ be any probability space and $X : \Omega \to \mathbb N$ be a discrete random variable. We say that $X$ follows a Bernoulli distribution with parameter $p \in [0, 1]$ , denoted $X \sim \mathrm{Ber}(p)$ , if

$\mathbb P(X = x) = \begin{cases}1-p, & x = 0, \\ p, & x = 1, \\ 0, & \text{otherwise.}\end{cases}$

Example 2. The random variable $X$ defined in Example 1 has the distribution $\mathrm{Ber}(p)$ . The random variable $Y := 1 - X$ has the distribution $\mathrm{Ber}(1-p)$ since

$\mathbb P(Y = 1) = \mathbb P(X = 0) = 1 - p.$

Example 3. The discrete random variable $U$ is uniform on $(a, b]$ given integers $-1 \leq a < b$ if

$\displaystyle \mathbb P(U = u) = \frac{1}{b-a},\quad u \in (a, b] \cap \mathbb N.$

Having properly defined a discrete random variable, a natural question arises: are there approaches to create new random variables from old ones? For instance, given two random variables $X$ and $Y$ , what is the distribution of their sum $X + Y$ ? In the special case of Example 2, it is obvious that by construction, $X + Y = X+ ( 1-X) = 1$ . But what if $X,Y$ don’t have any obvious connection?

Next time, we explore the idea of independence of random variables and think about ways to combine them.

—Joel Kindiak, 27 Jun 25, 1300H

September 2, 2025
Bayes’ Theorem
The 21st century mathematician Rick Durrett claimed in his lecture notes that measure theory ends and probability begins with the definition of independence. We explore that idea in this topic, as well as its generalisation in the form of Bayes’ theorem.

Let $(\Omega, \mathcal F, \mathbb P)$ be a probability space.

Lemma 1. Let $K$ be any event with positive probability: $\mathbb P(K) > 0$ . Then the map

$\displaystyle \mathbb P( \cdot \mid K) := \frac{ \mathbb P(\cdot \cap K) }{ \mathbb P(K) } : \mathcal F \to [0, 1]$

is a well-defined probability measure. In particular,
- $\mathbb P(L \mid K) = 1$ if $K \subseteq L$ , and
- $\mathbb P(L \mid K) = 0$ if $K \cap L = \emptyset$ .
Equivalently,

$\mathbb P(L \cap K) = \mathbb P(L \mid K) \cdot \mathbb P(K), \quad L \in \mathcal F.$

Proof. It suffices to prove that $\mathbb P(\Omega \mid K) = 1$ , which holds since $K \subseteq \Omega$ implies

$\displaystyle \mathbb P( \Omega \mid K) := \frac{ \mathbb P( \Omega \cap K) }{ \mathbb P(K) } = \frac{ \mathbb P( K) }{ \mathbb P(K) } = 1.$

Corollary 1. The law of total probability then reduces to the following: if $\Omega = \bigsqcup_{i=1}^n K_i$ and each $K_i$ has positive probability, then

$\displaystyle \mathbb P(K) = \sum_{i=1}^n \mathbb P(K \mid K_i) \cdot \mathbb P(K_i).$

What the quantity $\mathbb P(L \mid K)$ as defined in Lemma 1 measures, roughly speaking, is the probability that the event $L$ occurs under the assumption that the event $K$ occurs. This model fits the conclusion of Corollary 1 quite well: to evaluate $\mathbb P(K)$ , we condition on each of the varied $K_i$ , then evaluate $\mathbb P(K \mid K_i)$ for each $i$ , followed by summing up via the addition principle. Furthermore, we recover the following intuitions:
- if $K \subseteq L$ , then any outcome $\omega \in K$ automatically yields $\omega \in L$ ,
- if $K \cap L = \emptyset$ , then any outcome in $\omega \in K$ automatically yields $\omega \notin L$ .
In a sense, these two scenarios are the extremes: the first means that $K$ is totally included in $L$ , and the second means that $K$ is totally excluded from $L$ . But could there be a middle ground? What if, in a sense, event $L$ “does not care” about event $K$ ? Assuming that $\mathbb P(K) > 0$ , this observation amounts to the equality

$\displaystyle \mathbb P(L \mid K) = \mathbb P(L) \quad \Rightarrow \quad \mathbb P(K \cap L) = \mathbb P(K) \cdot \mathbb P(L).$

The equation on the left means that regardless of whether the event $K$ occurs or not, the event $L$ will hold with the same probability. The equation on the right is equivalent to the equation on the left if $\mathbb P(K) > 0$ , but deserves its own attention since it handles the situation where $\mathbb P(K) = 0$ . We use this definition for the notion of independence:

Definition 1. Two events $K, L \in \mathcal F$ are independent if

$\mathbb P(K \cap L) = \mathbb P(K) \cdot \mathbb P(L).$

Example 1. Flip a fair coin twice so that its sample space is

$\Omega := \{ \mathrm H, \mathrm T \}^2 = \{ (\mathrm H, \mathrm H), (\mathrm H, \mathrm T), (\mathrm T, \mathrm H), (\mathrm T, \mathrm T) \}.$

Let $\mathcal F := \mathcal P(\Omega)$ denote the discrete $\sigma$ -algebra and $\mathbb P$ denote the uniform counting measure $\mathbb P(\cdot) = |\cdot|/4$ on $\mathcal F$ .

Let $K := \{ (\mathrm H, \mathrm H), (\mathrm H, \mathrm T) \}$ denote the event that the first coin is a Head, and $L := \{ (\mathrm H, \mathrm H), (\mathrm T, \mathrm H) \}$ denote the event that the second coin is a Head. Then

$\displaystyle \mathbb P(K \cap L) = \mathbb P(\{ (\mathrm H, \mathrm H) \}) = \frac{1}{4} = \frac 12 \cdot \frac 12 = \mathbb P(K) \cdot \mathbb P(L).$

Thus, the events $K$ and $L$ are independent, and misunderstanding such may lead to financial ruin.

Independence of events is an insanely useful idea in probability theory, especially in the sense of independent random variables, which we will explore in future write-ups. In fact, many kinds of events are independent:

Theorem 1. We have the following independence (or not) properties:
- for any $K \in \mathcal F$ , $K$ and $\emptyset$ are independent,
- if $K, L$ have positive probability, then they cannot be mutually exclusive and independent at the same time,
- if $K$ has positive probability, then $K, K$ cannot be independent.
Furthermore, if $K, L$ are independent, the following pairs of events are independent as well:

$L,K, \quad K, \Omega \backslash L,\quad \Omega \backslash K, L, \quad \Omega \backslash K, \Omega \backslash L.$

Proof. We illustrate the proof of $K, \Omega \backslash L$ being independent and leave the rest as exercises. Since $K, L$ are independent, we use finite additivity to obtain

$\begin{aligned} \mathbb P(K) &= \mathbb P(K \cap (L \sqcup \Omega \backslash L)) \\ &= \mathbb P(K \cap L) + \mathbb P(K \cap \Omega \backslash L) \\ &= \mathbb P(K) \cdot \mathbb P(L) + \mathbb P(K \cap \Omega \backslash L). \end{aligned}$

Since $L \subseteq \Omega$ , we have $\Omega \cap L = L$ , so that

$\begin{aligned} \mathbb P(K \cap \Omega \backslash L) &= \mathbb P(K) - \mathbb P(K) \cdot \mathbb P(L) \\ &= \mathbb P(K) \cdot (1 - \mathbb P(L)) \\ &= \mathbb P(K) \cdot (\mathbb P(\Omega) - \mathbb P(\Omega \cap L)) \\ &= \mathbb P(K) \cdot \mathbb P(\Omega \backslash L). \end{aligned}$

The reality, however, is that in most situations, the quantity $\mathbb P(K \mid L)$ is nontrivial. Furthermore, the quantity seems trivial if, at least sequentially, the event $L$ either occurs (or not), and then the event $K$ occurs (or not).

For example, $L$ could indicate the event “I suspect that this patient has COVID-19” and $K$ could indicate the event “the patient tests positive for COVID-19”. Since we are finite human beings, there is no harm assuming that $\mathbb P(K) > 0$ and $\mathbb P(L) > 0$ . Now the quantity $\mathbb P(K \mid L)$ has a natural interpretation—it measures the probability that, under the assumption that a patient has COVID-19, the patient tests positive for the virus. Summarised using intuitive terms, $\mathbb P(K \mid L)$ measures the sensitivity of the COVID-19 test.

In a similar vein (no pun intended), $\mathbb P(\Omega \backslash K \mid \Omega \backslash L)$ measures the specificity of the COVID-19 test. The quantities $\mathbb P(K \mid \Omega \backslash L)$ and $\mathbb P(\Omega \backslash K \mid L)$ then measure the false positive rate and false negative rates respectively, and are connected to the sensitivity and specificity measures as follows:

$\begin{aligned} \mathbb P(K \mid \Omega \backslash L) = 1 - \text{specificity}, \quad \mathbb P(\Omega \backslash K \mid L) = 1 - \text{sensitivity}. \end{aligned}$

Now we present our case-study that generalises nicely into Bayes’ theorem.

Example 2. Suppose $100p\%$ of the population has been infected with COVID-19, and your COVID-19 test kit has a sensitivity of $95\%$ and a specificity of $90\%$ . Given that a patient tests positive using your test kit, what is the probability, in terms of $p$ , that this patient actually has COVID-19?

Solution. Using $K, L$ as our events, we observe that

$\mathbb P(K \mid L) = 0.95,\quad \mathbb P(\Omega \backslash K \mid \Omega \backslash L) = 0.9,\quad \mathbb P(L) = p \in [0, 1].$

We are interested in the quantity $\mathbb P(L \mid K)$ . Nothing in our problem-solving arsenal helps us at the moment, except perhaps for $\mathbb P(K \mid L)$ . We note that $K \cap L = L \cap K$ , so that

$\mathbb P(K \mid L) \cdot \mathbb P(L) = \mathbb P(K \cap L) = \mathbb P(L \cap K) = \mathbb P(L \mid K) \cdot \mathbb P(K).$

Doing some algebruh and substituting relevant values,

$\begin{aligned} \mathbb P(L \mid K) &= \frac{\mathbb P(K \mid L) \cdot \mathbb P(L)}{ \mathbb P(K)} \end{aligned}$

Now taking advantage of the law of total probability,

$\begin{aligned} f(p) := \mathbb P(L \mid K) &= \frac{\mathbb P(K \mid L) \cdot \mathbb P(L)}{ \mathbb P(K \mid L) \cdot \mathbb P(L) + \mathbb P(K \mid \Omega \backslash L) \cdot \mathbb P(\Omega \backslash L) } \\ &= \frac{0.95 \cdot p}{ 0.95 \cdot p + (1-0.9) \cdot (1-p) }. \end{aligned}$

The fascinating observation is that $f(5\%) \approx 33\%$ , $f(10\%) \approx 51\%$ , and $f(20\%) \approx 70\%$ . This means if we know that $20\%$ of the population has been infected with COVID-19, and assuming constant sensitivity and specificity of the COVID-19 test we tested positive for it, there is a $70\%$ chance that we have been infected with the virus too. For better or for worse, these data points inform governments on various public health policies and measures taken to curb the virus and “flatten the curve“.

Our computations above prove Bayes’ theorem:

Theorem 2 (Bayes). Given events $K, L$ with positive probability,

$\displaystyle \mathbb P(L \mid K) = \frac{\mathbb P(K \mid L) \cdot \mathbb P(L)}{\mathbb P(K)}.$

Furthermore, if $L = \bigsqcup_{i=1}^n L_i$ and each $L_i$ has positive probability, then

$\displaystyle \mathbb P(L \mid K) = \frac{\mathbb P(K \mid L) \cdot \mathbb P(L)}{\sum_{i=1}^n \mathbb P(K \mid L_i) \cdot \mathbb P(L_i)}.$

There is more to discuss on Bayes’ theorem, but we conclude with one more application. We notice that if we are given a constant $\mathbb P(K)$ , then

$\displaystyle \mathbb P(L \mid K) = \frac{1}{\mathbb P(K)} \cdot \mathbb P(K \mid L) \cdot \mathbb P(L).$

Then the higher the value of $\mathbb P(K \mid L)$ and $\mathbb P(L)$ , the higher the value of $\mathbb P(L \mid K)$ . This connection is often used in Bayesian statistics to model an update of belief: given a prior probability $\mathbb P(L)$ , the posterior probability is the new probability $\mathbb P(L \mid K)$ given that we have new evidence, namely $K$ .

We need to introduce one more key star player of probability, namely that of random variables. This we will do next time.

—Joel Kindiak, 26 Jun 25, 1847H
August 26, 2025
Probabilistic Events
Previously, we convinced ourselves that given various kinds of finite sets $K$ , we have many techniques to compute $|K|$ . Why we care is to compute probabilities: given a finite set $\Omega$ , we can define the probability measure $\mathbb P := | \cdot |/|\Omega| : \mathcal P(\Omega) \to [0, 1]$ . We say that we are computing the probabilities of events, since the elements of $\mathcal P(\Omega)$ satisfy several desirable properties.

Theorem 1. Call a collection $\mathcal F \subseteq \mathcal P(\Omega)$ a $\sigma$ -algebra over $\Omega$ if it satisfies the following properties:
- $\emptyset, K \in \mathcal F$ ,
- for any $K \in \mathcal F$ , $\Omega\backslash K \in\mathcal F$ ,
- for any $K_1,K_2,\dots \in \mathcal F$ , $\bigcup_{i=1}^\infty K_i \in \mathcal F$ .
Elements of $\mathcal F$ are then called events. Then $\mathcal P(\Omega)$ is a $\sigma$ -algebra.

Henceforth, let $\Omega$ denote a sample space and $\mathcal F$ denote any $\sigma$ -algebra on $\Omega$ .

For any measure $\mu$ on $\mathcal F$ with $\mu(\Omega) < \infty$ , $\mathbb P_{\mu} := \mu(\cdot) / \mu(\Omega)$ is a probability measure on $\mathcal F$ . In particular, these properties hold if $\Omega$ is a finite set and $\mu = | \cdot |$ .

The reason for these seemingly trivial observations and the definition of a $\sigma$ -algebra becomes more apparent when we consider $\Omega$ being an infinite set, say $\mathbb R$ . The collection $\mathcal P(\Omega)$ does still form a $\sigma$ -algebra over $\Omega$ , but it’s entirely unclear how we might assign a meaningful probability measure on $\mathcal P(\Omega)$ . We will explore this idea later on.

For now, let’s take a look at the elements of $\mathcal F$ .

Lemma 1. For any $K, L \in \mathcal F$ , $K \cap L, K \backslash L \in \mathcal F$ . Furthermore, for any $K, L \in \mathcal F$ , there exists $K_0, L_0 \in \mathcal F$ such that $K \cup L = K_0 \cup L_0$ and $K_0 \cap L_0 = \emptyset$ . In the latter, we say that $K, L$ are mutually exclusive.

Proof. By set complementation and de Morgan’s laws,

$K \cap L = \Omega \backslash (\Omega \backslash (K \cap L)) = \Omega \backslash (\Omega \backslash K \cup \Omega \backslash L) \in \mathcal F.$

Similarly, $K \backslash L = K \cap (\Omega \backslash L) \in \mathcal F$ . For the disjoint union claim, define $L_0 := K \backslash L \in \mathcal F$ .

Furthermore, we state the various measure properties on $\mathcal F$ . One key property defining measures is countable additivity, of which we get finite additivity as a special case:

$\mu(K \sqcup L) = \mu(K) + \mu(L),\quad K, L \in \mathcal F.$

Here, we write the disjoint union $K \sqcup L$ to refer to the set $K \cup L$ if $K \cap L = \emptyset$ .

Lemma 2. We have the following properties for any measure $\mu$ :
- for $K, L \in \mathcal F$ , $\mu(K) = \mu(K \backslash L) + \mu(K \cap L)$ ,
- if there exists $K \in \mathcal F$ such that $\mu(K) < \infty$ , then $\mu(\emptyset) = 0$ ,
- for $K, L \in \mathcal F$ , $\mu(K \cup L) + \mu(K \cap L) = \mu(K) + \mu(L)$ ,
- for $K, L \in \mathcal F$ , if $K \subseteq L$ , then $\mu(K) \leq \mu(L)$ .
Proof. For the set-difference claim,

$\begin{aligned} K &= K \cap \Omega \\ &= K \cap (L \sqcup \Omega \backslash L) \\ &= (K \cap L) \sqcup (K \cap \Omega \backslash L) \\ &= (K \cap L) \sqcup K \backslash L. \end{aligned}$

Then the result becomes immediate since

$\mu(K) = \mu(K \cap L) + \mu(K \backslash L).$

For the empty-set claim, the first result yields

$\mu(K) = \mu(K \cap K) + \mu(K \backslash K) = \mu(K) + \mu(\emptyset).$

Since $\mu(K) < \infty$ , subtracting on both sides yields $\mu(\emptyset) = 0$ .

For the set-union claim,

$\begin{aligned} \mu(K \cup L) &= \mu(K \sqcup L \backslash K) \\ &= \mu(K) + \mu(L \backslash K).\end{aligned}$

Adding $\mu(K \cap L)$ on both sides,

$\begin{aligned} \mu(K \cup L) + \mu(K \cap L) &= \mu(K) + \mu(L \backslash K) + \mu(K \cap L) \\ &= \mu(K) + \mu(L). \end{aligned}$

Finally, for the subset claim, we recall that $K \subseteq L$ implies that $K \cup L = L$ and replace $L$ with $L \backslash K$ and use the empty-set claim to obtain

$\begin{aligned} \mu(K) &\leq \mu(K) + \mu(L \backslash K) \\ &= \mu(K \cup L \backslash K) + \mu(K \cap L \backslash K) \\ &= \mu(K \cup L) + \mu(\emptyset) \\ &= \mu(L) + 0 = \mu(L). \end{aligned}$

Theorem 2. For any probability measure $\mathbb P$ on $\mathcal F$ , we have the following properties:
- $\mathbb P(\emptyset) = 0$ ,
- for $K, L \in \mathcal F$ , $\mathbb P(K \cup L) = \mathbb P(K) + \mathbb P(L) - \mathbb P(K \cap L)$ ,
- for $K, L \in \mathcal F$ , if $K \subseteq L$ , then $\mathbb P(K) \leq \mathbb P(L)$ .
In fact, these properties hold if $\mathbb P$ is replaced by any finite measure $\mu$ .

Proof. For any $K \in \mathcal F$ , $K \subseteq \Omega$ and $\mathbb P(K) \leq \mathbb P(\Omega) = 1$ , and all properties hold for Lemma 2.

Mutually exclusive events therefore help us take advantage of the measure properties to do case-splitting analysis whenever needed, summarised by the law of total probability:

Theorem 3. Suppose there exists $K_1, \cdots , K_n \in \mathcal F$ such that $\Omega = \bigsqcup_{i=1}^n K_i$ . Then for any $K \in \mathcal F$ ,

$\displaystyle \mathbb P(K) = \sum_{i=1}^n \mathbb P(K \cap K_i).$

Proof. Apply finite additivity onto the decomposition

$\displaystyle K = K \cap \Omega = K \cap \bigsqcup_{i=1}^n K_i = \bigsqcup_{i=1}^n (K \cap K_i).$

—Joel Kindiak, 25 Jun 25, 2312H
August 19, 2025
How to Count

Previously, we informally introduced some key ideas in probability that we will revisit when exploring the meat of the root—measure theory. Therein, we talked about the counting measure, which we will revisit for simplicity.

Theorem 1. Let $\Omega$ be a finite set and for any $K \subseteq \Omega$ , let $|K|$ denote the number of elements in $K$ . Then for any $K_1,\dots, K_n$ that do not share elements pair-wise (i.e. for $i \neq j$ , $K_i \cap K_j = \emptyset$ ),

$\displaystyle \left| \bigcup_{i = 1}^n K_i \right| = \sum_{i = 1}^n |K_i|.$

This is the first counting principle: the addition principle. Now we raise a seemingly obvious question: how do we count? When I read this I laughed. Shouldn’t we be beyond baby counting? Except that it’s not so obvious, and I’ll try to convince you why that’s the case in a moment.

Let’s analyse this peculiar expression: $(1+x)^n$ . For $n = 0$ and $n = 1$ , we get trivial results:

$(1+x)^0 = 1,\quad (1+x)^1 = 1+x.$

For $n = 2$ , we need to use the basic rules of expansion:

$\begin{aligned} (1+x)^2 &= (1+x)(1+x) \\ &= 1 \cdot (1+x) + x \cdot (1+x) \\ &= (1+x) + (x + x^2) \\ &= 1 + 2x + x^2. \end{aligned}$

For $n = 3$ , we need to do it again, but using the $n = 2$ case:

$\begin{aligned} (1+x)^3 &= (1+x)(1+x)^2 \\ &= (1+x)(1+ 2x + x^2) \\ &= 1 \cdot (1+ 2x + x^2) + x \cdot (1+ 2x + x^2) \\ &= (1+ 2x + x^2) + (x + 2x^2 + x^3) \\ &= 1+ (2 + 1)x + (1 + 2)x^2 + x^3 \\ &= 1 + 3x + 3x^2 + x^3. \end{aligned}$

You may have seen the sequence of these sequences $(1)$ , $(1, 1)$ , $(1, 2, 1)$ , $(1, 3, 3, 1)$ in the first four rows of Pascal’s triangle:

$\begin{aligned} &1,\\ & 1 \quad 1, \\ & 1 \quad 2 \quad 1, \\ & 1 \quad 3 \quad 3 \quad 1. \end{aligned}$

This connection is no coincidence, and we might revisit this idea later on.

Now, here is my question: how do you expand $(1+x)^{100}$ ? By observing the pattern, we can guess that this expansion will require $100 + 1 = 101$ terms, which will take…a long time. Indeed, we can formalise these patterns and more using the principle of mathematical induction and obtain the binomial theorem.

Theorem 2 (Binomial Theorem). For any $n \in \mathbb N_0$ ,

$\displaystyle (1 + x)^n = \sum_{k = 0}^n {n \choose k} x^k,$

where $\displaystyle {n \choose k}$ is the integer recursively defined by

$\displaystyle {n \choose 0} := 1, \quad {n \choose n} := 1,\quad {n+1 \choose k+1} := {n \choose k} + {n \choose k+1}.$

Proof. We have established the base case $n = 0$ . For the inductive step,

$\begin{aligned} (1 + x)^{k+1} &= (1+x)(1+x)^k \\ &= (1+x) \left( \sum_{j = 0}^k {k \choose j} x^j \right) \\ &= \sum_{j = 0}^k {k \choose j} (1+x)x^j \\ &= \sum_{j = 0}^k {k \choose j} (x^j + x^{j+1}) \\ &= \sum_{j = 0}^k {k \choose j} x^j + \sum_{j = 0}^k {k \choose j} x^{j+1} \\ &= \sum_{j = 0}^k {k \choose j} x^j + \sum_{j = 1}^{k+1} {k \choose j-1} x^{j} \\ &= {k \choose 0} x^0 + \sum_{j = 1}^k {k \choose j} x^j + \sum_{j = 1}^{k} {k \choose j-1} x^{j} + {k \choose k} x^k \\ &= {k \choose 0} x^0 + \sum_{j = 1}^k \left( {k \choose j} + {k \choose j-1} \right) x^{j} + {k \choose k} x^k \\ &= {k+1 \choose 0} x^0 + \sum_{j = 1}^k {k+1 \choose j} x^j + {k+1 \choose k+1} x^k \\ &= \sum_{j = 0}^{k+1} {k+1 \choose j} x^j. \end{aligned}$

However, how do we compute $\displaystyle {n \choose k}$ ? We will use $(1+x)^3$ as our case-study, and in doing so, derive a more meaningful interpretation of $\displaystyle {n \choose k}$ and a relatively effective method to compute it.

Let’s expand $(1+x)^3$ again. Intuitively, $(1+x)^3 = (1+x)(1+x)(1+x)$ , and when expanded, yields the sum of the following products:

$\begin{aligned} &1 \cdot 1 \cdot 1, \\ & x \cdot 1 \cdot 1,\quad 1 \cdot x \cdot 1,\quad 1 \cdot 1 \cdot x, \\ & x \cdot x \cdot 1,\quad x \cdot 1 \cdot x,\quad 1 \cdot x \cdot x, \\ &x \cdot x \cdot x. \end{aligned}$

For each $k$ , notice that the coefficient of $x^k$ is exactly the number of arrangements of $k$ copies of $x$ and $(3-k)$ copies of $1$ . We have particularised to $n = 3$ here, but there is no reason to stop at $3$ , unlike Singapore’s population planning post-WWII.

Let’s now discuss the idea of arrangements.

Theorem 2. Given finite sets $K_1,\dots,K_n$ , an $n$ –arrangement is a finite sequence $(x_1,\dots,x_n)$ , where $x_i \in K_i$ for each $i$ . Thus, the set of arrangements is defined by

$\displaystyle \prod_{i = 1}^n K_i \equiv \{(x_1,\dots,x_n) : x_i \in K_i\},$

and the number of elements it has is given by

$\displaystyle \left| \prod_{i = 1}^n K_i \right| = \prod_{i = 1}^n |K_i|.$

This is called the multiplication principle. In the special case $K_1 = \cdots = K_n = K$ , we have $|K^n| = |K|^n$ . An element of $K^n$ is called an $n$ –arrangement of objects in $K$ .

So what we are interested in the $(1+x)^n$ question is the collection of $n$ -arrangements of objects in $\{1, x\}$ . Indeed, our suspicions are confirmed, since for the $n = 3$ case, we did list out $2^3 = 8$ arrangements. But how do we “weed” out the coefficients of $x^k$ ? We need to find the arrangements of the objects

$\underbrace{ x,\dots,x }_k, \underbrace{ 1,\dots, 1 }_{n-k}.$

If we call this number $\displaystyle {n \choose k}$ and are able to compute this number, then immediately we recover the binomial theorem:

$\displaystyle (1 + x)^n = \sum_{k = 0}^n {n \choose k} x^k.$

However, how do we actually compute $\displaystyle {n \choose k}$ ? For some nontrivial insight, let’s analyse the case ${5 \choose 3}$ , so that we find the arrangements of the objects

$x, x, x, 1, 1.$

If we treated all of these object as different from one another, we aim to find arrangements of the objects

$x_1, x_2, x_3, x_4, x_5.$

Crucially, we want to arrange these objects without repetitions. We call such arrangements permutations.

Let $K = \{x_1,\dots, x_n\}$ be a finite set with $n$ distinct elements.

Theorem 3. An arrangement $(x_1,\dots,x_n)$ of objects in a set $K$ is called a permutation of $K$ if for any $i \neq j$ , $x_i \neq x_j$ . Then the number of permutations is given by $n!$ , called $n$ –factorial, defined by

$n! := n \times (n - 1) \times \cdots \times 2 \times 1.$

Proof. For convenience, define $0! := 1$ and for any $n \in \mathbb N^+$ ,

$n! := n \cdot (n-1)!.$

Then it is clear that

$n! = n \times (n - 1) \times \cdots \times 2 \times 1.$

We will prove the claim inductively on $n$ . For the base case, the one and only permutation of $\{x_1\}$ is $x_1$ . Therefore, the number of permutations is $1 = 1!$ .

Now for the inductive step, consider a set $K = \{x_1,\dots,x_k, x_{k+1} \}$ of $k+1$ distinct elements. There are $k+1$ possible choices for the last term $x_{k+1}'$ in the sequence. Now the set $K \backslash \{x_{k+1}'\}$ has $k$ elements. By the induction hypothesis, there are $k!$ permutations of the elements in the first $k$ slots. By the multiplication principle, the total number of permutations is

$k! \times (k+1) = (k+1)!,$

as required.

Corollary 1. The number of permutations of $\{ x_4,x_5 \}$ is $2! = 2$ and the number of permutations of $\{x_1,x_2,x_3\}$ is $3! = 6$ .

Proof. We have $2! = 2 \times 1! = 2 \times 1 = 2$ and $3! = 3 \times 2! = 3 \times 2 = 6$ .

We are almost there. We observe that given these labels, the permutations

$(x_1,x_2,x_3,x_4,x_5),\quad (x_1,x_2,x_3,x_5,x_4)$

are distinct. However, if we recall that $x_1,x_2,x_3$ are placeholders for $x$ and $x_4,x_5$ are placeholders for $1$ , then we obtain the identical permutations

$(x, x ,x , 1, 1),\quad (x, x, x , 1, 1).$

In fact, we can flip the question: how many permutations correspond to the overarching arrangement $(x, x, x, 1, 1)$ ? It would be the contribution of all permutations of $\{x_1,x_2,x_3\}$ and all permutations of $\{x_4,x_5\}$ . If there are $\displaystyle {5 \choose 3}$ overarching arrangements of $3$ copies of $x$ and $2$ copies of $1$ , then the multiplication principle yields

$\displaystyle {5 \choose 3} \times 3! \times 2! = 5!\quad \Rightarrow \quad {5 \choose 3} = \frac{5!}{3! \times 2!}.$

Extending this reasoning to $k$ copies of $x$ and $n$ copies of $1$ yields the computation of the binomial coefficient.

Theorem 4. For any $n \in \mathbb N^+$ and $k \in \mathbb N_0$ with $k \leq n$ , the $k$ -th binomial coefficient is given by $\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}$ .

Intriguingly, these two quantities, the factorial $n!$ and binomial coefficient $\displaystyle {n \choose k}$ help us discuss more about permutations and combinations.

Definition 1. Let $K = \{x_1,\dots,x_n\}$ be a set of $n$ elements. For integers $0 \leq k \leq n$ , a $k$ –combination of $K$ is a subset of $K$ (so that the collection of combinations of $K$ is $\mathcal P(K)$ ) and a $k$ –permutation is a permutation of some $k$ -combination of $K$ .

Given $k$ , how many $k$ -combinations are there? Furthermore, how many $k$ -permutations are there? We have seen that the number of $n$ -permutations is $n!$ , and clearly the number of $n$ -combinations is $1$ . More concretely, given $0 \leq k \leq n$ , we want to count

$\mathcal S_k := \{S \in \mathcal P(K) : |S| = k\}.$

Our key idea is as follows: fix $S \subseteq K$ such that $|S| = k$ . Form a sequence of $x$ and $1$ as follows: declare the $i$ -th term to be $x$ if $x_i \in S$ and $1$ otherwise. We formalise this construction in Lemma 1 below:

Lemma 1. For any $S \subseteq K$ , define $f_S \in \{1, x \}^n$ by

$f_S(i) = \begin{cases} x, & x_i \in S, \\ 1, & x_i \notin S. \end{cases}$

Then the map $f : \mathcal P(K) \to \{1, x\}^n$ defined by $f(S) := f_S$ is bijective.

In particular, $f(\mathcal S_k)$ corresponds to the number of arrangements of $k$ copies of $x$ and $(n-k)$ copies of $1$ . But we have computed this number already—it is $\displaystyle {n \choose k}$ . Hence, we have the following result.

Theorem 5. The number of $k$ -combinations of a set of $n$ distinct elements is $\displaystyle {n \choose k}$ . The number of $k$ -permutations of the same set of elements is $\displaystyle {n \choose k} \times k!$ .

Proof. The first claim follows from

$\displaystyle |\mathcal S_k| = |f(\mathcal S_k)| = {n \choose k}.$

For the second claim, we first have $\displaystyle {n \choose k}$ choices of $k$ -combinations, followed by $k!$ permutations of the elements in each $k$ -combination. The result follows from the multiplication principle.

There is a lot more that can be said about counting, studied in a much broader field called combinatorics. For now, we have convinced ourselves (somewhat) that we are able to compute $|K|$ for various kinds of sets $K$ , be it collections of permutations or combinations, with repetitions or otherwise.

—Joel Kindiak, 24 Jun 25, 1810H

August 12, 2025
The Friendship Formula
Friendship is a massively important topic of contemplation in my life, so much to the point I have proposed an equation to quantify the closeness between two friends. Suppose Persons X and Y are friends, and Person X wants to evaluate his closeness with Person Y.

Definition 1. Define the following random variables bounded in $[0, 1]$ :
- $Q$ denotes the space for vulnerability that Person X gives to Person Y (i.e. the extent to which Person Y does not need to feel defensive when interacting with Person X).
- $R$ denotes the space for vulnerability that Person X receives from Person Y.
- $S$ denotes the access that Person X gives to Person Y (i.e. the amount of personal information that Person X discloses to Person Y).
- $T$ denotes the access that Person X receives from Person Y.
Assume the random variables $Q,R,S,T$ are jointly independent continuous random variables.

Note that Person X determines these quantities, and may differ from Person Y’s evaluation (explaining why X can feel close to Y but the feelings are not mutual).

Axiom 1. The mutual closeness $C$ that X feels he shares with Y is defined by the equation

$C := \min\{ Q, R \} \cdot \min\{ S, T \}.$

Problem 1. Prove that $\mathbb E[C]$ is given by the quantity

$\displaystyle \begin{aligned} \left(\mathbb E[Q] + \mathbb E[R] - 1 + \int_{[0, 1]} F_Q \cdot F_R\, \mathrm d\lambda \right) \cdot \left(\mathbb E[S] + \mathbb E[T] - 1 + \int_{[0, 1]} F_S \cdot F_T\, \mathrm d\lambda\right). \end{aligned}$

This quantity evaluates the expected closeness that X feels with Y.

(Click for Solution)

Solution. We notice that all random variables have expectation bounded in $[0, 1]$ . Define

$V := \min\{ Q, R \},\quad A := \min\{ S, T \}.$

We first evaluate $\mathbb E[V]$ . By definition,

$\begin{aligned} \mathbb P(V > v) &= \mathbb P(\min\{Q, R\} > v) \\ &= \mathbb P( Q > v, R > v ) \\ &= \mathbb P( Q > v ) \cdot \mathbb P( R > v ). \end{aligned}$

In particular,

$\begin{aligned}(F_Q \cdot F_R)(v) &= F_Q(v) \cdot F_R(v) \\ &= (1 - \mathbb P(Q > v)) \cdot (1 - \mathbb P(R > v)) \\ &= 1 - \mathbb P(Q > v) - \mathbb P(R > v) + \mathbb P(Q > v) \cdot \mathbb P(R > v) \\ &= 1 - \mathbb P(Q > v) - \mathbb P(R > v) + \mathbb P(V > v). \end{aligned}$

Taking integrals on all sides, using the tail-probability characterisation of the expectation, and performing algebruh,

$\displaystyle \mathbb E[V] = \mathbb E[Q] + \mathbb E[R] - 1 + \int_{[0, 1]} (F_Q \cdot F_R)(v)\, \mathrm dv.$

Similarly,

$\displaystyle \mathbb E[A] = \mathbb E[S] + \mathbb E[T] - 1 + \int_0^1 (F_S \cdot F_T)(a)\, \mathrm da.$

Since $Q,R,S,T$ are jointly independent, $V = \min\{Q, R\}$ and $A = \min\{S, T\}$ are also independent, and

$\mathbb E[C] = \mathbb E[V \cdot A] = \mathbb E[V] \cdot \mathbb E[A],$

giving the desired result, after replacing relevant dummy variables.

—Joel Kindiak, 7 Aug 25, 2324H
August 9, 2025
Probability Nomenclature

Probability is our attempt at making sense of random events in our rather random world. The simplest example—a coin toss—will surprisingly motivate many topics that we will formulate with greater and greater generality.

Flip a coin. You get $1$ point if ‘Head’ comes up, and nothing if ‘Tail’ comes up. You start with a score of $0$ . After one flip, what is your score? Well, it depends. Does the coin land ‘Head’? Does it land ‘Tail’? It could go either way. How do we model this phenomenon. Well, there are $2$ outcomes, and if they are equally likely, then we can say that each outcome has a probability of $1/2$ .

In mathematical notation, we let the sample space $\Omega := \{\text{H}, \text{T}\}$ denote the set of possible outcomes after one flip of the coin. What are the different events that we can measure? Surely we have the non-negative probabilities

$\mathbb P( \{ \text{H} \} ) = \frac 12,\quad \mathbb P( \{ \text{T} \} ) = \frac 12.$

But more is true. What is the probability that we get either a ‘Head’ or a ‘Tail’? In the real would it could be the case that a coin lands on its edge, but in a mathematical world, we preclude such a possibility. This means that there are only two possible outcomes: a ‘Head’ or a ‘Tail’, and they don’t overlap. At least one of them must be true! Hence, it makes sense to assert

$\mathbb P(\Omega) = \mathbb P(\{ \text{H}, \text{T} \}) = 1.$

This discussion almost seems trivial, until we make one modification. Now flip the coin two times. You get $1$ point if ‘Head’ comes up, and nothing if ‘Tail’ comes up. You start with a score of $0$ . After two flips, what is your score?

Let’s list down the different possible outcomes:

$\Omega = \{ ( \text{H}, \text{H} ), ( \text{H}, \text{T} ), ( \text{T}, \text{H} ), ( \text{T}, \text{T} ) \} = \{\text H, \text T\}^2.$

How do we assign their probabilities? And furthermore, how do we determine our score? Assuming no funny business, we would think that all outcomes are equally likely. Once again, at least one outcome should hold, so we stipulate $\mathbb P(\Omega) = 1$ . Furthermore, for any two distinct outcomes $\omega_1 \neq \omega_2$ , we stipulate the event that either one occurs as their sum:

$\mathbb P(\{\omega_1, \omega_2\}) = \mathbb P(\{\omega_1\} \cup \{\omega_2\}) := \mathbb P(\{\omega_1\}) + \mathbb P(\{\omega_2\}).$

We can now formalise probability theory for finite sample spaces; the infinite case deserves a much, much longer elaboration.

Definition 1. Let $\Omega$ be a finite sample space and $\mathcal F := \mathcal P(\Omega)$ denote its power set (i.e. the collection of all of its possible subsets). We call the map $\mu : \mathcal F \to [0, \infty)$ a finite measure on $\Omega$ if

$\displaystyle \mu(\{\omega_1, \dots, \omega_n\}) = \sum_{i=1}^n \mu(\{\omega_i\})$ for distinct outcomes $\omega_1,\dots,\omega_n \in \Omega.$

Additionally, if $\mu(\Omega) = 1$ , we call $\mu$ a probability measure, and commonly denote it by $\mu \equiv \mathbb P$ .

Lemma 1. For any finite sample space $\Omega$ and finite measure $\mu : \mathcal P(\Omega) \to [0, \infty)$ with $\mu(\Omega) > 0$ , there exists a probability measure $\mathbb P : \mathcal P(\Omega) \to [0, 1]$ .

Proof. Define $\displaystyle \mathbb P := \frac 1{\mu(\Omega)} \cdot \mu$ and verify Definition 1: for distinct outcomes $\omega_1,\dots,\omega_n \in \Omega$ ,

$\begin{aligned} \mathbb P(\{\omega_1, \dots, \omega_n\}) &= \frac 1{\mu(\Omega)} \cdot \mu(\{\omega_1, \dots, \omega_n\}) \\ &= \frac 1{\mu(\Omega)} \sum_{i=1}^n \mu( \{\omega_i\} ) \\ &= \sum_{i=1}^n \frac 1{\mu(\Omega)} \cdot \mu( \{\omega_i\} ) = \sum_{i=1}^n \mathbb P( \{\omega_i\} ). \end{aligned}$

Hence, we can discuss most ideas using the more general $\mu$ and particularise to $\mathbb P$ whenever $0 < \mu(\Omega) < \infty$ .

Theorem 1. If $|\Omega|$ is finite and there exists $m > 0$ such that for any outcome $\omega \in \Omega$ , $\mu(\{\omega\}) = m$ , then $m = \mu(\Omega)/|\Omega|$ . We call $\mu$ the uniform measure on $\Omega$ . In the case $m = 1$ , we call $\mu$ the counting measure, since $\mu(\Omega) = |\Omega|$ .

Proof. Denoting $\Omega = \{\omega_1,\dots,\omega_{|\Omega|}\}$ ,

$\begin{aligned} m \cdot |\Omega| &= \sum_{i=1}^{|\Omega|} m = \sum_{i=1}^{|\Omega|} \mu(\{\omega_i\}) = \mu(\Omega). \end{aligned}$

Therefore, $m = \mu(\Omega)/|\Omega|$ .

In particular, for any $K \subseteq \Omega$ , $\mu(K) = |K|$ so that we can regard $| \cdot | : 2^\Omega \to \mathbb N_0$ as the counting measure.

Corollary 1. Under the conditions of Theorem 1, if $\mathbb P$ is a uniform probability measure, then for any $K \subseteq \Omega$ , $\mathbb P(K) = |K|/|\Omega|$ .

Proof. By Theorem 1, for any $\omega \in \Omega$ ,

$\displaystyle \mathbb P(\{\omega\}) = \frac{\mathbb P(\Omega)}{|\Omega|} = \frac{1}{|\Omega|}.$

Hence,

$\displaystyle \mathbb P(K) = \sum_{\omega \in K} \mathbb P(\{\omega\}) = \sum_{\omega \in K} \frac{1}{|\Omega|} = |K| \cdot \frac{1}{|\Omega|} = \frac{|K|}{|\Omega|}.$

In particular,

$\mathbb P(\{ ( \text{H}, \text{H} ) \} ) = \mathbb P( \{ ( \text{H}, \text{T} ) \} ) = \mathbb P( \{ ( \text{T}, \text{H} ) \} ) = \mathbb P(\{ ( \text{T}, \text{T} ) \}) = \frac 14.$

Let’s return to the situation

$\Omega = \{\text H, \text T\}^2 = \{ ( \text{H}, \text{H} ), ( \text{H}, \text{T} ), ( \text{T}, \text{H} ), ( \text{T}, \text{T} ) \}.$

Recall that our goal is to determine the score $X$ after $2$ coin flips. There are three possible scores: $X \in \{ 0, 1, 2 \}$ . Here’s a simple question: what is the probability that we end up with a score of $1$ ? Well, we notice that we can interpret the score $X$ as a function $X : \Omega \to \{0, 1, 2\}$ defined as follows:

$X(( \text{H}, \text{H} )) = 2, \quad X(( \text{H}, \text{T} )) = X(( \text{T}, \text{H} )) = 1,\quad X(( \text{T}, \text{T} )) = 0.$

This means that the outcomes $\omega \in \{ ( \text{H}, \text{T} ), ( \text{T}, \text{H} ) \}$ yield $X(\omega) = 1$ . Using inverse-image notation,

$X^{-1}(\{1\}) = \{\omega \in \Omega : X(\omega) = 1\} = \{ ( \text{H}, \text{T} ), ( \text{T}, \text{H} ) \}.$

Well then, what do we mean by $\mathbb P(X = 1)$ ? Intuitively, since there are $2$ outcomes with equal probability, we should have a combined probability of $2 \times 1/4 = 1/2$ . The probability is derived from the subset $X^{-1}(\{1\}) \subseteq \Omega$ of desired outcomes:

$\begin{aligned} \mathbb P(X = 1) &:= \mathbb P(X^{-1}(\{1\})) \\ &= \sum_{\omega \in X^{-1}(\{1\})} \mathbb P(\{\omega\}) \\ &= \sum_{\omega \in X^{-1}(\{1\})} \frac{1}{|\Omega|} \\ &= \frac{1}{|\Omega|} \cdot |X^{-1}(\{1\})| \\ &= \frac 14 \cdot 2 = \frac 12. \end{aligned}$

Definition 2. Let $\Omega$ be a finite sample space and $\mu$ be a measure on $\Omega$ . We call $X : \Omega \to \mathbb R$ a random variable on $\Omega$ . It is clear that $X(\Omega) = \{x_1,\dots,x_n\}$ is finite.

Theorem 2. As per the notation in Definition 2, denote $\mathcal F_X := \mathcal P(X(\Omega))$ . Then the map $\mu_X : \mathcal F_X \to [0, \infty)$ defined by $\mu_X(K) := \mu(X^{-1}(K))$ for any $K \subseteq X(\Omega)$ is a measure on $X(\Omega)$ . We abbreviate $\mu_X \equiv \mu \circ X^{-1}$ and call it the push-forward measure of $\mu$ under $X$ .

Proof. For any $\{x_1,\dots,x_n\} \subseteq X(\Omega)$ ,

$\begin{aligned} \mu_X(\{x_1,\dots,x_n\}) &= \mu(X^{-1}(\{x_1,\dots,x_n\}) ) \\ &= \mu(\{\omega \in \Omega : X(\omega) \in \{x_1, \dots, x_n\} \}) \\ &= \mu \left(\bigcup_{i=1}^n \{\omega \in \Omega : X(\omega) \in \{x_i\} \} \right) \\ &= \sum_{i=1}^n \mu(\{\omega \in \Omega : X(\omega) \in \{x_i\} \}) \\ &= \sum_{i=1}^n \mu(X^{-1}( \{x_i\} ) ) \\ &= \sum_{i=1}^n \mu_X ( \{x_i\} ). \end{aligned}$

Before continuing, you might wonder: what’s with the rather complicated terminology? Well, it’s to tease you on the key vocabulary that one cannot escape when studying measure theory and probability.

In fact, there is even a simpler question that isn’t entirely obvious, given a set $\Omega$ , how do we compute $|\Omega|$ ? This is where we need to discuss some basic combinatorics.

—Joel Kindiak, 22 Jun 25, 1249H

August 5, 2025