Every week I like to do the fivethirtyeight.com Riddler, an interesting and pleasantly challenging (at least for me) weekly math puzzle which comes out Fridays, with the answer and explanation to the previous problem being supplied when the new one is posted. I just looked at the solution to last week's problem, and while I understand the explanation given, I am at a loss as to why my approach produced an incorrect answer.

The problem is as follows: You're playing a game in which you kill monsters. Each time you kill a monster, it drops a gem, which you then collect. The gems can be either common, uncommon or rare, with probabilities ${1\over2}$, ${1\over3}$, and ${1\over6}$, respectively. If you play until you have 1 gem of each type, how many common gems will you have on average?

The official answer is 3.65, and the explanation is available here (scroll down past the introduction and todays puzzle-- not quite halfway down the page). My answer was 4.65 (interesting that I was off by exactly 1), and my reasoning was as follows:

It's possible that you collect both other rarities before you find your first common gem. This occurs with probability $ {1 \over 3} * {1 \over 4} +{1 \over 6 }*{2\over5}={3\over20}$. In such cases you will stop after you find your first common gem, and the number you've collected (henceforth $N$) will be 1.

In all other cases, play will proceed in two phases:

Phase 1: you find some number $N_a$ (possibly 0) of common gems followed by a single non-common gem (call it type $a$)

Phase 2: you find some number $N_b$ (possibly 0) of common gems, mixed with an irrelevant number of type $a$ gems, followed by a single gem of the other non-common type (call it type $b$).

Now I make a couple of simplifying observations. First, since the case addressed above where the common gem was the last one we found corresponds to the case were $N_a=N_b=0$, we don't need to explicitly remove this case to avoid double-counting. It represents the situation where $N$ exceeds $N_a+N_b$ rather than a case where the 2-phase model doesn't apply at all.

Second, for given types $a$ and $b$, $N_a$ and $N_b$ are independent, because the individual gem drops are independent.

Third, because there are (by definition) no type $b$ gems found in phase 1 and type $a$ gems found in Phase 2 are irrelevant, it doesn't matter which non-common type (rare or uncommon) is type $a$ and which is type $b$ because in either case $N_{rare}$ (the number of common gems found in the phase terminated by a rare gem) will be a geometrically distributed random variable with $p=$ (the probability of a rare gem being dropped given that an uncommon gem is not dropped) $= {1\over4}$, and likewise for $N_{uncommon}$.

Thus we have $$E[N]=E[N_{rare}]+E[N_{uncommon}]+{3\over20}=\frac{3\over5}{2\over5}+\frac{3\over4}{1\over4}+{3\over20}={3\over2}+3+{3\over20}={93\over20}=4.65$$

What's wrong with this method?

  • $\begingroup$ You are correct. I subtracted wrong. As my post is pointless after the correction, I am deleting it. $\endgroup$ – Paul Sinclair May 27 '16 at 18:35
  • $\begingroup$ I fixed a typo in the section covering the case where a common gem is the last type you find. $\endgroup$ – Gabriel Burns May 27 '16 at 19:15

There's a subtle flaw in your reasoning. You're effectively conditioning on which non-common gem type comes first. Your calculation for phase $2$ is correct: The non-common gem type already seen in phase $1$ has become irrelevant, and only the relative probabilities of the other two gem types matter.

But this doesn't work in phase $1$, because the length of phase $1$ is influenced by the conditioning. You can perhaps see this most clearly if you imagine the "uncommon" gem type to have probability close to $1$. Then if you condition on the rare gem type appearing before the "uncommon" gem type, you're almost certain not to get any "common" gems in phase $1$, no matter how much more probable they are than the rare gems, simply because it's so improbable that more than one gem wouldn't be "uncommon". This argument doesn't apply to phase $2$, where the gem type that's excluded really doesn't matter; even if it has probability close to $1$ and you collect thousands of that type, you can still ignore them for the purpose of calculating the number of common gems collected before encountering the third type.

P.S.: It's perhaps worth mentioning here another nice and relatively simple approach, which is also mentioned after the solution you linked to. The expected total number of gems drawn is the expected total number of coupons drawn in a coupon collector's problem with unequal probabilities (see e.g. The Coupon Collector's Problem):

$$ \frac1{\frac12}+\frac1{\frac13}+\frac1{\frac16}-\frac1{\frac12+\frac13}-\frac1{\frac13+\frac16}-\frac1{\frac16+\frac12}+\frac1{\frac12+\frac13+\frac16}=\frac{73}{10}\;. $$

The expected number of common gems drawn is half of this. It's a good exercise to think about why this is true, even though it's not true when you condition on the total number of gems drawn.

| cite | improve this answer | |
  • $\begingroup$ If one calculated this in separately for both possible choices of type $a$ and type $b$, weighted by the probability of each choice, the influence you are describing would be captured by the weights. In fact, that's how I initially did it. But as I stated in my third "simplifying observation", it turns out not to matter, because if a type is not type $a$, then it is type $b$, and the calculations are the same for each. So you have $E[N_{a}| $rare is type $ a]*P($rare is type $ a)+E[N_{b}|$rare is type $ b]*P($rare is type $ b)=N_{rare}$ no matter what the weights might be. $\endgroup$ – Gabriel Burns May 27 '16 at 22:30
  • $\begingroup$ Another way I calculated it (which returns the same answer) is to treat the two non-common gem types the same in phase 1 (that is, treat $N_a$ as a geometric random variable with $p={1\over2}$) and then calculate $N_b$ as a probability combination of $N_{rare}$ and $N_{uncommon}$ weighted by the probabilities of the first uncommon being found before the first rare, or vice versa. Since this method ignores the relative probabilities of the non-common gem types when counting commons in Phase 1, it seems to sidestep your objection. $\endgroup$ – Gabriel Burns May 27 '16 at 22:40
  • $\begingroup$ Sorry, just realized the RHS of the equation in my first comment is $N_{rare}$. it should be $E[N_{rare}]$. Just a typo, the point still holds, I believe. $\endgroup$ – Gabriel Burns May 27 '16 at 22:43
  • 1
    $\begingroup$ I think @joriki is right. The use of the expectation of a geometric mean is improper under the condition that, say, rare comes before uncommon. You are in effect saying that the distribution of the sequences up to the first rare in all the cases in which rare comes before uncommon is the same as you'd get if you started with just rare and common gems, with their relative probabilities unchanged, and drew until a rare appears. But that's not correct: the distribution will be biased towards shorter sequences because the likely appearance of uncommon gems makes longer ones rare. $\endgroup$ – Hector Pefo May 27 '16 at 23:00
  • 2
    $\begingroup$ Out of curiousity, is there any reason my (wrong) approach would be off by exactly 1, other than just a coincidental idiosyncrasy of this particular problem? $\endgroup$ – Gabriel Burns May 27 '16 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.