Probability of dealing the final blow

[mXSCNT]

Suppose you have a role playing game in which n players attack a boss with H hit points. Each hit reduces the boss's hit points by a certain amount. The players take turns hitting, starting with player 1, proceeding to player 2, onward to player n, and then back to player 1 again. Eventually, some player deals the final blow and the boss dies. The question is: what's the probability a given player will deal this final blow? We want to look at the limit as the boss's hit points increase to infinity, to smooth out any irregularities. We'd expect that the probability a player deals the final blow is in proportion to the average damage he does.

To specify the problem, let X be a random variable whose domain is subsets of the positive integers. Each particular subset x indicates which points of damage player 1 dealt; for instance, if x contains {5, 6, 8} but not 7, then that means the fifth, sixth, and eighth points of damage dealt to the boss came from player 1, but the seventh point came from some other player. Let the boss's "base" hit points be a probability distribution H over the positive integers, which we will multiply by a constant c and take the limit as c increases.

I believe the following, which corresponds to the idea that the probability a player deals the final blow is in proportion to the average damage he does.
[tex]
\lim_{c \rightarrow \infty} P(cH \in X) = \lim_{k \rightarrow \infty} \mathbb{E}(\sum_{i=1}^{k} | \{ z \in X : z \leq i \} |) / k
[/tex]
for all distributions H and X, whenever both limits exist.

I don't have a proof of this however.

 

[mfb]

Assuming no damage is negative:

I would go backwards: Consider the total damage done to the boss: Initially, it is 0. After the first hit of player 1, it is some positive value, after the first hit of player 2, it is some larger (or equal) value. Consider an arbitrary, infinite series of hits.
This can be represented as colors on a scale from 0 to infinity - each color represents one player, so player 1 gets the interval from 0 to his first damage value and so on.

If the boss has X hit points, the killing blow comes from the player which got X on this scale.
To randomize X, consider a uniform boss life distribution from 0 to n with n->infinity and calculate the winning probability for player i: ##p(i) = \lim_{n \to \infty} \rho(i,n)## where ##\rho(i,n)## is the fraction of damage from 0 to n which came from player i. In the limit of n->infinity, this corresponds to his fraction of average damage, so ##p(i)=\frac{d(i)}{\sum_j d(j)}## with the average damage d(i) for player i. This is true for any specific series of hits apart from a subset with probability 0, so it is true in the general case as well.

 

[bpet]

The above argument is compelling but I'm not sure how to fill in the gaps to make it rigorous. I've been thinking about this on and off for a while now, and perhaps the following would work (and it doesn't rely on X being random):

Let p(i,y) be the probability that the boss has taken exactly y points of damage after one of player i's hits. Assume for now that p(i,y) tends to a constant p(i) as y goes to infinity. If the damage per hit has a finite bound then it is easy to show that p(i+1) = p(i). Let p'(i) be the probability that player i gave the final blow, i.e. that the boss had less than X points of damage before i's hit and at least X points of damage after i's hit. Also let q(i,k) be the probability that a hit from player i does k points of damage. Then p'(i) = (q(i,1)p(i,X-1)+q(i,2)p(i,X-2)+...+q(i,m)p(i,X-m)) + (q(i,2)p(i,X-1)+...+q(i,m)p(i,X-m+1)) + ... + q(i,m)p(i,X-1). If X is sufficiently large then this reduces to p'(i)≈E[Ki]p(i) where Ki is the random damage by player i, so the probability of doing the final hit is simply the proportional of expected damage per hit by player i.

All that remains to be shown is that p(i,y) converges to p(i). I think the only necessary condition is that at least one of the players has non-deterministic damage per hit.

 

[techmologist]

All that remains to be shown is that p(i,y) converges to p(i). I think the only necessary condition is that at least one of the players has non-deterministic damage per hit.

Would it also need to be stationary? For instance, if a player that sensed weakness was able to focus all his energies to increase the damage he does far beyond what the other players are capable of, then that player would be very likely to deal the final blow. I have no idea if this applies in role playing games. I think if the distribution for number of damage points done were stationary and geometric, then the result would follow more easily. I used this approach to estimate the probability that a person wins a game of 9-ball as being proportional to the average number of balls they run per inning. Of course this is not the general result that the OP was asking for.

 

[lpetrich]

Here's how I would solve the problem.

Each hit's strength is h_i with a certain probability distribution with mean m and standard deviation σ, and let us suppose that the hit strengths are uncorrelated. The total of n hits is
H(n) = Σ_{i=1 to n}h_i

Its average value <H(n)> = Σ_{i = 1 to n}<h_i> = n*m

Now calculate the average value of the square of H(n):
<H(n)²> = Σ_{i,j = 1 to n}<h_i*h_j> = n*m
Since they are uncorrelated, for j != i,
<h_i*h_j> = <h_i>*<h_j> = m²
For j == i, by the definition of standard deviation,
<(h_i)²> = m² + σ²

This gives us
<H(n)²> = (n*m)² + n*σ²

Thus,
m(n) = n*m
σ(n) = sqrt(n)*σ

If that boss has a life of H0, then it will take, on average n0 = H0/m hits to kill it.

The standard deviation of that number is about sqrt(n0)*(σ/m), or (1/sqrt(n0))*(σ/m) * n0

So the more hits that one has to make, the less scatter there will be around using the mean strength.

 

[bpet]

Would it also need to be stationary? For instance, if a player that sensed weakness was able to focus all his energies to increase the damage he does far beyond what the other players are capable of, then that player would be very likely to deal the final blow. I have no idea if this applies in role playing games. I think if the distribution for number of damage points done were stationary and geometric, then the result would follow more easily. I used this approach to estimate the probability that a person wins a game of 9-ball as being proportional to the average number of balls they run per inning. Of course this is not the general result that the OP was asking for.

Yes I assumed that each player's damage per hit is stationary.

I think it's possible to modify the result to where players hit irregularly. For simplicity, assume that player i's hit rate is r(i) so the damage follows a compound Poisson process. Modifying the previous argument, let p(y) be the probability that the boss has taken exactly y points of damage at some point and assume that it tends to a constant as y tends to infinity. The probability that player i does the next hit is proportional to r(i) so by similar arguments it is easy to show that the probability that player i does the final blow is proportional to r(i)*E[K(i)] which is the expected damage rate.

The result should generalize to other hit rate processes where the probability that a player does the next hit given y points of damage so far, tends to a constant as y increases.

 

[mfb]

We don't even need the same order of players in each round, and we don't even need rounds, as long as the fraction of damage dealt approaches a constant for damage->infinity and [the boss life OR the damage is randomized with a sufficiently broad distribution].