Expected Value
Lesson · Intermediate
Probability
If X can take values
with probabilities
then
where
Expected value is the long-run average outcome if the experiment is repeated many times.
For any random variables X and Y,
More generally,
Also,
The key fact: Independence is not required.
Suppose X and Y are discrete random variables.
Then
Split the sum:
The first sum is E(X), and the second is E(Y).
Therefore,
A fair coin is tossed 20 times. Find the expected number of heads.
Let
Then
and
Therefore,
The numbers 1, 2, ..., n are randomly permuted.
Find the expected number of numbers that remain in their original positions.
Let Iₖ = 1 if k remains in position k.
Then
so
If X is the total number of fixed points,
Thus
So the expected number of fixed points is 1
Three distinct numbers are chosen uniformly at random from 1, 2, ..., 20.
Find the expected value of their sum.
Each number has probability
of being selected.
Let Iₖ = 1 if k is selected.
Then the sum is
Therefore,
A fair coin is tossed 10 times.
Find the expected number of indices i for which tosses i and i + 1 are the same.
There are 9 adjacent pairs.
Let Iᵢ = 1 if tosses i and i + 1 are equal.
For each pair,
Thus
Therefore,
A random permutation of 1, 2, ..., n is chosen.
An inversion is a pair i < j such that i appears after j.
Find the expected number of inversions.
For each pair i < j, define Iᵢⱼ = 1 if the pair forms an inversion.
For any fixed pair i, j, the two possible relative orders are equally likely.
Therefore,
There are
pairs.
Thus