An urn puzzle

It has been a while again since I last posted a puzzle, so…

You have once again been captured by mathematically-inclined pirates and threatened with walking the plank, unless you can win the following game: some number of black balls and white balls will be placed in an urn. The captain will randomly select and discard a ball from the urn, noting its color, then repeatedly draw and discard additional balls as long as they are the same color. The first drawn ball of a different color will be returned to the urn, and the whole process will be repeated. And repeated, and repeated, until the urn is empty. If the last ball drawn from the urn is black, you must walk the plank; if it is white, you will be set free.

You can choose any positive numbers b and w of black and white balls, respectively, to be placed in the urn at the start. How many of each should you start with to maximize your probability of survival?

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to An urn puzzle

  1. Unless I’ve made a mistake, a simple Monte Carlo simulation suggests it doesn’t matter what you pick for b and w. It’s always a 50% shot (result plot at the bottom):

    So the *real* puzzle is proving why this is the case. Perhaps some inductive proof? When a ball is removed, it’s essentially the same as choosing a smaller b or w, and so any choice of (b, w) can be reduced to (1, 1). While writing up my Monte Carlo simulation, I thought about using dynamic programming, which lead to this idea.

    • Right– actually, the “base cases” are (b,0) yielding probability 0 of survival and (0,w) yielding probability 1, but this is the idea. A search for “urn solitaire” yields a paper or two on the game, in particular the more challenging problem of determining the expected “duration” of the game (i.e., how many rounds of “draw until a different-colored ball”).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.