Question: 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?

(FiveThirtyEight)

Solution

If we think of the player’s health like a particle, it can either move to the right (when the level-up succeeds) or to the left (when the level-up fails). Whichever happens, a gem is spent.

Call the number of gems a player will spend on the way from Health Level $j$ to Level $5,$ $\tau_j.$

Starting from Level $j,$ we can move to Level $(j-1),$ from which we’ll spend another $\tau_{j-1}$ gems, with probability $P_{j,j-1}$ or to Level $(j+1),$ from which we’ll spend another $\tau_{j-1}$ gems, with probability $P_{j, j+1}.$

So, the expected number of gems we’ll spend from Level $j,$ $\tau_j,$ is just:

\[\tau_j = P_{j, j-1}(1 + \tau_{j-1}) + P_{j, j+1}(1 + \tau_{j+1})\]

Since $j$ can only go to Level $(j-1)$ or Level $(j+1),$ we know that $P_{j,j-1} + P_{j,j+1} = 1,$ so this becomes

\[\boxed{ \tau_j = 1 + P_{j, j-1}\tau_{j-1} + P_{j, j+1}\tau_{j+1} }\]

Writing this out for the six health levels, we get

\[\begin{align} \tau_0 &= 1 + \tau_1 \\ \tau_1 &= 1 + P_{1,0}\tau_0 + P_{1,2}\tau_2 \\ \tau_2 &= 1 + P_{2,1}\tau_1 + P_{2,3}\tau_3 \\ &\vdots \\ \tau_5 &= 0 \end{align}\]

Solving this system of equations for $\tau_0,$ we get the shimmering expression:

\[\boxed{ \tau_0 = \dfrac{1 + P_{0,1}\dfrac{1 + P_{1,2}\dfrac{1 + P_{2,3}\dfrac{1+P_{3,4}}{1-P_{3,4}P_{4,3}}}{1 - \dfrac{P_{2,3}P_{3,2}}{1 - P_{3,4}P_{4,3}}}}{1 - \dfrac{P_{1,2}P_{2,1}}{1 - \dfrac{P_{2,3}P_{3,2}}{1 - P_{3,4}P_{4,3}}}}}{1 - \dfrac{P_{0,1}P_{1,0}}{1 - \dfrac{P_{1,2}P_{2,1}}{1 - \dfrac{P_{2,3}P_{3,2}}{1 - P_{3,4}P_{4,3}}}}} }\]

which contains compounded geometric series of the products of pairs of the forward and backward coefficients, accounting for all possible random walks between Level $0$ and Level $5.$

Plugging in the values of the $P_{i,j},$ we get $\tau_0 = 128/3 \approx 42.67.$