Missing 5
Here is a probability puzzle I heard from my son Sergei. We even included this puzzle in our book Mathematical Puzzles and Curiosities. Our book includes the answer but omits the details. So, this blog post is devoted to said details.
Puzzle. Alice rolls a die until she gets 6. Then Bob observes that she never rolled a 5.
Question. What is the expected number of times that Alice rolled the die?
The answer depends on Bob’s strategy. Many people assume that Bob loves 5 and is only looking for 5. In this case, the answer is 3. Here is the argument: the expected number of rolls to get 5 or 6 is 3: this is equivalent to rolling a three-sided die and waiting to one side to appear. Only on the rolls without 5 will Bob say something.
However, there are other natural assumptions. In the book, we have two suggestions, where Bob treats every digit that is not 6 equally.
Modeling assumption 1. Suppose Bob lists all the numbers that are missing. Then, when he says that 5 is missing, we are guaranteed that Alice rolled 1, 2, 3, and 4 before 6. Such a strategy by Bob noticeably increases the expected number of rolls, and the answer is 8.7. Let us prove this.
This version of the problem is related to the coupon collector’s problem. Suppose we randomly get coupons, where the total number of coupons is 5, and we get each one with probability 1/5. How many coupons will we need to collect to get 4 different coupons? The first coupon appears immediately after one draw; after that, a different coupon appears with probability 4/5, which means the expected additional wait is 5/4. After we get the second coupon, the expected wait for the third coupon is 5/3. Continuing, the total wait for four different coupons to appear is 5/5 + 5/4 + 5/3 + 5/2 = 77/12.
However, we actually need 4 different coupons, not out of 5, but out of 6 to appear. That means that we need to multiply the answer by 6/5 to get 7.7. Then we add one extra roll for the final 6. The answer is 8.7.
Modeling assumption 2. Suppose Bob randomly chooses one number out of the ones that are missing. For example, if Alice rolled 1, 2, 3, 2, 1, 6, then Bob notices that 4 and 5 are missing, and mentions 5 with probability 1/2. In this case, the number of expected rolls is 4.26.
By using coupon-collecting ideas, we know, for each k, the expected number of rolls until k+1 distinct dice faces appear. To wit, for each k=0,1,2,3,4, the expected number of rolls is 1, 2.2, 3.7, 5.7, and 8.7, respectively.
Now we need to condition on the event that Bob actually says 5. By symmetry among the non-6 faces, the probability that Bob’s announcement is 5, given that he says something at all, is the same for each of the five digits. This conditioning does not bias the waiting time toward any particular missing digit, so the conditional distribution of the stopping time is obtained by averaging these expectations over the five possible values of k. Therefore, the expected number of rolls is (1 + 2.2 + 3.7 + 5.7 + 8.7)/5 = 4.26.
I am grateful to my other son, Alexey, for discussing this problem with me. Probability is a tricky subject, and it is nice to have experts in the family.
Share:
Leave a comment