The new forums will be named Coin Return (based on the most recent vote)! You can check on the status and timeline of the transition to the new forums here.
Math question!
WearingGlasses
Of the friendly neighborhood varietyRegistered User regular
Of the friendly neighborhood varietyRegistered User regular
Sorry, this is a bit hard to Google.
I'm playing a game (Marvel: Avengers Alliance) that has gives me a goal of getting 8 different comic covers. They are acquired randomly on opening a mystery box. The comic cover is random, and I assume even distribution is in place among eight covers.
I can't formulate the formula for: "What's the minimum number of mystery boxes you have to open so that your chances of getting all eight different covers approaches N% (say, 90)?" Combinations were never my strong suit, so... A little help, guys?
I'm playing a game (Marvel: Avengers Alliance) that has gives me a goal of getting 8 different comic covers. They are acquired randomly on opening a mystery box. The comic cover is random, and I assume even distribution is in place among eight covers.
I can't formulate the formula for: "What's the minimum number of mystery boxes you have to open so that your chances of getting all eight different covers approaches N% (say, 90)?" Combinations were never my strong suit, so... A little help, guys?
0
Posts
The usual way I've seen for deriving the expected number of picks ('trials') is this:
Say t_n is the number of mystery boxes I need to open to get n covers. If I get lucky, this could be as low as n. If I am unlucky, who knows. E(t_n) is the number of mystery boxes I expect to have to open to get n covers.
Now, if I have i-1 covers already, let X_i be the number of mystery boxes I need to open to get a cover I don't already have. That is, starting with the first box after I get my (i-1)th cover and ending with my getting the ith cover.
Then, I can say that t_n = sum(X_i, as i goes from 1 to n). For each box if I already have i covers, my probability of success is (n - i + 1)/n. Since X_i is a set of these box trials, X_i follows a geometric distribution (time to first success), and E( geometric distribution ) is 1/p, where p is the probability of each individual success. Thus, E(X_i) = n / (n - i + 1 ).
Going back to the beginning, E(t_n) then equals sum( n / ( n - i + 1 ), i goes from 1 to n), which simplifies to n * sum(1/i, as i goes from 1 to n).
sum(1/i, i goes from 1 to n) is a special sum known as the Harmonic Number, or H_n. In the case of n=8, n*H_n =~ 21.7 mystery boxes.
This doesn't really answer the question of what the 90% threshhold is, but that is to my recollection a much more complicated problem.
Other figures:
20 boxes for 50%
26 boxes for 75%
50 boxes for 99%
~68 boxes for 99.9%
~85 boxes for 99.99%
Random chance becomes a bigger factor as the number of boxes opened grows, since there are fewer cases where that happens.
The total number of possible orderings of k comic covers over n boxes is k^n
The total number of orders that have at least one of each is:
sum(i = 0 to k-1) (-1)^i * kCi * (k-i)^n
where kCi is k choose i, or k!/(i!(k-i)!)
The ratio is the probability that you will get at least one of each.
The sum comes from a recursion which is made clearer with an example with smaller numbers. Let's say that there are 3 covers (Hulk, Thor, and Iron Man), and you're picking up 6 boxes. There are 3^6 possibilities (that's the first term of the sum). Now, let's take out all the ones that don't have a Hulk. How many are there? 2^6, because each of the 6 boxes have two choices. We need to subtract this 3 times because we could be missing Thor or Iron man instead. This gives you a total of 3^6 - 3*2^6 outcomes.
Unfortunately, you've done some double counting. Let's say your outcome has neither a Hulk nor a Thor. This gets subtracted twice because it's in the "no Thor" outcomes and the "no Hulk" outcomes. So, we need to add back in the outcomes where we're missing two comics. Since there are only 3, these are the outcomes where all the comics are the same, of which there are 3: all Thors, all Hulks, and all Iron Mans. This leaves us with 3^6 - 3*2^6 + 3, which completes the sum. If you check those terms in the sums above, you'll see that they match the terms for k =3, n = 6.
In general, if we want to know how many outcomes there are where we are missing i items, it's just (k-i)^n. The number of ways to exclude i items is kCi, so those get multiplied. The (-1)^i is so we alternate adding and subtracting.
The problem now is the picking of item is actually weighted instead of completely evenly random, so my initial assumption is shot. I do not know how weighted it is, all I know is apparently once you get one of the eight items, they're slightly less to appear now. Figures.
Also, there are duplicate covers.
*edit for grammars!*