Thursday, August 30, 2007

Statistics and the Game Show

I was thinking about Hoy's post about human intuition and statistics. Since my intuition rejected Hoy's answer as correct (even though I've heard about the problem before), I thought I'd do a little simulation to see what happens.

My first instinct was to run a bunch of trials, and do enough of them to get a statistically significant result. But then I realized the problem-space was small enough to do a full enumeration of the space. Basically, there are three variables, the box the prize is in (p), the box I pick (i), and the box wink picks (w). I will invalidate any point in the problem space that violates the assumptions (Wink won't pick my box to show me, and he won't pick the box the prize is in).

Here's the abbreviated code*:

for p in prize:
for i in i_pick:
for w in wink_picks:
evaluate(p,i,w,True)
Here are the results:

box the prize is in, box I picked, box wink showed
1 1 1 invalid: wink picked my box.
1 1 2 I win!
1 1 3 I win!
1 2 1 invalid: wink picked the winner.
1 2 2 invalid: wink picked my box.
1 2 3 I lose.
1 3 1 invalid: wink picked the winner.
1 3 2 I lose.
1 3 3 invalid: wink picked my box.
2 1 1 invalid: wink picked my box.
2 1 2 invalid: wink picked the winner.
2 1 3 I lose.
2 2 1 I win!
2 2 2 invalid: wink picked my box.
2 2 3 I win!
2 3 1 I lose.
2 3 2 invalid: wink picked the winner.
2 3 3 invalid: wink picked my box.
3 1 1 invalid: wink picked my box.
3 1 2 I lose.
3 1 3 invalid: wink picked the winner.
3 2 1 I lose.
3 2 2 invalid: wink picked my box.
3 2 3 invalid: wink picked the winner.
3 3 1 I win!
3 3 2 I win!
3 3 3 invalid: wink picked my box.
6 wins. 6 losses.
15 invalid. 12 valid. 27 total.
winning percentage: 0.5
losing percentage: 0.5
Huh. So the simulation agrees with our intuition that there's a 50/50 chance the prize is in either our box or the one that's left. Since Marilyn Vos Savant is sure the remaining box has a 2/3 chance of being the winner, maybe this is why she says folks programming the problem "fared a little less well."

So, I tried coding it per my original idea. Simulating the choice a number of times, and seeing what average happens. The code:

while total_trials < number_of_trials:
choices = list([1,2,3])
p = random.choice(choices)
i = random.choice(choices)
choices.remove(i) # make sure wink doesn't pick my box
if p in choices:
choices.remove(p) # make sure wink doesn't pick the box with the prize
w = random.choice(choices)
evaluate(p,i,w)
And the results:

by method 2, 1000 trials:
337 wins. 663 losses.
0 invalid. 1000 valid. 1000 total.
winning percentage: 0.337
losing percentage: 0.663
Even before running the simulation above, it became obvious to me that the answer was going to be 1/3 wins for keeping the same box. In the code, none of the manipulations involving the other boxes ever changed anything relating to the original box.

So, the question is, why does the full enumeration of the problem-space give us the wrong answer?
Let's look at the problem space again, removing the invalid trials:

box the prize is in, box I picked, box wink showed
1 1 2 I win!
1 1 3 I win!
1 2 3 I lose.
1 3 2 I lose.
2 1 3 I lose.
2 2 1 I win!
2 2 3 I win!
2 3 1 I lose.
3 1 2 I lose.
3 2 1 I lose.
3 3 1 I win!
3 3 2 I win!
I've colored the wins to show how they pair up. This is an artifact of there being 2 non-winning boxes for Wink to pick when I've picked the winning box. Since he'll only ever pick one of them, we can collapse these into just 3 winning trials versus the 6 losing trials, giving us the correct 1/3 chance of winning with "our" box.

It turns out the flaw with this method is thinking of it as a problem in 3-dimensional space. It turns out that Wink's choice is completely (or at least mostly) dependent on the combination of where the prize is, and which box we choose. So we change the code to:

def winks_choice(p,i):
choices = list([1,2,3])
choices.remove(i) # make sure wink doesn't pick my box
if p in choices:
choices.remove(p) # make sure wink doesn't pick the box with the prize
return random.choice(choices)

for p in prize:
for i in i_pick:
w = winks_choice(p,i)
evaluate(p,i,w,True)
Giving us the correct result:

box the prize is in, box I picked, box wink showed
1 1 2 I win!
1 2 3 I lose.
1 3 2 I lose.
2 1 3 I lose.
2 2 3 I win!
2 3 1 I lose.
3 1 2 I lose.
3 2 1 I lose.
3 3 2 I win!
3 wins. 6 losses.
0 invalid. 9 valid. 9 total.
winning percentage: 0.333333333333
losing percentage: 0.666666666667


Okay, okay, I believe you now. ;-)


* Here's the full code, if you want to mess with it. (After creating "winks_choice", I refactored method 2 to use it.) Save it to "wink.py", and then type "python wink.py" on almost any mac or unix box.


import random

#
# routines
#

def clear_counters():
global i_win , i_lose , total_valid , total_invalid , total_trials
i_win = 0
i_lose = 0
total_valid = 0
total_invalid = 0
total_trials = 0

def evaluate(p,i,w,print_it=False):
global i_win , i_lose , total_valid , total_invalid , total_trials
if print_it:
print p,i,w,
if w == i:
if print_it:
print "invalid: wink picked my box."
total_invalid += 1
total_trials += 1
return
if w == p:
if print_it:
print "invalid: wink picked the winner."
total_invalid += 1
total_trials += 1
return
if p == i:
if print_it:
print "I win!"
i_win += 1
else:
if print_it:
print "I lose."
i_lose += 1
total_valid += 1
total_trials += 1

def print_results():
print i_win, "wins.", i_lose, "losses."
print total_invalid, "invalid.", total_valid, "valid.", total_trials, "total."
print "winning percentage:", float(i_win) / total_valid
print "losing percentage:", float(i_lose) / total_valid

def winks_choice(p,i):
choices = list([1,2,3])
choices.remove(i)
if p in choices:
choices.remove(p)
return random.choice(choices)

#
# method 1: iteration over the full problem space
#

clear_counters()

prize = [1,2,3]
i_pick = [1,2,3]
wink_picks = [1,2,3]

print "box the prize is in, box I picked, box wink showed"
for p in prize:
for i in i_pick:
for w in wink_picks:
evaluate(p,i,w,True)

print_results()

#
# method 2: tabulate independent trials
#

number_of_trials = 1000
print "by method 2,", number_of_trials, "trials:"

clear_counters()

while total_trials < number_of_trials:
choices = list([1,2,3])
p = random.choice(choices)
i = random.choice(choices)
w = winks_choice(p,i)

evaluate(p,i,w)

print_results()

#
# method 3: iteration over the problem space in *2* dimensions!
#

clear_counters()

print "Method 3. 2-dimensional problem-space."
print "box the prize is in, box I picked, box wink showed"
for p in prize:
for i in i_pick:
w = winks_choice(p,i)
evaluate(p,i,w,True)

print_results()

2 comments:

Schaubs said...

That's pretty cool!

Nice work, you da man.

Hammer Player a.k.a Hoyazo said...

Well done, Jobo. Not sure how you could possibly do this just sitting around on a Thursday, but it's a good effort and hopefully will help some people understand an admittedly very hard concept.

Thanks!
Hoy