Solving the Game Show Problem with Python

You might have heard of the famous "Game Show Problem" (it's also known as the "Monty Hall Problem"). If you did, there's a good chance that it confused you. If you didn't know it yet, there's a good chance that it will confuse you. It's a pretty famous example for applied probability theory and often featured in movies because it's a bit counter-intuitive but still simple enough to be understandable for most people.

The Situation

You are participant in a game show where you can win a car. You are shown three closed containers, in one of which the car is. The other two contain goats.

The host initially let's you choose one of the containers. If you chose the one with the car, the car will be yours.

However, after you have chosen the container, the host always opens one of the two remaining containers and always reveals a goat. Now you are offered to change your decision and instead choose the other unopened container. How would you decide?

Our Approach

We will do several things in this article:

1. Reformulate the problem
2. Simulate the problem
3. Examine the problem in detail
4. Generalize the problem

Reformulate the Problem

We do this first step only to make sure we all understood the problem correctly. Hence, we write it a bit more "algorithmically":

Assumptions:

• 3 containers, one contains the car, two contain a goat
• the probability that the car is in any specific container is 1/3
• we don't know which one container contains what
• we win if we chose the container with the car in the end
• the host has full information about the content of each container and opens always a goat container

Procedure

1. We choose one container.
2. The game show host open a different container than the one we chose. This container contains a goat.
3. We are asked wether we want to switch to the container.
4. We switch the container or not.
5. The container we chose in the end is opened.

I hope that we are all on the same page now. If something isn't clear so far, feel free to ask in a comment.

Simulate the Problem

Instead of making a deep dive into probability theory, we try to simulate the situation at first. Such explorative simulations are often a good idea because we might discover counter-intuitive behaviour. If we later analyse the problem in a more theoretical way, we can check if the results match.

Case A: No Switching

We start with the easier case, namely we don't switch when we have the chance. In this situation, the procedure is a lot simpler:

1. Choose a container
2. Game host opens our container and reveals wether we won

Because we never switch, the moderator doesn't have to open a container. Hence, we can ignore this step of the game.

Our simulation consists of two parts: In the first part, we simulate the mechanisms of one game. In the second part, we perform several games to get a good estimate for the true probability.

A single game looks like this:

def gameshow_no_switching(user_choice:int) -> bool:
    """One gameshow with the user strategy "no switching".

    The car is behind one of the three containers `0,1,2`.

    Parameters
    ----------
    - `user_choice`: container chosen by the user

    Returns
    -------
    - `true` if the user chose the container with the car
    - `false` otherwise
    """
    car_container = randint(0,2)

    if user_choice == car_container:
        return True
    return False

randint(0,2) chooses a random integer in {0,1,2}.

Repeating the games is a now trivial thing:

def simulate_gameshow(n_times:int) -> None:
    """Simulates the game show `n_times` and prints the 
    estimates for the probabilites to choose the container with
    the car. 
    """
    n_car = 0 # saves how often we get the car

    for _ in range(n_times):
        if gameshow_no_switching(randint(0,2)):
            n_car += 1

    print("Probabilty to choose the right container: {:.1f}%".format(n_car/n_times*100))

In order to get a reliable estimate, we run the gameshow a million times. The output always should be approximately 33.3%.

That's of course what our intuition would suggest: We can only guess which of the three doors is the right one. Hence we have chance of 1/3 to choose correctly.

Case B: Switching

In this case, everything becomes a bit more complex. Hence, we will write down what we have to do if we switch all the time:

1. We choose initially a container.
2. The host opens a different container and reveals a goat.
3. We switch to the other closed container.
4. This container is opened and checked to see wether we won.

Again, we divide our simulation in two steps: We describe the mechanism of one game and then run repeated games.

A single game looks like this:

def gameshow_switching(user_choice:int) -> bool:
    """One gameshow with the user strategy "switching".

    The car is behind one of the three containers `0,1,2`.

    Parameters
    ----------
    - `user_choice`: container initially chosen by the user

    Returns
    -------
    - `true` if the user chose the container with the car
    - `false` otherwise
    """
    car_container = randint(0,2)

    ### Game host opens a container and reveals a goat ###
    open_candidates = [0,1,2]

    # Host doesn't open the container with the car inside
    open_candidates.remove(car_container)

    # Host doesn't open the container we chose
    if user_choice in open_candidates:
        open_candidates.remove(user_choice)

    # Host chooses the first remaining container
    opened_container = open_candidates[0]

    ### Player switches container ###
    switch_candidates = [0,1,2]

    # Don't switch to the opened container
    switch_candidates.remove(opened_container)

    # Don't choose the same container we already selected
    switch_candidates.remove(user_choice)

    new_user_choice = switch_candidates[0]

    # Check if we chose the right container
    if new_user_choice == car_container:
        return True
    return False

I tried my best to write readable code and provide meaningful comments, but if you have suggestions for improvements I'd be happy to hear them!

Again, running the game repeatedly is trivial and looks identical to the "Case A":

def simulate_gameshow(n_times:int) -> None:
    """Simulates the game show `n_times` and prints the 
    estimates for the probabilites to choose the container with
    the car. 
    """
    n_car = 0 # saves how often we get the car

    for _ in range(n_times):
        if gameshow_switching(randint(0,2)):
            n_car += 1

    print("Probabilty to choose the right container: {:.1f}%".format(n_car/n_times*100))

If we now run our simulation, we get a different probability estimate: We choose the correct container in approximately 66.7% of the cases. We effectively doubled our chances to win a car!

The only interesting question is: Why?

Examine the Problem in Detail

So, our simulation gave us some crazy results, but honestly it didn't do anything to help us understand why we get these. Hence, it seems like a good time to take a more theoretical look at the problem.

If you don't want to read my explanation, here's a clip from a nice movie in which the problem is explained:

In order to make our analysis simpler, we assume that we always choose container 0. However, the car is still randomly distributed in all containers, so this restriction doesn't change the problem (you can verify this by modifying your simulation).

Now, we basically write down the "decision tree" for this problem to examine all possible scenarios.

At first, the car is randomly distributed in one of the three containers. So far, our tree looks like this:

Note 1: We annotate on the branches the probability how likely the specific decision is.
Note 2: If we stopped here, we had the situation like in case A and we would immediately see that we have a probability of 1/3 to choose the correct container.

In the second step, the game show host opens a container. Remember, we already chose container 0. If the car is in container 0, the host can choose between opening container 1 or 2. We assume that this happens randomly (that's in fact not necessary: it's also fine if the host always chooses the smaller container).

If however the car is in container 1 or 2, he only has one choice! Hence, the extended tree looks now like this:

Finally, we choose to switch the container. What's now interesting is that in all cases, we don't have a choice to where we want to switch! Hence, the probability to switch to a given container is always 1. Our final tree looks now like this:

In order to get the probability for each possible situation, we just have to multiply the probabilities on consecutive branches. E. g., for the left branch, we get: 1/3 * 1/2 * 1 = 1/6.

We now see that in 2/3 of all cases, we will in fact have chosen the right container in the end! That's because we profoundly changed the problem by introducing conditional probabilities.

Generalized Problems

Finally, we want to generalise this problem to a situation where we might have 100s or even millions of containers.

N Containers, N-2 Opened Containers

We now want to consider a situation with N containers, where N is a positive integer larger than 2. Again, the car is randomly hidden in one of the containers. For simplicity, we still always choose container "0".

However, this time the game show host opens N-2 containers; in each we find a goat. Now, the question is how likely we will get the car if we switch. Spoiler alert: The probability to win the car becomes (N-1)/N!

So, if we had 100 containers, we'd have a chance of 99% to win the car if we employ our switching strategy! That's definitely a lot better than our 1% chance if we stay with our initial decision.

I'll try to outline how we arrive at these crazy results: Initially, the chance that we chose the container with the car was 1/N. Hence, the probability that the car was in one of the other containers is (N-1)/N. A bit more graphical:

If the host opens N-2 of the other containers and none of them contains the car, that doesn't change how likely we guessed initially the correct container. So all the "remaining probability" shifts into the one unknown container that we didn't choose. Now our situation looks like this:

I encourage you to simulate this situation as well and check this theoretical result.

N Containers, M Opened Containers

Finally, we want one more generalisation: What if the host doesn't open all but one of the remaining containers and instead only a few of them?

Again, we consider the situation after we initially chose the container 0. The situation is identical to before, we just draw it a bit differently:

If the host now opens M containers and all of them contain a goat, the uncertainty for these containers is eliminated. However, the probability that our initial guess was correct is still 1/N:

There are N-1-M containers left that we could switch to. But the probability that the goat is in one of these is still P=(N-1)/N. Hence, the probability that we choose the correct container if we switch is P/(N-1-M)=(N-1)/((N-1-M)*N)=(N-1)/(N^2-N-MN).

Sadly, this is not exactly a very nice result, but we still can evaluate it. Assume we have N=100 containers and after our initial guess, the host opens M=80 of the remaining ones and each contains a goat. Then switch improves our probability of being correct from 1% to 99/100 * 1/(19)=99/1900=5.52%. That's at least 5 times better than before!

If M was 85, we would improve to 7.1%. If M was 90, we would get 11% right. If M was 95, it would even be 24.8%.

Conclusion

I'd briefly like to recap what we looked at in this article:

1. Making sure to understand the problem in the beginning makes subsequent steps easier.
2. Simulations can be a fast way to get important results for complex problems.
3. A theoretical treatment of these problems reveals the underlying mechanisms. It is supported by simulation results that we can test our theories against.
4. From a theoretical perspective on a specific problem we usually can abstract to more general problems and get broader insights.