Expected time to fuse a $D_{10}$ dragon

I play a game called DragonSky merge and idle (or something like this). The basic premise of the early game is that dragons will spawn, and will be fused in pairs. You continue to fuse these until you have a level $10$ dragon.

Let me be precise. Let $\{D_1,D_2,\dots, D_{10}\}$ denote the set of types of dragons. Then, the following occurs:

1. Every $.9$ seconds a dragon will spawn of type $D_1$ with probability $.8$, and of type $D_2$ with probability $.2$.
2. For each $i\in\Bbb N$ such that $1\leq i\leq 8$, two dragons of type $D_i$ will be fused to form a dragon of type $D_{i+1}$ with probability $P_1=.85$ or a dragon of type $D_{i+2}$ with probability $P_2=.15$. For $i=9$, they will always fuse to a dragon of type $D_{10}$. This merging will occur until there is no pair of dragons of the same type.

These two steps will continuously repeat. As a small example of $6$ time steps, let us denote a collection of $k$ dragons of type $D_i$ by $d_{i}^1,\dots,d_i^k$ (of course, after fusion $k\in\{0,1\}$). Then we could have the following sequence of sets of dragons, where $\overset{1}{\to}$ means rule $1$ was applied (a dragon spawned), and $\overset{2}{\to}$ means rule $2$ was applied (a pair of dragons was fused). $$\emptyset\overset{1}{\to}\{d_1^1\}\overset{1}{\to}\{d_1^1,d_1^2\}\overset{2}{\to}\{d_2^1\}\overset{1}{\to}\{d_2^1,d_2^2\}\overset{2}{\to}\{d_3^1\}\overset{1}{\to}\{d_2^1,d_3^1\}\overset{1}{\to}\{d_1^1,d_2^1,d_3^1\}\overset{1}{\to}\{d_1^1,d_1^2,d_2^1,d_3^1\}\overset{2}{\to}\{d_2^1,d_2^2,d_3^1\}\overset{2}{\to}\{d_3^1,d_3^2\}\overset{2}{\to}\{d_4^1\},$$ (This sequence might fully exhibit the behaviour I describe, noting that there are two steps where a $D_2$ was spawned, and $4$ where a $D_1$ was spawned.)

I am trying to determine the number of seconds it takes on average to form a dragon of type $D_{10}$ assuming that we initially start with no dragons. I have very little experience with probability theory, so my first approach was to simplify this by taking $P_1=1$ and $P_2=0$, but what I compute is definitely not correct. My approach there was to consider: $$E_n = \{(x,y)\mid x+y=n, x+2y\geq 2^{10}, x,y\in\Bbb Z_{\geq 0}\},$$ where $(x,y)\in E_n$ corresponds to a valid sequence of $n$ spawns that yields a $D_{10}$ dragon, such that there were $x$ spawns of $D_1$ and $y$ spawns of $D_2$. Then I thought I would only need to take $$S_n=\sum_{(x,y)\in E_n}(.2)^i,$$ for the probability that we have a $D_{10}$ in precisely $n$ steps, and I am then looking for $k$ such that $$\sum_{i=1}^k S_i\approx .5.$$ This led me to make a mistake (after many calculations), and also doesn't deal with the proper fusion rates.

A second thought I had would be to set this up in terms of Markov chains, where we simply enumerate all possible sequences $(n_1^t,\dots,n_{10}^t)$ of numbers of dragons $n_i^t$ of type $D_i$ at time step $t$, and edges corresponding to merging and spawning, but I had trouble setting this up precisely, and even doing so, it seemed that I (personally) can't calculate the resulting probability .

Can someone help me solve this problem?

Solution 1:

A second thought I had would be to set this up in terms of Markov chains

Spot on. I'll use a smaller problem (aiming for a $D_3$) to illustrate the technique.

First, we need to identify the states. Note that we never have three of the same dragon, because we don't spawn when there are multiple of the same dragon, and a fusion only generates one dragon. So the states are subsets of the inferior dragons, plus subsets with a single "double dragon". Finally we have the terminal state, when the target dragon has been produced.

Then we set up a transition graph with spawns from states without double dragons (solid) and mergers from states with double dragons (dashed):

Now we can eliminate the double-dragon states by inlining their transitions: for example, this is the result of inlining the state $200$:

By eliminating all of the double-dragon states we get a transition graph where every edge corresponds to a spawn plus whatever fusions it triggers:

If you want to think about this in terms of Markov transition matrices, it's equivalent to setting up a transition matrix with just the spawn transitions, and then multiplying it on the left by matrices with fusion transitions. Since we have an acyclic graph, we can do this in order of a topological sort: first merge $D_1$s, then $D_2$s, etc. Then we simplify the matrix by deleting rows and columns corresponding to states which are now unreachable.

Having obtained the "one step" transition graph, we can convert it into a transition matrix and use the powers of the matrix to identify the probability of having reached the terminal state:

$$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0.8 & 0 & 0 & 0 & 0 \\ 0.2 & 0.68 & 0 & 0 & 0 \\ 0 & 0.2 & 0.8 & 0 & 0 \\ 0 & 0.12 & 0.2 & 1 & 1 \end{pmatrix}^n \begin{pmatrix}1 \\ 0 \\ 0 \\ 0 \\ 0\end{pmatrix}$$

Note for practical implementation that the matrices we work with are sparse, and taking that into account gives a significant performance improvement. In fact, it's fast enough that the latest version of my Python implementation uses exact rational calculations, giving an expected number of steps for $D_{10}$ of $$\frac{5738090301380362377556157080519184410864485826643847546490211514813993114983976485449758219001202355420707028156222144670550864306260456830184088840858971140041057047870937482880307679788590398609848830826303688692885496232924709599530869322944108789179561887161202759264043990270228305675596880197444679236532038984484169568166958542200692275799573464815935282554191149959933151314775759590532847113473687943942560748068997011815405908890440992389891985798380209761135194486228748134492710796580625065156386185440973330360499634129791567180674247696925017607682109401480152171947449914665816208625386711754282984766415366288878822946492172123153593287912452344410841743483852714144044615847426277603425839462886081120117189214538189217380302535795027661644970530635530181613012455814181184913150755463275830247945140711928871135926654001329453036090742550587}{29134143481250807590980333263527085302251841932032839430748118489087024941680149628656933165626671106880904700218109771302393469121973838517524081365594080826098674969995239755840640915103262745865025602988530917052399286174173855937623776652356338837099858200255274278660961165377018080648451612997787311902221317681636750598905827303042315179482102394104003906250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}$$ which is approximately $196.954144373$.

As a combinatorialist, I also see an option which I can't justify rigorously but which does have a certain elegance. The transition matrix above stays in the terminal state once it reaches it, and the last element of the product with the column vector is the probability of reaching the terminal state in no more than $n$ steps. If we drop the $1$ in the bottom-right of the transition matrix (so that instead of remaining in the terminal state we "vanish"), the last element in the power product with the column vector will be the probability of reaching the terminal state in exactly $n$ steps. Then we can sum: $$(T + 2T^2 + 3T^3 + \cdots)\begin{pmatrix}1 \\ 0 \\ 0 \\ 0 \\ 0\end{pmatrix}$$ to get the expected number of steps until the terminal state. The unjustified step is to apply to matrices the identity $$T + 2T^2 + 3T^3 + \cdots = T(1 - T)^{-2}$$

This doesn't seem to quite work, but if we take $$(1 - T)^{-2} = 1 + 2T + 3T^2 + \cdots$$ then we get one more than the expected number of steps, and that does work:

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ -0.8 & 1 & 0 & 0 & 0 \\ -0.2 & -0.68 & 1 & 0 & 0 \\ 0 & -0.2 & -0.8 & 1 & 0 \\ 0 & -0.12 & -0.2 & -1 & 1\end{pmatrix}^{-2} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1.6 & 1 & 0 & 0 & 0 \\ 2.032 & 1.36 & 1 & 0 & 0 \\ 2.7008 & 2.032 & 1.6 & 1 & 0 \\ 4.2992 & 3.424 & 2.8 & 2 & 1\end{pmatrix}$$ and the expected number of steps until termination is indeed $3.2992$.

Solution 2:

An exact analytic solution is probably really hard, but we can make a vague approximation. Suppose that $\theta$ is the positive root of the equation $2=0.85a+0.15a^2$, so $\theta \approx 1.788$. Define the "power" of a $D_k$ dragon to be $\theta^k$. Then:

• The merging operation doesn't change the total power of all your dragons on average.
• Every time a new dragon spawns, you gain $0.8\theta + 0.2 \theta^2$ power.
• Immediately after you first get a $D_{10}$, your power will be at least $\theta^{10}$ and at most $\theta^{10}+\theta^9+\dots+\theta=\dfrac{\theta^{11}-\theta}{\theta - 1}$ (by the geometric series formula).

Note that $\dfrac{\theta^{10}}{0.8\theta+0.2\theta^2} \approx 161.3$, and $\dfrac{\theta^{11}-\theta}{(\theta-1)(0.8\theta+0.2\theta^2)} \approx 364.99$. So the expected number of steps to get a $D_{10}$ should be somewhere between $162$ and $364$.

If you want a more accurate approximation than this, I recommend simulation.