I am a big fan of MMORPGs, and this one, Cabal Online, has a particularly punishing upgrade system.
- Items can be upgraded to increase their stats, ranging from level 0 to level 15 (for simplicity).
- Upgrading costs cores (can be interpreted as currency).
- Attempting an upgrade can result can result in the item's level going up (+1), remaining the same (0), or going down (-1 or -2).
- The probabilities of these are summarized in the table below:
The question now is: What is the expected number of cores to upgrade an item from level 0 to level 15?
I initially tried approaching this using a binomial distribution approach, as it involved successes and trials, and failures, but realized that the trials change depending on the item grade and are not independent.
I then tried drawing it as a probability tree of sorts, but ended up with infinite recursion.
I realize that my current knowledge is not adequate to tackle such complex problems, analytically unfortunately.
However, I have managed to arrive at a value of 22,000 using a simulation that involved multiple nested for loops.
I'm now curious about whether there is a way to analytically calculate the number of cores required.
An analytic solution is possible by the method of Markov chains, but we will need some mathematical software such as Matlab, Octave, or Mathematica.
Let's number the stages from $1$, corresponding to zero weapons, to $16$, corresponding to 15 weapons, and let $\mathbf{P}$ be the $16$ by $16$ matrix of one step transition probabilities; i.e., $\mathbf{P}_{i,j}$ is the probability of moving from stage $i$ to stage $j$. So from the table in the problem statement,
$$\mathbf{P} = \left( \begin{array}{cccccccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.1 & 0.9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.2 & 0 & 0.8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.3 & 0 & 0.7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.4 & 0 & 0.6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.27 & 0.21 & 0 & 0.52 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.36 & 0.2 & 0 & 0.44 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.45 & 0.19 & 0 & 0.36 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.48 & 0.16 & 0 & 0.36 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.48 & 0.16 & 0 & 0.36 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.48 & 0.16 & 0 & 0.36 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 & 0.14 & 0 & 0.36 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 & 0.14 & 0 & 0.36 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 & 0.14 & 0 & 0.36 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$ Let's also number the steps of the game starting at $0$, so at step $0$ the player is in stage $1$, and let $\pi_n$ be the vector of probabilities of being in each stage at step $n$, written as a $1$ by $16$ matrix, so $$\pi_0 = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]$$ Given these definitions, the probabilities at step $n$ are given by $$\pi_n = \pi_0 \mathbf{P}^n$$ It remains to work in the cost in number of cores associated with each stage. Let $$c = (1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,0)^T$$ Then the expected cost of being at step $n$, disregarding the cost required by previous steps, is $$x_n = \pi_0 \mathbf{P}^n c$$
We want to know the expected total cost, $$\sum_{n=0}^{\infty} x_n = \sum_{n=0}^{\infty} \pi_0 \mathbf{P}^n c = \pi_0 \left( \sum_{n=0}^{\infty} \mathbf{P}^n \right) c = \pi_0 (I-\mathbf{P})^{-1} c$$
Using some mathematical software to invert $I-\mathbf{P}$ and perform the matrix multiplications involved, we find that the expected number of cores required to reach stage $16$ is $$\pi_0 (I-\mathbf{P})^{-1} c = \boxed{24120.6}$$