In working out the proof for World of Britain I came across a paradox. Maybe smarter Math Factorites can help me out? My sanity could depend on it.
In the puzzle you have five different tasks. On each day one of these tasks is given at random. How long do you expect it to take to get all five tasks?
First consider a simple case. Suppose some event has a probability, p, of happening on any one day. Let’s say that E(p) is the expected number of days we have to wait for the event to happen. For example if p=1 then the event is guaranteed to happen every day and so E(p)=1.
How can we calculate E(p)?
Andy does an experiment. He will wait for the event to happen and record how many days it took. He will do this several times, for long enough to ensure that he gets an answer that is as accurate as he needs. He will keep going for N days in total. Afterwards he will take the average of all of his wait times to get an estimate for E(p).
The average he calculates is the total of all the wait times divided by the number of occurrences of the event. But we can estimate both of these values and therefore estimate his value for E(p). The total of all of the wait times is going to be about N. Since the event has a probability of p of occurring on any particular day the number of occurrences will be about p times N.
So Andy’s average will be about N/(pN) which will be about 1/p.
We can make N as large as we like to make this result as accurate as we like. So we can confidently say that E(p) = 1/p.
Let’s get back to our puzzle about tasks. We need to wait for the first task, then the second, then the third and so on. When there are t tasks left then the chance of getting a new one is t/5.
So the total waiting time is
E(5/5) + E(4/5) + E(3/5) + E(2/5) + E(1/5) = 5/5 + 5/4 + 5/3 + 5/2 + 5/1
= 5(1/5 + 1/4 + 1/3 + 1/2 + 1) = 11 5/12 = 11.4166666… days
You may recognise the harmonic series!
So that’s the proof, now where’s the paradox?
Bob visits Andy when he is able and waits with him until the event occurs. Of course Andy may well have been waiting for some time.
If Bob turns up just after the event has happened then he will wait for the same time as Andy. If he turns up just before the event he will wait for one day. On average he will wait for about half the time that Andy does.
When the event occurs Bob disappears and comes back when he is next able to.
At the end of the experiment Bob averages all of his wait times to get an estimate for E(p). He gets an answer which is half of Andy’s!
That is the paradox!
Now Carol thinks she understands what is going on here. The problem is that Andy is distorting his results by always starting the clock straight after an event has occurred. That guarantees him to get the longest possible wait times.
She thinks the only way to get an accurate answer is to look at the wait time starting from each of the N days and then average these N wait times.
To calculate this she needs to make an assumption. She knows that the event occurs every 1/p days on average. She assumes they happen regularly every 1/p days.
Let’s say they happen every n days where n = 1/p. Remember Andy’s value for E(p) is 1/p = n. Bob’s value is half that, so about n/2.
The wait time will vary between 1 and n. The average wait time will be n(n+1)/2n = (n+1)/2.
So Carols estimate for E(p) is about n/2 whereas Andy’s was 1/p = n. So Carol is agreeing with Bob.
I can tell you that Andy had the right value and that the logic I used for Bob and Carol was flawed.
Can you see where?