Expected counts and inclusion-exclusion in depth (free… | StemPy Lab
Free previewCourse: Standard
Expected counts and inclusion-exclusion in depth
Ten letters go into ten envelopes at random. How many land in the right envelope on average? The answer is one, and an idea called an indicator finds it in two lines. This lesson finds averages of counts with indicators. It then counts with many overlapping events by inclusion-exclusion, and checks each answer in two ways.
This is the first lesson of Random Walks, Expected Counts and Geometric Chance: Beyond the Textbook, free for everyone to read.
What you will be able to do
find the average of a count by splitting it into indicators, one for each object;
use the fact that the average of a sum is the sum of the averages, even for events that are not independent;
count with three or more overlapping events by inclusion-exclusion, and check the count by a second route.
An average without a long count
In the free course on matching you counted the ways to put letters in envelopes with no match. Now ask a different question. Ten letters go into ten envelopes at random. On average, how many letters are in the right envelope?
Listing 10!=3628800 arrangements is too slow by hand. So we split the count. For letter i, let Ii=1 if letter i is in its own envelope, and Ii=0 if it is not. A number like this, which is 1 when an event happens and 0 when it does not, is called an indicator. The number of matches is
M=I1+I2+⋯+I10.
The average of an indicator. Repeat the experiment many times. Ii is 1 in a fraction P(letter i right) of the runs and 0 in the rest. So its long-run average is that probability, 101.
The average of a sum. The average of M is the sum of the averages of the Ii. So the average number of matches is 10×101=1. The same argument gives 1 for any number of letters.
We write the long-run average of a count as E(M), read "the expected value of M". The Class 12 chapter on random variables defines it in general. Here we need only the idea of an average.
Why the sum rule needs no independence
The events "letter 1 is right" and "letter 2 is right" are not independent. If nine letters are right, the tenth must be right too. Yet the sum rule still holds. Why?
Take n=3 letters. The six arrangements have 3, 1, 1, 1, 0 and 0 matches. The total is 6, so the average is 66=1. Now add the same table by columns: each letter is right in 2 of the 6 arrangements. So the total is 2+2+2=6 again. Adding a table by rows or by columns gives the same total. That is all the sum rule says, so no independence is needed.
Two parts side by side for three letters and three envelopes. On the left, a table lists the six arrangements of the letters 1, 2 and 3, one in each row, with a tick under each letter that sits in its own envelope. The last column gives the number of matches in each row: 3, 1, 1, 1, 0 and 0, with a total of 6. The bottom row gives the number of ticks in each column: 2, 2 and 2, with a total of 6. On the right, a bar chart shows the chance of each number of matches for six letters: 0 matches about 0.368, 1 match about 0.367, 2 matches about 0.188, 3 matches about 0.056, 4 matches about 0.021, 5 matches 0 and 6 matches about 0.001. A dashed vertical line at 1 marks the average.
Three more averages
Empty boxes.n balls are dropped at random into N boxes. A given box stays empty when every ball misses it, with probability (1−N1)n. So the average number of empty boxes is
E(empty)=N(1−N1)n.
Throw six dice. The average number of faces that do not show is 6×(65)6≈2.0094. So on average only about 3.99 different faces show.
Pairs that share a birthday. In a group of 28 people there are 28C2=378 pairs. Each pair shares a birthday with probability 3651. So the average number of pairs with a shared birthday is 365378≈1.036. This average is easy, even though the chance that some pair shares a birthday needs a long product.
Waiting for every face. How many throws of a die does it take, on average, to see all six faces? Split the wait into stages. When k faces are new, a throw shows a new face with probability 6k. In the next lesson we show that the average wait for an event of chance p is p1. So the average total is
66+56+46+36+26+16=6×2049=14.7 throws.
Inclusion-exclusion with many events
For two and three events you met the addition theorem. For n events A1,…,An the rule continues in the same pattern:
P(at least one)=S1−S2+S3−⋯±Sn.
Here S1 is the sum of the single probabilities, S2 the sum over all pairs of P(Ai∩Aj), S3 the sum over all triples, and so on. The signs alternate.
Why it works. Take an outcome that lies in exactly r of the events, with r≥1. It is counted rC1 times in S1, rC2 times in S2, and so on. In all it is counted rC1−rC2+rC3−⋯=1 time. That sum is 1 because (1−1)r=0.
A bound for free. If you stop after S1, you get too much. If you stop after S2, you get too little. The partial sums go above and below the true value in turn, so they also give quick bounds.
Every suit in five cards. Let As be "suit s is missing". Then P(some suit missing) is
52C5439C5−626C5+413C5.
The good hands are the rest, 685464 of the 2598960 hands, so P≈0.2637. Check it directly. Five cards in four suits must split as 2,1,1,1. Choose the suit with two cards in 4 ways, its two cards in 13C2=78 ways and one card of each other suit in 133 ways. That gives 4×78×2197=685464 again.
A worked example
Six dice are thrown. Find the average number of different faces that show. Then find the probability that all six faces show.
The average. The average number of missing faces is 6×(65)6=777615625≈2.0094. So the average number of different faces is 6−2.0094=3.9906.
All six faces, by inclusion-exclusion. The ways with no face missing are k=0∑6(−1)k6Ck(6−k)6=720, out of 66=46656.
Check by a second route. All six faces in six throws means an arrangement of the faces, and there are 6!=720 of them. The two counts agree, and P=46656720=3245≈0.0154.
Practise with new numbers
Try it in Python
The program lists every arrangement of six letters and finds the average number of matches. It then simulates six dice with a fixed seed and compares the average number of missing faces with the exact value. Last, it counts the hands of five cards with every suit in two ways.
Common mistakes
Multiplying instead of adding. The average of a count is the sum of the probabilities of its indicators, not their product.
Thinking the sum rule needs independence. It does not. Only a product of probabilities needs independence.
Stopping inclusion-exclusion too early. With four events you need four sums. Stopping early gives only a bound.
Confusing an average with a chance. An average of 1.036 shared pairs does not mean a chance of 1.036. A chance is never above 1.
Remember these
An indicator is 1 when its event happens and 0 otherwise. Its average is the probability of the event.
The average of a sum is the sum of the averages, with or without independence.
Average number of matches of n letters: 1. Average number of empty boxes: N(1−N1)n.
Inclusion-exclusion: S1−S2+S3−⋯, and the partial sums are bounds.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Five letters are put into five envelopes at random. What is the average number of letters in the right envelope?
Four dice are thrown. Find the average number of faces that do not show.
A group has 20 people. Find the average number of pairs that share a birthday, with 365 equally likely days.
Five different balls are dropped at random into 3 boxes. Find the probability that no box is empty.
The events "letter 1 is right" and "letter 2 is right" are not independent. Why can we still add their probabilities to find the average number of matches?
References
C. M. Grinstead and J. L. Snell, Introduction to Probability, Chapter 3 (inclusion-exclusion and fixed points) and Chapter 6 (expected value).
OpenStax, Introductory Statistics, Chapter 4, section on the mean or expected value of a discrete random variable.
Liked this lesson? There is more
Random Walks, Expected Counts and Geometric Chance: Beyond the Textbook is a Standard course. It adds 2 more lessons, practice and tests on top of the free chapter.
12Problems2Python Labs1Question Set1Mock Test
First-step analysis, the gambler's ruin and random walks: Two friends take turns to throw a die, and the first to throw a six wins. Who is more likely to win? Instead of adding an endless list of chances, look only at the first step and see that the game starts again. This lesson uses that idea for races, for a gambler who plays until ruin or a target, for the wait until a pattern of tosses, and for a walker on a line.
Geometric probability in space and the classic traps: Three numbers are chosen at random between 0 and 1. Can they be the sides of a triangle? The triple is a point in a cube, so the chance is a volume. This lesson finds chances as volumes, shows with Bertrand's chord why "at random" must be said exactly, and works through the famous traps with honest sample spaces. A short simulation checks each hard answer.