Essays/The Monty Hall Problem

From J Wiki
Jump to: navigation, search

The object of the game is to win a car.

Two goats and a car are hidden behind 3 doors, one item per door. You choose a door. The game-master (Monty Hall), who knows what's behind the doors, opens one of the other doors, revealing a goat, and offers you the opportunity to change your choice of doors. Your chosen door is then opened and you get what is revealed.

Should you stick or change?

Many people get this wrong, including people with Ph.D. degrees in mathematics and statistics, including Paul Erdős as recounted in chapter 6 of Paul Hoffman's The Man Who Loved Only Numbers.

Simulation

The present task is to write two simulation programs, one for the strategy of sticking with the original choice and another for the strategy of changing. The argument is the number of simulations of the game; the result is the number of cars won.

stick=: 3 : 0
 c=. ?y$3                       NB. where the car is hidden
 i=. ?y$3                       NB. your choice of door
 +/c=i                          NB. number of cars that you win
)

change=: 3 : 0
 c=. ?y$3                       NB. where the car is hidden
 i=. ?y$3                       NB. your choice of door
 j=. (c*i~:c)+(3|i+1+?y$2)*i=c  NB. your changed choice
 +/c=j                          NB. number of cars that you win
)

NB. if i~:c, Monty Hall opens the other  goat door,  and you change to the car door
NB. if i= c, Monty Hall opens one of the goat doors, and you change to the other goat door


   c     NB. where the car is hidden
1 0 1 2 2 2 0 2 0 1 2 0 0 0 1 1 1 1 1 0 0 1 1 2 1 2 1 0 0 0 2 2 2 2 1 2 1 2 0 2 1 1 0 2 2 0 1 0 2 1 2 0 2 2 2 2 2 ...
   i     NB. your choice of door
2 2 1 2 0 2 2 1 0 1 2 0 1 2 0 2 2 1 0 0 2 1 2 2 1 0 0 2 1 2 2 1 1 1 0 2 0 0 0 0 1 0 2 2 1 0 2 2 1 1 2 0 0 2 1 1 1 ...
   j     NB. your changed choice
1 0 2 1 2 0 0 2 2 0 1 1 0 0 1 1 1 2 1 2 0 0 1 0 2 2 1 0 0 0 1 2 2 2 1 0 1 2 1 2 0 1 0 1 2 1 1 0 2 2 1 2 2 1 2 2 2 ...


   stick 1e6
333143
   stick 1e6
332564

   change 1e6
666771
   change 1e6
665859

The Crucial Line

The crucial line in the simulation

 j=. (c*i~:c)+(3|i+1+?y$2)*i=c  NB. your changed choice

is in the pattern (p*~b) + q*b where b is a binary condition.

c * i~:c -- your original choice i is not equal to the car door c,  i.e. is a goat door. Monty Hall would have opened the other goat door, and a switch means a switch to the car door, i.e. to c .

(3|1+i+?y$2) * i=c -- your original choice i equals the car door c .  The analysis can be divided into 3 parts, depending on the value of i ,  and assumes the existence of a random binary noun r .

c i goat doors   j
0 0 1 2 1+r

3|1+r
3|i+1+r

1 1 0 2 3|2+r

3|i+1+r

2 2 0 1 r

3|3+r
3|i+1+r

That is, for each of the three possible values of i the value of j can be computed as 3|i+1+r .

Of course, with your original choice equaling the car door and the strategy being to switch, it doesn't matter which door Monty Hall opens and thence which door you switch to -- the i=c part of the sum should be 0. However, we want the simulation to be as realistic as possible. (See the values of c , i, and j in the previous section.) After all, further analysis eliminates the need to simulate at all, as follows:

Explanations without Simulation

My favorite explanation of why you should change your choice of doors is found on pages 104-105 of Sixty Days and Counting, a novel by Kim Stanley Robinson:

[E]ach box at the start had a one-third chance of being the one. When subject chooses one, the other two have two-thirds a chance of being right. After experimenter opens one of those two boxes, always empty, those two boxes still have two-thirds of a chance, now concentrated in the remaining unchosen box, while the subject's original choice still had its original one-third chance. So one should always change one's choice!

Another lucid explanation can be found on pages on page 65 of The Curious Incident of the Dog in the Night-Time, a novel by Mark Haddon. The universe of possible outcomes can be diagrammed as follows:

You are asked to choose a door
You choose the door with

goat 0
behind it

You choose the door with

goat 1
behind it

You choose the door with

the car
behind it

You stick You change You stick You change You stick You change
You get

a goat

You get

a car

You get

a goat

You get

a car

You get

a car

You get

a goat

If you change, 2 times out of 3 you get a car; if you stick, you get a car only 1 out of 3 times. The results from the simulations are consistent with this conclusion.



See also



Contributed by Roger Hui.