Spiral Knights - Probability in Spiral Knights

Probability in Spiral Knights

10 replies [Last post]

Wed, 10/26/2011 - 13:03

Bopp

In case there is interest, I thought I'd talk about some probabilities in Spiral Knights. Specifically, if every time you try something you have a 1 in N chance of succeeding, then how many times will you have to try, before you succeed? For example:

If about 3% of all Lockboxes contain Shadow Keys, then how many Lockboxes do you need to open, to find one?
If you want a CTR UV on a weapon, and this happens about 1 in 8 times you buy a single UV, then how many times do you need to buy, to get one?

First, here are some general answers. We assume that each try has a 1 in N chance of succeeding, independent of the other tries.

The expected number of tries, to succeed once, is N. (Edit: Think of this as the average number of tries required per successful try.)
For any integer A >= 1, the probability that your first success will happen in the first A tries is 1 - (1 - 1 / N)^A.
For any integer B such that 0 <= B < N, the probability that your first success will happen between your (N - B)th try and your (N + B)th try is (1 - 1 / N)^(N - B - 1) - (1 - 1 / N)^(N + B).

In the case of Shadow Keys, our best current data suggest that they show up about 1 in 33 times. So N = 33. You expect to try about 33 times, before you find one. You have about a 50% chance of your first Shadow Key showing up in your first 23 tries. There is a 64% chance of your first Shadow Key showing up in your first 33 tries. There's a 50% chance of your first Shadow Key showing up between your 13th and 53rd tries.

In the case of rolling for CTR UVs, suppose that each possible UV on a weapon (CTR, ASI, slime, gremlin, beast, fiend, undead, construct) has an equal chance of happening. Then N = 8. You expect to try about 8 times, before you get a CTR UV. There's a 50% chance of a CTR UV showing up in your first 5 tries. There's a 50% chance of your first CTR UV showing up between your 3rd and 13th tries. (The same logic applies to ASI UVs, fiend UVs, etc. But I don't really know whether all UV types have an equal chance of happening.)

In case anyone wants to check my work, or ask different questions about the same idea, here is a brief sketch of the logic. It's all based on the geometric distribution.

The probability that your first success happens on try K is equal to (1 - 1 / N)^(K - 1) (1 / N), because you must fail K - 1 times and then succeed. Call this number P(K).
From probability theory, the expectation is the sum of K P(K), where K ranges from 1 to infinity. This sum simplifies down to N.
The probability that your first success happens in the first A tries is the sum of P(K), where K ranges from 1 to A. This simplifies down to the answer I gave above.
The probability that your first success happens between your (N - B)th try and your (N + B)th try is the probability that it happens in your first N + B tries, minus the probability that it happens in your first N - B - 1 tries. You can compute each of those already; just subtract.

Wed, 10/26/2011 - 13:54

Martinsen

My... brain... hurts @____@

Wed, 10/26/2011 - 14:33

Sypsy

In layman terms (and from

In layman terms (and from what I remember about my last probability class from university several years ago).

If there is a 3% or 1 in 33 chance of a shadow key coming from an iron lockbox, 33 lockboxes does not guarantee 1 shadow key.
Infact, 53 boxes will provide a "reasonable expectation" that you will receive at least one shadow key.

Let's say you have opened 32 lockboxes so far, you cannot expect the next box to have a shadow key (this is obvious.) Infact, if you have no shadow keys after the 33rd lockbox, this would be considered well within "reasonable" due to probability. The chances of this occurring is fairly frequent. (Bopp could give you the exact % based on his defined N. My guess is that 30% of people will have no shadow key after 33 ironboxes.)
If, however, you have opened 53 boxes with no key, then you have truly "beaten" the odds as the chances of this scenario occurring is less than 1%. You can now really curse your luck. I have not checked Bopp's calculation to arrive to the 53 boxes for cover 99.9% of the curve.

Edit:
@Bopp: Do you mean: "There's a 50% chance of your first Shadow Key showing up between your 23rd and 53rd tries.?" Not 13th? Since it's 50% to the 23rd box....

Wed, 10/26/2011 - 15:55

Knight-Solaire

This topic has made me

This topic has made me realize how much I'd forgotten about Statistics since high school. Is 3% an official number, or is that an observed average based on boxes opened so far, or where did that come from? If it's true, then these numbers are kinda... distressing.

Wed, 10/26/2011 - 14:36

Sypsy

@Tlachtli The stat was taken

@Tlachtli

The stat was taken from: http://forums.spiralknights.com/en/node/30115
At one point the % was closer to 3%, but it's moved up to ~3.5% as of today, or 1 in 29 boxes.

Wed, 10/26/2011 - 14:49

Bopp

responses

Right, the 3% number is not at all official; it just comes from that data-collection thread. Adjust as needed.

Sypsy, you are correct that opening 33 Lockboxes would not guarantee a Shadow Key. In fact, no number of Lockboxes will. 33 is the "expectation", which basically means the average; on average, each Shadow Key you get is going to require about 33 Lockboxes.

Of course, in many instances finding a Shadow Key will require fewer (say, 29) or more (say, 41) Lockboxes. Because this is a random process, there is some variation around the expectation of 33. That's what the "50% chance of your first Shadow Key showing up between your 13th and 53rd tries" is all about. Half the time when you're hunting for a Shadow Key, you'll try somewhere between 13 and 53 times. The other half of the time, you'll get really lucky (fewer than 13 tries) or really unlucky (more than 53 tries).

Sypsy, I meant between 13 and 53, not 23 and 53. Yes, this overlaps a bit with the 1-23 range in which you also have a 50% chance. I gave this 13-53 range in order to characterize the variation about the expected number of 33.

If there is a more interesting/useful quantity that you all would like help computing, then let me know.

Wed, 10/26/2011 - 15:04

Sypsy

I see. I was assuming you had

I see.

I was assuming you had made this a normal probability curve for # of lockboxes for a single shadow key. I think this is easier to understand since you can see what falls within 98% (or 90% or whatever) of the normal curve. This makes it easy to see what would put you into the first 1% (let's say 1 lockbox for 1 shadow key) or last 1% of the curve (e.g, above 50 Boxes for 1 key) based on the number of boxes opened.

This overlapping 50% on the 13 - 23 range and geometric probability confuses me and is clearly over my rusty knowledge.

However, I do like how this thread reminds people that just because you have a "1 in X chance" of getting something does not mean it will take X tries to get 1 of these items. Infact, if you want a 95% chance of getting said item, it will take more than X boxes, and that's the way probability works.

Wed, 10/26/2011 - 15:16

Bopp

geometric distribution, not normal distribution

Sypsy, the normal distribution is really important in probability and statistics, but it doesn't apply to this problem. This problem is all about the geometric distribution. That's why your numbers are a little off. But your intuition for the pitfalls of probability still applies.

Wed, 10/26/2011 - 15:51

Mohandar

Move along, nothing to see here

Basic probability... if the odds of getting a shadow key are k (probabilities fall between 0 and 1), then the odds of NOT getting a shadow key are (1-k). If you open n lockboxes, the odds of NOT getting a key are (1-k)^n. And so the odds of getting at least one shadow key after opening n lockboxes is [1 - (1-k)^n]

So for a generous rate of 0.05 (5%), if we set our goal as obtaining at least one shadow key with probability 0.95 (95%) we can calculate:
1 - (0.95)^n = 0.95
Solve for n, and we get ~58. You would have to open about 58 lockboxes to guarantee with 95% probability of obtaining at least one shadow key. This means if you open 58 lockboxes, 19 out of 20 times you will get at least one shadow key.

You can solve for different target probabilities as well. For a 50% chance of at least one key, you'd need 14 boxes; for a 99% chance, that's 90 boxes.

Wed, 10/26/2011 - 17:30

Giannii

ugh and that's with a

ugh and that's with a generous rate, as you are the buyer you should try with a not so generous one.

Wed, 10/26/2011 - 20:23

#10

Bopp

yep, that's equivalent to my calculation

Mohandar, your argument is equivalent to the second of my three "general answers" above. The third "general answer" follows from the second, so it proves that too. However, it does not suffice for supplying the first "general answer", the expected number of tries to get the first success.

Yes, it is basic probability. I never portrayed it as anything more than that.

Search

Probability in Spiral Knights