Once again, The Riddler does not disappoint! This puzzle is about slaying monsters and collecting 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?
Here is my solution:
[Show Solution]
A simpler problem: coin flips
A popular (and simpler) version of this problem is the following: “I have a coin that comes up heads with probability $p$ and tails with probability $1-p.$ If I flip the coin until I get heads, how many flips will I make, on average?”. The standard approach to solving this problem is to enumerate all the possibilities:
- “H” (one flip), probability $p$.
- “T,H” (two flips), probability $(1-p)p$.
- “T,T,H” (three flips), probability $(1-p)^2p$.
- … (and so on)
To get the expected number of flips, you then multiply each number of flips with its associated probability and sum them:
\[
\sum_{k=1}^\infty k (1-p)^{k-1}p
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \sum_{k=1}^\infty (1-p)^k
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \left(\frac{1}{p}\right)
= \frac{1}{p}
\]
This is a pretty standard summation, and there are many ways of evaluating it. One particularly nice approach is to use recursion. Let $X$ be the expected number of flips. After we flipped our first coin, if our first flip was H (probability $p$), we stop flipping so there is no additional length added. If our first flip was a $T$ (probability $1-p$), then we will add $X$ more flips on average. Therefore: $X = 1 + p \cdot 0 + (1-p)\cdot X$. Solving for $X$, we find $X = \frac{1}{p}$, as before. This recursive approach works because the stopping criterion (flipping H) does not depend on what our previous flips were.
Back to monster slaying
We’ll use the recursive approach from the coin-flipping problem to solve the monster slaying problem. What makes this version more difficult is that the coin flips are not all independent. In other words, whether we should stop flipping coins (slaying monsters) depends on which types of gems we have accumulated so far. Let’s say the three types of gems are $p, q, r$. I’ll use the same variable names to denote the respective probability of each gem occurring. The first thing to realize is that to count the expected number of $p$’s that occur, it’s equivalent to count the total number of gems that occur and multiply the result by $p$. This follows from linearity of expectation. Specifically, if the sequence of gems has length $n$ and $X_i$ tells us whether gem $i$ is a $p$ or not, we have:
\begin{multline}
\mathbb{E}\left[\sum_{i=1}^n X_i\right]
= \mathbb{E}\left[ \mathbb{E}\left[ \sum_{i=1}^n X_i \,\middle|\, n \right] \right]
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i\,\middle|\, n \right] \right]\\
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i \right]\right]
= \mathbb{E}\left[ np \right]
= p\, \mathbb{E}[ n ]
\end{multline}
We stop collecting gems once we have at least one of each type of gem. We’ll need several variables to properly characterize our current state of gem accumulation. Define the following:
- $X$: the expected number gems we’ll collect from now on, assuming we haven’t collected any gems yet (this is $\mathbb{E}[n]$).
- $X_p$ (similarly $X_q, X_r$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem.
- $X_{pq}$ (similarly $X_{pr}, X_{qr}$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem and at least one $q$ gem.
The expected number of gems we expect to collect in the future depends on type of gem we get first. We can write the following recursion:
\[
X = 1 + p X_p + q X_q + r X_r
\]
In other words, if our first gem was $p$, we can expect $X_p$ subsequent $p$ gems, plus the first one we just collected. In the other cases, for example if the first gem is $q$, then we can expect $X_q$ subsequent $p$ gems. We can write similar recursions for when we’ve collected our first gem:
\begin{align}
X_p &= 1 + p X_p + q X_{pq} + r X_{pr} \\
X_q &= 1 + p X_{pq} + q X_q + r X_{qr} \\
X_r &= 1 + p X_{pr} + q X_{qr} + r X_r
\end{align}
And, recursions for when we’ve collected two different gems:
\begin{align}
X_{pq} &= 1 + p X_{pq} + q X_{pq} + r \cdot 0 \\
X_{pr} &= 1 + p X_{pr} + q \cdot 0 + r X_{pr} \\
X_{qr} &= 1 + p \cdot 0 + q X_{qr} + r X_{qr}
\end{align}
The last three recursions are decoupled. Solving them, we obtain:
\begin{gather}
X_{pq} = \frac{1}{1-p-q} = \frac{1}{r},\quad
X_{pr}=\frac{1}{1-p-r} = \frac{1}{q},\\
X_{qr}= \frac{1}{1-q-r} = \frac{1}{p}
\end{gather}
In the final equalities, we used the fact that $p + q + r = 1$. These results shouldn’t be surprising — once you’ve already obtained at least one $p$ and one $q$, the problem it simply to count how many more flips until you obtain $r$, and this is precisely the coin-flipping problem! Substituting into the previous set of recursions, we obtain:
\begin{gather}
X_p = \frac{1}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right),\quad
X_q = \frac{1}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right),\\
X_r = \frac{1}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{gather}
Finally, substitute these findings into the recursion for $X$, and obtain:
\begin{multline}
X = 1 + \frac{p}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right)
+ \frac{q}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right) \\
+ \frac{r}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{multline}
We can now substitute the values $p = \frac{1}{2}$, $q = \frac{1}{3}$, and $r = \frac{1}{6}$ and we obtain that the sequence will have expected length $\mathbb{E}[n] = X = \frac{73}{10}$. Therefore, the expected number of common gems is simply $p \,\mathbb{E}[n] = \frac{73}{20}.$
$\displaystyle
(\text{Expected number of common gems}) = \frac{73}{20} = 3.65
$
A more brute-force approach:
[Show Solution]
As in the previous solution, we’ll label the gems $p$, $q$, $r$ and use this notation for the respective probabilities as well. Moreover, we’ll work on computing the expected sequence length. Let $\mathbb{P}(n,k)$ be the probability that a sequence of gems has length $n$ and terminates with gem $k$. What we’d like to find is:
\[
\mathbb{E}[n] = \sum_{n=3}^\infty n \left( \mathbb{P}(n,p) + \mathbb{P}(n,q) + \mathbb{P}(n,r) \right)
\]
Taking a closer look at $\mathbb{P}(n,p)$, for example, we see that $\mathbb{P}(n,p)$ is the probability of the sequence consisting of $(n-1)$ $q$’s and $r$’s (at least one of each), and terminating with $p$. The probability of this happening is:
\[
\mathbb{P}(n,p) = p\left( (q+r)^{n-1} – q^{n-1} – r^{n-1} \right)
\]
since we must exclude the sequences consisting of all $q$’s or all $r$’s. Define: $f(x) = \sum_{n=3}^\infty n x^{n-1}$. Then we can write:
\begin{multline}
\mathbb{E}[n] = p\left( f(q+r)-f(q)-f(r) \right) \\
+ q\left( f(p+r)-f(p)-f(r) \right) \\
+ r\left( f(p+q)-f(p)-f(q) \right)
\end{multline}
So it remains to evaluate $f$. Notice that:
\[
f(x) = \sum_{n=3}^\infty n x^{n-1} = \frac{\mathrm{d}}{\mathrm{d}x} \sum_{n=3}^\infty x^n = \frac{\mathrm{d}}{\mathrm{d}x} \frac{x^3}{1-x} = \frac{3x^2-2x^3}{(1-x)^2}
\]
So that’s it! It remains to substitute $p=\tfrac12$, $q=\tfrac13$, $r=\tfrac16$, and to evaluate $\mathbb{E}[n]$. Doing so, we find $\mathbb{E}[n]=\tfrac{73}{10}$. Therefore, the expected number of common gems is $\mathbb{E}[p n]=\tfrac{73}{20}$.
Yet another solution approach with very nice write-up can be found on Andrew Mascioli’s blog
