2
$\begingroup$

Here's my problem written in terms of a marble bag problem:

I have a bag of $90$ marbles and $30$ unique colors. Let's assume each color is represented equally, so there are $3$ of each color marble. I will pick one marble out of the bag at a time and not replace it for $N$ picks. How many picks from the bag do I need in order to have a good probability ($\text~0.8-0.9$ maybe) to have at least $1$ of each color?

In other words, if I have this bag of $90$ marbles with $30$ unique colors, imagine I want to take out marbles one by one and put them in separate boxes, but I have a blindfold on. I want to continue doing this only as long as I have to until I'm confident enough that I've extracted at least $1$ of each different color marble.

I do not have much background in mathematics, and after looking at other probability examples online and trying to answer this myself, I'm very stuck and in over my head. I've tried looking up similar problems, "how to array a pooled library", and got nothing. I believe I know how to calculate this for something small, like $3$ colors and $6$ picks, by determining valid combinations, permutations, and individual probabilities to add all together. But I need to scale it up considerably and don't know how. I have a feeling there's some shortcut or series to use, but I don't know what it is. Can anyone help? Or perhaps point me in the right direction?

$\endgroup$
8
  • $\begingroup$ A quick simulation suggests that for this particular problem, we get to $80$ percent at about $72$ marbles, and $90$ percent at about $76$ marbles. I don't immediately see a way to an analytic solution; it's not coupon-collector because of the non-replacement. $\endgroup$
    – Brian Tung
    Sep 20, 2022 at 2:43
  • $\begingroup$ There are some questions in this site on a similar problem involving pairs of socks of different colors and random blind selection. They are not exactly your problem but can give you interesting ideas that might help you. Search for "socks". $\endgroup$
    – bluemaster
    Sep 20, 2022 at 2:46
  • $\begingroup$ Before attacking the problem, I advise you to do the preliminary research of exploring a similar problem. See the Coupon Collector's Problem. It is somewhat different from the problem that you posed, but it has similar considerations. $\endgroup$
    – user2661923
    Sep 20, 2022 at 3:03
  • $\begingroup$ If you have not had any pertinent Mathematical training (i.e. no education in Probability Theory or in Statistics), then I advise not trying to attack this problem. It would be like learning to swim by jumping into the middle of the ocean, rather than starting out in the shallow end of a pool. The graceful approach is to find the right Probability textbook(s) for you, open the book(s), one at a time, to page 1, and attacking. Since most of such learning is done by solving the book's exercises, you want each book to provide many exercises for you to solve (AKA struggle with). $\endgroup$
    – user2661923
    Sep 20, 2022 at 3:12
  • 1
    $\begingroup$ It might help if we knew where this problem was coming from. $\endgroup$
    – Brian Tung
    Sep 20, 2022 at 3:22

2 Answers 2

Reset to default
5
$\begingroup$

Using the principle of inclusion exclusion, the probability that your sample contains every color is $$ \frac{1}{\binom{90}N}\sum_{k=0}^{30}(-1)^{k}\binom{30}k\binom{90-3k}{N} $$ The smallest $N$ for which this exceeds $0.8$ is $72$, and the smallest $N$ for which this exceeds $0.9$ is $76$.

$\endgroup$
6
  • $\begingroup$ I must have misunderstood the problem (or possibly your answer). The minimum possible $N$ for even a non-zero probability of success should be $30$, shouldn't it? (One marble for each color.) It doesn't seem possible that merely four more marbles raises the probability to $0.8$. (It also doesn't jibe with my simulations.) $\endgroup$
    – Brian Tung
    Sep 21, 2022 at 5:28
  • 1
    $\begingroup$ I think you are missing a factor of $\binom{30}{k}$ in your summation (which has an effect on your numerical results). $\endgroup$
    – awkward
    Sep 21, 2022 at 12:38
  • $\begingroup$ @awkward Thank you for your help :) $\endgroup$
    – Mike Earnest
    Sep 21, 2022 at 13:25
  • $\begingroup$ Oh wow thank you! As far as my wanting to scale this up... do you know if this would be able to support this problem if I had something on the order of a million or even billion marbles? Or infinity? $\endgroup$
    – rcpi
    Sep 22, 2022 at 3:02
  • $\begingroup$ @rcpi If you have a second question, you should make a separate post. If you tag it combinatorics, I will see it, and probably answer. $\endgroup$
    – Mike Earnest
    Sep 22, 2022 at 17:02
0
$\begingroup$

I am unsure about the $80\%-90\%$ confidence part(since I do not know how to measure confidence exactly). However, I know how to be absolutely sure that you have drawn at least one marble of each color.

Consider the worst-case scenario: you draw a marble, then draw a marble of the same color, then draw a marble of the same color again. Now that color has been completely exhausted. Suppose this happens for every color you pick, for $29$ colors. You have currently drawn $87$ marbles, and have $29$ unique colors. Then, the only remaining marbles are of the same color, and all you have to do is draw one more to get all $30$ colors, for a total of $88$ marbles.

You may also be interested in the Pigeonhole Principle if you have not already discovered it. As simple as it seems, it can be used to solve Olympiad-level problems.

$\endgroup$
2
  • $\begingroup$ Hm I see what you're saying. What if I don't want to exhaustively pick marbles, or what if the marbles weren't all present in equal proportions? Does that change the Pigeonhole-ness? As for the "confidence", I was using that word to mean that the probability of my event (getting at least 1 of each color) occurring is between 0.8 and 0.9. I could be wrong here, but I was reading those probabilities as being "80 to 90% confident". Is there a way to ask how many marbles I need to pick in order for the probability my event occurs to be within a desired range? $\endgroup$
    – rcpi
    Sep 20, 2022 at 1:45
  • $\begingroup$ I'm not sure there is any other way to be $100\%$ sure. If they were not in equal proportions, then the answer would be $90$ - (the color with the smallest number of marbles) see if you can figure out why. I do not think this will take away from the "Pigeonhole-ness". Hmm... I will think about the confidence stuff then. $\endgroup$
    – bobeyt6
    Sep 20, 2022 at 1:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .