Sign in to follow this  
Calexus

Multiple Binomial Distributions?

Recommended Posts

I am using Binomial Distribution to calculate the probability of a character inflicting an amount of damage on another character. It's a dice based system so the probability of a wound is based of a series of successful dice rolls. But thats not really important. What i calculate is the probability of scoring n wounds with k attacks all having probability p to wound. But I have come to where I want to know the probability of a character (or group of characters) with multiple attacks with different probability to wound to kill a target. Does that make any sense at all? Maybe an example can clear things up. Lets say I have a group of 3 characters. Character A have 3 attacks and each have a probability of 21% damaging creature X. Character B 7 attacks, probability 6%. Character C 2 attacks, probability 35%. Now what is the probability of this group with 12 attacks scoring 3 wounds on creature X? I can calculate the probability for each character scoring a number of wounds but how do I calculate the combined probability of the group?

Share this post


Link to post
Share on other sites
There is no simple solution to this problem, since you have to study the distribution of the wounds for each character.

A naïve computation method would be:

let rec probability_to_inflict n attackers =
match attackers with
(* Zero attackers have a 100% probability to inflict zero wounds *)
| [] -> if n = 0 then 1. else 0.
(* Does the first attack of the first attacker wound? *)
| (num, prob) :: others ->
if num = 0 then probability_to_inflict n others
else prob *. (probability_to_inflict (n-1) ((num-1, prob)::others)) +.
(1. -. prob) *. (probability_to_inflict n ((num-1, prob)::others));;

(* 17.3% chances to inflict three wounds *)
probability_to_inflict 3 [3, 0.21; 7, 0.06; 2, 0.36];


A faster approach, if you have a lot of possibilities, would compute every possible number of wounds for every attacker (instead of treating attacks one by one).

Share this post


Link to post
Share on other sites
Here's something you can try if the attacks between characters are independent.

Character A's attack has the binomial function f(kA; 3, 0.21), character B's is f(kB; 7, 0.07), and character C's is f(kC; 2, 0.35). The probability that all three characters do 'K' wounds to the target is f(kA; 3, 0.21)*f(kB; 7, 0.07)*f(kC; 2, 0.35), where kA + kB + kC = K. So I believe that if you calculate that probability for all permutations of kA/kB/kC that sum to 'K' and add them together, you'll get the probability you're looking for.

Disclaimer, I am a little rusty [grin]

Share this post


Link to post
Share on other sites
You can use generating functions to compute this. The idea is that the number of injuries as a result of an attack is a random variable over the natural numbers. You can represent that using a power series. Since you have a finite number of possible injuries, you just have to deal with polynomials.

This is how the computation would go:

An attack by A is represented by the polynomial
P_A = .79+.21*x
Similarly,
P_B = .94+.06*x
P_C = .65+.35*x

The beauty of representing things in this bizarre way is that in order to combine attacks, you just have to multiply their corresponding polynomials. So the combined attack in your example can be described by:
P = P_A^3 * P_B^7 * P_C^2 = (.79+.21*x)^3 * (.94+.06*x)^7 * (.65+.35*x)^2

If you write the polynomial as P = P_0 + P_1*x + P_2*x^2 + P_3*x^3 + ..., then P_i is the probability that the number of injuries is exactly i.

[Edited by - alvaro on July 28, 2008 12:21:51 PM]

Share this post


Link to post
Share on other sites
Thanks for the suggestions :)

Haven't really had time to try any of them yet, so i don't know which one I'll go with.

ToohrVyk that code of yours... what is that? I think I understands what its doing but it not easy to read. Its some kind of recursive history with syntax I can barely follow, but it seems to work. Ó_ò


Zipster interesting method, and it would integrate pretty nicely with my existing code I think. Does it have a name? Think I'll try this one first.


And Alvaro, what can I say. That looks complicated. Generating functions, don't think I've ever heard of does. Maybe I have but I don't remember. Power series I do remember but not much more then the name...
Anyway it seems to be a pretty elegant way of doing it but polynomes in code, that cant be funny.

Maybe I should give it a try. Just so that I don't misunderstand anything now x in your example would represent what?

Share this post


Link to post
Share on other sites
Quote:
Original post by Calexus
And Alvaro, what can I say. That looks complicated. Generating functions, don't think I've ever heard of does. Maybe I have but I don't remember. Power series I do remember but not much more then the name...
Anyway it seems to be a pretty elegant way of doing it but polynomes in code, that cant be funny.

Maybe I should give it a try. Just so that I don't misunderstand anything now x in your example would represent what?


You can read about this on Wikipedia. It's not the easiest thing to digest, but I gave you enough details to actually implement it. Multiplying low-degree polynomials is not that hard.

I'll try to explain the method in simple terms. For any given attack or combination of attacks, we want to know the probability that the number of resulting injuries is 0, 1, 2, ... If we just list those probabilities as a sequence, we'll write:
Attack from A = (.79, .21, 0, 0, 0, 0, 0, ...)
Attack from B = (.94, .06, 0, 0, 0, 0, 0, ...)
Attack from C = (.65, .35, 0, 0, 0, 0, 0, ...)

Now the question is how we combine attacks. It turns out that if the attacks are independent (which you are probably assuming they are), you can combine two attacks by a formula that is identical to series multiplication.

As an example, let's combine one attack from A and one attack from B. What's the probability that you get 0 injuries as a result? Well, for that to happen, both attacks must have resulted in 0 injuries, so the probability of this happening is .79*.94 = .7426 . What's the probability that you get exactly 1 injury? There are two ways that can happen: Either A hit and B missed or A missed and B hit. The probability is then .21*.94+.79*.06 = .2448 . What's the probability that you get exactly 2 injuries? Both A and B have to hit, so it's .21*.06 = .0126 . Writing that as a sequence, it's (.7426, .2448, .0126, 0, 0, 0, ...).

Now we'll introduce the magic of polynomials. If we associate a sequence like above with a polynomial, by mapping the sequence (a0, a1, a2, a3, ...) to the polynomial a0 + a1*x + a2*x^2 + a3*x^3 + ..., we can just combine attacks by multiplying the polynomials. In the example of combining one attack from A and one from B, we have
(.79 + .21*x) * (.94 + .06*x) = .7426 + .2448*x + .0126*x^2

So `x' doesn't really mean anything. Well, you can read the term .0126*x^2 as "the probability of getting 2 injuries is .0126".

I hope my previous post makes more sense now.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this