Solving ‘The Monty Hall Problem’ using Models

Today is about my favorite probability puzzle – The Monty Hall problem. If you haven’t heard of it before you are in for a treat. The problem stated goes as follows (from Wikipedia):

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats*. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat**. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Vos Savant's response was that the contestant should always switch to the other door. […]

Many readers refused to believe that switching is beneficial. After the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming that vos Savant was wrong. (Tierney 1991) Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy.

*The probability of the car being behind any door is uniformly 1/3

**The door that is opened has to have a goat behind it, and it cannot be the one you picked initially, in case the host has multiple choices it is assumed that s/he chooses uniformly at random

The problem is brilliant in its simplicity and the correct answer feels extremely counter-intuitive at first. The natural tendency is to think that it makes no difference whether you switch or not – but the truth is that you should switch! And hopefully once you are done reading this article you will be convinced why.

For an in-depth explanation (although a little too narrative in my opinion) watch this YouTube video – and if you think the answer is obvious, just scan the comments on the video to convince yourself that people have a hard time understanding this answer!

Solving the problem through modeling

Let’s take a look at how we can tackle this problem in the world of Model-Based Testing [1]. This article is special in that I’m not going to have a system under test – there is nothing to test here! Instead, what I’ll be doing is constructing a model that will be useful for simulating the flow of the Monty Hall problem.

The model state machine consists of the following variables:

        const int NumberOfDoors = 3;

        const int DoorWithPrize = 0;

        static int first_choice = -1;

        static int revealed_door = -1;

        static int final_choice = -1;

First, one thing I’d like to make clear is that I’m simplifying the problem by fixing the door that contains the prize to be the first door – this does not make any difference, because the problem statement is equivalent no matter which door the prize is behind (likewise you could fix the initial choice and have the location of the prize be random). If you don’t believe this, then feel free to enumerate both policies for all three prize locations.

To break the model down, the game show contains three stages, they are:

1)      Pick your initial choice of door

2)      Game host reveals a goat behind another door

3)      You either switch or stick with your door

We will be modeling these stages as rules, and then define a slicing scenario that dictates the two choices of policies we have (switch/stick with choice).

The rules of the model become:

        // Chooses a first choice door between 0 and 2

        [Rule(Action = "PickDoor()/result")]

        static int PickDoorRule()

        {

            first_choice = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors);

            return first_choice;

        }

        // Chooses a door to reveal between 0 and 2 that:

        // * Is not our first choice

        // * Is not the door with the prize (door: 0)

        [Rule(Action = "RevealDoor()/result")]

        static int RevealDoorRule()

        {

            revealed_door = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors && i != first_choice && i != DoorWithPrize);

            return revealed_door;

        }

        // Switches our choice of door and saves the value in final_choice, by picking a door between 0 and 2 that:

        // * Is not our first choice

        // * Is not the revealed door

        [Rule(Action = "SwitchDoor()/result")]

        static int SwitchDoorRule()

        {

            final_choice = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors && i != first_choice && i != revealed_door);

            return final_choice;

        }

        // Simply sticks with our first choice by setting final choice = first choice

        [Rule(Action = "StickWithDoor()/result")]

        static int StickWithDoorRule()

        {

            final_choice = first_choice;

            return final_choice;

        }

Notice that we leverage Spec Explorers ability to handle stochastic choices! The model does not know up-front which door the contestant will start out picking, and neither does it know which door the game host will reveal.

So, we could simply explore the model composing these rules, but that model would be nonsensical because it violates the rule of the game show – e.g. it would allow the game host to reveal two doors, etc. Therefore, we need to constrain the model into a meaningful slice. We have two policies so we need two slices; the first slice is for ‘sticking with your initial choice’:

/// The scenario is equivalent to sticking with your choice in the 'Let's make a deal' game show

machine DontSwitchScenario() : Main where ForExploration = true

{

    (PickDoor; RevealDoor; StickWithDoor)

}

machine MontyHallDontSwitchModel() : Main where ForExploration = true

{

    DontSwitchScenario || MontyHallRules

}

Let’s explore this model and have a look at the results:

The state bubbles show the currently selected door, and at the end it includes the outcome – whether we found a Ferrari or a goat behind our final choice door.

From a quick glance of this model it looks like we are in pretty good shape – we see two goats versus two Ferraris. But we need to read the picture correctly, actually we don’t decide which door is revealed, it is stochastically decided, meaning there is a 50/50 chance that either door 1 or door 2 is revealed – however, the final outcome is the same – we win no matter which door the host reveals under this policy (which is expected because our choice is unaffected by the host’s choice when we stick with the initial choice).

To compute the expected outcome for this model observe that we pick the initial door randomly with 1/3 probability, then in two out of three options the game host can only reveal one door (with probability 1), and in the final option the game host picks one of the remaining doors with probability 0.5. Getting the Ferrari has utility 1 and the goat has 0. The expected outcome is then:

E[MontyHall|Stick with choice] = 1/3 * 0 + 1/3 * 0 + 1/3 * (1/2 * 1 + 1/2 * 1) = 1/3

The fact that there are two ways of winning when we have picked door zero initially should not count double. What matters is that given our initial three options, which paths will give what outcome? In our case the two left-most paths will result in ‘winning’ a goat, where the right-most choice (under our policy) will win us a Ferrari! Our chance of winning the Ferrari is thus 1/3.

Next, let’s look at the switching policy:

/// The scenario is equivalent to switching your choice in the 'Let's make a deal' game show

machine SwitchScenario() : Main where ForExploration = true

{

    (PickDoor; RevealDoor; SwitchDoor)

}

machine MontyHallSwitchModel() : Main where ForExploration = true

{

    SwitchScenario || MontyHallRules

}

It is clear that the only difference is in the third stage of the model, where we now switch our choice instead of sticking with it. The model looks slightly different:

Notice now that the mechanics of the game have switched! Under the policy where we switch, two of our initial branches will lead to winning the Ferrari! Only one branch will lead us down the path where we ‘win’ a goat – again it does not matter whether the game host reveals door one or two, once we are down the path of picking door zero initially we are guaranteed to lose the game. The expected outcome is:

E[MontyHall|Switch] = 1/3 * 1 + 1/3 * 1 + 1/3 * (1/2 * 0 + 1/2 * 0) = 2/3

The key to understanding this problem (in my opinion) lies with understanding what happens when the host reveals a door under the switching policy. Notice that under this policy the game host only has one option in two out of three cases – incidentally, in these two cases, when he reveals the door with the goat behind it he is consequently also revealing which door the Ferrari is behind!

Conclusion

We saw in this article how models can be useful for simulating problems without actually acting against a system under test. Modeling is a great technique for visualizing simulation results and through Spec Explorers powerful stochastic modeling feature you can simulate decision-trees for random processes, like the Monty Hall problem.

References

[1] Monty Hall Model