[Probability] Expected hits to kill

[benguino]

Re: [Probability] Expected hits to kill

oh my god i am literally the nerdiest person on ffr

agreed

Anyways, that was some really nice analysis you did there. I'm just curious how you ended up with the exact formula:

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

I mean, I find it hard to believe you looked at the numbers and conjured that formula out of nowhere, I mean, it doesn't exactly look "intuitive."

Anyways, I tried coming up with a proof, but I got stuck at trying to find the roots of the auxiliary equation in the general case. If I get blessed with a lot of free time and nothing to do, perhaps I'll come back to it later and try a different approach.

i can point you to resources for learning about markov chains if you want

that'd be appreciated I had the wikipedia article to get the "gist" of what you were talking about; however, in my opinion, Wikipedia is a good reference source, but not necessarily a learning source.

[igotrhythm]

Re: [Probability] Expected hits to kill

Okay, for x small and a and b large, you are correct Zap. However, in the original context of the problem (the average turn-based RPG) you wouldn't need to worry about this special case.

I would also like to point out that while the average number of hits to kill won't necessarily be a whole number, it will always be at least 1. So for x<a, hits to kill is always 1. If a<x<b, then the hits to kill is somewhere between 1 and 2, and if b<x then the hits to kill is at least 2. Thanks Zap for bringing this to my attention.

If in the context of the problem you have a "critical hit" modifier, or for some reason the weapon being used has a chance to have some other special effect, then you'd have to use the table of possible values to get the expected DPH value using the method I explained (poorly) above.

[Zapmeister]

Re: [Probability] Expected hits to kill

Anyways, that was some really nice analysis you did there. I'm just curious how you ended up with the exact formula:

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

I mean, I find it hard to believe you looked at the numbers and conjured that formula out of nowhere, I mean, it doesn't exactly look "intuitive."

i wrote a program similar to the one you wrote to compute k(x)-2x/(a+b) for x=500 and various values of a and b. for the small numbers it was obvious what fraction the decimals corresponded to, for big numbers i pasted the decimal into wolfram alpha to get the suspected fraction. there were a lot of give-away denominators like 49 for the (2,5) case and things like 81 and 121, so i multiplied everything by (a+b)^2 and got mostly integers with a bunch of 1/3s floating around, so i multiplied everything by 3. the result was obviously quadratic in a and b since the numbers went up with linear differences as you increase a and b (differences increasing by 4 each time). to find it i fixed a=1,2,3 and worked out the quadratic for b in each case (so for instance if a=1 the numerator was 2(b^2-1)), then generalised the coefficients for a using that it must be quadratic.

one more thing. this number i found is bounded above by 2/3. so if x is big enough, your estimated value of the mean hitting time 2x/(a+b) will never be off by more than 2/3 of a single hit. so yeah it may not have been worth all the time working that out

Anyways, I tried coming up with a proof, but I got stuck at trying to find the roots of the auxiliary equation in the general case. If I get blessed with a lot of free time and nothing to do, perhaps I'll come back to it later and try a different approach.

haha this is the thing i was pointing out in my earlier post. you can't do a difference equation of order b in general because it's like a polynomial of degree b-1. even with b=3 the roots have yucky complex numbers and square roots and stuff, so the nice form of the final answer suggests there's another way to do it.

that'd be appreciated I had the wikipedia article to get the "gist" of what you were talking about; however, in my opinion, Wikipedia is a good reference source, but not necessarily a learning source.

any set of university lecture notes or slides should be helpful. here are a bunch of slides that give a quick overview of most things, for more detail you ought to get some lecture notes. i use these, but you can just google "markov chains notes" and look through stuff until you find something accessible. (if all you're looking for is techniques and examples, you can skip some of the formal definitions and proofs of stuff.)

Okay, for x small and a and b large, you are correct Zap. However, in the original context of the problem (the average turn-based RPG) you wouldn't need to worry about this special case.

the point was that weird stuff happens for x small or comparable to a and b. if x gets bigger then these "end effects" don't make that much of a difference, but they're still there, in the O(1) and o(1) terms of the solution. in your earlier post you were trying to use (total health)/(expected damage) on x=3 and claiming it as exact.

If in the context of the problem you have a "critical hit" modifier, or for some reason the weapon being used has a chance to have some other special effect, then you'd have to use the table of possible values to get the expected DPH value using the method I explained (poorly) above.

well sure, you can always find the expected damage if you know all the nuances of whatever you're playing and all the probabilities and stuff. but the formula will never be as simple as mean hitting time = health / average damage, because of the "end effects", i.e. this still applies:

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.

(obviously with 2x/(a+b) replaced by x/(sum(d(i)p(i))) in your notation here)

so taking health / average damage will give a decently accurate formula for any instance in x accurate to O(1), which is often good enough. but it will be a little bit lower than the true value by some really small number like in this case. (for this specific example, i improved the accuracy to o(1) with a lot of effort, so in your general version, there's no way i'd bother trying to work out what the O(1) term is. it's probably between 0 and 1 anyway.)

[Guest15937]

Re: [Probability] Expected hits to kill

The number of times I've done this in RPGs...

[Untimely Friction]

Re: [Probability] Expected hits to kill

read your stat page and guess, surely that must be easier

[Reincarnate]

Re: [Probability] Expected hits to kill

E=[0]*(X+1)
s=0
for x in xrange(1,X+1):
    s += E[max(0,x-A)]-E[max(0,x-B-1)]
    E[x] = 1.0 + s/(B-A+1)        
print E[X]