Math Puzzle Solution: Pulling Balls Out of an Urn

April 9th, 2005 | Categories: Math Puzzles - Solutions

This is a solution to this puzzle.

The answer is yes, you should definitely play the game. The initial instinct is to reason that, since you have more black balls than white balls you’ll always end up losing. However, the main insight is that in the event you start losing, you can always just take out all of the balls and end up with 4 blacks and 3 whites, meaning a loss of 1$ at most; 1$ is a lower bound on your possible losses.

The particular strategy adopted depends on the number of black and white balls present; one needs to draw a game tree and map out all the options before finally computing the expectation value. Some leaves can be pruned; for example, if you’ve drawn 3 white balls, that would be a good place to stop - the remaining balls in the urn are black and will only cause you to lose money. Since the complete game tree for the 4-3 case is quite complicated to draw, I’ve prepared a tree for the case of 3 black balls and 2 white balls:

urngametreeThe black numbers indicate probabilities. The red numbers indicate earnings from a particular state (for example, from the state black-black-black you’d continue on drawing 2 white balls and end up with a total loss of 1$). Although it isn’t obvious a-priori, those actions inside the blue boxes are not beneficial and should be avoided; you should be able to convince yourselves of that by simply computing their expectations (they’re 0, and correspond to the case with 2 black balls and 1 white ball, which shouldn’t be played).

A quick computation of the expectation will yield an average of 0.2$ per game.

The actual computation of the expected earnings can be made using a recursive function: let E(m,n) be the earnings in the case you have m white balls and n black balls. Then:

E(m,n) = max(0, n/(m+n) * (1 + E(m-1, n)) + m/(m+n) * (-1 + E(m,n-1)))

That is, we need to compute the earnings whether we choose a white or a black ball, and weight them by the corresponding probabilities; note the use of the maximum - we can always choose not to play, and hence not to lose anything (in the mean).  The boundary conditions for this recursive equation are E(m,0) = m and E(0,n) = 0. Here is some MATLAB code that computes it:

function estimatedWinnings = BetValue(numWhites, numBlacks)
if numWhites == 0
    estimatedWinnings = 0;
    return
end
if numBlacks == 0
    estimatedWinnings = numWhites;
    return
end
totalBalls = numWhites + numBlacks;
probDrawWhite = numWhites/totalBalls;
probDrawBlack = numBlacks/totalBalls;
earningsIfDrawWhite = 1+BetValue(numWhites-1, numBlacks);
earningsIfDrawBlack = -1+BetValue(numWhites, numBlacks-1);
estimatedWinnings = max(0,probDrawWhite*earningsIfDrawWhite + probDrawBlack*earningsIfDrawBlack);

I’ve compiled a table of E(m,n) for m and n ranging from 0 to 7:

urntable

In our particular problem (3 whites, 4 blacks), the expected earnings are 0.34$ per game; however, this table does not reveal the strategy needed - I’ll leave that as a straightforward extension of the (2 whites, 3 blacks) case explored above.

  • Share/Save/Bookmark
No comments yet.