As was foretold, we've added advertisements to the forums! If you have questions, or if you encounter any bugs, please visit this thread: https://forums.penny-arcade.com/discussion/240191/forum-advertisement-faq-and-reports-thread/
Options

Math question!

WearingglassesWearingglasses 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?

Posts

  • Options
    MalyonsusMalyonsus Registered User regular
    edited January 2013
    Sounds like the coupon collector's problem, typically formulated as someone trying to collect n stamps, where each time he gets a stamp, it is randomly selected from the set of all stamps with uniform probability. As he gets more stamps, the likelihood of him getting a stamp he already has increases.

    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.

    Malyonsus on
  • Options
    SmasherSmasher Starting to get dizzy Registered User regular
    edited January 2013
    Some quick simulation says the answer is 33 boxes for 90%.

    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.

    Smasher on
  • Options
    MrTLiciousMrTLicious Registered User regular
    Probably not a way to easily invert this, but you can calculate the probability for a given number of boxes, so to get the threshold, you can just calculate this for a bunch of numbers of boxes and find where it crosses:


    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.

  • Options
    WearingglassesWearingglasses Of the friendly neighborhood variety Registered User regular
    Sorry I couldn't reply immediately. Thanks guys! I was also about to brute force it, but Smasher did that for me, heh. Good to know it has a name too, I know what to search for next time.

    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.

  • Options
    PantshandshakePantshandshake Registered User regular
    edited January 2013
    Well, in the Collection screen where you open your magnetic boxes to get comic covers to unlock Magneto as a usable character (I *might* play Avenger's Alliance too...) it tells you that you have a 7% chance of getting a comic by opening 1 box, and a 100% chance of getting a comic by opening 10 boxes at once. Which will certainly influence the math that I have no idea how to do.

    Also, there are duplicate covers.

    *edit for grammars!*

    Pantshandshake on
  • Options
    MrTLiciousMrTLicious Registered User regular
    It's still possible to get the probability without simulations (would require some nasty summations), but you would need to know how the drop rates change.

Sign In or Register to comment.