The Sleeping Beauty Problem

I will begin the discussion of the Sleeping Beauty Paradox by considering a variant of the problem:

• Imagine that we have a smart computer that accurately calculates the answers to probability questions that are put to it;
• a coin is flipped and the outcome recorded but not input into the computer data base;
• the computer has no clock and the memory is erased when it is turned off;
• when the computer is turned on it boots into exactly the same memory state;
• each time the computer is turned on it is given the information concerning this experiment;
• if the coin lands heads, then the computer is turned on once and asked to decide the "credence" that the coin is heads;
• if the coin lands tails, then the computer is turned on and asked to decide the "credence" that the coin is heads, it is then turned off and turned on again and asked to decide the "credence" that the coin is heads.

The first obvious fact is that if the coin lands tails, there is no difference between the first and second interview. Indeed, there is no difference, as far as the computer can tell, between any of the interviews. Likewise when the coin lands heads, there is nothing that precludes us from turning the computer off and restarting the computer and interviewing it.

In other words, the anti-symmetric nature of the original problem is something of a red herring. The only analysis that the computer can give is that the probability that the coin was heads is 1/2 which is also the obvious answer.

Now let us consider a slightly different question: Which answer maximizes the expectation of being correct. We have the following slightly more complicated example:

• the probability of heads is p and tails is 1- p;
• if the coin lands heads, then we will interview the rebooted computer k times;
• if the coin lands tails, we will interview the rebooted computer n times;
• we will add 1 to the score for each correct guess by the computer;
• the computer will maximize the expected score.

Now assume the following strategy and outcome:

• the computer answers heads at random with probability q and otherwise tails;
• if the coin lands heads, then the expected number of correct answers is qk;
• if the coin lands tails, then the expected number of correct answers is (1-q)n;
• the expected number of correct answers for the problem is pqk+(1-p)(1-q)n

Can you determine the maximum score and the maximum strategy in each case? See comment.

More About 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 assumptions 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.

What is a self-referential statement?

A self-referential statement is a statement that can contains in it a reference about the statement. For instance:

This statement is false.

If we analyze this sentence we see the following:

• If the statement on its face is true, then we must conclude that the statement is in fact false;
• If the statement is on its face a false statement, then we can conclude that the statement represents a true fact.

We must conclude that the statement is self-contradictory. The fact that a statement is self-referential does not mean that it is contradictory, but it does hold the potential to be self-contradictory since it may contain information which implies two equally valid logical arguments which are not consistent. See comment for more.

The Inevitable Surprise

If necessary read the introduction to this problem on the Mathematics Recreation blog using the link at the top of the page

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.

On reflection, it becomes clear that since the judge has several days to pick from for the execution, it is impossible to predict at the sentencing which day the hangman might appear. Consider the following variation: The hangman will appear at the cell door at any time in the week, and his appearance will not be expected. In this context, the statement of the judge seems entirely reasonable from the point of view that there are almost an infinite number of possibilities.

Let us consider another version: the judges claims that the hangman will appear at the cell door at noon on some day within a year of the sentence. The lawyer's argument can be restated but it now appears to lack credibility. The year long wait is a middle case between the case of seven choices in the original sentencing and essentially infinitely many choices posed in the paragraph above.

Let us consider one last version: the judge claims that the sentence will be carried out on Friday or Saturday. In this version, unlike the other versions it is quite clear that the judge can not pick Saturday for the hanging since the hangman will surely be expected. We must analyze this version from a different perspective. First of all, what does it mean to expect the hangman? It might mean that one has 100 per cent certainty of the day the hangman will appear at the very time the sentence is pronounced. If this is a correct interpretation, then the judge is free to pick either day and the prisoner will be unable to predict the day with 100 certainty.

A second question that arises from this analysis is: what is the meaning of the word surprise? Does surprise mean that you are convinced that the hangman will definitely not appear only to find out that he appears. In the initial version of the problem (i.e. the hangman may appear on Sunday at noon through Saturday at noon) , the prisoner’s lawyer advances an argument that convinces the prisoner that the judges sentence can not be carried out and so the prisoner will escape the hangman. The implication is that the judge will realize that he has made a self-contradictory statement and will then declare the sentence unenforceable and hence the prisoner will escape the execution of that same sentence.

On the other hand, when the prisoner begins to believe that he can not be hanged, he is in constant danger of being surprised by an unexpected hangman. As you might already see, many of the problems that must be overcome in this sort of logical conundrum involve the ambiguity of the wording no less than the ambiguity of the meaning of words themselves. There is ambiguity in the meaning of the word “surprise”. There is a sort of implicit understanding of this and yet an attempt is made to gloss over this fact and pretend that the meaning is quite clear. There is an ambiguity in the use of the word “expect”. Again there is a variation of interpretations in the solution of the problem. This leads to the controversies among analysts.

Logical puzzles such as these make interesting controversies when the parameters and definitions of the problem are left undefined. The advantage of careful definitions is that everyone can agree with a correct solution once it has been posed. The disadvantage of a careful mathematical treatment is that everyone may not accept that the premises of the mathematical problem as it is posed are the correct premises.

To give a careful analysis of this problem we will apply the mathematical methods of game theory. We begin by defining the game. The problem that we have before us can be discussed in a variety of settings. We will use the following setting as a model for the game.

Before us there are several boxes, say 10. Each box is labeled with a number starting with 1 and going to 10. Inside one of the boxes is hidden an egg. There are two players. Player A hides the egg in one of the boxes and selects box 1 and asks Player B whether he can prove that the egg is in box 1. Player B must respond with a “yes” or a no”. If “yes ”, then Player B must provide the proof. The process continues until the egg is uncovered or Player B makes a claim and fails to prove it or having proved the claim discovers that the egg is not in the given box.

If the egg is placed in box 10 , then for Player B to win, Player B must have responded “no” for each box up to box 10. When Player A finally chooses box 10 and asks if Player B knows whether the egg is in box 10, then Player B, may clearly respond “yes” and give a correct proof, by observing that the egg is in one box but it is not in boxes 1 through 9. Therefore it must be in box 10. This is a correct proof and so in this case Player B wins.

We have reduced the problem to a problem of knowledge. But this is the only case in which Player B can win. If this case is allowed, and we assume that it is, then Player A will win every time the egg is placed in a box other than 10. It is only by assuming that Player B may not win, that it makes any sense to eliminate this possibility.

But you may object that since the judge’s statement is assumed to be true, that in the case of the unexpected hanging, Saturday is not a possible choice. But as we can see from the game, box 10 is a potential choice but not a legitimate choice. If Player B, does not see box 10 as a potential choice, then he may say “yes” when box 9 is presented. Unfortunately, he can not prove with 100 per cent certainty that the egg is in box 9 without already knowing that Player A’s strategy includes only placing the egg in boxes 1 through 9. It may well be that Player A will never choose box 10, but Player B can not prove that this choice is not possible.

For instance suppose that Player A is aware of Player B’s reasoning or at least expects that Player B may reason that Box 10 can not be picked. Then Player A is free to choose box 10 on the basis that Player B will say “yes” when asked about box 9. In such a case, the argument that Player A can not choose Box 10 will then be invalid in as much as Player A has already done so and consequently wins when Player B then says “yes” for box nine. Even if the egg is in box nine it can not be proven to be in box nine.

From this analysis we can see that one must already know the strategy of Player A in order to prove that the egg is in box nine. Without this knowledge Player B can not win whenever the egg is placed in a box other than 10. Observe that the game theory analysis leads to a clear and complete solution. In particular, we are able to see that box 10 is a potential choice even though it need never be an actual choice. The freedom to choose box 10 makes it impossible to give a proof that the egg can be in box 9 or any other box for that matter.

What now becomes obvious is the fact that the contradiction lies in the obsevation that the probability that the egg was in box 9 instead of box 10 is very nearly 1. This means that for all practical purposes we would be correct to say that the egg is in box 9, but unfortunately, this is not a proof. There is an ambiguity in natural language between an absolute certainty in the mathematical sense and a near certainty in a philosophical sense. Most people consider a near certainty to imply a certainty. In particular, it is impossible to assign a probability to the question of whether or not the egg is in box 9, given that it was not in one of the first 8 boxes.

To understand the premises of the game more fully, consider the case such that the boxes are not numbered. The question that may now be asked is whether this case is actually different than the numbered box case. From the point of view of Player B it appears that the only plausible strategy is to wait until nine boxes have been revealed which do not contain the egg. Again, Player

B may win the by saying “yes” to box ten and then giving a valid proof that the egg must be in the tenth box to be revealed. Again strategy plays a role. It may be that Player A never chooses to leave the egg reveal until the 10th box, but can Player B know this to a certainty?

Let us leave game theory analysis to the side for a moment and assume that the word expect merely means that we think the probability of the egg being in a certain box is nearly one, i.e. the probability is say 99 per cent. Do the number of boxes actually matter with regard to a solution? Obviously there must be always more than one box. If there are say 100 boxes, then common sense tells us that no argument can can convince us that we expect the egg to be in any one box provided that Player A does not choose to place it anywhere near box 99. The same result would hold for say 10 boxes.

Now let us narrow the field to 2 boxes. In this case, strategy must play a role. If Player B believes that Player A will always put the egg in the first box, then Player B may reasonably expect that the egg will be in the first box. But now the conditions and the strategy change. The question now should be: can Player B predict the box that the egg is in before the answer is revealed by opening box 1? Admittedly, this is a different question than the case of the judge’s sentencing, since the judge claims that the prisoner will in fact be surprised at a specific time and place. It is true: we have changed the question somewhat in the case of 2 boxes, but in any case, Player A must play a mixed strategy for the case of 2 boxes in which case, provided that the strategy is essential a random choice among the two boxes, then Player B can never accurately predict the box from which the egg will appear.

My motto is: Expect the Unexpected.