Simulating Monty Hall

The Monty Hall problem is one of the most notorious math exercises when we want to explore a bit more the practical impact of the ideas behind Bayes' Theorem

Bayes' Theorem

The problem consists in a simple game involving three different players.

Monty Hall Players

The Monty Hall will choose a door between [1,2,3]. The same will do the player Conservative and player Risky. The idea is for Conservative and Risky to figure out which is the number selected by the Monty Hall. There's another point. Monty Hall will open one invalid door from one of the two doors not selected by the player and give the player the possibility to review his choice.

The players have two different strategies. The Conservative will stick with his original choice. The Risky will use the information provided by Monty Hall and change his previous decision based on that new information.

Lets proceed with an example

Conservative Play

Risky Play

Our naive may say that sticking or changing the selected option should not make any difference since all have the same probability of one third to happen.

Here we will not use Bayes Theorem to deduce the solution, for that I recommend this very nice article. Instead we will devise a simulation to see how things unfold.

We will model the problem in go language because it simple and expressive and fun (personal opinion here).

First let us first formalize the concept of door.

type MontyDoor int

The door in this game is represented with the type MontyDoor which is simply an int representing the number of the door. In this case we will have the [1,2,3]

Now that we have defined what we understand by door lets move into the concept of Player. In this case we will use an interface to formalize the behavior we want to assign to a player

type Player interface {  
    SelectDoor()
    ChangeDoor(door MontyDoor)
    GetDoor() MontyDoor
}

So a player will be able to:

Select an initial door with SelectDoor()
Change the door after one door is open by the Presenter with ChangeDoor(door MontyDoor)
Show his selected door with GetDoor()

We also have a specific behavior for the presenter, in this case he will be able to open one of the three doors

type Presenter interface {  
    OpenDoor(door MontyDoor) MontyDoor
}

Now its time to define state for the three agents of the game (in the code the Risky is called Changer)

type MontyHall struct {  
    solution MontyDoor
}

type ConservativePlayer struct {  
    solution MontyDoor
}

type ChangerPlayer struct {  
    solution MontyDoor
}

Each of them has one field attribute that represents their selected door.

Now that we have a structured representation of the several entities involved in the game its time to implement some useful behavior. Since all the players need to select some door, ideally in a random way, we should start by implementing this idea first

func RandomDoor() MontyDoor {  
    rand.Seed(time.Now().UnixNano())
    return MontyDoor(rand.Intn(3) + 1)
}

This small function does essentially two things:

Set a seed to be used by the pseudo random number generator
Select a random value between 1 and 3 using the seed provided

For this to behave more nondeterministic we use the time as the seed value.

Now that we have devised a way to select doors randomly we can start implementing the behavior for the three players. Lets first start with the king of the show, Monty Hall himself. In summary we just need to describe all the actions the player/presenter will do during the game

Monty Hall will select secretly a door
Monty Hall will open an invalid door
Monty Hall will show the right door

We can translate this behavior into code

//Select a door
 func (montyHall *MontyHall) SelectDoor() {
    montyHall.solution = RandomDoor()
}

// Monty Hall will never change the selected door so
// we can just define the method with an empty body.
// This effectively says, do nothing.
func (montyHall *MontyHall) ChangeDoor(sol MontyDoor) {  
    //Does nothing
}

// To show the selected door we just need to provide access
// to the previous selected door
func (montyHall *MontyHall) GetDoor() MontyDoor {  
    return montyHall.solution
}

Now that we have the behavior implemented for Monty Hall we just need to provide behavior to the two new players, the Conservative and the Changer.

Conservative
- Select a door
- Show the selected door
- When Monty Hall opens an invalid door just do nothing
- Show the selected door
Changer
- Select door
- Show the selected door
- When Monty Hall opens an invalid door just change to one of the two remaining doors
- Show selected door

In code this will look like

// The conservative player
func (player *ConservativePlayer) SelectDoor() {  
    player.solution = RandomDoor()
}

func (player *ConservativePlayer) ChangeDoor(sol MontyDoor) {  
    //Does nothing
}

func (player *ConservativePlayer) GetDoor() MontyDoor {  
    return player.solution
}

//The Changer player
func (player *ChangerPlayer) SelectDoor() {  
    player.solution = RandomDoor()
}

func (player *ChangerPlayer) ChangeDoor(sol MontyDoor) {  
    alternative := RandomDoor()
    for ok := true; ok; ok = alternative == player.solution || alternative == sol {
        alternative = RandomDoor()
    }
    player.solution = alternative
}

func (player *ChangerPlayer) GetDoor() MontyDoor {  
    return player.solution
}

Now we have all the behavior needed to run our simulation. In our case we will run 1000 times the game and we will track the game results with an additional data structure

type SolutionCounter struct {  
        Conservative  int
        ChangerBefore int
        ChangerAfter  int
    }

This will hold the number of correct choices for three distinct cases

The number of times Conservative player won
The number of times Changer player hit with his original choice
The number of times Changer player hit with the second choice

By gathering all these ideas together we can implement the simulation as we can see in the montyhall.go file

If you build and run the program you'll get an output very similar with the following

[Conservative: s=1,p=3,b=2,a=2] -- x
[Changer: s=3,p=1,b=3,a=2]      -- x

[Conservative: s=3,p=1,b=2,a=2] -- x
[Changer: s=2,p=3,b=1,a=2]      -- o

[Conservative: s=3,p=1,b=2,a=2] -- x
[Changer: s=1,p=2,b=3,a=1]      -- o

[Conservative: s=1,p=2,b=1,a=1] -- o
[Changer: s=3,p=1,b=2,a=3]      -- o

[Conservative: 322/32.200001, ChangerBefore: 379/37.900002, ChangerAfter: 621/62.099998]

In this particular 1000 game simulation we can see that both the Conservative as well as the Changer hit approximately the same proportion of correct answers, 32.2% and 37.9% (if you run the simulation again you'll notice that they tend to be the same, on another simulation I got the 33.19 33.79 as example).

The surprising result, that is backed by bayes theorem, is the case when the Changer player swap his choice. In this scenario we noticed that he was right 62.09% of the time (66.19 on another where the theoretical value is 66 or 2/3).

This simulation is a simple exercise that we can use to train our programming skills it is also a good way to get an intuitive understanding about the not so intuitive case of the Monty Hall problem. Also, next time you play some TV game maybe you can exploit probabilities in your favor.

To see the entire source code you can check it out here

Menu