Expected steps to eliminate a character?

Question

This came up in a game theory crafting exercise.

Imagine a character has 195 hit points.

You can shoot at them and there are three results:

Critical - 100 damage - 40% of shots

Body - 50 damage - 40%

Miss -0 damage - 20%

The gun shoots 1 bullet per second.

Besides running through thousands of different simulations and averaging the result, is there a way to get the average time to kill using a formula? The point would be to compare hundreds of guns with different damage numbers and different hit percentages potentially.

EDIT for solutions - I initially thought a weighted average damage per bullet (which is 60) would solve for this. But I was wrong.

Answer 1

In the particular situation posited there is a possibility of the targeted character receiving $0,50,100,150$ or $200+$ damage points. Because the character initially has $195$ "hit points", once the damage exceeds that it's "game over".

In discrete probability we call this an absorbing Markov chain. You have a distribution of probabilities for the accumulated damage points at each time step. The relationship between probabilities at time $t$ and time $t+1$ is given by multiplying by a probability transition matrix.

The damage points at time $t=0$ is known to be zero, so labeling the "damage points" states as multiples $0,1,2,3$ of $50$ points together with a terminal state of $200$ or more damage points, we have an initial vector:

$$ v_0 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$

at time $t=0$, and subsequent probability distribution vectors:

$$ v_t = v_0 P^t $$

for times $t= 1,2,3,\ldots$, where $P$ is the probability transition matrix:

$$ P = \begin{bmatrix} 0.2 & 0.4 & 0.4 & 0.0 & 0.0 \\ 0.0 & 0.2 & 0.4 & 0.4 & 0.0 \\ 0.0 & 0.0 & 0.2 & 0.4 & 0.4 \\ 0.0 & 0.0 & 0.0 & 0.2 & 0.8 \\ 0.0 & 0.0 & 0.0 & 0.0 & 1.0 \end{bmatrix} $$

If we write $P$ in block form that highlights that the final state is "absorbing" (once the character receives $200$ damage points, no further change in states occurs):

$$ P = \begin{bmatrix} Q & R \\ 0 & 1 \end{bmatrix} $$

then the "fundamental matrix" $N = (I-Q)^{-1}$ allows us to compute the expected number of steps to reach the absorbing state from each of the transient states:

$$ N \vec{1} $$

Here $\vec{1}$ is a column vector of all ones, and the entries of $N \vec{1}$ give the expected number of steps starting from a corresponding transient state to reach the absorbing state:

$$ N = \begin{bmatrix} 1.25 & 0.625 & 0.9375 & 0.78125 \\ 0.00 & 1.25 & 0.625 & 0.9375 \\ 0.00 & 0.00 & 1.25 & 0.625 \\ 0.00 & 0.00 & 0.00 & 1.25 \end{bmatrix} $$

$$ N \vec{1} = \begin{pmatrix} 3.59375 \\ 2.8125 \\ 1.875 \\ 1.25 \end{pmatrix} $$

As a reality check let's consider the final entry's value of $1.25$. If the targeted character has already received $150$ damage points when shooting begins, the chance of surviving one more step (second) is $0.2$ (Miss!). Any hit (Body or Critical) means that step is the last. So the expected number of steps is:

$$ 1 + 0.2 + 0.2^2 + \ldots = \frac{1}{1 - 0.8} = \frac{5}{4} = 1.25 $$

Thus the standard computation sketched above tells us that the expected number of steps to take out the targeted character, starting from the undamaged (195 hit points) state, is $3.59375$.

Answer 2

An easy algebraic way to solve this is to first consider all of the states the player could be in, and then calculate, from bottom up, the expected time until death. The more sophisticated approach in hardmath's answer can handle any healing effects with greater ease, but is not strictly necessary here.

In particular, observe that a player could only lose a multiple of $50$ HP, so their health is one of $0,\,45,\,95,\,145,\,195$. Let us define $T_{x}$ as the expected time until death given that the player has $x$ health now and that the gun will fire in $1$ second.

We start out by noting that $T_0=0$, since at that point the player is dead. Next, we have $$T_{45}=(1\text{ second}) + (20\%)T_{45}+(80\%)T_0$$ since they will survive at least until the next shot, when they will be missed with probability $20\%$ (leaving them with $45$ health) and will otherwise be struck to $0$ health. Plugging in $T_0=0$ and solving gives $$T_{45}=\frac{1\text{ second}}{1-20\%}=1.25\text{ seconds}.$$ Note that we treat $80\%=.8$, as is standard.

Then, we can proceed to $T_{95}$, writing $$T_{95}=(1\text{ second})+(20\%)T_{95}+(40\%)T_{45}+(40\%)T_0$$ where again, we write out all the possible outcomes, along with their probabilities. We can substitute in $T_{45}=1.25\text{ seconds}$ and $T_0=0$ and solve to $$T_{95}=\frac{(1\text{ second})+(40\%)(1.25 \text{ seconds})}{1-20\%}=1.875\text{ seconds}.$$

For $T_{145}$, we repeat this process to get $$T_{145}=\frac{(1\text{ second})+(40\%)T_{95}+(40\%)T_{45}}{1-20\%}=2.8125\text{ seconds}$$ and for $T_{195}$ we get $$T_{195}=\frac{(1\text{ second})+(40\%)T_{95}+(40\%)T_{45}}{1-20\%}=3.59375\text{ seconds}$$ where the algebra to reach these results is the same as before.