A slower way to understand the three-door problem
The three-door problem, commonly known as the Monty Hall problem [1], is a game between a host and a player. As one of the most popular probabilistic puzzles, it is easy to find explanations or simulations to address the correct answer. Here in this article, instead of finding brilliant shortcuts, we challenge ourselves to use the heaviest way to decompose the problem. Doing so will reward us with a much more general formulation, which then can be extended beyond the original problem.
1. Three doors problem
The game starts with a car hidden behind one of three closed doors. The player, don’t know which door leads to the car, will be given a chance to guess one without actually opening any door. It is then followed by the host, who knows where the car is, opening up the one that does not lead to the car nor is the player’s initial guess. In any case, the player will be left with two doors to choose from.
The question arises: will changing away from the first guess gain any advantages/disadvantages of winning?
2. Notations and Formulations
To convert the problem into sad and boring (but solvable) equations, we will utilize the notion of conditional probability and Bayes’ theorem, which readers may refer to [2] to equip necessary tools for this journey. As a reminder, we give an example with two variables below.
2.1 Problem overview
We consider a similar problem but with N-doors (N≥3), which is formalized as a probability experiment with four variables each taking an integer from 1 to N. Listing out, we have “z”-the door index that leads to a car, “x₁”-the player’s first guess, “y”-the door revealed by host and at last, “x₂”-final decision of the player. Known dependencies between variables can then be illustrated in the following diagram. For instance, “p(y|z,x₁)” indicates the probability of “y” over door indices given known “z” and “x₁”, essentially the host’s strategy.
2.2 Modelling behaviours
As a preparatory step, here we assert two relations that hold for the whole article. Starting with the player’s first guess “x₁”, we follow a natural assumption that it is uniform and independent to “z”-the index of the winning door. On the other hand, knowing and reacting on both “z” and “x₁”, the host’s decision on “y” can be formalized as below using the language of conditional probability.
We introduce the Kronecker delta function “δᵢⱼ” for a compact expression.
Reader may verify that the expression of the host’s behaviour is to choose a random door while avoiding “z” and “x₁”, covering either case if “x₁=z” or not.
2.3 Which way to go?
To solve such a problem, we will exploit two different approaches. In §3, the problem was transcripted more directly as we presume several player’s strategies “p(x₂|x₁,y)”, express them explicitly, then solve the probability of event “x₂=z”. In contrast, without any assumptions on the player’s strategy, in §4 we simply ask the probability of “z” based on observed fact, denoted as “p(z|x₁,y)”. Beyond what we aim for, the latter approach also gives a pathway to show the optimality of certain strategies.
3. Forward calculation
As the last piece of the puzzle, we list out a few common strategies “p(x₂|x₁,y)” which drive the decision on “x₂”. Note that a rational player would likely take “x₁” and “y” into consideration, hence having the conditional expression.
There is also a strategy to pick the same door as “y”, funny, but this would play its role as we march towards §6.
3.1 Strategy A: Avoid “y”
Now with everything ready, we can directly expand and calculate the target event “x₂=z” over all possible trajectories of “x₁” and “y”:
In terms of winning rate, we only gain marginal advantage from “1/N” to “1/(N-1)”. Shouldn’t be a surprise as this is not different from playing a fresh new “N-1 doors game”.
3.2 Strategy B: Keep “x₁”
Similarly, by changing the term of “p(x₂|x₁,y)” highlighted in blue, we have the winning rate by insisting on our first guess where “x₂=x₁”:
Besides the miserable outcome where we gain exactly nothing compared to “1/N”, was there any shortcut to calculate the winning rate for Strategy C directly from here?
3.3 Strategy C: Avoid both “y” and “x₁”
Finally, with strategy C depending on both “y” and “x₁”:
Here we use the following identity:
Here we use the following identity:
Examining the result would show that it is always greater than “1/(N-1)”, indicating that changing away from “x₁” does gain advantages, even surpassing the case with a simple “N-1” doors game.
Just to emphasize the difference, for the 3-doors case, strategies A, B, and C would each lead to a winning rate of 1/2, 1/3, and a whopping 2/3!
4. Optimal Strategy?
Though giving the right answer, the approach of §3 cannot tell if Strategy B is the best we can squeeze out of this problem. In this section, instead of watching far from a bird’s view, we step into the game as the player.
4.1 Beliefs and updates
Starting from the beginning, we have our beliefs on “z” denoted as “p(z)” (we abuse the notation as this is not necessarily the same as the probability for “z”). Without good reason, this is naturally a uniform distribution over all doors. The question for us (the player) is: How would choosing “x₁” and observing the host’s reaction as “y” affect our belief on “z”?
Considering that this “updated belief” in our head is under the fact of “x₁=j” and “y=k”, we can rationalize this process as finding the conditional probability “p(z|x₁,y)”. We brutally expanded this idea as follows and take the assumption of a uniform prior belief on “z”.
The result simply prompts a higher but uniform amplitude for those away from “x₁”, confirming that strategy B is the optimal strategy we should apply from our limited information.
5. Implications
Winding up our discussion, we formalize the N doors problem by describing both the player’s and host’s behaviour algebraically, enabling us to calculate the winning rate under a few strategies. Hopefully, during the derivation, the complexity caused by the host’s decision “y” is obvious enough to show that it brings more information than simply leaving us with an N-1 doors game.
6. Faster way
As an extension from §3, if the host opened “n” doors, the winning rate with strategy C can still be easily derived without explicit expression of the host’s strategy. The following graph would help picture the problem.
To do so, we need to establish two facts. First, follow the derivation as shown below, if we play with strategy B where “x₂=x₁”, we’ll have a winning chance of 1/N. Note we use the fact that strategy B is independent of to host’s reaction.
Second, we utilize the identity relations by combining strategies B, C, and D, essentially having a strategy with uniform likelihood (=1). Viewed differently, this is just a fancy way of saying that the car must be in one of the rest.
This would then prompt an equality relation between choosing “x₁”, “y”, or any others as shown below.
This result can also be found in [3].
7. Reference
- Selvin, Steve, M. Bloxham, A. I. Khuri, Michael Moore, Rodney Coleman, G. Rex Bryce, James A. Hagans, Thomas C. Chalmers, E. A. Maxwell, and Gary N. Smith. “Letters to the Editor.” The American Statistician 29, no. 1 (1975): 67–71. http://www.jstor.org/stable/2683689.
- Thrun, Sebastian., Burgard, Wolfram., Fox, Dieter. Probabilistic robotics. Cambridge: MIT Press, 2005.
- Dickey, James, N. T. Gridgeman, M. C. S. Kingsley, I. J. Good, James E. Carlson, Daniel Gianola, Michael H. Kutner, and Steve Selvin. “Letters to the Editor.” The American Statistician 29, no. 3 (1975): 131–34. http://www.jstor.org/stable/2683443.