gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

OffTopic > Combinatoric Probability (Item Drops as an Example)

#174109 - sgeos - Tue May 18, 2010 9:00 pm

So, lets say I have four monsters, and each one has a 4.1% chance of dropping an item? What are the chances of not receiving an item? Just getting one? Two? Three? Four?

I remember how to do this in a manual fashion. Using a spreadsheet to create 16 scenarios (drop VS no drop to the power of 4), this is what I get.
0 items @ 84.5813% = (95.9%^4 * 4.1%^0) * 1
1 item @ 14.4644% = (95.9%^3 * 4.1%^1) * 4
2 items @ 0.9276% = (95.9%^2 * 4.1%^2) * 6
3 items @ 0.0264% = (95.9%^1 * 4.1%^3) * 4
4 items @ 0.0003% = (95.9%^0 * 4.1%^4) * 1

This becomes the general formula:
(DROP_RATE^DROPS * (1 - DROP_RATE)^(MONSTERS - DROPS)) * X

I'm having trouble remembering how to derive X from the MONSTERS and DROPS. (Obviously DROP_RATE doesn't affect it.) A quick google search didn't turn anything up, although I'm sure it is out there somewhere. In any case, does anyone remember how do this? If not, can anyone point me to a site that explains this?

Thanks.

EDIT: The above formula only works for one type of item. If the monsters have, say, a 4.1% chance of a normal drop, and a 0.9% chance of a rare drop, things quickly become far more complicated. It is relatively easy to generate a LUT of X (see above formula) when there are only two outcomes (drop VS no drop).

Code:
Look Up Table of X

             Monsters
       1   2  3   4   5   6
     --- --- --- --- --- ---
  0 =  1   1  1   1   1   1
D 1 =  1   2  3   4   5   6
r 2 =      1  3   6  10  15
o 3 =         1   4  10  20
p 4 =             1   5  15
s 5 =                 1   6
  6 =                     1


0 and max drops always equal 1, and 1 and (max - 1) drops always equal the number of monsters. Presumably these are magic numbers that some sort of general formula spits out. I can't make heads of tails of the numbers in the middle.

Total X in a column always equals 2^monsters for 2 outcomes. Presumably the sum of X for a given number of monsters is outcomes^monsters using a more general forumula. (This could be extended to handle any fixed number of item drops.)

To get the value in the next column, add the values in the previous column with a "shifted" copy of the previous column. For example, the values for seven monsters are 1, 7, 21, 35, 35, 21, 7, 1. (I have not check to see if this will hold with more than 2 outcomes.)

Unless I'm doing this totally wrong, I've got enough math under my belt to solve any particular problem, but the solution doesn't feel elegant because I need to do more calculations to extend it.

/EDIT

Last edited by sgeos on Tue May 18, 2010 9:44 pm; edited 1 time in total

#174111 - Dwedit - Tue May 18, 2010 9:41 pm

The term is "Binomial distribution"
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#174112 - sgeos - Tue May 18, 2010 9:51 pm

Thanks. What term am I looking for if my problem has more than two outcomes?

To make things silly, say a monster can drop 19 different types of items. Obviously I can figure out the probably of receiving two item 12's and one item 3 given a group of six monsters.

Presumably the formula for that will be some combination of two or three of these:
(FAIL_RATE^POW_F * RATE_0^POW_0 * ... * RATE_18^POW_18) * DISTRIBUTION

EDIT: "Polynomial distribution" seems like the obvious term, but the results do not seem to point to a general formula of which binomial probability is a simple case... /EDIT

#174118 - elwing - Wed May 19, 2010 6:36 am

hum, just a quick question:
since the problem is dead trivial for 1 monster why not use some divide & conquer method? it does not look like you're gonna do this computation every frame and it's not so bad either...


by the way, cearn posted a nice article on probabilities... it's a quite usefull read for people who did never learned probabilty or the one who never used them for the last 5years...

#174133 - Cearn - Wed May 19, 2010 5:31 pm

Oh hai!

The general case is given by eq 18. I'm not sure it has a proper name, but I like to call it the multinomial distribution, since the multiple-choice variant of the binomial coefficient is called the multinomial.

sgeos wrote:
Look Up Table of X

Monsters
1 2 3 4 5 6
--- --- --- --- --- ---
0 = 1 1 1 1 1 1
D 1 = 1 2 3 4 5 6
r 2 = 1 3 6 10 15
o 3 = 1 4 10 20
p 4 = 1 5 15
s 5 = 1 6
6 = 1


0 and max drops always equal 1, and 1 and (max - 1) drops always equal the number of monsters. Presumably these are magic numbers that some sort of general formula spits out. I can't make heads of tails of the numbers in the middle.

Total X in a column always equals 2^monsters for 2 outcomes. Presumably the sum of X for a given number of monsters is outcomes^monsters using a more general formula. (This could be extended to handle any fixed number of item drops.)

To get the value in the next column, add the values in the previous column with a "shifted" copy of the previous column. For example, the values for seven monsters are 1, 7, 21, 35, 35, 21, 7, 1. (I have not check to see if this will hold with more than 2 outcomes.)

The magic numbers are the result of the binomial coefficient. It gives the number of ways you can distribute two indistinguishable groups of items, like for example the different Left-Right turns you can take to reach a location in Pascal's Triangle. For two choices, the answer is (k1+k2)! / k1! / k2!. For details, interpretation and extension to more choices, see the article. Do note that calculating the coefficient like this can be tricky, as the numbers get big pretty fast.

sgeos wrote:
To make things silly, say a monster can drop 19 different types of items. Obviously I can figure out the probably of receiving two item 12's and one item 3 given a group of six monsters.

In this case, you'd have three things to consider: choice A (item 12) with a probability pa and count ka=2, choice B (item 3) with count kb=1, and a choice C (neither) with pc and kc=3. the chance of getting a specific order of results, like aabccc, is found by multiplying the probabilities of each sub result: pa*pa*pb*pc*pc*pc. This then has to be multiplied by all the different ways you can distribute 2 as, 1 b and 3 cs, which is 6!/2!/1!/3!.

You can also break it apart into 'treasure' and 'non-treasure' first, giving the binomial distribution, and then later subdivide the 'treasure' group into A and B. It'll give the same answer, but may take a little longer.

If you have a graphic calculator, the functions relevant functions will be called something like binompdf for partial probabilities P(X=k) and binomcdf for cumulative probabilities, P(X≤k).

#174141 - sgeos - Thu May 20, 2010 3:10 am

Thanks for the reply.

Nice article. Everything makes sense, and it is really simple once you know how to do it.

This math can even be used for totally unrelated events. Ie, I have a 17% chance of encountering 4 iron golems. Each golem has a 28% chance of dropping ore, and a 2% chance of dropping an anvil. What is the chance of encountering 4 iron golems and receiving at least two ore and one anvil on my first battle. =)

The answer is 0.2239104% for an exact match and 0.25696384% if extra items are allowed to drop, right? (Hopefully I didn't botch that...)

EDIT: It seems like there should be some sort of a shortcut for dealing with wildcard results. In the example above, the behavior of one of the golems doesn't matter... but which particular golem that happens to be is arbitrary... Maybe not? /EDIT