The Urn of Destiny Part 1

Not without a shudder may the human hand reach into the mysterious urn of destiny.
Friedrich Schiller
Here’s the situation:
An urn is filled with 75 white beans and 150 black ones. Next to the urn is a large pile of black beans. The beans are removed from the urn according to certain rules.
Remove two beans from the urn at random.
If at least one of the beans is black, place it on the pile and drop the other bean, whether white or black, back into the urn.
But if both of the removed beans are white, discard both of them and take one black bean from the pile and drop it into the urn.
(From Dewdney, A. K. (1993). The Tinkertoy computer and other machinations. New York: W.H. Freeman.)
If you read the rules carefully, you’ll notice that the urn loses one bean for each turn. Eventually you will reach the point where you only have one bean left. The question is, what color is that bean?
Since I don’t have an urn handy and the only beans I have are canned, I’m going to see if I can simulate this problem using my computer and find out the color of the last bean. Just like last time, I’ll sketch out the problem using pseudo code to get it into a form that my stupid computer can understand. (Note that although computers are not smart, it turns out that being stupid really, really quickly simulates smartness.)
First we set up our urn.
Bean_wht=75
Bean_blk=150

Now the next bit may seem a little strange for those of you who don’t program computers. However, it turns out that programmers have to dumb down the problem in order to get the computer to understand it, so the code can get a little..metaphorical. Programmers put a lot of time and effort to pick the right metaphor for a particular problem.
(As a side note, computers don’t really do randomness but they can fake it. The explanation is a bit obscure but suffice it to say that if computers were truly random devices then we couldn’t get any real work done on them.)
# Pick two beans at random
Let bean1 = random(black,white)
If (bean1 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# (The bean has to be either black or white, right?)
Let bean2 = random(black,white)
If (bean2 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# if bean1 is black, put bean2 back in the urn. If bean2 is black, put bean1 back.
If (bean1 = bean2)
then increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>
if (bean1=black)
then increment Bean_wht by one
else increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>

# In short, if bean1 and bean2 are both the same color, add a black bean to the urn.
# If we have one bean left, stop picking beans and report the color of the last bean.
if (URN=1)
then if (Bean_wht)
print “the last bean is white”
else print “the last bean is black”
Okay, let me take a few moments to plug this in (or something like it) and see what I get. The metaphor (or paradigm) I’m using is “There is NO urn”. I just count beans. Yes, I’m literally a bean-counter. Anyway, this is what I’ve got:

#!/bin/bash

# Beans.sh - a script to simulate the Grecian Urn problem from A.K. Dewdney's 'The 
# Tinkertoy Computer"

# An urn has 150 black beans and 75 white beans. You pick two beans at random and then
# follow these rules:

# If at least one of the beans is black, place it on the pile and drop the other bean, 
# whether white or black, back into the urn.

# But if both of the removed beans are white, discard both of them and 
# take one black bean from the pile and drop it into the urn.

# Setup

export BEAN_BLK=150
export BEAN_WHT=75
URN=$((BEAN_BLK+BEAN_WHT)) # Total number of beans in the URN

# Let's out-source our bean picking to its own chunk of code
# This is actually a bit subtle, as my initial assumption is 
# that I'm equally likely to pick a black bean as a white bean
# But we know that's not true, don't we, boys and girls?

pick_bean ()
{
	# First, check to see if we've run out of white or black beans
	if [ $BEAN_BLK -eq 0 ] # no black beans left
	then 
	{
		echo "white"
		return
	}
	fi

	if [ $BEAN_WHT -eq 0 ] # no white beans left
	then 
	{
		echo "black"
		return
	}
	fi

	RANGE=`expr $BEAN_BLK + $BEAN_WHT`
	number=$RANDOM

	let "number %= $RANGE" # pick a number from 0 to the number of beans

	if [ "$number" -lt $BEAN_WHT ]
	then
		{
		echo "white"
		}
	else
		{
		echo "black"
		}
	fi

}

#Another function to tell me how many beans I have left.
beans_remaining ()
{
echo Black beans left: $BEAN_BLK
echo White beans left: $BEAN_WHT
}

# Setup our beans
BEAN1=
BEAN2=

while [ `expr $BEAN_BLK + $BEAN_WHT` -gt 1 ]
do
{
	BEAN1=`pick_bean`
	BEAN2=`pick_bean`

	if [ "$BEAN1" == white ]
	then let "BEAN_WHT -= 1" # decrement white beans
	else let "BEAN_BLK -= 1" # decrement black beans
	fi

	if [ "$BEAN2" == white ]
		then let "BEAN_WHT -= 1"
		else let "BEAN_BLK -= 1"
	fi

	if [ "$BEAN1" == "$BEAN2" ]
		then 
		{
			let "BEAN_BLK += 1"
			continue
		}
	fi

	if [ "$BEAN1" = black ]
	then
		{
		let "BEAN_WHT += 1"
		continue
		}
	fi

	if [ "$BEAN1" = white ]
	then
		{
		let "BEAN_WHT += 1"
		continue
		}
	fi

#URN=$((BEAN_BLK+BEAN_WHT))

}
done # End of while loop

beans_remaining

When I run it, here’s my output:

isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1

I ran it several times and it looks like the last bean left is in fact white, just as Dewdney claims. Of course, the plural of anecdote is NOT data. If I ran it an infinite number of times, would it always come out the same?

For part 2 of this post, I’d like to see if I can explain why this is and prove, if possible, that it will always work out with one white bean left. If any of you have an answer or even just speculation, feel free to post it in the comments. For you advanced types, can you tell me if it makes a difference starting with equal amounts of white and black beans?

Advertisements

One thought on “The Urn of Destiny Part 1

  1. Pingback: The Urn of Destiny Part 2 | We Hate Math

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s