Can You Slay The Puzzle Of The Monsters’ Gems?

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 (three common gems for every two uncommon gems for every one rare gem, on average). If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

The Riddler, FiveThirtyEight(original post)

Solution

The drop ratio $3:2:1$ makes a gem common with probability $\tfrac12$, uncommon with $\tfrac13$, rare with $\tfrac16$. Let $E(S)$ be the expected number of common gems still to come, counting from the moment your collected set of types is $S$, until $S$ grows to all three. Every common drop adds one to the tally whether or not you already own a common, so a single slay gives $$E(S) = \tfrac12\big(1 + E(S\cup c)\big) + \tfrac13\,E(S\cup u) + \tfrac16\,E(S\cup r),$$ with $E(\{c,u,r\}) = 0$. We want $E(\varnothing)$.

Start with the states that are one type short. When only the rare is missing, each slay ends the hunt with probability $\tfrac16$ and otherwise drops a common with probability $\tfrac12$; solving $E = \tfrac12(1+E) + \tfrac13 E$ gives $E(\{c,u\}) = 3$. The same step gives $E(\{c,r\}) = \tfrac32$ (only the uncommon missing) and $E(\{u,r\}) = 1$ (only the common missing, and the completing drop is itself a common).

Feeding these back one level produces $E(\{c\}) = \tfrac72$, $E(\{u\}) = \tfrac{13}{4}$, $E(\{r\}) = \tfrac{19}{10}$, and finally $$E(\varnothing) = \tfrac12\big(1 + \tfrac72\big) + \tfrac13\cdot\tfrac{13}{4} + \tfrac16\cdot\tfrac{19}{10} = \frac{73}{20} = \boxed{3.65}.$$

The computation

Play it out: slay monsters, drawing a common, uncommon or rare with probabilities $\tfrac12,\tfrac13,\tfrac16$, until all three types have appeared, and record how many commons were collected. Averaging over many runs lands on $73/20$.

import numpy as np
rng = np.random.default_rng(0)
runs = 2_000_000
commons = 0
for _ in range(runs):
    seen_u = seen_r = False; c = 0
    while not (c and seen_u and seen_r):   # until all three appear
        x = rng.random()
        if x < 1/2:                        # common gem
            c += 1
        elif x < 5/6:                      # uncommon gem (1/2 + 1/3)
            seen_u = True
        else:                              # rare gem
            seen_r = True
    commons += c
print(commons / runs)                      # ~3.65 = 73/20