Probability of dependent events in an MMORPG [duplicate]

The item upgrade procedure you describe is a birth-death process that can be modeled as a Markov chain with an absorbing state. An exact formula for the distribution of number of failures is likely to be rather ugly, but it and the averages that you ask about can be computed without much fuss if you have access to a decent matrix calculator.

Let the states of the Markov chain be indexed by upgrade level. The probability of success at level $i<9$ is $p_i={10-i\over10}$; let $q_i=1-p_i$ be the probability of failure. The last state, corresponding to an upgrade level of +9, is the lone absorbing state of the Markov Chain, that is, once the process reaches that state, it stays in it with probability $1$. The canonical-form transition matrix for this process is thus $$P=\left[\begin{array}{cccccc|c}0&p_0&0&0&0 & \cdots & 0 \\ q_1&0&p_1&0&0 & \cdots & 0 \\ 0&q_2&0&p_2&0 & \cdots & 0\\ 0&0&q_3&0&p_3 & \cdots & 0 \\ \vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots \\ 0&0&0&0&0& \cdots &p_8 \\ \hline 0&0&0&0&0 & \cdots & 1\end{array}\right].$$ This matrix is divided into submatrices as shown: $$P=\left[\begin{array}{c|c}Q&R\\\hline\mathbf0&I\end{array}\right].$$ The so-called fundamental matrix $N=\sum_{k=0}^\infty Q^k=(I-Q)^{-1}.$ The $(i,j)$-th element of this matrix is the expected (average) number of times that the system will be in state $j$ given that it started in state $i$. The vector $N\mathbf 1$ (i.e., the vector of row sums of $N$) gives the expected times to absorption starting from each transient state, so the expected time for a full upgrade from +0 is the first element of this vector. Mathematica gives a value of ${10303\over63}\approx163.54$ for this. It takes at least 9 iterations to reach +9, and each failure adds two iterations, so the expected number of failures is $\frac12\left({10303\over63}-9\right)={4868\over63}\approx77.270$. The long tail of the distribution contributes a lot to this value. (Your estimate was off because you computed a sum of probabilities, but for a random variable $X$ that can take on non-negative integer values, the expected value is the weighted average $\mathbb E[X]=\sum_{k=0}^\infty k\Pr(X=k)$.) Incidentally, the average number of attempts to get from +8 to +9 is about 112. This makes some amount of sense, I suppose, since beyond +5 you’re more likely to make the item worse by attempting an upgrade, and the system will tend to hover around +5 for a while.

The average cost of upgrading to +9 can be computed using $N$ and linearity of expectation. Let $\mathbf c$ be the cost vector, with each element $c_j$ the cost to attempt an upgrade from level +$j$. The cost is charged every time the system is in one of the transient states, so the total expected cost is computed by summing the product of the +$k$ cost with the expected number of times the system is in state +$k$. These expectations are exactly the elements of $N$, so the expected cost of a full upgrade from +0 is the first element of $N\mathbf c$, which is equal to the dot product of $\mathbf c$ with the first row of $N$.

Let the random variable $X$ count the number of failures before attaining +9. To compute the probability distribution of $X$, we turn back to the transition matrix $P$. The $(i,j)$-th element of this matrix gives the probability of going from state $i$ to state $j$ in one step. The $k$-step transition probabilities are given by the matrix $P^k$, with the upper-right element being the probability of interest: the chance of being at +9 after $k$ steps, having started at +0. The minimal time for a full upgrade is 9 steps, and as noted above each failure adds two steps, so we’re interested in the sequence of matrices $P^{9+2k}$. Since +9 is an absorbing state, the system may have reached it and stayed there before $9+2k$ steps, so this probability is cumulative—it’s the probability $\Pr(X\le k)$ of maxing out the upgrades after at most $k$ failures. The individual probabilities that you’re looking for are thus the differences between successive values.

$\Pr(X=0)$ is the upper-right element of $P^9$ and corresponds to an upgrade path in which each attempt is successful. This probability can be computed directly: $$\Pr(X=0)={10!\over10^9}={567\over156250}\approx0.00363.$$ At this point I turn back to Mathematica for the grunt work. A plot of the computed values of $\Pr(X=k)$ for $0\le k\le250$ matches your simulation quite well:

This is clearly not a simple geometric distribution, but the ratio ${\Pr(X=k+1)\over\Pr(X=k)}$ does converge fairly quickly, and starting around $k=20$ a constant ratio of $0.9869$ produces a very good approximation to the real distribution. This value for a “long-term” failure probability produces an expected value that is pretty close to the value of $\mathbb E[X]$ computed earlier, supporting the idea that the almost-geometric tail of the distribution dominates the initial spike in the long term.

Incidentally, this process looks very similar to a discrete-time Ehrenfest model, so some further insights might be gained by comparison with that. It’s also related to the “snail climbing a cliff” problem, except that the non-uniform success probabilities here don’t lend themselves to a neat, simple recurrence.

Consider the matrix for this Markov chain: $$P=\left[\begin{array}{cccccccccc} 0&1&&&&&&&&\\ 1-p_{1}&0&p_{1}&&&\ddots&&&&\\ &1-p_{2}&0&p_{2}&&&0&&&\\ &&1-p_{3}&0&p_{3}&&&\ddots&&\\ &&&1-p_{4}&0&p_{4}&&&&\\ &&&&1-p_{5}&0&p_{5}&&&\\ &&\ddots&&&1-p_{6}&0&p_{6}&&\\ &&&0&&&1-p_{7}&0&p_{7}&\\ &&&&\ddots&&&1-p_{8}&0&p_{8}\\ &&&&&&&&0&1\end{array}\right],$$ where the transition probability of going from state $i$ to state $j$ is $P_{i,j}$ for each $0\leq i,j\leq 9.$ Then the probability of going from state $i$ to state $j$ in $n$ steps is just $(P^{n})_{i,j},$ the $(i,j)$th entry of the $n$th power of $P.$ Since 9 is an absorbing state, to find the probability that we go from state 0 to state 9 in exactly $n$ steps, we just need to consider $(P^{n})_{0,9}-(P^{n-1})_{0,9},$ since this is the probability that we reach state 9 from state 0 in $n$ steps, but didn't reach state 9 before the $n$th step.

Now, to find the probability that the number of failures before hitting 9 is $f,$ for some specific integer $f\geq 0,$ and using @amd's comment, we see that we must hit state 9 at the $(2f+9)$th step of the process (starting from 0). Using the above, we can calculate this probability as $(P^{2f+9})_{0,9}-(P^{2f+8})_{0,9}.$ This gives us the probability mass function for the number of failures before reaching state 9, i.e., $p(f)=P(f\text{ failures}).$ Then to compute the average number of failures before reaching state 9, we would need to compute $\sum_{f=0}^{\infty}f\cdot p(f),$ using the definition of the mean of a random variable.

On the other hand, while all of this can be approximated numerically for specific values of the $p_{i}$, I have some doubt that you can obtain a general formula in terms of the $p_{i}$ for either $p(f)$ or the average number of failures.