2 thoughts on “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):

   
   

   	/* An urn puzzle
   	* https://possiblywrong.wordpress.com/2018/07/04/an-urn-puzzle/
   	*
   	* $ cc -O3 -fopenmp urn.c
   	*
   	* 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?
   	*/
   	#include <stdio.h>
   	#include <stdint.h>
   	#define N 100000
   	#define Z 100
   	static uint64_t
   	xoroshiro128plus(uint64_t s[2])
   	{
   	uint64_t s0 = s[0];
   	uint64_t s1 = s[1];
   	uint64_t result = s0 + s1;
   	s1 ^= s0;
   	s[0] = ((s0 << 24) | (s0 >> 40)) ^ s1 ^ (s1 << 16);
   	s[1] = (s1 << 37) | (s1 >> 27);
   	return result;
   	}
   	static uint64_t
   	hash64shift(uint64_t x)
   	{
   	x = (~x) + (x << 21);
   	x = x ^ (x >> 24);
   	x = (x + (x << 3)) + (x << 8);
   	x = x ^ (x >> 14);
   	x = (x + (x << 2)) + (x << 4);
   	x = x ^ (x >> 28);
   	x = x + (x << 31);
   	return x;
   	}
   	int
   	main(void)
   	{
   	double results[Z][Z];
   	#pragma omp parallel for schedule(dynamic)
   	for (int n = 0; n < Z * Z; n++) {
   	int b = n / Z + 1;
   	int w = n % Z + 1;
   	uint64_t s[2] = {
   	0x1fc0cb841750ba4b ^ hash64shift(b),
   	0x73f8ed6cb30e77b3 ^ hash64shift(w)
   	};
   	int death = 0;
   	for (int i = 0; i < N; i++) {
   	int color = -1;
   	int urn[2] = {b, w};
   	do {
   	int sum = urn[0] + urn[1];
   	int rand = xoroshiro128plus(s) % sum;
   	int select = rand >= urn[0];
   	if (color == -1) {
   	color = select;
   	urn[select]–;
   	} else if (color == select) {
   	urn[select]–;
   	} else {
   	color = -1;
   	}
   	} while (urn[0] || urn[1]);
   	death += color == 0;
   	}
   	results[b – 1][w – 1] = death / (double)N;
   	fprintf(stderr, "done %d / %d\n", n + 1, Z * Z);
   	}
   	for (int b = 1; b <= Z; b++)
   	for (int w = 1; w <= Z; w++)
   	printf("%.17g%c", results[b – 1][w – 1], w == Z ? '\n' : ' ');
   	}

   view raw
   
   urn.c
   
   hosted with ❤ by GitHub

   

   view raw
   
   urn.png
   
   hosted with ❤ by GitHub

   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.

   Reply ↓

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

     Reply ↓

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