[Probability] Expected hits to kill

[beary605]

A problem I came up with one day in a boring math class...

"A player deals A~B damage (both natural numbers) with every hit. If a monster has X HP (also natural), what is the expected number of hits needed to kill the monster?"

Is there a nice mathematical way of solving this?

[Zapmeister]

Re: [Probability] Expected hits to kill

looks like a standard markov chain problem.

write k(x) for the average number of hits needed to get to 0 from initial state (health) x, then write out the mean hitting time equations:

for each x, there's a probability of 1/(b-a+1) that you'll get to any of x-a, x-a-1, x-a-2, ..., x-b at the next stage, so your hitting time equation is

k(x) = 1 + 1/(b-a+1) * (k(x-a) + k(x-a-1) + ... + k(x-b))

with boundary conditions: k(x) = 0 for all x<=0.

unfortunately this is a difference equation of order b, which is about as hard to solve as a polynomial of degree b-1 (because 1 is always a root), so i'd be really surprised if there was a nice solution for b >= 4.

damn.

oh well. here are some examples to show what happens for small b

so if a=1 b=2 your difference equation for the mean hitting time looks like this

k(x) = 1 + 1/2*(k(x-1) + k(x-2))

or alternatively 2k(x) - k(x-1) - k(x-2) = 2

the auxiliary equation 2y^2 - y - 1 = 2 has roots 1 and -1/2, and you want your particular solution to have the form constant * x, so you do that (tell me if you want to know more about solving difference equations, it's a whole other topic), and your solution is:

k(x) = -2/9 * (-3x + (-1/2)^x - 1)

another example: a=2, b=3

this time your equation is k(x) = 1 + 1/2*(k(x-2) + k(x-3))

auxiliary equation 2y^3 - y - 1 = 2 has roots 1 and the complex roots (-1+i)/2 and (-1-i)/2 (where i is the imaginary unit)

to clear things up you can rewrite the complex solutions in terms of sin and cos. it's fiddly but you have (i think)

k(x) = 2/25 * (5x + 4 + (3 sin(3pi*x/4) - 4 cos(3pi*x/4))/sqrt(2)^x)

i really don't think there's a nice solution for general a, b.

edit: forgot to divide by the damn sqrt2^x

[benguino]

Re: [Probability] Expected hits to kill

I don't know if I'm oversimplifying or misinterpreting the problem, but if a player deals between A and B damage (all with equal probability) and the monster has X health, couldn't you just calculate the average damage, (A+B)/2, and then from there you have the average number of hits X/((A+B)/2)=2X/(A+B)?

[igotrhythm]

Re: [Probability] Expected hits to kill

Even if every damage value doesn't have an equal chance to occur per hit (and we must incorporate 0 in here in case the attack misses) we can still figure out the average number of ATTACKS to kill by using the concept of the expected value.

The way it works is simple. You put together a table of all the possible values the attack's damage can take, including the chance of a miss next to 0, and you multiply it all together as follows:

D(n) is the damage value. P(n) is the probability of that damage occurring.

d(1)p(1) + d(2)p(2)+...+d(n)p(n)

By getting the expected value of damage per attack, you then divide the monster's HP by this number to get the average number of attacks needed to kill.

So if our attack damage table goes as follows on a monster with 120 HP:

0 damage (miss) = 30% chance
57 damage (hit) = 30% chance
24 damage (hit) = 40% chance

Our expected damage per attack is 57*.3 + 24*.4 = 17.1 + 9.6 = 26.7, which will drop this monster on average in about 6 attacks.

[beary605]

Re: [Probability] Expected hits to kill

I wrote a computer program to do this for me which just takes all possible paths, can someone verify that I'm calculating the expected value right here?

1~2 damage, 3 HP
every iteration is a hit

Iteration 1: 3-1, 3-2 = 2, 1
0 monster deaths
Iteration 2: 2-1, 2-2, 1-1, 1-2 = 1, 0, 0, -1
3 monster deaths
Iteration 3: 1-1, 1-2, 0-1, 0-2, 0-1, 0-2, -1-1, -1-2 = 0, -1, -1, -2, -1, -2, -2, -3
1 monster death

So the expected value = sum of (deaths) * 1/(possibilities) * hits
= 0/2 * 1 + 3/4 * 2 + 1/8 * 3
= 15/8?

[igotrhythm]

Re: [Probability] Expected hits to kill

The expected value is of the hit. So we have 3 HP monsters, we assign equal probabilities of 1/3 each to damages of 0, 1 and 2, and well it doesn't take much math to show that the average damage of an attack is 1, and therefore the average number of attacks needed for a kill is 3.

If you're talking expected number of HITS, then the average damage of a hit is the average of 1 and 2, which is 1.5, and 3 HP monsters die on average in 2 hits.

More generally, if there's an equal chance for every natural number to come up on a damage roll of A to B inclusive, then the average damage per hit is (A+B)/2 and the average number of hits to kill a monster with X health is X/((A+B)/2) = 2X/(A+B)

[beary605]

Re: [Probability] Expected hits to kill

Are the probabilities the same? I found them to be different...

Kill in one hit = none
Kill in two hits = [1, 2] [2, 1] [2, 2]
Kill in three hits = [1, 1, 1]

Probability of killing in two hits? There are four possible scenarios: [1, 1] [1, 2] [2, 1] [2, 2] and three of them result in a kill, so P(2) = 3/4

P(3) = 1/8 by the same logic (3 hits, 2 possibilities per hit = 8 different scenarios)

[benguino]

Re: [Probability] Expected hits to kill

I think IGR is talking about the amount of damage being done per hit having equal probability. For example, if the damage done ranges from 0 to 2, then if the damage done per hit has equal probability, then you have a 33.3% chance of dealing 0 damage in your next hit, 33.3% chance of dealing 1 damage on your next hit, and 33.3% chance of dealing 2 damage on your next hit.

The analysis of this problem changes if this isn't the case though.

[benguino]

Re: [Probability] Expected hits to kill

Are the probabilities the same? I found them to be different...

Kill in one hit = none
Kill in two hits = [1, 2] [2, 1] [2, 2]
Kill in three hits = [1, 1, 1]

Probability of killing in two hits? There are four possible scenarios: [1, 1] [1, 2] [2, 1] [2, 2] and three of them result in a kill, so P(2) = 3/4

P(3) = 1/8 by the same logic (3 hits, 2 possibilities per hit = 8 different scenarios)

I'm not too sure if I'm following; in your analysis, it seems that you allow the damage per hit to be either 1 or 2. If this is the case and if the monster's HP is 3, then we know we need at least two hits but no more than three hits to kill the monster. However, your probabilities aren't adding up (P = P(2)+P(3) = 3/4+1/8 =/= 1).

[beary605]

Re: [Probability] Expected hits to kill

That is true... how strange. Hmm.

Oh! I got it. :X I have to let [1, 1, 2] in too, which now fixes the probability of P(3) to be 2/8, making it add up to 1!

[benguino]

Re: [Probability] Expected hits to kill

Also, in your analysis, there is a very small yet subtle difference between the probability of killing a monster in two hits vs the probability of a monster dying given that you hit it twice (which is what you calculated).

EDIT: perhaps listing all the ways the monster could die, and then seeing which of those have a sequence of length of two would be a better way of going about it:

[1,1] (not a death)
[1,2]
[2,1]
[2,2]
[1,1,1]
[1,1,2]
[1,2,1] (this one and below is really a two-hit death since the first two coordinates is greater than or equal to 3)
[1,2,2]
[2,1,1]
[2,1,2]
[2,2,1]
[2,2,2]

so really what we have is
[1,2]
[2,1]
[2,2]
[1,1,1]
[1,1,2]

So the probability of killing in 2 hits is 3/5 and the probability of killing in 3 hits is 2/5. So on average, we have 2*(3/5)+3*(2/5) = 12/5 = 2.4 hits to kill

edit: oops, my bad, let me fix that, that's not quite right

[beary605]

Re: [Probability] Expected hits to kill

Oh, I think I know what you mean
P(killed on second|it survived one hit) != P(hitting it twice and killing it)

Although I don't see the difference in them logically

after your EDIT: Ahahaha, ok I got it.

[benguino]

Re: [Probability] Expected hits to kill

I made a small boo-boo, at the end, I assumed that each of those 5 scenarios had equal probability (but they don't). The first there have a 1/4 chance of occurring while the last two have a 1/8 chance each of occuring (which is what you were getting at earlier I believe). So that means there is a 3/4 chance of killing in two hits (3 cases, each with 1/4 probability) and 1/4 chance of killing in three hits (2 cases, each with 1/8 probability)

EDIT: so on average, the number of hits is 2hits * 3/4 + 3hits*1/4 = 7/4 = 2.25

I ran some code, killing 100,000 monsters, and on average it killed them in 2.24963750362496 hits so I think we're good now

EDITv2: although, for the sake of simplicity, calculating and using the average damage per hit and using the formula average hits = 2X/(A+B) is much more quick and efficient (although slightly less accurate but not by much)

EDITv3: With that in mind, Zap's explanation seems to make a bit more sense now (I'm not too familiar with Markov Chains though). But it seems to give a method of finding an -exact- probability as opposed to an estimated one that uses the average damage per hit. However, comparing accuracy with computation time/power/memory, solving using Markov chains doesn't seem to be "worth it"

EDITv4: no offense to you Zapmeister, I'm not saying your solution is invalid or anything. I'm just saying (in my subjective opinion) that the increase in accuracy is not worth it if you have to do all that analysis when there is another method that gives you a rough estimation in less than a second.

EDITv5: Hey Zapmeister, although it becomes hard to give an explicit formula for larger values of b, your analysis is still nice in the sense that it's not too difficult to figure out k(x) for a specific value of x if we just start at the bottom of the recursion (at k(0)) and work our way up.

like, the example we've been doing would be equal to k(3)

k(x) = 1 + 1/2*(k(x-1) + k(x-2)), k(x) = 0 for x <=0
k(0) = 0
k(1) = 1+1/2*(k(0)+k(-1)) = 1+1/2(0+0) = 1
k(2) = 1+1/2*(k(1)+k(0)) = 1+1/2(1+0) = 3/2
k(3) = 1+1/2*(k(2)+k(1)) = 1+1/2(3/2+1) = 9/4 = 2.25

and a computer program could easily be created to iterate up to k(x) for whatever x we need to go up to.

EDITv6: ok, enough edits for now. I'm going to leave this thread until someone posts again, I feel like I'm talking to a wall at this point and that I'm going to go insane.

[benguino]

Re: [Probability] Expected hits to kill

Using Zapmeister's Markov chain analysis (which I'm trusting), here's a script that calculates the exact average number of hits. This code was written in Sage, which is primarily Python based so it may or may not work in Python.

a=1 #minimum damage dealt
b=2 #maximum damage dealt
x=3 #monster HP
kOfX = []

for i in (0..x):
    sum = 1
    for j in (i-b..i-a):
        if j > 0:
            sum += 1/(b-a+1) * kOfX[j]
    kOfX.append(sum)
print kOfX[len(kOfX)-1]+0.0

[Zapmeister]

Re: [Probability] Expected hits to kill

EDITv5: Hey Zapmeister, although it becomes hard to give an explicit formula for larger values of b, your analysis is still nice in the sense that it's not too difficult to figure out k(x) for a specific value of x if we just start at the bottom of the recursion (at k(0)) and work our way up.

well yeah, if you're just looking for a straightforward way to compute the mean hitting time you could iterate the recurrence

k(x) = 1 + 1/(b-a+1) * (k(x-a) + k(x-a-1) + ... + k(x-b))

with boundary conditions: k(x) = 0 for all x<=0.

this would give you the expected value in linear time, and you could do it by writing a quick program like reuben_tate's last post. simple enough

EDITv4: no offense to you Zapmeister, I'm not saying your solution is invalid or anything. I'm just saying (in my subjective opinion) that the increase in accuracy is not worth it if you have to do all that analysis when there is another method that gives you a rough estimation in less than a second.

true, haha. if i had to do a rough estimate as well i'd have done that too.

however, beary605 was asking for a "nice mathematical way of solving this", which i interpreted as an exact solution.

which as i said is hard to find for b>=4.

EDITv3: With that in mind, Zap's explanation seems to make a bit more sense now (I'm not too familiar with Markov Chains though). But it seems to give a method of finding an -exact- probability as opposed to an estimated one that uses the average damage per hit.

correct, it gives an exact value. i can point you to resources for learning about markov chains if you want

ok, now about all this 2x/(a+b) stuff.

I don't know if I'm oversimplifying or misinterpreting the problem, but if a player deals between A and B damage (all with equal probability) and the monster has X health, couldn't you just calculate the average damage, (A+B)/2, and then from there you have the average number of hits X/((A+B)/2)=2X/(A+B)?

if x is really big compared to a and b, this intuition would be correct, and that does in fact give a very good approximation. but it's not exact.

If you're talking expected number of HITS, then the average damage of a hit is the average of 1 and 2, which is 1.5, and 3 HP monsters die on average in 2 hits.

More generally, if there's an equal chance for every natural number to come up on a damage roll of A to B inclusive, then the average damage per hit is (A+B)/2 and the average number of hits to kill a monster with X health is X/((A+B)/2) = 2X/(A+B)

that asymptotic formula clearly won't work if x is a similar size compared to a and b. for instance if x=1 and a=1000000 and b=10000000000000 then you'd still need 1 hit to kill off the monster, even though the average damage per hit is enormous.

one reason why the asymptotic formula mean-hitting-time = 2x/(a+b) doesn't work for small x is because when the monster dies it doesn't always end up at exactly zero. the last hit can take the monster's health to as low as 1-b, so when the monster dies its final health is somewhere in the range [1-b, 0]. if you hit it 2x/(a+b) times its expected final health is 0, which is at the top end of the range.

so your answer would always be a little bit bigger than 2x/(a+b).




ok, now for some more calculations. try not to die of boredom while reading this post.

in fact for x large, you have mean-hitting-time = 2x/(a+b) + constant + o(1).

the fact that it has to be in this form is intuitive, since if x is big it doesn't really "care about" what happens for small x when the monster dies, so the difference between k(x) and 2x/(a+b) should be independent of x, so it's a constant (depending on a and b). there is a way to prove it properly with the difference equation but that's completely unenlightening, so it's in a spoiler:

the difference equation k(x) = 1 + 1/(b-a+1) * (k(x-a) + k(x-a-1) + ... + k(x-b)) must have solutions that are a sum of: constants, powers of x, and exponentials c_i^x, for c_i the roots of the auxiliary equation 1 = 1/(b-a+1) * (y^-a + y^-a-1 + ... + y^-b), and possibly powers of x times c_i^x for when the c_i are repeated roots.

claim: |c_i|<=1 with equality iff c_i=1.
proof: if you had that |c_i|>=1 instead, substitute y=c_i and each term on the rhs has modulus less than or equal to y/(b-a+1), then use the triangle inequality on the whole thing to get that the modulus of the lhs is at least as big than the modulus of the rhs. then equality holds only if |c_i|=1 and all the powers of c_i lie in a straight line in the same direction in the complex plane, so c_i = 1.

that means that all the c_i^x, and the powers of x times c_i^x, terms go to 0 as x gets big, so they're o(1) in x.

that leaves the powers of x term. the top power is going to come from the particular solution to this difference equation, and you want that to be linear, so that's equivalent to saying that 1 is a single root of the equation (so the particular solution looks like 2x/(a+b)) but not a double root. well it's clearly a single root. then just differentiate the equation, set y=1, and it doesn't work, so 1 isn't a double root.

so the general solution to that equation is always going to be of the form 2x/(a+b) + constant + o(1).

here's the formula for a=1, b=2 again:
k(x) = 2/9 * (3x + 1 - (-1/2)^x)

the red bit is linear in x and is equal to the 2x/(a+b) formula that holds for large x. the green bit is the constant that adjusts for the fact that the monster's final health may be <0. the blue bit goes to 0 quickly as x gets big, so for large x you can ignore it.

here's the formula for a=2, b=3:
k(x) = 2/25 * (5x + 4 + (3 sin(3pi*x/4) - 4 cos(3pi*x/4))/sqrt(2)^x)
red = 2x/(a+b), green = O(1), blue = o(1).

going back to the general case you want a formula of the form 2x/(a+b) + constant + o(1) that satisfies the hitting time equation.

unfortunately i can't find an easy way to do that, if i try substituting that into the difference equation both terms disappear because the constant is part of the complementary function (i think).

i actually got bored enough to compute the value of this constant, which is the limiting value as x -> infinity of k(x) - 2x/(a+b), for various a,b using a program similar to reuben_tate's and it looks like to me that this constant is

2(a^2+ab-2a+b^2-b)
---------------------
3(a+b)^2

which looks nice enough, but i can't see a proof. i may send a bunch of credits to anyone who can prove that, because i'm generous and stuff.

tl:dr; it's going to be a little bit bigger than 2x/(a+b).
for large x, k(x) = 2x/(a+b) + 2(a^2+ab-2a+b^2-b)/(3(a+b)^2) + o(1)
which improves on the naive estimate of k(x) = 2x/(a+b) + O(1). oh my god i am literally the nerdiest person on ffr