E[X]

Unexpected expected value

Apr 7, 2023

As mentioned, I have a written-out lecture from MBL-B on this topic: here.

The expected value of an event is the sum of all expected values of all possible outcomes of that event. Now what's the expected value of an outcome is simple ; it's just the value of that particular outcome times its likelihood. The expected value of any event, put mathematically:

\[ \textnormal{Expected value} (\textnormal{event}) = \sum \limits_{\textnormal{outcome}}^{\textnormal{all possible outcomes}} \ \textnormal{Value(outcome)} \cdot P(\textnormal{event = outcome}) \]

or with standard notations, $X$ being the name for the event and $x$ being the value of the event.

\[ \mathbb{E}[X] = \sum \limits_{x}^{} \ x \cdot P(X = x) \]

Note the differences in capitalization of $x$ represent different things. To make this clear, here's the standard example:

Imagine you throw a six-sided dice $100$ times and add up all the numbers you got. What approximate number do you expect i.e. what's the expected value of this event?

Going by the above definition the problem would be partitioned into $6$ events: you roll a $1$, you roll a $2$ ... you roll a $6$. Calculating the expected value of one dice roll you get: $1/6 \cdot 1 + 1/6 \cdot 2 + ... + 1/6 \cdot 6 = 3.5$. It is obvious that the expected values "stack" (you can verify by calculating the $100$ at once) so we can conclude that the expected value of our $100$ rolls is $350$.

~~When I was little,~~ I loved to play the Pokémon Trading Card Game. Though, I hated these types of moves:

"Flip $3$ coins. This attack does $10$ damage times the number of heads."

"Flip a coin until you get tails. This attack does $30$ damage times the number of heads."

I didn't know whether I should save up more energy for the second attack or do the first attack for less energy. I didn't know whether the move is any good compared to other Pokémon's moves I could have put into my deck. I didn't have an idea of what's the average damage of the first move. After I learned enough math and taught myself expected values, I decided to figure it out.

I found the average in two ways. First one using pretty standard calculations with probability and the second one I used Linearity of Expectations. I'll first work on the Cubchoo.

Cubchoo's move - Fury Swipes

Solution 1:

Let $T$ be tails, and $H$ be heads. $HTT$ means we got one heads in three throws and it was in the first throw.
There's a total of $8$ different possible outcomes of these $3$ coin flips:

\[ TTT, TTH, THT, THH, HTT, HTH, HHT, HHH \]

(binary strings of length $3$ if you think of the $H$ as a $1$).

The outcome $TTT$ has value $0$ and its probability of happening is $1/8$.
The outcome $HHH$ has value $10 \times 3$ and probability $1/8$.
The outcomes $HTT, THT, TTH$ have value $30$ and probability $3/8$ that any of them happens.
The outcomes $HHT, HTH, THH$ have value $20$ and probability $3/8$ that any of them happens.

We've covered all cases and can calculate the expected value now:

\[ \mathbb{E}[\textnormal{Fury Swipes}] = \frac{1}{8} \cdot 0 + \frac{1}{8} \cdot 30 + \frac{3}{8} \cdot 20 + \frac{3}{8} \cdot 10 = 15 \]

It turns out that it's no accident that this is $3 \cdot 10 /2$. Generalizing the move to $n$ throws, each dealing $d$ damage we get: $\frac{d\cdot n}{2}$. Here's the proof:

We need to calculate the probability of having exactly $k$ heads $(k \in (0,n) )$. This is the same as calculating the number of binary strings of length $n$ with exactly $k$ ones. This is just the number of ways to choose $k$ places to place the ones, so this is ${n \choose k}$. So this contributes to our expected value with $\frac{n \choose k}{2^n} \cdot d \cdot k$.
We need to calculate the sum

\[ \sum \limits_{k=0}^{n} {d \cdot k} \cdot \frac{n \choose k}{2^n} = d \cdot \sum \limits_{k=0}^{n} k \cdot \frac{n \choose k}{2^n} = d \cdot \sum \limits_{k=0}^{n} n \cdot \frac{n - 1 \choose k - 1}{2^n} = \frac{dn}{2} \]

I used the following facts: \[ (1+1)^n = \sum \limits_{k=0}^{n} {n \choose k} = 2^n \] \[ k \cdot {n \choose k} = n \cdot {n-1 \choose k-1} \]

Solution 2:

A much faster solution is to use Linearity of Expectations. Linearity says that $\mathbb{E}[A+B] = \mathbb{E}[A] + \mathbb{E}[B]$ for $A,B$ independent or dependent events. For example, if we have two dice rolls the expected value of this event as a whole is the same as the expected value of the first dice roll plus the second roll.
This logic allows us to destroy the above problem. Each coin flip is an event of its own and has its own expected value. The expected value of one coin flip is obviously $d/2$ so since we have $n$ flips the expected value will be $dn/2$ and we're done.
This might not be too impressive, but the second link in further reading will show the true power of LoE (Linearity of Expectations) on the problem What's the expected number of cycles in a random permutation?.

Spoiler: turns out for $n$ elements it's the harmonic sum up until $n$ terms.

Pikachu's move - Iron Tail

As a fun exercise, try to determine the expected value of Pikachu's move that deals an additional $30$ damage for each flip until you get a tails. The answer is somewhat surprisingly just $30$. In general for $d$ damage per heads the answer is $d$.

Here's a nice diagram that depicts the possibility space of the flips:

Each level down you go, you add $1/2$ to probability of it happening.

Now let's calculate the expected value:
Following the tree downwards, keeping track of the red letters where we stop, we get the following:

\[ \mathbb{E}[\textnormal{Iron Tail}] = \frac{1}{2} \cdot 0 + \frac{1}{2^2}\cdot d + \frac{1}{2^3}\cdot 2d + \frac{1}{2^4}\cdot 3d + \ldots \]

\[ \mathbb{E}[\textnormal{Iron Tail}] = \frac{d}{2} \cdot (\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\ldots) \]

We find the following sum: \[ \sum \limits_{k=1}^{\infty} \frac{k}{2^k} = 2 \] hence we get: \[ \mathbb{E}[\textnormal{Iron Tail}] = \frac{d}{2} \cdot 2 = d \ \ \blacksquare. \] You can find the above sum in a plethora of ways (See most of them here). My favorite go-to method is the Method of Pertrubation:

Denote the sum up until $k$ terms as $s_k$. I'll find the closed form of $s_k$.

\[ s_{k+1} = s_{k} + \frac{k+1}{2^{k+1}} = \frac{1}{2}+(\frac{2}{2^2}+\frac{3}{2^3}+\ldots + \frac{k+1}{2^{k+1}}) \]

\[ = \frac{1}{2} + (\frac{1}{2^2} + \ldots \frac{1}{2^{k+1}}) + \frac{1}{2}(\frac{1}{2} + \frac{2}{2^2} + \ldots + \frac{k}{2^k}) \]

\[ = \frac{1}{2} + \frac{1}{4} \cdot (1-\frac{1}{2^k}) \cdot 2 + \frac{1}{2} \cdot s_k\]

\[ \implies s_k = 2 - \frac{k+2}{2^k} \] I left out the comparing of the first equation with the last. It's straightforward.
Hence its limit is $2$ as $k$ goes to infinity since $k+2$ is eaten up by the $2^k$.
The idea is to first separate the first term and the last and then compare the two expressions. The goal is to manipulate the both sides to reach previous terms, analogous to recursion. It works on a lot of different sums and is very useful to keep in mind.
Such sums are also called arithmetico-geometric sums. They can be calculated with the trick of multiplying by $1/2$ and then subtracting from the original sum - something very similar to the Pertrubation method. Read more on arithmetico-geometric series.

The Pikachu problem is actually a subcase of the Mean Time to Failure problem which states the following:

Mean Time to Failure

If a system independently fails at each time step with probability $p$, then the expected number of steps up to the first failure is $\frac 1p$.

This is very intuitive. Think of a Nintendo that has a $1/7$ probability of crashing each time you run Pokémon, you expect to be able to play $7$ times with $1$ crash.
We've already proved this problem for the subcase $p=1/2$ (with the added $d$ in front for damage) and got the result. Think of the tails as being a crash and the heads adding $1$ to our counter of how many have already been heads/not crashed.
Let $\mathbb{E}[X]$ denote the expected number of games until you crash. Examine the first try - the first time you tried turning on Pokémon. We divide our examination into two cases: $1)$ It turned on, yay! $2)$ It crashed, nay. Here's the equation we get:

\[ \mathbb{E}[\textnormal{number of attempts until failure}] = \mathbb{P}(\textnormal{of failure}) \cdot 1 + \mathbb{P}(\textnormal{of success}) \cdot \mathbb{E}[\textnormal{number of attempts until failure in this case}]\]

In general if we let $X$ be the r.v. number of attempts until failure, $F$ failure and $S$ success we have:

\[ \mathbb{E}[X] = \mathbb{P}(F)\cdot \mathbb{E}[X|F] + \mathbb{P}(S) \cdot \mathbb{E}[X|S] \]

\[ \mathbb{E}[X]= p \cdot 1 + (1-p) \cdot (\mathbb{E}[X] + 1) \]

\[ \implies \mathbb{E}[X] = \frac 1p \]

Calculating directly instead of the case examination would lead us to the following solution:

\[ \mathbb{E}[X] = \sum \limits_{1}^{\infty} k \cdot (1-p)^{k-1}\cdot p = \frac 1p \]

"As a further example, suppose a couple insists on having children until they get a boy, then how many baby girls should they expect before their first boy? Assume for simplicity that there is a $50%$ chance that a child will be a boy and that the genders of siblings are mutually independent. This is really a variant of the previous problem. The question, “How many hours until the program crashes?” is mathematically the same as the question, “How many children must the couple have until they get a boy?” In this case, a crash corresponds to having a boy, so $p=1/2$. By the preceding analysis, the couple should expect a baby boy after having $1/p = 2$ children. Since the last of these will be a boy, they should expect just one girl. So even in societies where couples pursue this commitment to boys, the expected population will divide evenly between boys and girls." (taken from MIT OCW - Expectation: Chapter 18.4-18.5)

Problems

Problem 1 (Random permutations): Each year, as part of a “Secret Santa” tradition, a group of $n$ friends write their names on slips of papers and place the slips into a hat. Each member of the group draws a name at random from the hat and must by a gift for that person. Of course, it is possible that they draw their own name, in which case they buy a gift for themselves. What is the expected number of people who draw their own name?
Problem 2 (Coupon collector): McDonald’s decides to give a Pokémon toy with every Happy Meal. Each time you buy a Happy Meal, you are equally likely to get any one of the $n$ Pokémon. What is the expected number of Happy Meals that you have to buy until you “catch ’em all”?
Problem 3 (Birthday paradox): A group of $60$ people are comparing their birthdays (as usual, assume that their birthdays are independent, all $365$ days are equally likely, etc.). Find the expected number of days in the year on which at least two of these people were born.
Problem 4 (Shoelace problem): There are $100$ shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops?

Unexpected expected values

Mathematics - Expected value - Method of Pertrubation