The Monte Hall 'Make a Deal' Problem

One of the most controversial recreational problems is the Monte Hall Problem. The idea stems from the original game show entitle 'Let's Make A Deal.' The problem appeared first in an article by Steve Selvin in the journal American Statistician.

The problem gained attention when it became the object of a Marilyn Vos Savant column in Parade magazine where it was stated in the following form:

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 is 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 says that the probability of obtaining the car improves if you switch. Many people find this answer runs counter to intuition. This answer like all answers depends on the assumptions that are made especially in regard to the statement

the host, who knows what is behind the doors,...

If we assume that the strategy of the host is to minimize the number of cars given away, then he will not always show the contestant a goat, but the common assumption in the problem is that the host will always show a door that has a goat behind it.

Let us assume that the host does show a goat to the contestant no matter which door is originally chosen. The probability that the car was originally chosen is 1/3rd. The probability that the contestant did not chose the car is 2/3rds, so it follows that the contestant will obtain the car 2/3rds of the time by switching after the host shows a goat.

It is easier to see this relation by considering the question when the number of doors is large. For instance, suppose there are 100 doors. We further assume you pick one door at random and then the host opens 98 doors with goats in them. Obviously, the probability is 1/100 that you originally picked the right door and the probability that the car is behind the remaining door is 99/100.

But suppose the host wishes to minimize the likelihood that the contestant will get the car. What strategy ought he to pursue ?

The Lottery Paradox

Consider the following lottery problem:

• one million tickets are sold for one dollar each
• one ticket is chosen and the owner of the ticket wins the entire pot

The probability of any one ticket winning is 1/1000000. In other words, the probability of winning is nearly zero but the collective sum of these probabilities is 1.

The paradox involves the rationality of belief. It is rational to believe that one individual ticket may win but the conglomeration of this rational belief leads to the belief that no ticket can win which is clearly a false belief.

The paradox is related to the question of knowledge and the the accumulation of nearly perfect knowledge which leads to a false conclusion. This is not a mathematical paradox in the sense that nearly perfect knowledge of the truth of a set of hypothesis does not even allow one to conclude that even one of the hypotheses hold.

On the one hand, we have mathematical methods which give one result, but on the other hand, we have a philosophical approach which leads to confidence, not certainty, in another result.

A practical example of this problem occurs in digital communication. In a communication channel, like the channels used to distribute web-pages over the internet, there is a small possibility that a digit can be changed during transmission. While the probability is extremely small for any one digit, the conglomeration of millions of digits implies that eventually an error will occur. Internet protocols generate a method for correcting the errors, when they occur, in most cases.

The Sleeping Beauty Paradox or the Computer Decision Tree Problem

The Sleeping Beauty Paradox grows out of the Absent-Minded Driver Paradox which in turn stems from a computer programming problem studied by M. Piccione and A. Rubenstein in the journal Games and Economic Behavior, 1997. We first consider the form of the problem ( rather than paradox) as stated in the so-called Sleeping Beauty Paradox. Here is the problem as originally posed by Jamie Dreier in an internet recreational puzzle discussion group:

• We plan to put Beauty to sleep by chemical means, and then we'll flip a fair coin, i.e. the probability of heads is 1/2 and the probability of tails is 1/2.
• If the coin lands heads, we will awaken Beauty on Monday afternoon and interview her. If it lands tails, we will awaken her Monday afternoon, interview her, put her back to sleep, and then awaken her again on Tuesday afternoon and interview her again.
• In each case the interview is to consist of the one question: what is your credence now for the proposition that the flipped coin landed heads?
• Under no circumstances will Beauty be able to tell which day it is, nor will she remember whether she has been awakened before. She only knows the details of the experiment.
• What credence should she state in answer to the interview question?

In the form of the Absent-Minded Driver one version allows that there consequences for poor choices. Hence, the problem involves what is called the maximization of the expected outcome. As stated, the Sleeping Beauty Problem asks the question: what credence should Sleeping Beauty give to the two outcomes of the coin toss?

This question does not make clear what is meant by credence. It appears that rather than restating the Absent-Minded Drivers Problem, the Sleeping Beauty problem is inspired by it and only closely related to it. Most interpretations of the Sleeping Beauty Problem give a solution in terms of probability theory and this seems to be a reasonable approach. Some interpretations appear to consider the question of credence to be related to expected correct answers.

How should the game be interpreted and what is the correct answer under the various interpretations?

More on the Unexpected Hanging

See the problem "The Inevitable Surprise" below for the initial discussion.

Some authors consider the problem of the unexpected hanging to be an example of an actual paradox, meaning that the sentence of the judge is self contradictory. Assuming that the judge has seven days to choose from, we have shown using game theory that the the sentence is not self contradictory. But consider the reduced problem where the judge pronounces the sentence on Thursday saying thatt the hangman will appear at the jail cell on Friday or Saturday and the hangman will be unexpected.

The assumption are:

1. The judge's statement is true;
2. Predicate logic holds.

Under these assumptions we can see that

• If the judge chooses Saturday, then the hangman will be expected;
• The judge must choose Friday, so by the previous statement the prisoner ought to expect the hangmen on Friday.
• If the hangman can be expected on Friday, then the judges statement is false and so the statement is self-contradictory.

Some authors claim that the reason for this paradox is that the judge's sentence is self-referential. More on this at the Mathematics Resolution link at the top of the blog.

The Inevitable Surprise

In Martin Gardner's book The Unexpected Hanging and other Mathematical Diversions, a logic puzzle is proposed according to which a judge pronounces on a Saturday a sentence of hanging. In addition, the sentence will be imposed in such a way that the hangman will appear at the jail cell door at noon on some day during the following week beginning with Sunday and extending to Saturday. Finally, the appearance of the hangman will occur on a day that the prisoner does not expect.

There are many versions of this puzzle including the original version in which an air raid warden announces that there will be a surprise drill at 8 p.m. some night in the next seven days. Of course, such a statement could be said of a pop quiz or any military drill. Part of the controversy in each case is the question as to whether this sort of statement can be absolutely true.

Gardner does a very good job of outlining the paradoxical nature of the problem. On the one hand, the prisoner's lawyer argues that if the prisoner is not hanged by Friday, then the predicted surprise can not occur on Saturday at noon since then the judge's statement would have been false. Hence the purported contradiction to the judge's pronouncement of sentence. But we must assume that the judge's sentence is a statement of fact and so the prisoner must be hanged on some day before Saturday. If this must be true, then we can conclude that if the prisoner is not hanged by Thursday, then he will know that the judge can not delay the hanging until Saturday and so will know for a certainty that he can not be hanged on Friday.

Likewise, if the prisoner is not hanged on Wednesday, he will know that he cannot be hanged on Friday or Saturday and so he must expect the hangman to come on Thursday. But the hangman can not come when expected, so He can not be hanged on Thursday, Friday or Saturday.

The argument continues in this fashion so that it is clear to the prisoner that there is no day which the judge may pick for which the prisoner will not expect the hangmen. Secure in this knowledge the prisoner does not expect the hangman when he appears on Wednesday at noon. See comments for a discussion