Techniques for calculating expected values

This is a list of techniques I’ve found useful for computing expected values. In the interest of clarity and intuition over strict theoretical correctness, I’ve opted to take some liberties with the notation and not to document every assumption.

• Weighted average of possible values

  • $\mathbb{E}[X] = \displaystyle\sum_i x_i \mathbb{P}(X = x_i)$
  • This is the standard definition of expected value. It’s usually only useful if you can easily calculate the probability distribution $\mathbb{P}(X = x_i)$.
  • Example: If $R$ is the value of a single roll of a die, then
  $$\mathbb{E}[R] = \left(1\cdot\frac16\right) + \left(2\cdot\frac16\right) + \cdots + \left(6\cdot\frac16\right) = \frac{7}{2}$$

• Linearity of expectation

  • $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$
  • Example: If $S$ is the sum of two independent rolls of a die, then
  $$\mathbb{E}[S] = \mathbb{E}[R_1 + R_2] = \mathbb{E}[R_1] + \mathbb{E}[R_2] = 7$$
  • Example: Suppose $n$ people enter a restaurant and leave their hats at reception. At the end of dinner, each person gets a hat back at random. In expectation, how many people get their own hat back?
    • Let $H$ be the number of people who correctly get their own hat back and $H_i$ be an indicator variable indicating whether the $i$th person got their own hat back.
    • $\mathbb{E}[H] = \mathbb{E}[H_1] + \mathbb{E}[H_2] + \cdots + \mathbb{E}[H_n] = n\mathbb{E}[H_1] = n(1/n) = 1$
    • Note that $H_i$ and $H_j$ aren’t independent, but linearity of expectation works anyway! $H$ is a classic example of a random variable whose expected value is much easier to compute than its distribution.

• Law of total expectation

  • $\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X|Y]]$
  • Sometimes the random variable is simpler if you condition on another random variable.
  • Example: Suppose you roll a fair die and record the value. Then you continue rolling the die until you obtain a value at least as large as the first roll. In expectation, how many additional rolls are there after the first?
    • Let $N$ be the number of additional rolls after the first and $X_1$ be the value of the first roll.
    • Given $X_1 = i$, each subsequent roll succeeds with probability $(7-i)/6$, so $N | X_1$ is geometric with mean $6 / (7-i)$.
    • Then $\mathbb{E}[N] = \mathbb{E}[\mathbb{E}[N|X_1]] = \mathbb{E}[6 / (7 - X_1)] = \sum_{i=1}^{6} (1/6)(6/(7-i)) = 49/20$.
    • In this case, it’s hard to understand $N$ without first conditioning on $X_1$, but we can calculate $\mathbb{E}[N]$ by “averaging” over all the possible values of $X_1$.

• Symmetry

  • If $(X_1, \ldots, X_n)$ are exchangeable and $\sum_{i=1}^{n} X_i = T$, then $\mathbb{E}[X_i] = \mathbb{E}[T] / n$.
  • Example: If you randomly break a stick of length $L$ into $n$ pieces, then the expected length of the leftmost piece is $L/n$.
  • Example: Suppose each day either 100 or 200 birds appear (each with 50% probability) and then divide themselves randomly among 15 statues. Let $B$ be the total number of birds on each day and $B_i$ be the number of birds on the $i$th statue. Then $\mathbb{E}[B_i] = \mathbb{E}[B] / 15 = 150 / 15 = 10$

• Recursion

  • Example: What is the expected number of coin flips to see HTH?
    • There are 4 states: 0 (Start), 1 (Have seen H), 2 (Have seen HT), and 3 (Done).
    • Let $X_i$ represent the number of flips to transition from state $i$ to state 3. We want to compute $\mathbb{E}[X_0]$.
    • Obviously $X_3 = 0$, so $\mathbb{E}[X_3] = 0$.
    • From state 2, we flip once and transition to either state 3 or state 0, so $\mathbb{E}[X_2] = 1 + \mathbb{E}[X_3]/2 + \mathbb{E}[X_0]/2 = 1 + \mathbb{E}[X_0]/2$
    • From state 1, we flip once and transition to either state 1 or state 2, so $\mathbb{E}[X_1] = 1 + \mathbb{E}[X_1]/2 + \mathbb{E}[X_2]/2$
    • From state 0, we flip once and transition to either state 0 or state 1, so $\mathbb{E}[X_0] = 1 + \mathbb{E}[X_0]/2 + \mathbb{E}[X_1]/2$
    • We have three equations in three variables. Solving yields $\mathbb{E}[X_0] = 10$, $\mathbb{E}[X_1] = 8$, $\mathbb{E}[X_2] = 6$.

• Product of independent random variables

  • If $X$ and $Y$ are independent random variables, then $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$
  • Example: A factory makes widgets. Each widget goes through 2 inspections. Each inspection has an independent 90% chance of passing. Let $I_1, I_2$ be the indicator variables for passing each respective inspection. Then $\mathbb{E}[I_1I_2] = \mathbb{E}[I_1]\mathbb{E}[I_2] = 81\%$

• Wald’s equation

  • If $X_1, X_2, \ldots$ are real and iid, and $N$ is a random integer, then $\mathbb{E}[X_1 + \cdots + X_N] = \mathbb{E}[N] \cdot \mathbb{E}[X_1]$.
  • Example: A pirate opens identical treasure chests one-by-one. Each chest randomly contains between 1 and 6 coins. The pirate stops when he opens a “cursed” chest containing only 1 coin. Let $N$ be the number of chests opened, $C$ be the total number of coins collected, and $C_i$ be the number of coins in the $i$th chest. Then $\mathbb{E}[C] = \mathbb{E}[\sum_{i=1}^{N} C_i] = \mathbb{E}[N] \cdot \mathbb{E}[C_1] = 6 \cdot 3.5 = 21$

• Tail-sum

  • If $X$ is non-negative and continuous, then $\mathbb{E}[X] = \displaystyle\int_{0}^{\infty} \mathbb{P}(X > t) \mathop{}\!\mathrm{d} t$
  • If $X$ is non-negative and integer-valued, then $\mathbb{E}[X] = \displaystyle\sum_{t=0}^{\infty} \mathbb{P}(X > t)$
  • Example: Let $N$ be the number of coin flips needed to get the first head. Then $\mathbb{E}[N] = \sum_{t=0}^{\infty} \mathbb{P}(N > t) = 1 + 1/2 + 1/4 + \cdots = 2$, since the event $N > t$ occurs if and only if the first $t$ flips are all tails and therefore $\mathbb{P}(N > t) = 1/2^t$.