I have a game that assigns the probability of finding items in treasure chests by making several independent checks until it fills a quota, with duplicates not allowed. I am trying to figure out how to calculate the resulting probabilities of finding each item - without breaking the bank in terms of calculation brute force.
For an example: The % chance of getting a small chest is 30. For a medium chest it's 15, and for a big chest it's 5. (There is no requirement that these add to 100.)
The algorithm:
- Roll random against the large's 5%.
- If successful, it's a large. If not, roll random against the medium's 15%.
- If successful, it's a medium. If not, roll random against the small's 30%.
- If successful, it's a small. If not, return to rolling for the large, and repeat the process indefinitely until something is successful.
This is then repeated over three layers. The layers are:
- size of treasure chest
- item category (e.g. weapon or armour)
- specific item (e.g. for weapons: sword or pike; for armour: helmet, gloves, or boots)
So first the game makes this "roll until success" check to decide what chest to get. The chest selected determines which item pool is drawn from and how many items are needed. For each item needed, the game does a "roll until success" check for category, and then another for item. It repeats these two checks until it has the requisite number of items. Duplicates are not allowed; if an item would be a duplicate, the process is restarted. (Which I think is identical to changing the % chance of potential duplicates to 0.)
I am trying to, given the % chances for everything in all 3 layers, calculate the final probability that you will get a chest that has a specific item in it. I'm not looking for a one-time result of any particular example data: I'd like help in figuring out how to formulate the algorithm so I can apply it to any data.
This is giving me a headache for two reasons:
- It's really close to being a geometric distribution, but because the "success rate" at each step is not identical, it isn't. Also you have to fudge the meaning of "success" because what item you get matters.
- Ignoring duplicates is a pain. If item 2 is in a different category than item 1, there's no effect. But if item 2 is in the same category - or if one category has been completely exhausted - the rest of the things in that level all have different rates for item 2.
The brute force way of formulating this doesn't seem too hard (e.g. doing the $(1-p)^k(p)$ thing for each p in order a bunch of times). But I don't want to use brute force, because I have to present the data using MediaWiki, which can do this given the variable and loop extensions but I imagine doing this a ton will not be ideal - taking 2 items from a chest that has 4 categories and 3 things in each category looks like I need 21 iterations of $(1-p)^k(p)$ (1 for "chance of picking this", 1 for each other option to get "chance of picking this given I previously picked that"). If possible, I'm looking for something more pragmatic.
Other notes:
- Some items can appear in more than one size of chest, with different rates. It should be easy enough to calculate them separately and proportionally add them together.
Related-looking questions:
- Exhibit A - Very similar, but no answer.
- Exhibit B - The same problem in essence (including the part where there's multiple levels of selection), but without the all-important "repeat until something succeeds" condition.
Examples of possible data:
Set 1
1% large chest (pick 2)
50% weapon
30% big sword
10% claymore
20% armour
50% steel helmet
50% steel gauntlets
50% steel boots
10% jewel
20% ruby
30% sapphire
40% emerald
20% potion
10% red potion
20% blue potion
30% green potion
40% yellow potion
10% medium chest (pick 2)
50% potion
40% water
20% red potion
10% weapon
40% medium sword
20% armour
40% iron helmet
40% iron boots
100% small chest (10% chance of pick 2, 90% chance of pick 1)
100% creature bits
15% tail
70% hair
Set 2
5% large chest (pick 2)
50% weapon
30% claymore
30% big sword
20% giant club
30% armour
100% magic bracelet
10% jewel
50% emerald
100% diamond
30% potion
10% red potion
20% blue potion
30% green potion
40% yellow potion
15% medium chest (pick 2)
40% potion
80% water
10% red potion
5% weapon
40% small sword
20% medium sword
25% armour
40% iron helmet
40% iron boots
100% small chest (10% chance of pick 2, 90% chance of pick 1)
100% creature bits
40% tail
70% hair
Note: this was done when the chests were checked small, medium, large. The same approach works in the opposite order, but the numbers change a bit.
Given your chest algorithm, the chances of the three kinds of chest must add to $100\%$ because you will generate a chest-you keep trying until you do. We can calculate the chance of each kind. The chance we generate a chest on the first round is $1-.7\cdot .85 \cdot .95=\frac{1739}{4000}$ The chance we generate a small chest is then $0.3 \cdot \frac {4000}{1739}\approx 0.69$ The chance we generate a medium chest is $0.7 \cdot 0.15 \cdot \frac {4000}{1739}\approx 0.24$ and the chance for a large chest is $0.7 \cdot 0.85 \cdot 0.05 \cdot \frac {4000}{1739} \approx 0.07$.
You can do a similar calculation for the other parts but did not present the information to do it.