Skip to main content

MA 415G course notes

Benjamin Braun

Section 4.2 Finite Probability Spaces and Random Variables

Our first task is to clearly define what we mean when we talk about likelihood of an event occurring.
🔗

Definition 4.2.1.

Let \(\Omega\) be a finite set. We refer to the elements of \(\Omega\) as events. A probability distribution on \(\Omega\) is a function
\begin{equation*} P:\Omega\mapsto \mathbb{R_{\geq 0}} \end{equation*}
such that
\begin{equation*} \sum_{x\in \Omega}P(x)=1 \, . \end{equation*}
Given a finite set \(\Omega\) together with a probability distribution \(P\text{,}\) we call the pair \((\Omega,P)\) a finite probability space.
🔗
We call a subset \(A\subseteq \Omega\) an event set, and define the probability of the event set \(A\) to be
\begin{equation*} P(A):=\sum_{x\in A}P(x) \, . \end{equation*}
If \(P(x)=1/|\Omega|\) for all \(x\in \Omega\text{,}\) then we call \(P\) the uniform distribution.
🔗
🔗

Example 4.2.2.

Consider the set
\begin{equation*} \Omega=\{00,10,01,11\} \end{equation*}
of binary strings of length two, with the uniform distribution \(P(x)=1/4\text{.}\) The interpretation of this distribution is that if you pick one of the four binarys string of length two at random, you are equally likely to pick any of the four strings -- each will appear \(1/4\) of the time.
🔗
🔗

Example 4.2.3.

Consider the set of outcomes from rolling a die, which is the values appearing on the six sides:
\begin{equation*} \Omega=\{1,2,3,4,5,6\} \, . \end{equation*}
The uniform distribution in this case gives \(P(x)=1/6\text{.}\) The interpretation of this distribution is that if you roll a fair die, you are equally likely to roll any of the six sides -- each will appear \(1/6\) of the time.
🔗
🔗

Example 4.2.4.

Consider again the set
\begin{equation*} \Omega=\{00,10,01,11\} \end{equation*}
of binary strings of length two, but this time we will use a different probability distribution. Set
\begin{equation*} P_{1/8}(x)=(1/8)^{\text{number of }0\text{'s in }x}(7/8)^{\text{number of }1\text{'s in }x} \, . \end{equation*}
Is this a probability distribution? Let’s check!
🔗
First observe that
\begin{align*} P_{1/8}(00) \amp =(1/8)^2(7/8)^0\\ P_{1/8}(10)=P_{1/8}(01) \amp =(1/8)^1(7/8)^1\\ P_{1/8}(11) \amp =(1/8)^0(7/8)^2 \end{align*}
and therefore using the binomial theorem we have
\begin{align*} \amp P_{1/8}(00)+P_{1/8}(10)+P_{1/8}(01)+P_{1/8}(11) = \\ \amp (1/8)^2(7/8)^0 + 2(1/8)^1(7/8)^1 + (1/8)^0(7/8)^2 = \\ \amp (1/8+7/8)^2 =\\ \amp 1 \, . \end{align*}
So, this is a probability distribution on \(\{00,10,01,11\}\) -- it is one which strongly favors binary strings that contain more \(1\)’s.
🔗
🔗

Checkpoint 4.2.5.

Let \(p\in (0,1)\text{.}\) Prove that if \(\Omega\) is the set of all binary strings of length \(3\text{,}\) the function
\begin{equation*} P_{p}(x)=(p)^{\text{number of }0\text{'s in }x}(1-p)^{\text{number of }1\text{'s in }x} \end{equation*}
is a probability distribution.
🔗
🔗
The previous exercise is a special case of the following theorem.
🔗

Proof.

Using the binomial theorem, we have that
\begin{align*} \sum_{w\in \Omega} [(p)^{\text{number of }0\text{'s in }x}(1-p)^{\text{number of }1\text{'s in }x}] \amp =\sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k} \\ \amp = (p+(1-p))^n \\ \amp = 1 \, . \end{align*}
🔗
🔗

Checkpoint 4.2.7.

Discuss the proof above. Does it make sense? Why or why not?
🔗
🔗

Checkpoint 4.2.8.

Explain why the binomial distribution
\begin{equation*} P_{p}(w)=(p)^{\text{number of }0\text{'s in }w}(1-p)^{\text{number of }1\text{'s in }w} \, . \end{equation*}
on binary strings of length \(n\) with parameter \(p=1/2\) is the uniform distribution.
🔗
🔗

Definition 4.2.9.

Given a probability distribution \(P\) on a finite set \(\Omega\text{,}\) a random variable is a function \(X:\Omega\mapsto \mathbb{R}\text{.}\) If \(x\in \Omega\text{,}\) we refer to \(X(x)\) as the value of the random variable \(X\) on the event \(x\text{.}\)
🔗
🔗

Example 4.2.10.

Consider again the set \(\Omega=\{00,10,01,11\}\) of binary strings of length two, with the uniform distribution. Define the random variable \(X:\Omega\mapsto \mathbb{R}\) by
\begin{equation*} X(00)=0, X(10)=1, X(01)=1, X(11)=2\text{.} \end{equation*}
The interpretation of this random variable is that \(X(w)\) counts the number of \(1\)’s in the binary string \(w\text{.}\)
🔗
🔗

Example 4.2.11.

Consider again the set of outcomes from rolling a die, which is the values appearing on the six sides: \(\Omega=\{1,2,3,4,5,6\}\text{,}\) with the uniform distribution. Define the random variable \(Y:\Omega\mapsto \mathbb{R}\) by
\begin{equation*} Y(i)=i\text{.} \end{equation*}
The interpretation of this random variable is that \(Y(i)\) is the value appearing on the side of the die when you roll a \(i\text{.}\)
🔗
🔗

Example 4.2.12.

Consider the set of permutations \(\Omega=\ss_n\) with the uniform distribution. Let \(X:\ss_n\mapsto \mathbb{R}\) be the random variable defined by
\begin{equation*} X(\pi)=\text{number of fixed points of }\pi \, . \end{equation*}
The interpretation of this random variable is that \(X(\pi)\) counts the number of fixed points in the permutation \(\pi\text{.}\)
🔗
🔗

Example 4.2.13.

Consider the set of all graphs on \(n\) vertices, which we will write \(\Omega=\mathcal{G}_n\text{,}\) with the uniform distribution. Let \(X:\mathcal{G}_n\mapsto \mathbb{R}\) be the random variable defined by
\begin{equation*} X(G)=\text{number of spanning trees of }G \, . \end{equation*}
The interpretation of this random variable is that \(X(G)\) counts the number of spanning trees in the graph \(G\text{.}\)
🔗
🔗
The key question we want to answer is: given a random variable \(X\) on a finite probability space \((\Omega,P)\text{,}\) if I pick an element of \(\Omega\) according to the distribution \(P\text{,}\) what is the expected value of \(X(w)\text{?}\)
🔗
🔗
PrevTopNext