Expected time to fuse a $D_{10}$ dragon
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$.
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.