[math-fun] Siimple probability problem
It is now clear that I've lost essentially all of my math skills... sigh. My wife asked what seemed to me to be a simple problem but I couldn't see a way to approach it... I kept going down what felt like blind alleys that just got more complicated rather than leading toward a solution: You have a jar with N *each* of C colors of marbles [that is, you start with the same number of each color, N*C marbles in the jar]. You start removing marbles [without replacement]. What is the expected number of marbles you have to remove to have a 50% chance of having at least one of each color. Is there some easy/obvious way to approach/analyze this? THANKS! /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
If N > 0, you already have at least one of each color. How many do you have to remove before that is no longer true? But seriously, I'm guessing the question you're actually asking is what is the probability p(k) of selecting one of each color when selecting k marbles without replacement, and then, when is p(k) first >= .5? --ms On 2014-06-30 15:50, Bernie Cosell wrote:
It is now clear that I've lost essentially all of my math skills... sigh. My wife asked what seemed to me to be a simple problem but I couldn't see a way to approach it... I kept going down what felt like blind alleys that just got more complicated rather than leading toward a solution:
You have a jar with N *each* of C colors of marbles [that is, you start with the same number of each color, N*C marbles in the jar]. You start removing marbles [without replacement]. What is the expected number of marbles you have to remove to have a 50% chance of having at least one of each color.
Is there some easy/obvious way to approach/analyze this? THANKS!
/Bernie\
Given a jar holding N marbles of each of C colors: -------------------------------------------------- I'm guessing the intended problem is either ----- I) Let f(r) be the probability that, after r marbles are removed one by one at random, there remain at least one marble of each color. Let r(1/2) be the unique real solution to the equation (*) f(r) = 1/2 . (Even though r is originally defined as an integer, f(r) will be a function of what may be thought of as a real variable r, decreasing (for r >= N) strictly monotonically to 0 as r -> oo, so (*) will have a non-integer solution.) Then R(1/2) is the sought-after number. ----- --or-- ----- II) Remove marbles one by one until the jar first fails to contain at least one marble of each color. Let the random variable X be that number. (Or if you prefer, that number minus 1.) What is E(X) ? ----- . The two questions are unlikely to have the same answer. --Dan On Jun 30, 2014, at 1:20 PM, Mike Speciner <ms@alum.mit.edu> wrote:
If N > 0, you already have at least one of each color. How many do you have to remove before that is no longer true?
But seriously,
I'm guessing the question you're actually asking is what is the probability p(k) of selecting one of each color when selecting k marbles without replacement, and then, when is p(k) first >= .5?
--ms
On 2014-06-30 15:50, Bernie Cosell wrote:
It is now clear that I've lost essentially all of my math skills... sigh. My wife asked what seemed to me to be a simple problem but I couldn't see a way to approach it... I kept going down what felt like blind alleys that just got more complicated rather than leading toward a solution:
You have a jar with N *each* of C colors of marbles [that is, you start with the same number of each color, N*C marbles in the jar]. You start removing marbles [without replacement]. What is the expected number of marbles you have to remove to have a 50% chance of having at least one of each color.
Is there some easy/obvious way to approach/analyze this? THANKS!
/Bernie\
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 30 Jun 2014 at 16:09, Dan Asimov wrote:
Given a jar holding N marbles of each of C colors: --------------------------------------------------
I'm guessing the intended problem is either
----- I) Let f(r) be the probability that, after r marbles are removed one by one at random, there remain at least one marble of each color.
II) Remove marbles one by one until the jar first fails to contain at least one marble of each color. Let the random variable X be that number. (Or if you prefer, that number minus 1.) What is E(X) ? -----
Alas, I didn't realize I had proposed something so ambiguous. You are picking marbles and the question my wife was curious about was how many you would have to pick to have a p=.5 chance that _YOU_ hold at least one of each color. I figured that you probably need to calculate P(n) = probability that your handful of marbles includes at least one of each color after you've taking n marbles. And then solve for P(n) ~ .5 /B\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
On 30/06/2014 20:50, Bernie Cosell wrote:
You have a jar with N *each* of C colors of marbles [that is, you start with the same number of each color, N*C marbles in the jar]. You start removing marbles [without replacement]. What is the expected number of marbles you have to remove to have a 50% chance of having at least one of each color.
Inclusion-exclusion: Pr(at least one of each colour) = 1 - sum{i} Pr(none of colour i) + sum{i,j} Pr(none of colour i,j) - sum{i,j,k} Pr(none of colour i,j,k) + ... = sum (-1)^r (C choose r) ((C-r)N choose M) / (CN choose M) if M is the number of marbles you take. This doesn't seem like the sort of thing that would have an obvious closed form but I'm not an expert on such sums. -- g
participants (4)
-
Bernie Cosell -
Dan Asimov -
Gareth McCaughan -
Mike Speciner