Monday, May 31, 2021

Errata: What's the toughest unit in Memoir '44?

I was preparing to revisit what the toughest unit in Memoir '44 is by looking at it using a Markov chain model. Then I discovered that I had an error in my earlier calculation. I'll fix my calculation and derive the expected number of dice needed to eliminate each type of unit. Recall that I derived the following equation for the expected number of dice needed to eliminate a given unit, $N$, as follows. \begin{align} \mathbb{E} N &= \sum_{n=0}^\infty 1 - F_N(n) \end{align} Here $F_N(n)$ is the CDF of $N$, meaning that $F_N(n) = P(N \leq 0)$. See the previous analysis for the derivation of the CDF. The error came in the range of the summation for $\mathbb{E} N$, which starts at zero. However, my code to the computation stored the CDF starting at $n=1$, since it is known to be 0 at $n=0$; it's impossible to eliminate a unit without rolling any dice. This means that I should add one to the previous estimates, as shown below. \begin{align} \widehat{\mathbb{E} N_\text{infantry}} & \approx 8.000000000000002 \\ \widehat{\mathbb{E} N_\text{armor}} & \approx 8.999999999999932 \\ \widehat{\mathbb{E} N_\text{artillery}} & \approx 11.999998659711212 \\ \end{align} 

Figure 1: Estimating expected value with finite sum

This means that our guess as to the true expected values are below and the updated formula would be $\mathbb{E} N = f/p$. \begin{align} \mathbb{E} N_\text{infantry} & = 8 \\ \mathbb{E} N_\text{armor} & = 9 \\ \mathbb{E} N_\text{artillery} & = 12 \end{align} This makes a lot more sense and perhaps I should have caught the previous error. Without the odd $-1$ hanging off the back end of the equation, this means that the expected value of proportional to the number of starting figures. This makes sense, especially in our one die at a time analysis. If it takes an average of $1/p$ dice to remove one figure, then it should take an average of $f/p$ dice to remove $f$ figures. First, we remove one figure, then the second, and then so on $f$ times. Each time takes an average of $1/p$ dice, so $f/p$ dice in total. The expectation is also inversely proportional to $p$. While clearly in the correct direction, it'll take a little more analysis to establish this precise relationship. If we increase the probability of hitting with each die, it'll decrease the number of dice we need to roll before getting a hit. Let's analysis the expected number of dice rolled to get the first hit, $N_\text{hit}$, for a unit with a probability of getting hitting one die $p$. To get a hit on the $n$-th die, after missing previously, the probability is, \begin{align} P(N_\text{hit} = n) = (1-p)^{n-1} \cdot p. \end{align} While we could use this, we can use the same shortcut to find the expected value as before. \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty P(N_\text{hit} > n) \end{align} The probability that we haven't gotten a hit in $n$ dice, $P(N_\text{hit} > n)$ is the probability that we roll a miss all $n$ times. \begin{align} P(N_\text{hit} > n) = (1-p)^n \end{align} Thus, the expected value is, \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty (1-p)^n . \end{align} This is a familiar infinite series, although it might not be immediately recognizable in this form. If we instead substitute $a = 1-p$ and notice that $a < 1$ for $p > 0$, then it becomes more familiar. \begin{align} \mathbb{E} N_\text{hit} &= \sum_{n=0}^\infty a^n \\ &= a^0 + a^1 + a^2 + a^3 + \ldots \\ & = \frac{1}{1-a} \end{align} This is very similar to the analysis done related to rolling for actions in First Martians. Finally, we substitute back in that $a = 1-p$. \begin{align} \mathbb{E} N_\text{hit} &= \frac{1}{1-a} \\ &= \frac{1}{1 - (1-p)} \\ & = \frac{1}{p} \end{align} Combining this result for a single figure with the previous analysis we find that indeed $\mathbb{E} N = f/p$.

No comments:

Post a Comment