J.S. Kowontan
Aug 25, 2017 · 11 min read

MONTY HALL PROBLEM & BAYES’ RULE

“…no other statistical puzzle comes so close to fooling all the people all the time.”

— Massimo Piattelli-Palmarini

“After the problem appeared in Parade magazine, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming Marilyn vos Savant was wrong.”

— John Tierney, The New York Times


I. Introduction

Monty Hall problem is a brain teaser, in form of a probability puzzle, loosely based on the American TV game show Let’s Make a Deal and named after its original host, Monty Hall.

On September 9, 1990, Craig F. Whitaker, a reader of Marilyn vos Savant’s Parade Magazine column, “Ask Marilyn”, stated the Monty Hall problem in a letter to her:

Vos Savant correctly answered the question. Her response was that:

the contestant should switch to the other door. Under the standard assumptions, contestants who switch have a 2/3 chance of winning the car, while contestants who stick to their choice have only a 1/3 chance.

But her counter-intuitive solution was generally not accepted by mathematicians and everyday problem solvers around the world. In particular, Scott Smith, PhD holder from the University of Florida, presented the view of the general public:

“After the host reveals a goat, you now have a one-in-two (1/2) chance of being correct. Whether you change your selection or not, the odds are the same.”

It is therefore the main objective of this article to present a mathematical proof of Marilyn vos Savant’s answer using Bayes’ rule. The proof presented here leads to the statement of result:

If the contestant’s initial door choice is X[i] and Monty Hall opens another door H, which does not contain the prize, then the probability of the contestant winning the prize by accepting to switch the initial door choice, P (switch) is 2/3. While the probability of winning by rejecting the offer, P (stick) is 1/3.

Hence, it is concluded, that under the standard assumptions that the game is fair and unbiased, the contestant has an advantage of winning by switching the initial door choice.

The major key to the proof is the introduction of the joint probability of winning the prize P (m, n) i.e.

The probability of winning the prize giving that the contestant initially picks any of the three doors X [i] and the prize is hidden behind any of the three doors Y and Monty Hall opens either of the two doors H left and the contestant then correctly switch to or stick with the door behind which the prize is hidden X [i+1] when offered a deal i.e.

P (m, n) = P(X [i] & Y & H & X[i+1])

This joint probability is obtained using Bayes’ rule recursively.


II. Proof

  • Bayes’ Rule

Bayes' rule stated mathematically is as follows:

where X and Y are events and P (X) is not equal to zero.

  • P (X) and P (Y) are the probabilities of observing X and Y without regard to each other.
  • P (Y|X), a conditional (transistion) probability, is the probability of observing event Y given that X is true.
  • P (Y & X) is the joint probability of observing events X and Y together
  • Proof Outline

The Monty Hall problem can be solved by forming a chain of events during the game using Bayes’ rule recursively.

For the Monty Hall problem, we have four separate events:

  1. X [i] — The contestant’s initial door choice
  2. Y — The door choice behind which the car is hidden
  3. H — The door opened by Monty Hall
  4. X [i+1] — The contestant’s second door choice i.e. to switch door or not

The game proceeds in a series of event as stated in Monty Hall Problem:

  • The contestant can only choose one of the three doors in the initial stage. We arbitrarily take that door to be door 1 without any loss of generality i.e. X [i] = 1
  • In the second stage, Monty Hall can choose to open any of the other two doors that does not contain the prize i.e. H = 2 or H = 3.
  • In the final stage, the contestant can accept the choice to switch the initial door choice or not; depending on the door opened by Monty Hall i.e. X [i+1] = 1, 2 or 3.
  • At any stage, the car can be behind any of the three doors i.e. Y = 1, 2 or 3.

From the game proceedings, only X[i+1] and Y can take any of the allowed values, while X[i] and H take predetermined values. Hence, we fix X[i] and H and vary X[i+1] and Y.

Thus, the solution to the Monty Hall problem is the joint probability of winning a car for the event:

(X[i]=1) & Y & (H =2 or 3) & X [i+1]

We represent this joint probability by the notation P (m, n) expressed as:

Where Y = m and X (i+1) = n for m, n = 1, 2, 3.

The contraction in the notation for P(m,n) is because we have fixed the values of X [i] and H. Hence, the joint probability should only vary with X[i+1] and Y.

  • Standard assumptions

To ensure the game is unbaised and fair, the following conditions are imposed:

  1. the hidden car location Y is independent of the contestant’s initial door choice X[i]
  2. The probability of the car being behind any of the three door is uniformly distributed i.e. P(Y=n)=1/3 for any n = 1, 2 or 3
  • Proof

Stage 1:

Since from the standard assumption,

the hidden car location Y is independent of the contestant’s initial choice X[i] and the probability of being behind any of the three door is equally distributed i.e. 1/3

Therefore, each element of the transistion matrix P (Y|X [i]) becomes

P (Y = m|X [i] = n) = P (Y=m) =1/3

for any m and n.

Hence, the initial transition matrix can be expressed as;

Based on the standard assumption we can also assign any probability to the possible initial door choice X [i] because the contestant’s bias has no effect on the game outcome.

Thus we arbitrarily assign the initial choice of door 1 (any other door could be chosen) a probability of 1 and to the others a probability of 0.

Thus, the first link in the Monty Hall chain of event can now be written from Bayes’ rule as;

To use Baye’s rule in matrix form to obtain the joint probability matrix, we must place the elements of P (X [i]) = [1 0 0] along the diagonal of a zero matrix and compute as below;

Stage 2 (set X[i] = 1) :

Consider that the player picked door 1 and it is Mr Monty Hall turn to open one of the remaining two doors that does not contain the car.

If the car is behind door 1 (Y = 1) and given that the contestant has chosen door 1 (X [i] = 1), then Mr Monty Hall can open any of the remaining doors (2 or 3) with equal probability (i.e. 1/2) but cannot open door 1. Hence, the transistion matrix first row can be expressed as;

If the car is behind door 2 (Y = 2) and given that the contestant chose door 1 (X [i] = 1), then Mr Monty Hall cannot open door 1 and door 2, but must open door 3. Hence, the transition matrix second row can be expressed as;

Similarly, if the car is behind door 3 (Y=3) and given that the contestant chose door 1 (X [i]=1), then Mr Monty Hall cannot open door 1 and door 3, but must open door 2. Hence, the transistion matrix third row can be expressed as;

The transition matrix for the second stage of the game is thus;

The second link in the Monty Hall chain of event can be written from Bayes’ rule as;

But from the joint probability matrix of P(Y & X [i]) obtained in stage 1

We again place the row matrix above along the diagonal of a zero matrix and compute the joint probability of the second stage of the game as below;

Stage 3 (set H = 2 or 3):

At the final stage, Mr Monty Hall offers the player a chance to switch the initial chosen door X [i] to another door X [i+1].

The problem is to determine if the player should accept this offer or not.

There are two possible cases depending on which door (2 or 3) Monty Hall opened in the last stage. The door opened determines the option available to the contestant.

We now calculate the joint probability of winning a car for both case.

Case 1: H = 2

The transition matrix that wins the car after Monty Hall opens door 2 is obtained as follows:

If the car is located behind door 1 and Mr Monty Hall opened door 2 then the contestant should not accept the offer, since his initial choice of door 1 contains the car. Hence, the first row of the transition matrix is expressed as;

At this stage, the car cannot be behind door 2 (it has been opened by Monty Hall) and the transition matrix second row must be filled with zeros;

If the car is located behind door 3 and Mr Monty Hall has opened door 2 then the contestant should accept the offer to switch from door 1 to door 3, since his initial choice of door 1 does not contain the car. Hence, the third row of the transition matrix is expressed as;

The transition probability matrix that wins the car is thus;

The third link in the Monty Hall chain of event for this case can be written from the Bayes’ rule as

But from the joint probability matrix of P((H = 2) & Y & (X [i] = 1)) obtained in stage 2 (notice we picked the values from the second column, not the second row, because H is to the left of Y, therefore it represents the column index)

We again place the row matrix above along the diagonal of a zero matrix and compute the joint probability of the third stage of the game as below;

Case 2: H = 3

The transistion probability matrix that wins the car at this stage is obtained as follows:

If the car is located behind door 1 and Mr Monty Hall has opened door 3 then the contestant should not accept the offer, since his initial choice of door 1 contains the car. Hence, the first row of the transition matrix is expressed as;

If the car is located behind door 2 and Mr Monty Hall has opened door 3 then the contestant should accept the offer to switch doors, since his initial choice of door 1 does not contain the car. Hence, the second row of the transition matrix is expressed as;

At this stage, the car cannot be behind door 3 and the transition matrix third row must be filled with zeros;

The transistion matrix that wins the car is thus;

The third link in the Monty Hall chain of event in this case can be written from Bayes’ rule as

But from the joint probability matrix of P((H = 3) & Y & (X [i] = 1)) obtained in stage 2 (notice we picked the values from the third column, not the third row, because H is to the left of Y)

We again place the row matrix above along the diagonal of a zero matrix and compute the joint probability of the third stage of the game as below;


The Joint Probability of Winning a Car

The joint probability of winning a car P(m, n), which was expressed in the outline section as

Is simply the sum of the matrix obtained in case 1 and 2 of the final stage.

The matrix nonzero diagonal elements contain the necessary information to determine if the contestant should switch or not.

We note the following:

  1. The total sum of the diagonal elements is equal to 1 and they are therefore the only situations that can occur.
  2. In each diagonal element, the contestant final door choice X[i+1] equal the door the car is hidden behind Y. Therefore they indicate when the contestant wins the prize
  3. Depending on if X [i+1] = X [i] or not in a diagonal element, we distinguish scenarios in which the contestant wins by switching or sticking to their door.

Scenario 1 (Stick): X [i+1] = X[i]

This only occurs for the diagonal element P (1,1). Thus we have;

P (stick) = P (1, 1) = 1/3

Scenario 2 (Switch): X [i+1] =/= X[i]

This occurs for two diagonal elements P (2,2) and P (3,3). Hence, we have;

P (switch) = P (2,2) + P (3,3)

P (switch) = 1/3 + 1/3 = 2/3

This concludes our proof that the contestant wins the prize 2/3 time if the initial door choice is switched and 1/3 time if the door choice is not switched. QED

)

J.S. Kowontan

Written by

Consultant & academic researcher in diverse scientific and engineering fields. Operations Research scientist. Mathematician. Algorithm developer. @JS_Kowontan

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade