7

I know there's gaming stackexchange for gaming questions, but I believe this is purely maths related.

I'll try to avoid using game jargon and keep it simple. I'm collecting keys in game, each key taking a fair bit of time to obtain. They open a chest, which generates one random reward from a predeterimed table. On the loot table, there are five different armor pieces, each with a chance of 1/1000 to obtain. The catch is, because of game's inventory limitations, I can't open the chest every time I get a key and just get the five armor pieces that way - I have to do big openings of multiple keys at once. If I don't get a full set, but, for example, 4 out of 5 pieces, it would limit the speed of obtaining future keys.

Which is why I would like to count an optimal amount of keys to have to get the full set at once. Is there a set method or a formula for similar problems?

If the above explaination is too convoluted, I can try to further simplify it if needed.

user3767919
  • 81

1 Answers1

6

Let $c_a(k)$ be the chance you have collected $a$ armour pieces after opening $k$ keys and $p(a)$ the chance of getting a new armour piece given that you have found $a$ armour pieces already. Then we find:

$$c_{0}(k) = (1 - p(0))c_0(k-1)$$ $$c_{a}(k) = p(a-1)c_{a-1}(k-1) + (1 - p(a))c_a(k-1)$$

$$c_{a}(0) = \begin{cases}1&a = 0\\0& a> 0\end{cases}$$

$$p(a) = \begin{cases}\frac{5-a}{1000}&0 \leq a \leq 5\\0&\text{otherwise}\end{cases}$$

Programming this recurrence in Python we find the following chances of collecting all 5 armour pieces:

\begin{array}{cc} \text{Keys}&\text{Chance}\\ \hline 2045&50\%\\ 2883&75\%\\ 3869&90\%\\ 4583&95\%\\ 6208&99\% \end{array}

And a plot:

plot

orlp
  • 10,508
  • 1
    Thank you so much! I expected that "if the chance is 1/1000, I should need around 1k keys" is the wrong approach, but I wasn't expecting to have to get so much more. Thanks for the help! – user3767919 Jun 01 '20 at 05:39
  • 1
    @user3767919 This holds for a lot of grinds in Runescape if you want every single drop. See the Coupon collector's problem. – orlp Jun 01 '20 at 05:42
  • Hey, sorry to bother you, but I have just one question - if p(a) is the chance of getting a new armor piece given that I have gotten a armor pieces already, shouldn't p(a) be always flat 1/1000? Probability of getting a certain piece isn't affected if I have another piece – user3767919 Jun 01 '20 at 05:48
  • 1
    @user3767919 If you have 0 pieces there are 5 new pieces you can get, thus $5 \cdot 1/1000$. If you already have 3/5 pieces then only two of the pieces will be a new piece, giving $2/1000$. – orlp Jun 01 '20 at 05:52
  • Okay, I misunderstood the purpose of p(a) then, thanks again for clarifying! – user3767919 Jun 01 '20 at 05:54