I'm not sure what the proper way to describe what I'm looking for is, so apologies if the title is misleading. In developing a game, I am working on a particular algorithm that consists of multiple steps and has a percentage chance of duplicating the input at each step. I'm trying to calculate what the average final multiplier will be.
For example:
Assume a 3 step process that I insert 1 resource into.
- Step 1: Doubles its input
- Step 2: Has a 15% chance to double its input
- Step 3: Has a 30% chance to double its input
Each time the input of a step doubles, both the original resource as well as the double pass through all remaining steps. So Step 2 will execute twice (once on step 1's original input, then again on the duplicate from step 1). Step 3 will execute at least twice (on the original outputs from Step 1), but potentially as many as 4 times (if both Step 2 executions also caused a duplication).
My initial attempt at this was to consider the percentages as partial resources to calculate the final multiplier after each step like so:
- Step 1 = x2 (Step 1 always doubles)
- Step 2 = x2 (from Step 1) + 0.15*2 (15% for each output from Step 1) = x2.3
- Step 3 = x2.3 (from Step 2) + 0.3*2 (30% for each guaranteed output from Step 2) = x2.9
So if I run this process consistently, I can assume a 2.9x multiple on the input. This kind of makes sense, but I feel like I'm not handling Step 3 appropriately, as that produces 30% of Step 2's 15% in some cases, but I'm not sure how to handle that.
Am I on the right track, and is it really as simple as I think, or am I missing a pretty sizable piece (as I suspect)?
Best Answer
Churned on this some more and approaching it with some different ways of thinking led me to what I am nearly certain is the correct answer. I vaguely recall this concept from a statistics course I took long ago.
Basically, the trick is to look at it algorithmically. The equation to calculate the output of any given step is $(1+x)=a$ where $1$ is the guaranteed output, $x$ is the percentage chance of that output duplicating and $a$ is the output multiplier.
When we consider step 2, we want to consider all combinations of outcomes of both step 1 and 2, and thus the result is multiplicative $(1+x)(1+y)=b$ where $x$ is the percentage chance of step 1 duplicating, $y$ is the percentage chance of step 2 duplicating, and $b$ is the total multiplier after step 2.
Building an equation for each step, plugging in the values from my example problem, and then solving the system of equations we get the following:
$$ \left\{ \begin{aligned} (1+1.0)=a \\ (1+1.0)(1+0.15)=b \\ (1+1.0)(1+0.15)(1+0.3)=c \end{aligned} \right. $$ with the result of $$ \left\{ \begin{aligned} a=2 \\ b=2.3 \\ c=2.99 \end{aligned} \right. $$ I'll leave this open for a few more days to allow for comments correcting me in case I'm wrong or providing actually correct answers.