Expectation value of fighting time of Knight vs Monster problem

Question

I get this problem when I play computer game. When I see my knight is attacking the monster, I think what is the expectation value of fighting time. My knight is much more powerful than the monster, so my knight always win but what is the expectation value of fighting time.

So, I simulate the situation:

Monster has Hp = 10000
My knight deal damage vary from 400 to 600 (500+-100) uniform distribution.
Each time that my knight attack has 5% chance to miss(no damage).
Each time that my knight hit monster has 10% chance to deal 1000 critical damage(critical damage is constant).
My knight attack speed is 1 time per second

What is the expectation value of fighting time ?

I calculate this by using DpS or damage per second.

mean(DpS) = 95%x((500x90%)+(1000x10%)) = 0.95*(0.9*500+0.1*1000) = 522.5

mean(Number of Hit) = 10000/522.5 = 19.138756

mean(fighting time) = (19.138756-1)/1 = 18.138756 second

I also use program to make sure that I am correct. I use online python.

https://www.onlinegdb.com/online_python_compiler

from random import randint;

n=100000;

H=0;

Hp=10000;

for x in range(1, n):

x=0;

h=0;

while Hp > x:

    temp=randint(1,100);

    if temp > 5:

         temp=randint(1,100);

         if temp > 10:

              x=x+randint(400, 600);

         else:

              x=x+1000;

    h=h+1;

H=H+h;

print('h_ave =',H/n)

The program yield mean(Number of Hit) = 19.69778 which has some different from my calculation. I don't know why. I should be nearly same because I simulate 100000 time.

Please help me or tell me what is incorrect.

score 1 · Accepted Answer · answered May 02 '19 at 19:38

This problem is surprisingly subtle. Let $D_n$ be the number of damage dealt on the $n^{th}$ attack, and suppose that $N$ attacks are needed. Then $$ D_1+D_2+\dots+D_N=10,000+\text{overkill} $$ That is, the total damage done is in general going to be more than $10,000$. Taking expected values, you get $$ E[D_1]+\dots+E[D_N]=10,000+E[\text{overkill}] $$ Since each summand on the left has the same expected value, and there are $N$ summands, this can be written as $$ E[N]\cdot E[D]=10,000+E[\text{overkill}],\tag{*} $$ so that $$ E[N]=\frac{10,000+E[\text{overkill}]}{E[D]} $$ where $D$ is just the damage of a generic attack. This illustrates the difference between your two results: you cannot just divide the hit points by the expected damage rate, because in general you will in total deal more than $10,000$ total. This means the true result is higher than what you initially calculated, as you found. You have to be much more careful to compute $E[\text{overkill}]$ exactly.

*You might be wondering why the left hand side of this equation is $E[N]E[D]$ as opposed to $NE[D]$. This is justified by Wald's equation.

Further, if you estimate $E[\text{overkill}] \approx E[D]/2$, then $E[N] \approx {10000\over E[D]} + {1\over 2} \approx 19.64$ which is much closer to the simulated result of $19.70$. There are better estimates for $E[\text{overkill}]$ but $E[D]/2$ is pretty good for your $D$. — antkam, May 02 '19 at 21:02
Related question on a simpler case but solving the distribution of the overkill exactly. Based on the answers there (by Mike and myself), if we approximate your $D$ by ignoring the $5$% miss chance and the $10$% crit chance, a uniform $D$ should lead to $E[\text{overkill}] \approx {2E[D]\over 3}$ in the large limit and $E[N] \approx 19.81$, but I'm not sure if $10000$ is large enough... — antkam, May 02 '19 at 21:32

Expectation value of fighting time of Knight vs Monster problem

1 Answers1