Expectation adds, even when nothing is independent
Tonight's idea
\(n\) people hand in their hats, which come back in a random order. On average, how many people get their own? Counting the orders is hard work. There is a one-line route.
The expected value \(E(X)\) is the long-run average of a random number \(X\) (sheet a14). The key fact:
\(E(X + Y) = E(X) + E(Y)\), always, independent or not.
Why? Average \(X + Y\) over many runs. That is one long sum, and you may add the \(X\)s first and the \(Y\)s second. How they affect each other never comes into it.
To count, use indicators. Let \(X_i\) be 1 if person \(i\) gets their own hat, 0 if not. Its average is the chance of a 1, which is \(\tfrac1n\). The number of matches is \(X_1 + \cdots + X_n\), so
\[E(\text{matches}) = n \times \tfrac1n = 1.\]
One, for 3 people or 3 million. The \(X_i\) are not independent: if everyone else has their own hat, so do you. It did not matter.
Watch one: heads twice in a row
Flip a coin 20 times. Count the places where a head is followed at once by another head, so HHH counts twice. What is the expected count?
There are 19 neighbouring pairs of flips. Give each an indicator: 1 if it is HH, with chance \(\tfrac14\). Add them up:
\[E = 19 \times \tfrac14 = 4.75.\]
Neighbouring pairs share a flip, so they are far from independent. The sum did not care. Check with 3 flips: of the 8 sequences, HHH scores 2, HHT and THH score 1, a total of 4. The average is \(\tfrac48 = 2 \times \tfrac14\).
Your turn
- (a) Thirty students each roll a die. What is the expected number of sixes? (b) What is the expected total when you roll ten dice?
- Shuffle a 52-card deck (26 red, 26 black) and deal it in a row. Find the expected number of neighbouring pairs in which both cards are red.
- Thirty people are in a room. Assume 365 equally likely birthdays. Find the expected number of pairs of people who share a birthday. (Give each pair an indicator.)
- Ten people enter a lift on the ground floor. There are 5 floors above, and each person picks one at random, independently. Find the expected number of floors at which the lift stops. Choose your indicators with care.
Stretch: records
Ten different numbers are read out in a random order. A number is a record if it is bigger than every number before it, so the first is always a record. Find the expected number of records.
Answers
- (a) Thirty indicators, each with chance \(\tfrac16\): \(30 \times \tfrac16 = 5\). (b) One die averages \((1 + 2 + \cdots + 6)/6 = 3.5\), so ten average \(35\).
- There are 51 neighbouring pairs. A given pair is red-red with chance \(\tfrac{26}{52} \times \tfrac{25}{51}\). So \(E = 51 \times \tfrac{26}{52} \times \tfrac{25}{51} = 12.5\).
- There are \(\binom{30}{2} = 435\) pairs, and each shares a birthday with chance \(\tfrac1{365}\). \(E = 435/365 \approx 1.19\). More than one shared pair is expected, which is why a shared birthday in a class is no surprise (the birthday paradox).
- Use one indicator per floor, not per person. A floor is missed if all ten people choose another floor: chance \(\left(\tfrac45\right)^{10} \approx 0.107\). So the lift stops there with chance \(0.893\), and \(E = 5 \times \left(1 - 0.8^{10}\right) \approx 4.46\) stops.
Stretch. The \(i\)th number is a record when it is the largest of the first \(i\). Each of those \(i\) is equally likely to be the largest, so the chance is \(\tfrac1i\). \(E = 1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1{10} = \tfrac{7381}{2520} \approx 2.93\). Fewer than three records on average.