Probability spaces and Random Variables

Paradoxes without rigor

We’re going to begin this course by setting up probability axiomatically. A sample space will be a set $\Omega$; certain (not all) subsets of it will be events that we can measure probabilities of, and measurable (not all) functions on the sample space will be random variables. This rigorous formalization was introduced by Kolmogorov in 1933.

Why this rigor? Without it many things are “meta math” and often nonsense.

Example 1 (Two envelopes problem). Imagine you are given two identical envelopes, each containing money. One contains twice as much as the other. You may pick one envelope and keep the money it contains. Having chosen an envelope at will, but before inspecting it, you are given the chance to switch envelopes. Should you switch?

On one hand, both envelopes are identical so switching shouldn’t make a difference. On the other hand, if the envelope you chose has $x$ dollars, the other one is equally likely to have either $x/2$ or $2x$ dollars. So switching will get you $1.25\, x > x$ on average.

Example 2 (St. Petersberg Paradox). A fair coin is flipped until it lands on Heads. If Heads appears on the $n$-th toss, you win $2^n$ dollars. What is a fair price to pay to enter this game?

A simple calculation shows that the expected return is infinite; meaning you should in theory be willing to pay any amount of money for this game and still come out ahead on average. But most people won’t be willing to pay more than a few dollars.

Example 3 (Bertrand’s paradox). Consider an equilateral triangle inscribed in a circle. If you choose a chord of the circle “at random”, what is the probability that its length is greater than the side length of the triangle?

There are at least three correct sounding ways to do this, all of which give different answers.

Sample spaces

For most of this course we will focus on finite (or countable) sample spaces; however we begin with the definitions in general.

Definition 4. A probability space is a tripe $(\Omega, \mathcal F, \P)$ where:

  • $\Omega$ is a set, called the sample space representing all possible outcomes of an experiment.
  • $\mathcal F \subseteq \mathcal P(\Omega)$ is a $\sigma$-algebra (defined below), representing events we can measure probabilities of.
  • $\P$ is a probability measure on $\mathcal F$ (defined below), representing the probabilities of events.

Remark 5. Above $\mathcal P(\Omega)$ refers to the power set of $\Omega$.

Example 6. You can represent one fair coin toss by $\Omega = \set{H, T}$, $\mathcal F = \mathcal P(\Omega)$, and $\P(\emptyset) = 0$, $\P(\set{H}) = \P(\set{T}) = 1/2$, $\P(\Omega) = 1$.

Example 7. You can represent one two independent coin tosses by $\Omega = \set{HH, HT, TH, TT}$, $\mathcal F = \mathcal P(\Omega)$, and $\P(A) = \abs{A} / 4$ for all $A \subseteq \Omega$.

Definition 8 ($\sigma$-algebra). Let $\Omega$ be a set. We say $\mathcal F \subseteq \mathcal P(\Omega)$ is a $\sigma$-algebra on $\Omega$ if it is:

  1. Nonempty: $\emptyset \in \mathcal F$
  2. Closed under complements: $A \in \mathcal F \implies A^c \in \mathcal F$.
  3. Closed under countable unions: $A_i \in \mathcal F \implies \bigcup_{i=1}^\infty A_i \in \mathcal F$.

Remark 9. If you know the probability of two events $A, B$, you’d like to also know the probability of $A \cap B$, $A - B$, $B - A$, etc. For this we need to know that if $A, B \in \mathcal F$, then $A \cap B \in \mathcal F$, $A - B \in \mathcal F$, etc. While this isn’t assumed in the definition, it follows immediately from De Morgan’s law.

Problem 10. If $\mathcal F$ is a $\sigma$-algebra, then:

  1. $\Omega \in \mathcal F$.
  2. $\mathcal F$ is also closed under finite unions – that is if $A_1$, …, $A_N \in \mathcal F$ then $A_1 \cup \cdots \cup A_N \in \mathcal F$.
  3. If $A_i \in \mathcal F$, then $\bigcap_{i=1}^\infty A_i \in \mathcal F$.
  4. If $A, B \in \mathcal F$ then $A - B \in \mathcal F$

Definition 11. We say $\P$ is a probability measure on $(\Omega, \mathcal F)$ if:

  1. $\P$ is a function from $\mathcal F \to [0, 1]$. (That is, if $A \in \mathcal F$, then $\P(A) \in [0, 1]$.
  2. $\P(\emptyset) = 0$ and $\P(\Omega) = 1$,
  3. For any countable collection of pairwise disjoint events $A_1, A_2, \dots \in \mathcal F$, we have $$ \P(\bigcup_{i=1}^\infty A_i) = \sum_{i=1}^\infty \P(A_i) \,. $$ Here by pairwise disjoint we mean $A_i \cap A_j = \emptyset$ whenever $i \neq j$.

Remark 12. Recall, elements of $\mathcal F$ are called events or sometimes $\mathcal F$-measurable events (remember $\mathcal F \subseteq \mathcal P(\Omega)$, so elements of $\mathcal F$ are subsets of the sample space). Events are subsets of the sample space where $\P$ is guaranteed to be defined, and for any event $A$, $\P(A)$ represents the probability that the event $A$ occurs.

Remark 13. There are several subtle issues that arise when $\Omega$ is uncountably infinite. When $\Omega$ is countable, it is often desirable to choose $\mathcal F = \mathcal P(\Omega)$.

In general, constructing probability measures is hard and typically requires a Kolmogorov extension / Carathéodory theorem. However, in the finite (or the countable) case, we typically construct probability measures as follows.

Example 14. Suppose $\Omega$ is a countable set, and $p \colon \Omega \to [0, 1]$ is a function such that $ \sum_{\omega \in \Omega} p(\omega) = 1 $. Let $\mathcal F = \mathcal P(\Omega)$, and define $\P$ by $$ \P(A) = \sum_{a \in A} p(a) $$ Then $\P$ is a probability measure on $(\Omega, \mathcal F)$. In this case, the function $p$ is called a probability mass function.

Proposition 15. On any probability space $(\Omega, \mathcal F, \P)$, if $A, B \in \mathcal F$ with $A \subseteq B$ then $\P(B - A) = \P(B) - \P(A)$. Consequently $\P(A^c) = 1 - \P(A)$.

Problem 16. Is the previous proposition true if we don’t assume $A \subseteq B$? If not, can you correct it?

Proposition 17. 1. If $A_1 \subseteq A_2 \cdots$ are all events in $\mathcal F$, then $\P(\cup_1^\infty A_n) = \lim_{n \to \infty} \P(A_n)$.

  1. If $A_1 \supseteq A_2 \cdots$ are all events in $\mathcal F$, then $\P(\cap_1^\infty A_n) = \lim_{n \to \infty} \P(A_n)$.

Random variables

Definition 18. Let $(\Omega, \mathcal F, \P)$ be a probability space. We say $X$ is a random variable on $\Omega$ if:

  1. $X \colon \Omega \to \R$ is a function.
  2. For every $a \in \R$, we have $\set{X < a} \in \mathcal F$.

The function $X$ represents all possible values your random variable can take when you perform your experiment. If $\omega \in\Omega$ is one particular outcome of your experiment, then $X(\omega)$ is called a realization of the random variable.

Remark 19. By $\set{X < a}$ we mean $\set{\omega \in \Omega \st X(\omega) < a}$.

Proposition 20. For any $a, b \in \R$, the sets $\set{X = a}$, $\set{X > a}$, $\set{X \geq a}$, $\set{a < X < b }$, $\set{a \leq X < b}$, $\set{a < X \leq b}$ are all also in $\mathcal F$.

Remark 21. In light of the previous proposition, $\P(X < a) \defeq \P( \set{\omega \in \Omega \st X(\omega) < a})$ is defined, as is $\P(X = a)$, $\P(x > a)$, etc.

Example 22. Let $N \in \N$, and $\Omega = \set{H, T}^N$, $\mathcal F = \mathcal P(\Omega)$ and $\P(A) = \abs{A} / 2^N$. For $\omega = (\omega_1, \dots, \omega_N) \in \Omega$, let $X_n(\omega) = 1$ if $\omega_n = H$ and $-1$ if $\omega_n = T$. This is a probability space representing $N$ independent tosses of a fair coin, and $X_n$ is the outcome of a game where you get $\dollar 1$ if the $n$-th coin lands heads, and lose $\dollar 1$ if the $n$-th coin lands tails.

As mentioned earlier, there are several technicalities that arise when the probability space is infinite. Here is one. Suppose now we wanted to represent an infinite sequence of independent coin tosses. Let’s define $\Omega = \set{H, T}^\N$ (i.e. $\Omega$ is infinite sequences $(\omega_1, \omega_2, \dots)$ where each $\omega_i \in \set{H, T}$. How should we define $\P$? Clearly for any finite sequence $\hat \omega_N = (\hat \omega_1, \dots, \hat \omega_N)$, we would like $$\label{e:P}\tag{P} \P( \set{ (\omega_1, \omega_2, \dots) \in \Omega \st \forall i \leq N, \omega_i = \hat \omega_i } ) = \frac{1}{2^N} \,. $$

Theorem 23. There does not exist a probability measure $\P$ on $(\Omega, \mathcal P(\Omega))$ for which \eqref{e:P} holds. There does, however, exist a $\sigma$-algebra $\mathcal F$ and a probability measure $\P$ on $(\Omega, \mathcal F)$ such that the left hand side of \eqref{e:P} is always defined, and the identity \eqref{e:P} holds.

Another example to keep in mind is the continuous case. Think about an experiment where you draw a real number in the interval $[0, 1]$ uniformly at random. For instance, you lay down a string of length $1$ and cut it at a location chosen uniformly at random. One would represent this experiment by choosing the sample space to be $\Omega = [0, 1]$, and find a probability measure so that $\P( [0, x] ) = x$ for every $x \in [0, 1]$. It’s easy to see that this is equivalent to finding a probability measure $\P$ such that $$\label{e:I}\tag{I} \P( [a, b] ) = b - a \quad \text{for every } a, b \in [0, 1], a < b \,. $$

Theorem 24. There does not exist a probability measure $\P$ on $(\Omega, \mathcal P(\Omega))$ for which \eqref{e:I} holds. There does, however, exist a $\sigma$-algebra $\mathcal L$ and a probability measure $\P$ on $(\Omega, \mathcal L)$ such that the left hand side of \eqref{e:I} is always defined, and the identity \eqref{e:I} holds.

The probability measure above is called the Lebesgue measure. While intuitive, it typically takes a little work to construct, and won’t be done in this course.

Proposition 25. Let $X, Y$ be two random variables on $(\Omega, \mathcal F, \P)$.

  1. Show that $X + Y$ and $XY$ are also random variables.
  2. If $f \colon \R \to \R$ is continuous, then show that $f(X)$ is also a random variable.

Proof sketch. First show $X + Y$ is a random variable.

For the second part, note $\set{f(X) < \alpha} = \set{X \in f^{-1}( (-\infty, \alpha) )}$. Recall, a standard fact about continuous functions guarantees this is again an open set. Write $f^{-1}( (-\infty, \alpha) )$ as a countable union of open intervals.

Finally, use $2XY = (X + Y)^2 - X^2 - Y^2$ to show $XY$ is a random variable.

Definition 26 (Cumulative density function). Let $X$ be a random variable. The cumulative density function (or CDF) of $X$ is defined by $$ F_X(x) = \P(X \leq x) \,. $$

Problem 27. Is the CDF of a random variable left continuous? Is it right continuous? If yes, prove it. If no, find a counter example.

Proof sketch. Recall $F_X$ is right continuous at $\alpha$ if and only if for every sequence $(a_n)_{n \in \N}$ such that $a_n > \alpha$ and $a_n \to \alpha$ as $n \to \infty$, we have $F_X(a_n) \to F_X(\alpha)$ as $n \to \infty$.

Discrete Random Variables

The study of discrete random variables is a little simpler to start with as it avoids several of the technicalities mentioned above. However, even in a first course on probability, one will encounter random variables that are not discrete. These are often handled un-rigorously, imprecisely, or by black-boxing technicalities. We will avoid them for the most part; and black box technicalities when needed.

Definition 28 (Discrete random variables). Let $(\Omega, \mathcal F, \P)$ be a probability space. We say a random variable $X \colon \Omega \to \R$ is discrete if $X(\Omega)$ is countable.

Proposition 29. A random variable is discrete if and only if $X \colon \Omega \to \R$ is a function such that $X(\Omega)$ is countable, and for every $x \in \R$, $\set{X = x} \in \mathcal F$.

Remark 30. For a discrete random variable, for every $A \subseteq \R$, we have $\set{X \in A} \in \mathcal F$.

Definition 31. If $X$ is a discrete random variable, the probability mass function of $X$ is defined by $$ p_X(x) = \P(X = x) \,. $$

Remark 32. For a discrete random variable the probability mass function of a discrete random variable is nonzero at only countably many points.

Very often, we are only interested in the distribution of $X$, and not the probability space $(\Omega, \mathcal F, \P)$. All statistical properties of $X$ can be determined by the probability mass function $p_X$ (for discrete random variables).

Definition 33. Let $X$ be a discrete random variable, and $q \colon \R \to [0, 1]$ be a function. We say $X \sim q$ if for every $x \in \R$, $\P(X = x) = q(x)$ (i.e. if $p_X = q$).

Remark 34. If $X \sim q$, the function $q$ above has to define a (discrete) probability distribution on $\R$. That is $\set{q > 0}$ is countable, and $\sum_{q(x) > 0} q(x) = 1$. One can slightly abuse notation and write $$ \sum_{q(x) > 0} q(x) = \sum_{x \in \R} q(x) \,, $$ where we interpret the sum on the right by ignoring all terms where $q$ vanishes.

Remark 35. Given a discrete random variable $X$, by a similar abuse of notation we define a probability measure $\P_X$ on $(\R, \mathcal P(\R))$ by $$ \P_X(A) = \sum_{a \in A} p_X(a) = \sum_{a \in A} \P(X = a) = \P(X \in A) \,, $$ by ignoring all terms in the sum where $p_X = 0$.

Definition 36. The measure $\P_X$ is called the distribution of the (discrete) random variable $X$.

Remark 37. As before, all statistical properties of $X$ can be determined from the distribution (or the probability mass function), without knowledge of the sample space. Often, given a probability $\mathbf{Q}$ measure on $\R$, we will write $X \sim \mathbf{Q}$ to mean $\P_X = \mathbf{Q}$.

Remark 38. The distribution $\P_X$ is defined even if $X$ is any random variable, and not just a discrete random variable. However, in this case some care has to be taken. $\P_X$ is not always defined on $\mathcal P(\R)$; However, $\P_X$ is a probability measure on $(\R, \mathcal B(\R))$, where $\mathcal B(\R)$ is the Borel $\sigma$-algebra on $\R$ – that is, $\mathcal B(\R)$ is the smallest $\sigma$-algebra that contains all open sets.

A few standard distributions

Definition 39 (Uniform distribution). Let $A \subseteq \R$ be finite, and $X$ be a (discrete) random variable. We say $X$ follows the uniform distribution on $A$ (notation $X \sim \Unif(A)$) if for every $a \in A$ we have $\P(X = a) = 1 / \abs{A}$.

Example 40. The outcome of a roll of a fair die is a uniform random variable on $\set{1, \dots, 6}$.

Remark 41. While the uniform distribution exists on any finite set, there isn’t a discrete uniform distribution on an infinite set. For instance, there isn’t a uniform distribution on the set of natural numbers, and it’s meaningless to say “Choose a natural number uniformly at random”.

Definition 42 (Bernoulli distribution). Let $p \in [0, 1]$. We say a random variable $X$ follows the Bernoulli distribution with parameter $p$ (notation $X \sim \Bernoulli(p)$) if $\P(X = 1) = p$ and $\P(X = 0) = 1 - p$. (Typically this models an experiment that succeeds with probability $p$.)

Definition 43. We say a random variable $X$ follows the Binomial distribution with parameters $N \in \N$, $p \in [0, 1]$ (notation $X \sim \Binom(N, p)$) if for all $k \in \set{0, \dots, N}$ we have $$ \P(X = k) = \binom{N}{k} p^k (1-p)^{N - k} \,. $$

Definition 44 (Geometric distribution). We say a random variable $X$ follows the Geometric distribution with parameter $p \in (0, 1)$ (notation $X \sim \Geom(p)$) if $$ \P(X = k) = p (1- p)^{k-1} \quad\text{for every } k \in \set{1, 2, 3, \dots} $$

The above distributions often arise with experiments involving repeated Bernoulli trials.

Problem 45. Let $N \in \N$, $p \in [0, 1]$, $q = 1 - p$. Let $\Omega = \set{0, 1}^N$, and define $p_m \colon \Omega \to [0, 1]$ by $$ p_m(\omega) = \prod_{i = 1}^N p^{\omega_i} q^{1 - \omega_i} $$ This is a probability space modelling $N$-independent Bernoulli trials with parameter $p$.

  1. Show that $p_m$ is a probability mass function.
  2. If $\omega = (\omega_1, \dots, \omega_N) \in \Omega$, let $X_n(\omega) = \omega_n$. Show that for every $n \in \set{1, \dots, N}$, $X_n \sim \Bernoulli(p)$.
  3. Let $H(\omega) = \sum_1^N \omega_i$ be the number of successes. Show that $H \sim \Binom(N, p)$

Problem 46. Let $p \in (0, 1)$, $q = 1 - p$, and suppose now $\Omega = \set{0, 1}^\N$. For every $n \in \N$, and $\omega = (\omega_1, \omega_2, \dots) \in \Omega$ define $$ X_n(\omega) = \omega_n \,. $$ Suppose further there exists a $\sigma$-algebra, and a probability measure $\P$ such that each $X_n$ is a random variable, and for any finite $N$, and any $\omega = (\omega_1, \omega_2, \dots) \in \Omega)$, we have $$ \P(X_1 = \omega_1, X_2 = \omega_2, \dots, X_N = \omega_N) = \prod_{i = 1}^N p^{\omega_i} q^{1 - \omega_i} $$ This probability space represents running infinitely many independent random $\Bernoulli(p)$ trials. Constructing $\P$ is not easy, which is why we assume for now it exists. Note, from the previous problem, we immediately see that $X_n \sim \Bernoulli(p)$ for every $p$.

  1. For every $\omega \in \Omega$ show that $\P(\omega) = 0$. (Here $\P(\omega)$ means $\P(\set{\omega})$.)
    Hint. Let $C_N(\omega) = \set{\omega’ \in \Omega \st \omega’_i = \omega_i \forall i \leq N}$, and note $\set{\omega} = \cap_N C_N(\omega)$.
  2. Let $\tau(\omega) = \min \set{i \st \omega_i = 1}$ be the number of trials until the first success. Show that $\tau \sim \Geom(p)$. [Note: $\tau$ is undefined when $\omega = (0, 0, \dots)$; but since this is an event of probability $0$, it will not affect any probability computations and we may define $\tau$ arbitrarily on that event.]

Remark 47. The previous problem tells you that even if an event occurs extremely rarely; if you do enough repeated independent trials, it will eventually occur. Indeed, you can compute $\P(\set{\omega \st \omega_i = 0 \forall i}) = \P(\tau = \infty) = 0$. This is a proof of the Infinite monkey theorem, which asserts that if you give a monkey a typewriter, and let it hit keys at random, it will eventually produce the complete works of Shakespeare.

Definition 48 (Poisson distribution). We say a random variable $X$ follows the Poisson distribution with mean $\lambda > 0$ (notation $X \sim \Pois(\lambda)$) if $$ \P(X = k) = \frac{e^{-\lambda} \lambda^k}{k!} \quad\text{for every } k \in \set{0, 1, 2, \dots} \,. $$

The Poisson distribution is a good way to model rare events; if you repeat a Bernoulli trial $N$ times, but the probability of success is of order $O(1/N)$, then the number of successes approaches the Poisson distribution.

Proposition 49. Let $(p_N)_{N \in \N}$ be a sequence in $[0, 1]$, and for every $N \in \N$ suppose $X_N \sim \Binom(N, p_N)$.

  1. If for some $\lambda > 0$, the sequence $N p_N \to \lambda$ as $N \to \infty$, then show that $$ \lim_{N \to \infty} \P( X_N = k ) = \P( Y = k ) \quad\text{for every } k \in \N \,. $$ where $Y \sim \Pois(\lambda)$.
  2. If $N p_N \to 0$ as $N \to \infty$, then show that $$ \lim_{N \to \infty} \P( X_N = k ) = \begin{cases} 0 & k \in \set{1, 2, 3, \dots }\,,\\ 1 & k = 0 \,. \end{cases} $$
  3. If $N p_N \to \infty$ as $N \to \infty$ then show that $$ \lim_{N \to \infty} \P( X_N = k ) = 0 \quad\text{for every } k \in \set{0, 1, 2, \dots} $$

Remark 50. Let’s interpret the result of the previous problem: If $N p_N \to 0$, you’re not performing enough trials of the experiment, and (with probability 1) you never see a success as $N \to \infty$. If $N p_N \to \lambda$, you have a balance; the number of successes you see follows the Poisson distribution with parameter $\lambda$. The last one is a bit trickier to interpret: In this case you’re repeating the experiment too often, and you get overwhelmed by successes. You’re going to see infinitely many successes, which is why for any finite $k$, $\P(X_N = k) \to 0$.