bonanova Posted May 1, 2014 Report Share Posted May 1, 2014 An urn contains b black balls and w white balls. Balls are removed singly and randomly until all the balls of one color are removed. What is the expected number of balls that remain in the urn? Quote Link to comment Share on other sites More sharing options...
0 m00li Posted May 6, 2014 Report Share Posted May 6, 2014 (I) Lets look at a scenario where all blacks are finished first and only k whites are finished. No. of balls remaining are (w-k). The probability of this happening is b-1+kCk(b*(b-1)*(b-2)..*1*w*(w-1)*(w-2)..(w-(k-1)) / (w+b)*(w+b-1)*...(w-(b+k-1)) = b-1+kCk(b!*k!wCk) / (b+k)!w+bCb+k = (b/(b+k))*(wCk/w+bCb+k) =(1/w+bCb)*(b/(b+k))*(b+kCb) =(1/w+bCb)*b+k-1Cb-1 therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y (II) Alternative (I) could have also be interpreted as: probability that w-k whites remain = (arranging b blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (arranging b-1 blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (b+k-1Cb-1/w+bCb) therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y ... gotta rush.. will continue later continuing... S0->w-1[b+k-1Cb-1(w-k)] = w*S0->w-1(b+k-1Ck) - S0->w-1(b+k-1Ck*k) ...(A) Using nCr + n-1Cr-1 = n+1Cr : w*S0->w-1(b+k-1Cb-1) = w*b+w-1Cw-1 Using S0->ns+kCkk = (s+1)s+n+1Cn-1: S0->w-1(b+k-1Ck*k) = b*b+w-1Cw-2 Hence, (A) = w*b+w-1Cw-1 - b*b+w-1Cw-2 = b+wCw-1 Similarly S0->b-1[w+k-1Cw-1(b-k)] = b*w+b-1Cb-1 - w*w+b-1Cb-2 = b+wCb-1 Therefore, expected number of balls remaining = (b+wCw-1 + b+wCb-1)/b+wCb = w/(b+1) + b/(w+1) Quote Link to comment Share on other sites More sharing options...
0 m00li Posted May 3, 2014 Report Share Posted May 3, 2014 (I) Lets look at a scenario where all blacks are finished first and only k whites are finished. No. of balls remaining are (w-k). The probability of this happening is b-1+kCk(b*(b-1)*(b-2)..*1*w*(w-1)*(w-2)..(w-(k-1)) / (w+b)*(w+b-1)*...(w-(b+k-1)) = b-1+kCk(b!*k!wCk) / (b+k)!w+bCb+k = (b/(b+k))*(wCk/w+bCb+k) =(1/w+bCb)*(b/(b+k))*(b+kCb) =(1/w+bCb)*b+k-1Cb-1 therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y (II) Alternative (I) could have also be interpreted as: probability that w-k whites remain = (arranging b blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (arranging b-1 blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (b+k-1Cb-1/w+bCb) therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y ... gotta rush.. will continue later Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 3, 2014 Author Report Share Posted May 3, 2014 Heroic work. Can you (aha) enumerate the equally likely cases more simply? Quote Link to comment Share on other sites More sharing options...
0 DeGe Posted May 4, 2014 Report Share Posted May 4, 2014 I would say that the expected number of balls left in the urn is 1. The number of balls would tend to get even. For b>w for example, the probability of black being drawn also increases... Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 5, 2014 Author Report Share Posted May 5, 2014 I would say that the expected number of balls left in the urn is 1. The number of balls would tend to get even. For b>w for example, the probability of black being drawn also increases... It's true the numbers tend to equality: p(draw white) = w/(w+b) etc. Think about the case where w, say, is initially 1, and b = 10. If we draw out all the balls, there are only 11 possibilities (balls of the same color are indistinguishable,) and they are equally likely. Average the remaining balls for those cases if you stop when either [1] w is drawn or [2] w is the last one remaining. See if that suggests a general formula. Quote Link to comment Share on other sites More sharing options...
0 plasmid Posted May 5, 2014 Report Share Posted May 5, 2014 Well, the aha! solution that I had in mind didn't work.In case it's helpful to anyone:Black: 1, White: 1, Average: 1 Black: 2, White: 1, Average: 1.3238Black: 2, White: 2, Average: 1.3221 Black: 3, White: 1, Average: 1.7536Black: 3, White: 2, Average: 1.4906Black: 3, White: 3, Average: 1.5094 Black: 4, White: 1, Average: 2.1944Black: 4, White: 2, Average: 1.7316Black: 4, White: 3, Average: 1.6055Black: 4, White: 4, Average: 1.6058 Black: 5, White: 1, Average: 2.67Black: 5, White: 2, Average: 1.9984Black: 5, White: 3, Average: 1.748Black: 5, White: 4, Average: 1.662Black: 5, White: 5, Average: 1.6767 Black: 6, White: 1, Average: 3.1652Black: 6, White: 2, Average: 2.2881Black: 6, White: 3, Average: 1.9363Black: 6, White: 4, Average: 1.7768Black: 6, White: 5, Average: 1.7023Black: 6, White: 6, Average: 1.7127 Black: 7, White: 1, Average: 3.639Black: 7, White: 2, Average: 2.5745Black: 7, White: 3, Average: 2.1375Black: 7, White: 4, Average: 1.8973Black: 7, White: 5, Average: 1.7845Black: 7, White: 6, Average: 1.7537Black: 7, White: 7, Average: 1.7412 Black: 8, White: 1, Average: 4.0732Black: 8, White: 2, Average: 2.8833Black: 8, White: 3, Average: 2.3335Black: 8, White: 4, Average: 2.0171Black: 8, White: 5, Average: 1.8991Black: 8, White: 6, Average: 1.8125Black: 8, White: 7, Average: 1.7912Black: 8, White: 8, Average: 1.7727 Black: 9, White: 1, Average: 4.6142Black: 9, White: 2, Average: 3.1809Black: 9, White: 3, Average: 2.5587Black: 9, White: 4, Average: 2.2349Black: 9, White: 5, Average: 1.9706Black: 9, White: 6, Average: 1.8707Black: 9, White: 7, Average: 1.8247Black: 9, White: 8, Average: 1.8039Black: 9, White: 9, Average: 1.807 Black: 10, White: 1, Average: 5.0788Black: 10, White: 2, Average: 3.5366Black: 10, White: 3, Average: 2.7728Black: 10, White: 4, Average: 2.3568Black: 10, White: 5, Average: 2.1577Black: 10, White: 6, Average: 1.9788Black: 10, White: 7, Average: 1.8612Black: 10, White: 8, Average: 1.8322Black: 10, White: 9, Average: 1.8311Black: 10, White: 10, Average: 1.7937#!/usr/bin/perl use strict; use warnings; my $iterations=10000; for(my $black=1; $black<11; $black++) { for(my $white=1; $white<$black+1; $white++) { my $total=0; for(my $iteration=0; $iteration<$iterations; $iteration++) { my $b = $black; my $w = $white; while($b*$w) { if(rand($b+$w)>$b) { $w--; }else{ $b--; } } $total += $b+$w; } print "Black: $black, White: $white, Average: " . $total/$iterations . "\n"; } print "\n"; } Quote Link to comment Share on other sites More sharing options...
0 k-man Posted May 5, 2014 Report Share Posted May 5, 2014 Let's call the function of expected number of balls remaining as f(w,b). Obviously f(1,1)=1. We can also recursively calculate f(w,b) for any w and b using the recursive formula f(w,b) = ( w * f(w-1,b) + b * f(w,b-1) ) / ( w + b ) I created an excel spreadsheet and populated it with this formula for the range 1-30 for both black and white balls. Here is the nice surface chart that resulted: Here are a couple of observations from the chart and underlying numbers: 1) in extreme cases, where there is initially only 1 black ball and many white balls, the expected number tends to be half of the initial white ball quantity as that quantity grows. For example, for 1 black and 1000 white, the expected number is 500.001 2) in balanced cases where the number of balls is large and balanced (w is close to or equals b), the expected number of balls remaining approaches 2. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 6, 2014 Author Report Share Posted May 6, 2014 (I) Lets look at a scenario where all blacks are finished first and only k whites are finished. No. of balls remaining are (w-k). The probability of this happening isb-1+kCk(b*(b-1)*(b-2)..*1*w*(w-1)*(w-2)..(w-(k-1)) / (w+b)*(w+b-1)*...(w-(b+k-1)) = b-1+kCk(b!*k!wCk) / (b+k)!w+bCb+k = (b/(b+k))*(wCk/w+bCb+k) =(1/w+bCb)*(b/(b+k))*(b+kCb) =(1/w+bCb)*b+k-1Cb-1 therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y (II) Alternative (I) could have also be interpreted as: probability that w-k whites remain = (arranging b blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (arranging b-1 blacks and k whites such that last ball picked is a black)/(arranging b black and w white balls) = (b+k-1Cb-1/w+bCb) therefore, expected number of balls remaining = (1/w+bCb)*(S0->w-1[b+k-1Cb-1(w-k)] + S0->b-1[w+k-1Cw-1(b-k)]) .... where Sx->y denotes sum of series from x to y ... gotta rush.. will continue later continuing... S0->w-1[b+k-1Cb-1(w-k)] = w*S0->w-1(b+k-1Ck) - S0->w-1(b+k-1Ck*k) ...(A) Using nCr + n-1Cr-1 = n+1Cr : w*S0->w-1(b+k-1Cb-1) = w*b+w-1Cw-1Using S0->ns+kCkk = (s+1)s+n+1Cn-1: S0->w-1(b+k-1Ck*k) = b*b+w-1Cw-2 Hence, (A) = w*b+w-1Cw-1 - b*b+w-1Cw-2 = b+wCw-1 Similarly S0->b-1[w+k-1Cw-1(b-k)] = b*w+b-1Cb-1 - w*w+b-1Cb-2 = b+wCb-1 Therefore, expected number of balls remaining = (b+wCw-1 + b+wCb-1)/b+wCb = w/(b+1) + b/(w+1) That's the right formula, and it fits plasmid's simulation numbers and k-man's insights. I'm marking it solved. If the simplicity of the expression suggests a words-only derivation, I'll hold off saying anything more. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 6, 2014 Author Report Share Posted May 6, 2014 Think of the answer as b x 1/(w+1) + w x 1/(b+1). What interpretations can we give to the separate terms? 1/(w+1) looks like (the probability of) one particular outcome out of w+1 equally likely outcomes. b x 1/(w+1) suggests that that probability applies to each of the black balls. w x 1/(b+1) suggests that a similar probability applies to each of the white balls. What are the w+1 outcomes for each black ball and the b+1 outcomes for each white ball? Do these outcomes cover the entire set of possible outcomes? Quote Link to comment Share on other sites More sharing options...
0 bubbled Posted May 12, 2014 Report Share Posted May 12, 2014 (edited) Think of the answer as b x 1/(w+1) + w x 1/(b+1). What interpretations can we give to the separate terms? 1/(w+1) looks like (the probability of) one particular outcome out of w+1 equally likely outcomes. b x 1/(w+1) suggests that that probability applies to each of the black balls. w x 1/(b+1) suggests that a similar probability applies to each of the white balls. What are the w+1 outcomes for each black ball and the b+1 outcomes for each white ball? Do these outcomes cover the entire set of possible outcomes? "aha" still eludes me. I ran a simple Python simulation as well. But I thought I'd share my friend's elegant recursive approach to this problem. The nice thing was he got exact answers, which helps when looking for patterns. def ubw(w,b): if w == 0: return b if b == 0: return w return w/float(w+b)*ubw(w-1,b) + b/float(w+b)*ubw(w,b-1) def main(): for w in range(10): for b in range(10): print 'w= ', w, ' b= ', b, 'Expectation = ', ubw(w+1,b+1) main() Edited May 12, 2014 by bubbled Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 12, 2014 Author Report Share Posted May 12, 2014 Consider the possible drawing sequences when there are originally w white balls and a single black ball. The black ball appears, with equal likelihood, in one of w+1 regions defined by the white balls: Before the first white ball, between the first and second white ball ... just before the last white ball, and after the last white ball. In (just one of) these cases, the last one, there will be a black ball in the urn after balls of only one color remain. The expected number of black balls in the urn when balls of only one color remain is thus 1/(w+1) If there are originally b black balls, this expectation becomes b/(w+1). Symmetrically, the expected number of white balls in the urn when balls of only one color remain is w/(b+1). The total expected ball count is b/(w+1) + w/(b+1). Quote Link to comment Share on other sites More sharing options...
0 bubbled Posted May 14, 2014 Report Share Posted May 14, 2014 Consider the possible drawing sequences when there are originally w white balls and a single black ball. The black ball appears, with equal likelihood, in one of w+1 regions defined by the white balls: Before the first white ball, between the first and second white ball ... just before the last white ball, and after the last white ball. In (just one of) these cases, the last one, there will be a black ball in the urn after balls of only one color remain. The expected number of black balls in the urn when balls of only one color remain is thus 1/(w+1) If there are originally b black balls, this expectation becomes b/(w+1). Symmetrically, the expected number of white balls in the urn when balls of only one color remain is w/(b+1). The total expected ball count is b/(w+1) + w/(b+1). I'm not totally convinced by this argument. I obviously believe it. But don't see the logical argument why the number of black balls left scales linearly with the starting number of black balls, given a fixed number of white balls. For instance. It's obvious that if w = 10 and b = 1, then on average, there will be 1/11 black balls left. But let's look at w = 10 and b = 2. I would use this formula: 1/12 * 1/11 * 2 * 2 + 1/12 * 10/11 * 2 * 1 which does equal the expected result of 2/11. The first term is chances a particular black ball is in last position * chances the other black ball is in second-to-last position * 2 ways for that happen * 2 black balls left. The second term is chances a particular black ball is in last position * chances the second black ball is not in second-to-last position * 2 ways for that to happen * 1 black ball remaining. But the statement "If there are originally b black balls, this expectation becomes b/(w+1)" does not convince me of this fact. Maybe I'm missing a simple identity, but I haven't been "aha'ed" just yet. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 14, 2014 Author Report Share Posted May 14, 2014 What is true of any black ball is true of every black ball. They are indistinguishable. They can't have distinct probabilities. Every black ball has a probability of 1/(w+1) of being in the urn after the last white ball has been drawn. If you like, it's precisely this awareness that constitutes the aha moment. If you want to say this black ball has this probability and that black ball has another probability, you'd have to say why this is so, and you'd have to say how you can tell them apart. Quote Link to comment Share on other sites More sharing options...
0 bubbled Posted May 14, 2014 Report Share Posted May 14, 2014 What is true of any black ball is true of every black ball. They are indistinguishable. They can't have distinct probabilities. Every black ball has a probability of 1/(w+1) of being in the urn after the last white ball has been drawn. If you like, it's precisely this awareness that constitutes the aha moment. If you want to say this black ball has this probability and that black ball has another probability, you'd have to say why this is so, and you'd have to say how you can tell them apart. Aha!! Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 14, 2014 Author Report Share Posted May 14, 2014 Lovely, isn't it? I was going to add ... think of the string of black balls like a stick. And the white balls like cutting the stick in w random locations. Quote Link to comment Share on other sites More sharing options...
0 bubbled Posted May 14, 2014 Report Share Posted May 14, 2014 Lovely, isn't it? I was going to add ... think of the string of black balls like a stick. And the white balls like cutting the stick in w random locations. Indeed. One really interesting aspect of this problem is that by removing the balls, you even out the odds of pulling one color or another as the numbers get big. For example, I ran a simulation 1,000 times where I flipped a fair coin 1,000,000 times and noted abs( H - T ). The average value was 783. But if we put 500,000 black balls and 500,000 white balls in the urn, the average number of balls left after exhausting one color is very close to 2! Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 14, 2014 Author Report Share Posted May 14, 2014 Lovely, isn't it? I was going to add ... think of the string of black balls like a stick. And the white balls like cutting the stick in w random locations. Indeed. One really interesting aspect of this problem is that by removing the balls, you even out the odds of pulling one color or another as the numbers get big. For example, I ran a simulation 1,000 times where I flipped a fair coin 1,000,000 times and noted abs( H - T ). The average value was 783. But if we put 500,000 black balls and 500,000 white balls in the urn, the average number of balls left after exhausting one color is very close to 2! Coin outcomes remain 50-50. Ball outcomes readjust to b/(b+w) and w/(b+w). Quote Link to comment Share on other sites More sharing options...
0 bubbled Posted May 16, 2014 Report Share Posted May 16, 2014 Lovely, isn't it? I was going to add ... think of the string of black balls like a stick. And the white balls like cutting the stick in w random locations. Indeed. One really interesting aspect of this problem is that by removing the balls, you even out the odds of pulling one color or another as the numbers get big. For example, I ran a simulation 1,000 times where I flipped a fair coin 1,000,000 times and noted abs( H - T ). The average value was 783. But if we put 500,000 black balls and 500,000 white balls in the urn, the average number of balls left after exhausting one color is very close to 2! Coin outcomes remain 50-50. Ball outcomes readjust to b/(b+w) and w/(b+w). This puzzle has revealed so many nice symmetries, I thought I'd share another one. If you have b black balls and w white balls in an urn, the expected number of monochromatic balls you will pick out of the urn before you pick a ball of the other color is the same as the expected number of balls remaining after you have exhausted one color. Pretty interesting. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted May 16, 2014 Author Report Share Posted May 16, 2014 The other end of the stick in post 18. Nice. Quote Link to comment Share on other sites More sharing options...
Question
bonanova
An urn contains b black balls and w white balls.
Balls are removed singly and randomly until all the balls of one color are removed.
What is the expected number of balls that remain in the urn?
Link to comment
Share on other sites
19 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.