Leveling up your Armor
Pobability; Difficulty: medium
How many gems will you purchase to make it in this game?
The Riddler Classic from this week (Apr 22, 2022) is probably an exercise of the sort that keeps revenue teams at game studios busy: estimating the no. of gem purchases a player makes on average. A related interesting question I explore is how many gems should you purchase upfront to give you a required probability of getting to a desired level. Here’s the Classic reproduced:
In the hit online game World of Riddlecraft, players can level up their armor. Armor levels range from 0 to 5. Now, attempting to level up your armor requires a cerulean gem, which is destroyed in the process. If the attempt is successful, your armor’s level goes up by one; if not, it goes down by one.
Fortunately, it’s impossible to fail when attempting to upgrade your armor from level 0 to level 1. However, the likelihood of success goes down the higher level the armor is before the upgrade. More specifically:
Upgrading from level 0 to level 1 has a 100 percent chance of success.
Upgrading from level 1 to level 2 has an 80 percent chance of success.
Upgrading from level 2 to level 3 has a 60 percent chance of success.
Upgrading from level 3 to level 4 has a 40 percent chance of success.
Upgrading from level 4 to level 5 has a 20 percent chance of success.
On average, how many cerulean gems can you expect to use up in order to upgrade your armor from level 0 to level 5?
*spoiler alert* solution and answer follow in the sections below.—
Solution (expected value and probability distribution)
Let \(E_n\) be the expected number of gems used in going from level \(n\) to level 5; integer n with \( 0 \leq n \leq 4 \).
Starting at level 0, the first purchase results in reaching level 1 with certainty. From level \(n\) between 1 and 4, using a gem pushes you to level \(n+1\) or level \(n-1\) with known probabilities. Note that at any level, the next level you get to with gem use is determined solely by your current level and completely independent of how you got there (this is an example of a type of Stochastic process: A Markov Chain). Consequently, determining the expected number of gems to get to level 5 becomes immediately solvable by conditioning the expectation on the first jump from a level \(n\).
For example: Starting at level 0 will necessarily require 1 gem more on average to get to level 5 than starting at step 1. Similarly starting at step 1, there is an 80% chance of getting to step 2 and hence requiring 1 step more on average to get to level 5 than starting at level 2 OR a 20% chance of going down to level 1 and requiring 1 step more on average to get to level 5 than starting at level 1. Applying this logic gives us these relations between the expected gem uses starting at different levels:
\begin{align*}
E_0 &= 1 + E_1 \\
E_1 &= 0.8(1 + E_2) + 0.2(1+E_0) &&= 1 + 0.8E_2 + 0.2E_0 \\
E_2 &= 0.6(1 + E_3) + 0.4(1+E_1) &&= 1 + 0.6E_3 +0.4E_1 \\
E_3 &= 0.4(1 + E_4) + 0.6(1+E_2) &&= 1 + 0.4E_4 + 0.6E_2 \\
E_4 &= 0.2 + 0.8(1 +E_3) &&= 1 + 0.8E_3
\end{align*}
This system of 5 equations and 5 unknowns is easily solved by using the expression for \(E_0\) from the first equation in the second; then using the resultant value of \(E_1\) from the second equation in the third and so on to eventually solve for the individual \(E_0\) to \(E_4\). The required values are:
\begin{align*}
E_0 &= {\color{Red} {42\tfrac{2}{3}}} \\
E_1 &= 41\tfrac{2}{3} \\
E_2 &= 40\tfrac{1}{6}\\
E_3 &= 37\tfrac{1}{2} \\
E_4 &= 31
\end{align*}
The required answer is then 42.67 gems on average to get from level 0 to level 5: more than I would have (gu)estimated at the outset. It’s interesting that even if you start at level 4, you will still need 31 gems on average to get to level 5. That’s a lot of in app purchases to get to level 5 in this game!
Now imagine that you could buy gem packs in advance, with discounts increasing with pack size, as is typical of games these days. How many gems do you need to buy to give you, say 90% confidence, of getting to level 5?
Read on for a more detailed analysis that answers this question and shows how to calculate the probability of getting to level 5 after spending \(n\) gems.
Probability distribution of getting to level 5 as a function of gems used
As mentioned before, the armor leveling can be thought of as a stochastic Markov Chain process with spending a gem resulting in a state/level shift. The transition probability matrix is:
\[
P = \begin{bmatrix}
0& 1& 0& 0& 0& 0 \\
0.2& 0& 0.8& 0& 0& 0 \\
0& 0.4& 0& 0.6& 0& 0\\
0& 0& 0.6& 0& 0.4& 0 \\
0& 0& 0& 0.8& 0& 0.2 \\
0& 0& 0& 0& 0& 1
\end{bmatrix}
\]
The six rows and columns represent the levels 0 to 5. Each matrix element \(P_{ij}\) is the probability of going to from state \(i\) to \(j\) e.g. the second row above describes the probability of going from level 1 →0 = 0.2 and level 1→2 = 0.8 and all other transitions being impossible and hence 0. The bottom right element showing probability 1 represents level 5 being an absorbing state: you’re done once you reach level 5 and do not transition out.
The initial state matrix indicating that we start with certainty at level 0 is:
\[
a = \begin{bmatrix}
1 &0 &0 &0 &0 &0
\end{bmatrix}
\]
Now it can be shown fairly easily that the probability distribution after \(n\) transitions (gem spends) is given by:
\[
P_n = aP^n
\]
which is pretty neat! An interesting exercise if you want to try it out.
Since level 5 is absorbing, applying this formula and calculating the 6th element of \(P_n\) gives us the cumulative probability of having reached level 5 with \(n\) gems. The values calculated are shown in the chart below.
(The horizontal jaggedness is a result of transitions to level 5 occurring only on odd number of gems spent)
What this shows is that if you want a 50% chance of getting to level 5, you would be advised to buy the 31 gem pack. For 75% confidence get the 57 pack. But if you want 90% or 95% certainty, fork up for the 93 or 119 gem packs respectively.
If you’re one of the unluckiest 1%, be prepared to spend over 179 gems in pursuit of level 5!
4 thoughts on “Leveling up your Armor”
Cool analysis! Your subscripts on the second line of the system of equations need tweaking. E0 not E1.
Ah!good catch – thank you. Corrected now.
Pingback: Who Wins A Very Boring Basketball Game? | FiveThirtyEight
Pingback: Tetrahedral Dice Game – Starvind astrophotography