The "aha!" problems 7. Urning the balls

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

[m00li]

(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+kC_k(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+kC_k(b!*k!^wC_k) / (b+k)!^w+bC_b+k

= (b/(b+k))*(^wC_k/^w+bC_b+k)

=(1/^w+bC_b)*(b/(b+k))*(^b+kC_b)

=(1/^w+bC_b)*^b+k-1C_b-1

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->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-1C_b-1/^w+bC_b)

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->y denotes sum of series from x to y

... gotta rush.. will continue later

[bonanova]

Heroic work.

Can you (aha) enumerate the equally likely cases more simply?

[DeGe]

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...

[bonanova]

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.

[plasmid]

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.3238

Black: 2, White: 2, Average: 1.3221

Black: 3, White: 1, Average: 1.7536

Black: 3, White: 2, Average: 1.4906

Black: 3, White: 3, Average: 1.5094

Black: 4, White: 1, Average: 2.1944

Black: 4, White: 2, Average: 1.7316

Black: 4, White: 3, Average: 1.6055

Black: 4, White: 4, Average: 1.6058

Black: 5, White: 1, Average: 2.67

Black: 5, White: 2, Average: 1.9984

Black: 5, White: 3, Average: 1.748

Black: 5, White: 4, Average: 1.662

Black: 5, White: 5, Average: 1.6767

Black: 6, White: 1, Average: 3.1652

Black: 6, White: 2, Average: 2.2881

Black: 6, White: 3, Average: 1.9363

Black: 6, White: 4, Average: 1.7768

Black: 6, White: 5, Average: 1.7023

Black: 6, White: 6, Average: 1.7127

Black: 7, White: 1, Average: 3.639

Black: 7, White: 2, Average: 2.5745

Black: 7, White: 3, Average: 2.1375

Black: 7, White: 4, Average: 1.8973

Black: 7, White: 5, Average: 1.7845

Black: 7, White: 6, Average: 1.7537

Black: 7, White: 7, Average: 1.7412

Black: 8, White: 1, Average: 4.0732

Black: 8, White: 2, Average: 2.8833

Black: 8, White: 3, Average: 2.3335

Black: 8, White: 4, Average: 2.0171

Black: 8, White: 5, Average: 1.8991

Black: 8, White: 6, Average: 1.8125

Black: 8, White: 7, Average: 1.7912

Black: 8, White: 8, Average: 1.7727

Black: 9, White: 1, Average: 4.6142

Black: 9, White: 2, Average: 3.1809

Black: 9, White: 3, Average: 2.5587

Black: 9, White: 4, Average: 2.2349

Black: 9, White: 5, Average: 1.9706

Black: 9, White: 6, Average: 1.8707

Black: 9, White: 7, Average: 1.8247

Black: 9, White: 8, Average: 1.8039

Black: 9, White: 9, Average: 1.807

Black: 10, White: 1, Average: 5.0788

Black: 10, White: 2, Average: 3.5366

Black: 10, White: 3, Average: 2.7728

Black: 10, White: 4, Average: 2.3568

Black: 10, White: 5, Average: 2.1577

Black: 10, White: 6, Average: 1.9788

Black: 10, White: 7, Average: 1.8612

Black: 10, White: 8, Average: 1.8322

Black: 10, White: 9, Average: 1.8311

Black: 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";
}

[k-man]

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.

[m00li]

(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+kC_k(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+kC_k(b!*k!^wC_k) / (b+k)!^w+bC_b+k

= (b/(b+k))*(^wC_k/^w+bC_b+k)

=(1/^w+bC_b)*(b/(b+k))*(^b+kC_b)

=(1/^w+bC_b)*^b+k-1C_b-1

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->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-1C_b-1/^w+bC_b)

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->y denotes sum of series from x to y

... gotta rush.. will continue later

continuing...

S_0->w-1[^b+k-1C_b-1(w-k)] = w*S_0->w-1(^b+k-1C_k) - S_0->w-1(^b+k-1C_k*k) ...(A)

Using nCr + n-1Cr-1 = n+1Cr : w*S0->w-1(b+k-1Cb-1) = w*b+w-1Cw-1

_Using S_0->n^s+kC_kk = (s+1)^s+n+1C_n-1: S_0->w-1(^b+k-1C_k*k) = b*^b+w-1C_w-2

Hence, (A) = w*^b+w-1C_{w-1 -} b*^b+w-1C_w-2 = ^b+wC_w-1

Similarly S_0->b-1[^w+k-1C_w-1(b-k)] = b*^w+b-1C_{b-1 - w}*^w+b-1C_b-2 = ^b+wC_b-1

_{Therefore, expected number of balls remaining =} (^b+wC_w-1 + ^b+wC_b-1)/^b+wC_b = w/(b+1) + b/(w+1)

[bonanova]

(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+kC_k(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+kC_k(b!*k!^wC_k) / (b+k)!^w+bC_b+k

= (b/(b+k))*(^wC_k/^w+bC_b+k)

=(1/^w+bC_b)*(b/(b+k))*(^b+kC_b)

=(1/^w+bC_b)*^b+k-1C_b-1

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->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-1C_b-1/^w+bC_b)

therefore, expected number of balls remaining = (1/^w+bC_b)*(S_0->w-1[^b+k-1C_b-1(w-k)] + S_0->b-1[^w+k-1C_w-1(b-k)]) .... where S_x->y denotes sum of series from x to y

... gotta rush.. will continue later

continuing...

S_0->w-1[^b+k-1C_b-1(w-k)] = w*S_0->w-1(^b+k-1C_k) - S_0->w-1(^b+k-1C_k*k) ...(A)

Using nCr + n-1Cr-1 = n+1Cr : w*S0->w-1(b+k-1Cb-1) = w*b+w-1Cw-1

_Using S_0->n^s+kC_kk = (s+1)^s+n+1C_n-1: S_0->w-1(^b+k-1C_k*k) = b*^b+w-1C_w-2

Hence, (A) = w*^b+w-1C_{w-1 -} b*^b+w-1C_w-2 = ^b+wC_w-1

Similarly S_0->b-1[^w+k-1C_w-1(b-k)] = b*^w+b-1C_{b-1 - w}*^w+b-1C_b-2 = ^b+wC_b-1

_{Therefore, expected number of balls remaining =} (^b+wC_w-1 + ^b+wC_b-1)/^b+wC_b = 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.

[bonanova]

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?

[bubbled]

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

[bonanova]

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).

[bubbled]

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.

[bonanova]

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.

[bubbled]

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!!

[bonanova]

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.

[bubbled]

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!

[bonanova]

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).

[bubbled]

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.

[bonanova]

The other end of the stick in post 18.

Nice.