14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I only see time introduced in the $0.9$ seconds in Rule 1; is it to be specified elsewhere? If not, how do we decide when two $D_2$'s merge to produce a $D_3$ or $D_4$, as opposed to a $D_1$ spawning a new $D_2$? If there are an odd number of $D_k$, how do the merging dynamics work there? $\endgroup$ – Brian Tung Nov 20 at 23:32
  • $\begingroup$ @BrianTung The time step occurs every $0.9$ seconds. After $0.9$ seconds a dragon will spawn, and then instantaneously an arbitrary number of merges are completed, until there are no pairs of dragons of a single type left. I'm not sure if that answers your question though! $\endgroup$ – Ted E Nov 20 at 23:34
  • $\begingroup$ Maybe my example helps, although I imagine there is a better choice of notation. $\endgroup$ – Ted E Nov 20 at 23:36
  • $\begingroup$ Since nothing is infinite or repeating here, it is possible to just write a brute-force algorithm to go through all possibilities. I haven't done the math, but this might take too long. $\endgroup$ – automaticallyGenerated Nov 21 at 2:54
  • $\begingroup$ @automaticallyGenerated I was obtaining underflow errors, but I really am interested in the mathematical approach, not just the solution. $\endgroup$ – Ted E Nov 21 at 3:05
10
+50
$\begingroup$

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):

Graph with nine states

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

Graph with eight states

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:

Graph with five states

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$.

$\endgroup$
  • $\begingroup$ Wow, this is an impressive answer! Thank you! $\endgroup$ – Ted E Nov 22 at 23:51
  • $\begingroup$ @Ted, I had previously rejected the idea of doing exact calculations because I thought it would be too slow, but it occurred to me that the optimisations I came up with later might make it feasible, and indeed it is. Less than 2 minutes to get the exact answer. $\endgroup$ – Peter Taylor Nov 23 at 9:01
  • $\begingroup$ It was a CSS issue that is now fixed. $\endgroup$ – Ted E Dec 4 at 22:37
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Good approach. I think you can justify that the number of steps is toward the low end because there will be few dragons left over. The only way you can have a level $9$ left over is if you make a $9$, then make two $8$s and they merge to form a $10$. I think this carries over and you would expect to have only a $\frac 15$ chance of having an extra dragon of each level. $\endgroup$ – Ross Millikan Nov 20 at 23:38
  • $\begingroup$ Wow, this is really clever! It's also fairly consistent with my experience playing the game. $\endgroup$ – Ted E Nov 20 at 23:48
  • $\begingroup$ When I simulate it I get an expected value very close to $197$, in agreement with Ross's claim that the expected value ought to be close to the low end of the range. $\endgroup$ – Micah Nov 21 at 2:30
  • 2
    $\begingroup$ My Markov code, without any thought given to numerical analysis, gives $196.954144372671$. $\endgroup$ – Peter Taylor Nov 22 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.