Comment Permalink

nerzhin14y110

There is an enormous (far too enormous for its value to the world, in my opinion) literature on the unexpected hanging paradox (also known as the surprise exam paradox) in the philosophy and mathematics literature. The best treatments are:

Timothy Y. Chow, The surprise examination or unexpected hanging paradox, American Mathematical Monthly 105 (1998) pp. 41-51. (ungated)

Elliot Sober, To give a surprise exam, use game theory, Synthese 115 (1998) pp. 355-373. (ungated)

SilasBarta14y30

far too enormous for its value to the world, in my opinion

The paradox actually has practical implications. It shows a general mechanism by which you can "surprise" someone despite a predictable outcome. It goes like this:

1) You tell someone they will be "surprised" by an upcoming event (e.g., what gift you will buy them).
2) They start to suspect it will be one of a number of unusual outcomes.
3) The event actually has its regular, boring, predictable outcome.
4) But the other person is still surprised, since they did not expect the ... (read more)

2cousin_it14y

Yeah, came here to say the same. Thanks. When I tried to solve this problem about 10 years ago, I came up with the equivalent of Fitch's "Goedelized" solution, described on pages 5-6 of Chow's article. I'm still not sure why many people consider it wrong; it seems to utterly dissolve the "paradox" for me.

See in context

13 Resolving the unexpected hanging paradox

by AlexMennen

25th Jan 2011

2 min read

13

The unexpected hanging paradox: The warden tells a prisoner on death row that he will be executed on some day in the following week (last possible day is Friday) at noon, and that he will be surprised when he gets hanged. The prisoner realizes that he will not be hanged on Friday, because that being the last possible day, he would see it coming. It follows that Thursday is effectively the last day that he can be hanged, but by the same reasoning, he would then be unsurprised to be hanged on Thursday, and Wednesday is the last day he can be hanged. He follows this reasoning all the way back and realizes that he cannot be hanged any day that week at noon without him knowing it in advance. The hangman comes for him on Wednesday, and he is surprised.

Supposedly, even though the warden's statement to the prisoner was paradoxical, it ended up being true anyway. However, if the prisoner is no better at making inferences than he is in the problem, the warden's statement is true and not paradoxical; the prisoner was executed at noon within the week, and was surprised. This just shows that you can mess with the minds of people who can't make inferences properly. Nothing new there.

If the prisoner can evaluate the warden's statement properly, then the prisoner follows the same logic, realizes that he will not be hanged at noon within the week, remembers that the warden told him that he would be, and concludes that the warden's statements must be unreliable, and does not use them to predict actual events with confidence. If the hangman comes for him at noon any day that week, he will be unsurprised, even though he is not confident that he will be executed that week at all either. The warden's statement is then false and unparadoxical. This is similar to the one-day analogue, where the warden says "You will be executed tomorrow at noon, and will be surprised" and the prisoner says "wtf?".

Now let's assume that the prisoner can make these inferences, the warden always tells the truth, and the prisoner knows this. Well then, yes, that's a paradox. But assigning 100% probability to each of two propositions that contradict each other completely destroys any probability distribution, making the prisoner still unable to make predictions, and thus still not letting the warden’s statement be both paradoxical and correct.

If someone actually tried the unexpected hanging paradox, the closest simple model of what would actually be going on is probably that the warden chose a probability distribution so that, if the prisoner knew what the distribution was, the prisoner’s average expected assessment of the probability that he is about to get executed on the day that he does is minimized. This is a solvable and unparadoxical problem.

Logic & Mathematics Paradoxes

Personal Blog

13

New Comment

41 comments, sorted by

top scoring

Click to highlight new comments since: Today at 2:07 PM

[-]nerzhin14y110

Timothy Y. Chow, The surprise examination or unexpected hanging paradox, American Mathematical Monthly 105 (1998) pp. 41-51. (ungated)

Elliot Sober, To give a surprise exam, use game theory, Synthese 115 (1998) pp. 355-373. (ungated)

[-]SilasBarta14y30

far too enormous for its value to the world, in my opinion

The paradox actually has practical implications. It shows a general mechanism by which you can "surprise" someone despite a predictable outcome. It goes like this:

I know of a major case where this reasoning was applied: on one season of the TV show The Apprentice. (The show where people try to get a job with Donald Trump and one person is eliminated from consideration ["fired"] each week.) During the second episode/competition, one contestant walked out due to frustration, and she didn't come back until evaluation time.

Then, in ads for the next episode, they said, "Next time, on The Apprentice, one candidate will quit the competition -- and you'll never guess who it is!"

This, of course, prompted speculation that someone other than the last episode's quitter would be the one to quit ... but no, it was the same woman who left, this time permanently, rather than being fired. Well, it was certainly a suprise by that point!

[-]cousin_it14y20

Yeah, came here to say the same. Thanks.

When I tried to solve this problem about 10 years ago, I came up with the equivalent of Fitch's "Goedelized" solution, described on pages 5-6 of Chow's article. I'm still not sure why many people consider it wrong; it seems to utterly dissolve the "paradox" for me.

[-]Skatche14y60

You know, I just don't understand why the prisoner is so surprised when he's executed on Wednesday - I mean, the executioner comes on Wednesday every single time I read about this thing, and it's just not that surprising anymore.

[-]Dufaer14y20

OK, let’s look at this: The prisoner receives 2 pieces of information from the warden at the beginning:

The first piece of information is: He will be killed at noon of one day of the next five days.

Assuming that the warden's claim is true, there are 5 possible outcomes:

Death at noon of Mon, Tue, Wed, Thu or Fri.

Assuming furthermore that the prisoner has no other information that and that he uses probability theory, he will construct the following uniform probability distribution:

P(Death at noon of X.)=1/5 where X can be Mon, Tue, Wed, Thu or Fri.

Furthermore he can now also infer the conditional probabilities

P(Death at noon of X.|Not dead after noon of Mon.)=1/4 for X = Tue, Wed, Thu or Fri.

P(Death at noon of X.|Not dead after noon of Tue.)=1/3 for X = Wed, Thu or Fri.

P(Death at noon of X.|Not dead after noon of Wed.)=1/2 for X = Thu or Fri.

And finally:

P(Death at noon of Fri.|Not dead after noon of Thu.)=1

Thus the prisoner will now be not 'surprised' only by a death at noon of Friday. As in: The occurring event had P>1/2.

Is this the proper notion of 'surprise'?

I don't think so. - Surprise should be always measured quantitatively.

But observe that in the 'death at noon of Friday' scenario there is no surprise whatsoever. It is qualitatively absent under the condition that the warden speaks the truth:

P(Death at noon of Fri.|Not dead after noon of Thu., The warden speaks truth.)=1 P(Death at noon of Fri.|Death at noon of Fri.)=1 (duh) There is no updating.

The second piece of information from the warden is:

The prisoner will be surprised by his death.

What does this mean, anyway? Can we actually alter our probability distribution based on this datum?

I highly doubt that, but the prisoner in the canonical treatment certainly does update: As it holds that:

P(Death at noon of Fri.|Not dead after noon of Thu.)=1

He concludes:

P(Not dead after noon of Thu. AND The prisoner will be surprised by his death.)=0

And:

P(Death at noon of Fri.|Not dead after noon of Thu., The prisoner will be surprised by his death. )=0

As a special case of 'P(Anything.|Contradiction.)=0'

He then runs a few iterations and concludes that all outcomes have the P=0 under all conditions.

Here the background assumption is still that the warden's words are true. This assumption however is contradictory if the updating procedure of the prisoner is correct. But we can easily see that the new belief structure of the prisoner will be surprised by any of the outcomes; rendering the warden correct. Thus the paradox.

The solution is simply that the prisoner's updating procedure is incorrect.

The datum 'The prisoner will be surprised by his death.' does not warrant the update. The warden's statements are contradictory if the original belief structure is retained and if the only remaining outcome is death at noon of Friday. However, after the first change of the belief structure by the prisoner this no longer holds. The further 'iterations' make even less sense and the whole 'update' is unstable, as our simple reflection shows - now the prisoner will be surprised by any outcome.

So obviously, this is not Bayesian updating.

The prisoner tried to reason. Concluded that he couldn't be killed without proving the warden wrong. Changed his probability distribution over outcomes to reflect this. Thus changing the prerequisites for his initial conclusion. He did not examine the implications of the changed prerequisites. Ensuring that the warden could always be right.

He thus updated wrongly - his believes do not reflect reality.

Observe that the outcome 'The warden was correct.' and it's negation 'The warden was incorrect.' regarding the proposition 'The prisoner will be surprised by his death.', given 'He will be killed at noon of one day of the next five days.' depend solely on the belief structure of the prisoner.

Given that a belief structure is normally used by an agent to maximize utility and yet the prisoner is not an agent (he lacks a utility function), the belief structure is inconsequential apart from proving the warden right or wrong. The shaping of the structure is the only choice given to the prisoner and as such it can be hardly called a structure of belief at all.

If there was a non-constant utility function over 'The warden was correct.' and 'The warden was incorrect.', this would be a 'belief-determined problem' which is likely an inconsistent class of problems by itself - an agent trying to maximize such a problem would have to simultaneously represent the problem and 'believe' in things which generally contradicting this representation in order to maximize the payoff, thus making the 'belief' something indistinguishable from a 'mere' decision.

Nevertheless, in the canonical treatment the prisoner ensured by 'incorrect' updating that the warden was always right.

Likewise, we can construct an 'incorrect' belief structure that ensures that the warden will always be incorrect:

P(Death at noon of day #(N).|Not dead after noon of #(N-1).)=1

This structure will be 'surprised' by any survival, as it expects certain death each day.

Of course, this is total BS from the perspective of probability theory, but so is the original updating scheme.

[-]Anatoly_Vorobey14y20

concludes that the warden's statements must be unreliable, and does not use them to predict actual events with confidence. If the hangman comes for him at noon any day that week, he will be unsurprised, even though he is not confident that he will be executed that week at all either.

"Surprised" in this paradox merely stands for "you will not be able to predict the hangman's appearance on any given day before the hangman appears". So if the prisoner chooses not to believe the warden's statement, that still leaves him surprised when the hangman comes.

[-]AlexMennen14y00

True. I was thinking of "surprised" as "assigned a small probability to" rather than "did not assign 100% probability to". If we use the latter interpretation, then there is more interesting contradiction. So much for my resolution.

[-]SilasBarta14y10

Information theory has useful concepts for this situation (as usual). It uses the term "surprisal" as a way to quantify how surprising an outcome is. It is equal to the log of the inverse of the probability ( log (1/p) ) you had assigned to an event before you learn that it happened. [1]

What surprisal value should the judge's statement be interpreted as meaning? One first approach would be to say that the judge means the prisoner will find the result more surprising than if he had simply assumed an equal probability to the seven days. Thus, the judge is saying that "the surprisal, or information gain, from learning your execution date will be greater than log(7)."

So, uh, how on earth are you supposed to move your probability distribution over execution days upon being given that kind of evidence? If you (wisely) start from a uniform probability distribution, you already have, in expectation, the maximum surprisal value. (Entropy is equal to the "expected" [i.e., probability-weighted] surprisal, and a uniform distribution is maximum entropy.)

No change in probability distribution can increase the expected surprisal -- unless, of course, you deliberately skew your PD so that it decreases the weight on when you "really" expect to be executed. But then that brings up the messy issue of what you really believe vs. what you believe you believe.

[1]Consequently, it is equal to how much information you get upon observing the event -- observing improbable events tells you more than observing probable ones. Intuitively, do you learn more from when a suspect says they're guilty, or when they claim innocence?

[-]John Paul Logan5y10

the issue i see here is it is only a paradox if it requires the judge tells the truth and is always correct. but if that is the case then the prisoner is concluding that the judge is lying or made a mistake when he concludes he will not be hanged. so since the conclusion he won't be hanged is a contradiction itself how can he conclude it is definitely true? if he can't conclude his conclusion is definitely true then he will be uncertain each day

[-]MinibearRex14y00

The main issue is how intelligent the prisoner is. As it is, the prisoner used some clever logic to prove that he will not be executed that week, failing to consider the possibility that the judge will predict that. If he thought about it a bit more, he might realize that in fact the judge might well be anticipating that, and therefore, expect the hangman to come on any given day.

Then, if he kept thinking, it might occur to him that it is possible that the judge predicted that too, and so might not send the hangman. However, the judge is capable of making mistakes. He is human. So, the prisoner can come to the conclusion that he may well be hanged this week, even though it won't be a surprise, or that the hangman will not come, and in fact the judge has predicted him perfectly.

This paradox is only confusing (from the prisoner's standpoint) if you consider the judge to be infallible. He's not. If the judge were Omega, on the other hand, we might run into some problems.

[-][anonymous]14y00

Consider the sentence "AlexMennen does not believe this sentence". If you believe it, you're wrong. If you don't, you're wrong.

I think the sentence "AlexMennen will be hanged tomorrow but will believe he won't be hanged" is similar. If you tomorrow believe it, you believe a contradiction and therefore you're wrong. If tomorrow you don't believe it, you get hanged and proven wrong.

[-]Ultima14y-10

I'm totally confused.

Why would anybody in that situation ever be surprised?

I mean, they would know that somebody will execute them at noon on one of the days (monday, tuesday, wednesday, thursday, or friday). No matter what day it come on, why would they be surprised? If it comes at noon on monday, they would think, "Oh, it's noon on monday, and I'm about to die; nothing surprising here." If it doesn't come at noon on monday, they would think, "Oh, it's noon on monday, and I'm not about to die; nothing surprising here (I guess that it will come on one of the other days)." Or whatever.

(Assuming that the the warden told the truth, and the prisoner assumed that.)

[-]Costanza14y120

This is an old problem, and apparently it's a lot harder than it looks. Wikipedia says 'no consensus on its correct resolution has yet been established.'

My preferred solution, if the question is posed in vague enough language, is for the warden to show up just before noon on Friday to hang the prisoner, while wearing a sequined evening gown and scuba gear in place of his usual uniform. The prisoner didn't see that coming!

[-]Ultima14y20

Perfect!

[-]benelliott14y00

For the purposes of the problem, to be surprised just means that something happened to you which you didn't predict beforehand.

Its not the usual definition (among other things it implies I should be 'surprised' if a coin I flip comes up heads) but presumably whoever first came up with the paradox couldn't think of a better word to express whatever they meant.

[-]Ultima14y00

For the purposes of the problem, to be surprised just means that something happened to you which you didn't predict beforehand.

Okay, I understand that.

Its not the usual definition (among other things it implies I should be 'surprised' if a coin I flip comes up heads) but presumably whoever first came up with the paradox couldn't think of a better word to express whatever they meant.

But I don't understand that.

I mean, why couldn't I simply predict that it would be heads or tails?

[-]benelliott14y00

Can you accurately predict whether a coin will come up heads or tails? I can't.

[-]Ultima14y00

No, but I can accurately predict that a coin will come heads or tails.

[-]John Paul Logan5y10

what if it lands on its edge like in batman

[-]benelliott14y00

Okay, it seems we have hit another problem with words.

For the purposes of this definition to predict something means to have sufficient evidence to assign it a probability very close to 1.

[-]Ultima14y00

Oh okay.

[-]Ultima14y00

Then wouldn't the prisoner be surprised no matter what?

But, wait, when exactly are we judging whether he's surprised?

Let's say that it's thursday in the afternoon, and he's sitting around saying to himself, "I'm totally surprised that it's going to come on friday. I was online reading about this exact situation, and I thought that it couldn't come on friday, because it would be the last available day, and I would know that it would be coming." Or are we waiting for that surprise to dissipate, and turn into "well, I guess that I'm going to die tomorrow"?

From what I can see at this point, I think that the "paradox" comes of an equivocation between those two situations (being surprised right after it doesn't happen, and then having that surprise dissipate into expectation). But I could be wrong.

[-]benelliott14y20

The improper use of surprise is distracting you from the main point here, so I suggest you ignore it.

Allow me to rephrase:

The warden tells a prisoner on death row that he will be executed on some day in the following week (last possible day is Friday) at noon, and that on the day he is hanged he will not know he is going to be hanged until he sees the man with the noose at his cell door.

Not as pithy, but that's the price you sometimes pay to avoid ambiguity.

[-]Ultima14y00

Sounds like a garden variety contradiction.

(If it's past noon on thursday, obviously he would know that it's going to come the next day at noon; the warden simply would have been wrong.)

Or am I still misunderstanding it?

[-]John Paul Logan5y10

the paradox is because the prisoner would know the hangman will come at noon on friday if he is alive thursday afternoon he wouldn't be surprised if he did come. then he concludes that it can't come friday because he would predict it and be not surprised. but since the judge knows he will say it can't happen on friday he will actually be surprised if the hangman does come on friday

[-]prase14y00

If the warden is wrong, the paradox is no more. The paradox depends on the assumption that the warden tells the truth, and the prisoner knows for certain that the warden tells the truth.

[-]Ultima14y00

Then here's an analogous "paradox":

There were two men standing in front of me. One said that the ground was red, and the other said that it was blue. Neither of them are ever wrong.

So, yeah, that's why I said that it sounds like a garden variety contradiction.

[-]prase14y00

That's not exactly like that, is it? In the hanging paradox the warden was correct in the end. There was no contradiction, at least not one easy to pinpoint.

[-]Ultima14y00

the warden was correct in the end

Where?

[-]prase14y00

The warden had made two statements:

The prisoner will be hanged on one of the five specified occasions.
The prisoner will never know for sure when he is going to be hanged before the hangman comes.

Both statements are true. In your "paradox" at least one man is wrong.

[-][anonymous]14y00

What if the prisoner were thinking about it in the afternoon on thursday?

[-]Ultima14y-10

What about if the prisoner is still alive on thursday in the afternoon?

[-]prase14y00

He is executed on wednesday. The warden knew it all along. And even if he didn't, his statements are true.

[-]Ultima14y-10

Wait, why on wednesday?

[-]prase14y00

The hangman comes for him on Wednesday, and he is surprised.

This is how it is described in the original post.

(I have a weak feeling that you may be making fun of me. If so, my sense of humour is probably incompatible with yours. If not, please include some explanation to your questions, I find it hard to guess what exactly you disagree with and why. Thanks.)

[-]Ultima14y00

Wasn't that line (the one saying that the hangman comes for him on wednesday) just supposed to be an example? I didn't think that the problem required the hangman to come on wednesday; I thought that it left open when he would actually come.

(And, no, I'm definitely not making fun of you.)

[-]prase14y00

Sorry for misinterpretation, then.

I suppose Wednesday was not required, but if you accept the story as it is told, then it is counterfactual to ask "what if the prisoner was still alive on Thursday evening". But even if he were, since he deduced that he couldn't be hanged, he would be surprised even then, after the hangman appeared on Friday. (Some interpretations may require the hanging to happen sooner than Friday to preserve paradoxness.)

This comment links to a good article by Chow, where he analyses the paradox in detail from different points of view, and shows that there is indeed a contradiction in one specific (reasonable) interpretation of the paradox, but it isn't apparent because the interpretation relies on self-referential formulation of the problem. It is far less clear than "X says A, Y says not A, both are right".

[-]AlexMennen14y00

Benelliott worded it well. Your objections are similar to the ones I was raising.

[-]Ultima14y00

Oh, I see.

At first, I missed the significance of this passage:

The warden's statement is then false and unparadoxical. This is similar to the one-day analogue, where the warden says "You will be executed tomorrow at noon, and will be surprised" and the prisoner says "wtf?".

[-]TheOtherDave14y00

(blink?)

Does the same reasoning not tell you that nobody is ever surprised by their death? I mean, I know I will die on some day, but if I have a fatal heart attack right now I'd certainly be surprised.

[-]Ultima14y10

Sure, you would be surprised that you were about to die now.

But would you also be surprised that your life didn't end up being eternal? No, because you know that you will die someday.

But what's the significance of this distinction for this problem? Well, I don't understand how the prisoner could think anything other than, "I guess that I'm going to end up dead one of these days around noon (monday, tuesday, wednesday, thursday, or friday)." It's not like he has any reason to think that it would be more likely to happen one of the days rather than another. But, in your example, you do have a reason for that (dying now would be less likely than dying later).

But, wait, isn't that the whole issue in contention (whether he has any reason to think that it would be more likely to happen one of the days rather than another)? Yeah, so let me get back to that.

Let's say that the hangman shows up on the first day at noon (monday). Would the prisoner be "surprised" that it was monday rather than one of the other days? Why would he? He wouldn't have any information besides that it would be on one of those days. Or let's say that the hangman shows up on the second day at noon (tuesday). Would the prisoner be "surprised" that it was tuesday instead of one of the other days? I mean, why would he? He wouldn't have any knowledge except that it would be on one of the next 3 days.

I'm completely confused by this "paradox".

Maybe you could help me out?

Moderation Log