Expected values
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 probability. The expected value of any event:
or with standard notations, $X$ being the random variable representing the event and $x$ being the value of the random variable for a particular outcome. Note the differences in capitalization of $x$. To make this clear, here's the first example given in most textbooks:
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?
When I was little, I loved to play the Pokémon Trading Card Game. Though, I was confused by these types of moves:
Fury Swipes: Flip $3$ coins. This attack does $10$ damage times the number of heads.
Iron Tail: 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 I decided to figure it out. (That is probably the single best way of learning math, start with a problem you want to solve and then learn the math you need to solve it.)
I found the answer in two ways. The first way 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$ equally likely different possible outcomes for these $3$ coin flips:
(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:
It turns out that it's no accident that this is $3 \cdot 10 /2$.
Generalization
Generalizing the move to $n$ throws, each dealing $d$ damage the answer is $\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
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 random variables. 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 now makes the above problem easy. 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. 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 another fun exercise, lets 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:
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$. Rewrite it in two ways and compare:
\[ \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 as another tool for such summations.
The easiest way to solve this sum is to differentiate the geometric series (but this requires The Differentiation Theorem for Power Series which is non-trivial).
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 case 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. Condition on 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:
In general if we let $X$ be the r.v. representing the number of attempts until failure, $F$ failure and $S$ success we have:
Calculating directly instead of the case examination would lead us to the following solution:
A further (simple) example
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)
Practice 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?
- Problem 5 (Oxford Problem Sheet Question)
-
Consider a symmetric random walk on a cycle with $N$ sites, labelled $0, 1, 2, . . . , N-1$.
A particle starts at site $0$, and at each step it jumps from its current site $i$ to one of its
two neighbours $i+1 \ (\text{mod } N)$ and $i-1 \ (\text{mod } N)$ with equal probability (independently
of how it arrived at its current position).
$\text(a)$ Find the expected number of steps until every site has been visited. [Hint: just after a new site has been visited, what does the set of visited sites look like?]
$\text(b)$ For each $k = 1, . . . , N-1$, what is the probability that $k$ is the last site to be visited? [Hint: before visiting site $k$, the walk must visit either site $k-1$ or site $k+1$. What needs to happen from that point onwards?]
