Sunday, February 12, 2006

Lets Make A Deal Game Theory

(originally posted 10:08 AM, Feb 11, 2006)

A couple days ago (yes, in a bar) I became intrigued with a fairly well known game problem, here's my version:

  1. There are three doors, one of which is a winner.
  2. You pick one door, but it isn't opened yet.
  3. At this point at least one of the unpicked doors (maybe both) are losers.
  4. A losing unpicked door is opened.
  5. You now have the option of either sticking with your original choice, or switching to the remaining unopened door. Which has a better chance of being the winner?
Here is a Perl script I wrote which will play the game using both the "switch" and "stay" strategies: http://eigenstate.net/misc_scripts/make_a_deal.pl

What do you think?

Tags: , ,







12 Feb 2006 - addition:

Here is one way of explaining what is going on:

When the losing choice is revealed, you gain some new information.

At the start, you have equal knowledge of all the choices, so at first every door has 1/n chance (1/3 if there are three doors).

You then divide doors into two groups: one door in group A (your first pick) and the rest of the doors in group B. With three doors group A carries 1/3 of the chances and group B carries 2/3.

When one of the doors in group B is revealed to be a loser you know something new:

You know that the group of chances that was in group B at the start must now be redistributed among the remaining doors in group B.

So if group B had 2/3 of the chances at the start, it *still has* 2/3 of the chances, but those all ride on the one remaining door in group B. So, the remaining door in group B has a 2/3 chance fo winning, whilst the door you originally picked, in group A still has only a 1/3 chance.

What has happend is that the revelation of the loser in group B has told you that all the other doors in group are more likely to be a winner.

If you try it with 10 doors it is still better to switch - to pick any remaining door in group B - than to stay with the door in group A.

Where N is the number of doors, the chance of the first pick winning is 1/N, and the chance of a door in group B after eliminating a loser from group B is: (N-1)/N

It is the -1 that makes swicthing worth it.

We can generalize the problem further by saying that T is the Total number of doors, A is the number of doors in group A, and B is the number in group B before a loser is revealed. Then the chance of a door in group A is A/T (for example, 1/3) and the chance of a door in group B, after the elimination is B - 1 / T.

So if there are 10 door total, and you put 3 doors in group A at the start:

T = 10
A = 3
B = 7

Each group A door has a 1/10 chance (3/10 for the group as a whole.) After eliminating a loser from group B, the group as a whole still has 7/10 chances and thus each remaining group B door has a 6/10 11 2/3% chance of being the winner. (thanks to keith for the correction)

4 comments:

Paul Bissex said...

Here's a version in Python --- far less thorough and generalized than yours, but it got me to think through the problem, which might have been your point.

Malcolm Gladwell writes about this in his book Blink. I didn't really believe his explanation until I coded it up myself!

http://e-scribe.com/software/python/deal.txt

Matisse Enzer said...

Cool!

I've added one kind of explanation to the original post.

Keith said...

So if there are 10 door total, and you put 3 doors in group A at the start:

T = 10
A = 3
B = 7

Each group A door has a 1/10 chance (3/10 for the group as a whole.) After eliminating a loser from group B, each remaining group B doors has a 6/10 chance of being the winner.


No; each group B door does not have a 6/10 chance.

Each group A door still has the original 10% chance. The 70% chance that had originally been allocated to the 7 group B doors is now divided among only 6 group B doors, giving each an 11 2/3% chance. Better than the 10% of the group A doors, but nowhere near 60%.

Matisse Enzer said...

You're right Keith, I'll correct the post - after the removal, "group B" as a whole still has 70%, but each individual door in group B has 11 2/3% like you say. Thanks for catching that.