2.5a Expectation

Expectation (LOTUS)

The expectation of a random variable represents its probability-weighted average value. The generalized expectation function can be given by the Law of the Unconscious Statistician (LOTUS):

• The expectation of a discrete random variable $X=g(Y)$ with a range $\mathcal{X}$, where $g:\mathbb{R}\to \mathbb{R}$, is generally defined as,
  $\mathbb{E}[X]={\sum }_{x\in \mathcal{X}}^{}x\cdot p_X(x)={\sum }_{x\in \mathcal{X}}^{}g(y)\cdot p_X(g(y)).$

• Similarly, the expectation of a continuous random variable $X=g(Y)$ is defined as
  $\mathbb{E}(X)={\int }_{-\infty }^{\infty }x\cdot f_X(x)dx={\int }_{-\infty }^{\infty }g(y)\cdot f_X(x)dy.$

Intuition

The expectation can be seen as the average or mean of a probability distribution. It is the most expected value given all probabilities.

Properties

(Linearity) Any $X,Y$ satisfy $\mathbb{E}[\alpha X+\beta Y+\gamma ]=\alpha \mathbb{E}(X)+\beta \mathbb{E}(Y)+\gamma .$

The linearity of expectation can be proved by taking $\mathbb{P}[X=a]={\sum }_{\text{upomega}\in \text{Upomega}}^{}\mathbb{P}[\text{upomega}]$ (sum to one rule). Then taking the definition of a random variable, we get:

$$\begin{array}{c}\begin{array}{rl}\mathbb{E}[X]& =\sum _{a\in \mathcal{A}}a\times \mathbb{P}[X=a]\\ & =\sum _{\text{upomega}\in \text{Upomega}}X(\text{upomega})\times \mathbb{P}[\text{upomega}]\end{array}\end{array}$$

Then, for random variables $X$ and $Y$,

$$\begin{array}{c}\begin{array}{rl}\mathbb{E}[X+Y]& =\sum _{\text{upomega}\in \text{Upomega}}(X+Y)(\text{upomega})\times \mathbb{P}[\text{upomega}]\\ & =\sum _{\text{upomega}\in \text{Upomega}}(X(\text{upomega})+Y(\text{upomega}))\times \mathbb{P}[\text{upomega}]\\ & =\sum _{\text{upomega}\in \text{Upomega}}X(\text{upomega})\times \mathbb{P}[\text{upomega}]+\sum _{\text{upomega}\in \text{Upomega}}Y(\text{upomega})\times \mathbb{P}[\text{upomega}]\\ & =\mathbb{E}[X]+\mathbb{E}[Y]\end{array}\end{array}$$

Why does the probability $\mathbb{P}[\text{upomega}]$ not change with the amount of variables? Well, because we simplify each event $X=a$ into $\text{upomega}\in \text{Upomega}$. All of the above stems from this simple fact, since by the definition of the random variable, \set{\upomega \in \Upomega : X(\upomega) = a} and $\{(a,\mathbb{P}[X=a]):a\in \mathcal{A}\}$. From there, we replace $a$ with $X(\text{upomega})$, and therefore $\mathbb{P}[X=a]$ with $\mathbb{P}[\text{upomega}]$.

(Tail Formula) Any $X\ge 0$ satisfies $\mathbb{E}[X]=\{\begin{array}{l}\sum _{k=1}^{\infty }\mathbb{P}[X\ge k],\\ {\int }_0^{\infty }\mathbb{P}(X\ge k)dk.\end{array}$

For a random variable $X$ that takes values $i\in \{0,1,2,...\}$, each with probability $p_i$,

$$\begin{array}{c}\begin{array}{rl}\mathbb{E}[X]& =(0\times p_0)+(1\times p_1)+(2\times p_2)+...+((i-1)\times p_{i-1})+(i\times p_i)\\ & =(p_1+p_2+...+p_{i-1}+p_i)+(p_2+...+p_{i-1}+p_i)+...+(p_{i-1}+p_i)+p_i\\ & =\mathbb{P}[X\ge 1]+\mathbb{P}[X\ge 2]+...+\mathbb{P}[X\ge i-1]+\mathbb{P}[X\ge i]\\ & =\sum _{i=1}^{\infty }\mathbb{P}[X\ge i].\end{array}\end{array}$$

(Independence) If $X$ and $Y$ are independent, then $\mathbb{E}[XY]=\mathbb{E}[X]\cdot \mathbb{E}[Y]$.

(Conditionality) $\mathbb{E}[X\mid Y=y]=\{\begin{array}{l}\sum _{x\in \mathcal{X}}x\cdot p_{X\mid Y}(x\mid y),\\ {\int }_{-\infty }^{\infty }x\cdot f_{X\mid Y}(x\mid y)dx.\end{array}$

(Iterated/Total Expectation) $\mathbb{E}[X]=\mathbb{E}[\mathbb{E}[X\mid Y]]=\{\begin{array}{l}\sum _{y\in \mathcal{Y}}{p}_Y(y)\mathbb{E}[X\mid Y=y],\\ {\int }_{-\infty }^{\infty }{f}_Y(y)\mathbb{E}[X\mid Y=y]dy.\end{array}$

(Wald’s Identity) If $X=\sum _{i=1}^n{X}_i$, then $\mathbb{E}[X]=\mathbb{E}[X_1]\cdot \mathbb{E}[Y]$.

(Jensen’s Inequality) Any convex $\phi :\mathbb{R}\to \mathbb{R}$ satisfies $\phi (\mathbb{E}[X])\le \mathbb{E}[\phi (X)]$.

Examples

(Expectation, Indicator Variables) Connecting Ropes

You have $n$ identical lengths of rope, each with two loose ends. You toss all ropes into a bag, swirl them around, then–without looking–pull out two ends and tie them together.

What is the probability that the two ends you just tied belong to the same rope? Before grabbing any rope, we have $2n$ possible ends to grab. After grabbing the first end, we grab another one of the $2n-1$ ends. This gives us $2n(2n-1)$ possible outcomes for grabbing two random ends.

Consider the possibility of grabbing the same rope. Before grabbing any end, we can blindly pick any one of the $2n$ ropes. However, after we grab our first end, there is exactly $1$ way of grabbing the other end of the same rope. Therefore, there are exactly $2n$ ways of grabbing the same rope. This makes intuitive sense: you can grab either ends of the same rope in the beginning, and then grab the second end. Therefore, we have:
$\mathbb{P}(\text{Same rope in first attempt})=\frac{2n}{2n(2n-1)}=\frac{1}{2n-1}.$

If you continue this process until all ends are connected, what is the expected total number of times you ever tie the two ends of the same rope together?

Consider the following indicator variable:

1 & \text{the two ends of rope } i \text{ are paired}, \
0 & \text{otherwise,}
\end{cases}$$

where $\mathbb{P}(I_i=1)=\frac{1}{2n-1}$ for all $i$. Then, $N={\sum }_{i=1}^n{I}_i$ is the number of self-loops after all ends have been tied. As such,
$\mathbb{E}(N)={\sum }_{i=1}^n\mathbb{E}(I_i)=\frac{n}{2n-1}.$

What is the expected number of total loops after there are no loose ends left? $2n$ loose ends and immediately tie 2 ends, yielding $2n-1$ loose ends. We proceed until there are no loose ends left. Let $\mathbb{E}[T_n]$ represent the number of total loops given $n$ ropes.

We start with

(Iterated Expectation) Dice Game

You roll a dice. For each roll, you are paid the face value. If a roll gives 4, 5, or 6, you can roll the dice again. Once you get 1, 2, or 3, the game stops.

What is the expected payoff of this game? $X_n$ be your cumulative expected payoff in round $n$, and let $C_{i-1}\sim \text{Ber}(1/2)$ be an indicator variable showing the outcome of your last throw (i.e., whether you rolled 4, 5, 6 or not). Then,

Let

\mathbb{E}(X)&=\mathbb{E}(\mathbb{E}(X \mid C)) \
&=\frac{1}{2} \cdot \mathbb{E}(X \mid C=0) + \frac{1}{2} \cdot \mathbb{E}(X \mid C=1) \
&= \frac{1}{2} \cdot \frac{1+2+3}{3}+\frac{1}{2} \cdot \left(\frac{4+5+6}{3}+\mathbb{E}(X)\right) \
&= 7.
\end{align}$$

We add $\mathbb{E}(X)$ to our payoff on the right hand side, since you continue playing if you roll 4, 5, or 6 for an indefinite amount of time.

Ace Hunt

Ace Hunt is a solo “table game” played with a freshly shuffled 52-card deck placed face-down in the center. You (the dealer) turn over cards one at a time into a single community pile, pausing only when the very first Ace appears; at that moment the hand ends and the total number of cards revealed is recorded. The person whose guess is closest to the recorded number of total cards wins.

What is the probability that you will need to turn over exactly $k$ cards before revealing the first Ace? Let $X_n$ denote the even that the $n$-th card turned over is an Ace. Then, $\mathbb{P}\left(X_{k+1}|{\bigcap }_{i=1}^k{X}_i=0\right)=\frac{4}{52-k}.$

What is the expected number of cards you must expose to see the first Ace? $X$ as the number of cards turned over before the first ace. Then, $X=1+{\sum }_{i=1}^{48}{X}_i$ (since there are at most 48 non-Ace cards drawn before the first ace, where

Denote

1 & \text{i-th card is not an Ace} \
0 & \text{otherwise}.
\end{cases}$$

Coupon Collector

Let there be $n$ distinct coupon types, labeled $1,2,\dots ,n$.  You collect coupons from cereal boxes one at a time; on each trial you receive exactly one coupon, and each type is always equally likely.

If you want to collect a complete set of coupons with at least one of each type, how many boxes on average are needed to complete the set? $X_i$ represent the number of additional (marginal) draws needed to collect the $i$-th coupon type after $i-1$ types have been collected. Then, $X={\sum }_{i=1}^n{X}_i$ is the total number of coupons needed for all $n$ coupon types to be collected.

Let

Given that $i-1$ coupons are collected, a new coupon will be a different type with probability $1-\frac{i-1}{n}$. Since each $X_i$ is a first-success measure, $X_i\sim \text{Geom}\left(\frac{n-i+1}{n}\right)$. As such,

If you have collected $k$ coupons, what is the expected number of distinct coupon types? Let $X={\sum }_{i=1}^n{X}_i$ represent the present coupon types, such that $X_i$ indicates whether the $i$-th coupon type is present. The probability of a coupon type that is NOT the $i$-th type is exactly $\frac{n-1}{n}$, and therefore $\mathbb{P}(X_i=0)={\left(\frac{n-1}{n}\right)}^k$ indicates that in the sequence of $k$ draws, the $i$-th coupon does not appear once. We can express $X$ as a sum of $X_i\sim \text{Ber}\left(1-{\left[\frac{n-1}{n}\right]}^k\right)$, such that