I wrote this some time ago but have never posted it to the 'net. A brief Google search didn't turn up any similar papers or writings on this. So, here's my solution:
Shannon and the Hangman
Shannon Information
Information or surprisal is a measure of the decrease in uncertainty at the receiver. Uncertainty is proportional to entropy and the expected surprisal. Very probable symbols do not decrease the uncertainty about the transmitted message at the receiver as much as very improbable symbols do.
Entropy is not interchangeable with information since entropy is really the weighted average or expected value of the information.
In the presence of noise, the uncertainty does not decrease at as great a rate as it does in the absence of noise. When the noise is great enough, the decrease in uncertainty is zero (no information can be communicated). When the rate of transmission is large enough, the rate at which the code is decreasing our uncertainty is as large as it can be.
Information theoretic analysis of the unexpected hanging paradox
Relax the conditions by allowing the day on which the prisoner will be hanged to be announced ahead of time instead of on the day itself. This removes the logical dependencies.
"I am going to tell you the day on which you will be hanged. It will be sometime in the next x days, and you will be surprised."
As long as x > 1, the judge is telling the truth. Let us assume that x = 8. How surprised will the prisoner be when he hears which day he will be hanged? If the judge uses coin tosses to decide his day of execution, then the prisoner will receive exactly 3 bits of self-information, which is identically equal to his surprisal.
This result is theoretically sound and self-evident from an information theoretic point of view. We now replace the logical dependency introduced by saying that his day of execution will be told to him on that day.
Let us set x = 8 again. From an information theoretic point of view, this is equivalent to saying, "You will receive up to seven clear bits and a stop bit (set). Which code you receive will surprise you."
First, note that there is actually a distribution of surprisal:
1 3 bits 01 2.8 bits 001 2.6 bits 0001 2.32 bits 00001 2 bits 000001 1.58 bits 0000001 1 bit 00000001 0 bits
We can see how this is the case by assuming that the judge chooses by a lottery, perhaps using an urn with x-1 white balls and 1 black ball. Each day that the judge draws a white ball, the information content of drawing the black ball on the next day's lottery decreases. On the first draw, the surprisal of drawing the black ball is 3 bits, but if a white ball is drawn, then the surprisal will be 2.8 bits the following day if the black ball is drawn and so on.
The paradox arises because the judge has stated that the prisoner will be surprised on the day when he finds out he is to be hanged - if the judge were to draw 7 white balls, then there is no need to do a further drawing since the only ball left in the urn is the black ball. Therefore, the prisoner cannot be surprised on the 8th day after 7 white balls have been already drawn.
There is a discrepancy between two, very similar senses of the word "surprise" and these are being conflated. In the first sense, we can say the prisoner will be surprised by the particular code he receives - this is like the first scenario where the judge simply flipped a coin 3 times to decide what day the prisoner will be hanged. In this sense, the judge's statement is true.
But in the second sense of surprise - the surprise at the receipt of the final stop bit of a code transmitted day-by-day - the judge's statement is simply false. He claims that the prisoner will (with certainty) be surprised when he learns that he is to be executed but, in fact, the prisoner will not be surprised on the day of his execution in the case when 7 white balls were drawn.
But leaving aside the falsity of the judge's statement, does the prisoner's reasoning hold? I think his reasoning does hold and it is a consequence of the contradiction in the judge's claim that the prisoner will (with certainty) be surprised on the day of his execution, when the last code-sequences above has 0 bits of surprisal. So, the prisoner may use a process of elimination to argue that - since the day of execution can only come on a day when there is some non-zero surprisal - the 8th day cannot be the day on which he is to be executed. Then he can reason that the 7th day would have no surprisal and so on until he has eliminated all the days. Once he has done this, he can simply (and correctly) conclude that the judge's statement is false.
The fact that the prisoner is still surprised when the knock comes doesn't mean that there is a paradox. Rather, it is again the result of conflating the two senses of surprise; this time, by switching back to the first sense (surprise at which day he is to be executed). The fact that the prisoner will, of course, be surprised at which of the 8 days is chosen by 3 coin flips (to the tune of 3 bits) does not alter the fact that the judge's statement was false and would have been shown to be false in the case that the day selected by coin flip is the last day.
Clayton -
I just thought of another way to state my solution that might make it less murky.
First of all, we can simplify the problem by considering the simplest case: 2 days.
The judge tells the prisoner, "You will be executed sometime within the next 2 days. When you are told - on the day you are to be executed - you will be surprised."
In order to choose which of the two days he will execute the prisoner, the judge flips a coin. If the coin is heads, he will execute the prisoner on Day 1. If tails, he will execute him on Day 2.
The prisoner, meanwhile, has an urn with a black ball and a white ball. If he is told on Day 1 that he is to be executed, he will draw the black ball. If he is told on Day 1 that he is not to be executed, he will draw the white ball, leaving the black ball in the urn. Note that on Day 1, the surprisal of drawing either ball is 1 bit. If the execution happens to be set for Day 1, then the judge's claim that the prisoner would be surprised was true (but we'll see the sense in which his overall claim is false, below). We can see this because there are still two balls in the urn. But in the case when the execution happens to be set for Day 2, the prisoner cannot possibly be surprised because there is only one ball in his urn and there is nothing to be surprised about.
There is exactly 1 bit of information to be transmitted from the judge to the prisoner - whether the execution is to occur on Day 1 or Day 2. In the illustration, that information is potentially sampled by the prisoner twice - once on Day 1 and once on Day 2. But the fact is that in order to communicate 1 bit of information, only one binary sample is required, in the absence of noise. That is, the second sample is superfluous - there is no surprisal in the prisoner's mind, he already knows if he is not executed on Day 1 that he will be executed on Day 2.
So, let's go back to the judge's assertion: "When you are told on the day you are to be executed, you will be surprised." - this can be slightly rephrased to emphasize his meaning, "When you are told on the day you are to be executed, it is certain that you will be surprised."
Here we see that this statement is simply false - not paradoxical - since there is a 50% probability that the execution will be on Day 2, in which case the prisoner will not be surprised. Yet the judge has asserted that there is a 100% probability that the prisoner will be surprised. The "process of elimination" by which the prisoner reckons he cannot be executed on any of the days is a result of this contradiction (it's analogous to being able to prove 1=2 in a math system with inconsistent axioms).
We can restore the original illustration by letting the judge flip the coin three times to choose one of 8 days on which to execute the prisoner (assigning the pattern TTT=Day 1, TTH=Day 2, etc.) In this case, the prisoner has 7 white balls and one black ball; his surprisal at being told to draw the black ball follows the distribution given in the first post (calculated as log_2(8), log_2(7), log_2(6), ...)
I do not believe the Hangman's Paradox is a genuine paradox.
Thanks!
I got the idea when I was studying information theory and I saw the Hangman's Paradox called the "surprise hanging paradox" - the central idea of Information Theory is surprisal so I tried framing the problem in terms of a communication channel. Once I did this, I realized "hey, there's no paradox here at all, the judge is simply contradicting himself."
Wait. This is a problem that requires a solution at all? I highly fail to see why. The man being executed obviously used flawed logic, and hence he is surprised.
He took the logic only part of the way by knocking off one day at a time. At the end, he concluded that he will not be hanged on any day. At this point the only thing that could surprise him, then, was for him to actually be hanged on any day at all. Hence, he has no more information than when he started out.
It appears that the problem in the man's logic occurs when he strings the days together. In his reasoning about Friday, he is correct in the first step - if he is to be hanged Friday, then on midnight of Thursday he will no longer be surprised. He hence knocks off Friday with this initial condition.
As soon as he knocks off one day - his expectation then becomes that he cannot be hanged on that day. Therefore, to surprise him, hang him on that very day.
I'm not even sure why this is a problem...
The prisoner's surprise is not the result of his "faulty" reasoning and his reasoning is no more faulty than those algebraic proofs that 1=2 (by ignoring the fact that you can't divide by zero). That is, he starts from the assumption that the judge's statement is true. From that, he derives an absurd conclusion (he cannot be hanged on any day). This absurd conclusion should be the evidence that one of the original axioms was false. The false axiom is the judge's claim that "You will be hanged on one of the following 8 days and you will with certainty be surprised on the day you find out you are to be hanged."
I want to read this but no time now. From a skim, it really reminds me of the Surprise Test Paradox [warning: time sink, if you're one of those people who can't resist solving a problem]. Highlight the white text below for the riddle.
A teacher announces that there will be a surprise test next week. A student objects that this is impossible: “The class meets on Monday, Wednesday, and Friday. If the test is given on Friday, then on Thursday I would be able to predict that the test is on Friday. It would not be a surprise. Can the test be given on Wednesday? No, because on Tuesday I would know that the test will not be on Friday (thanks to the previous reasoning) and know that the test was not on Monday (thanks to memory). Therefore, on Tuesday I could foresee that the test will be on Wednesday. A test on Wednesday would not be a surprise. Could the surprise test be on Monday? On Sunday, the previous two eliminations would be available to me. Consequently, I would know that the test must be on Monday. So a Monday test would also fail to be a surprise. Therefore, it is impossible for there to be a surprise test.”
The riddle is: Can the teacher fulfill his announcement?
Why anarchy fails
The hangman's paradox and surprise test paradox are formally equivalent.
A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day. Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the "surprise hanging" can't be on Friday, as if he hasn't been hanged by Thursday, there is only one day left - and so it won't be a surprise if he's hanged on Friday. Since the judge's sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday. He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn't been hanged by Wednesday night, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all. The next week, the executioner knocks on the prisoner's door at noon on Wednesday — which, despite all the above, was an utter surprise to him. Everything the judge said came true.
A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day.
Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the "surprise hanging" can't be on Friday, as if he hasn't been hanged by Thursday, there is only one day left - and so it won't be a surprise if he's hanged on Friday. Since the judge's sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday.
He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn't been hanged by Wednesday night, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all.
The next week, the executioner knocks on the prisoner's door at noon on Wednesday — which, despite all the above, was an utter surprise to him. Everything the judge said came true.
From my layman's point of view, I don't understand why "there is no consensus on its precise nature and consequently a final 'correct' resolution has not yet been established" [*] . The prisoner estimates the chances of unexpected hanging looking backwards from Friday. But time flows forwards, so he cannot eliminate so easily Frday, Thursday,...
It makes me think that a good deal of so called "paradoxes" (Paradox of thrift, for instance) remain such only within boundaries of specific discipline for the experts who fall victim to their own logic. As you say,
This absurd conclusion should be the evidence that one of the original axioms was false
P.S. No offence, Clayton, I haven't read your explanation simply because it is beyound my cognitive abilities)
Clayton:the judge is simply contradicting himself."
Isn't that the "solution" that the logical school of thought already came up with?:
[...] One approach, offered by the logical school of thought, suggests that the problem arises in a self-contradictory self-referencing statement at the heart of the judge's sentence.
One approach, offered by the logical school of thought, suggests that the problem arises in a self-contradictory self-referencing statement at the heart of the judge's sentence.
Clayton's point is the statement is just plainly false. No self-referencing required. In effect, the judge could have promised to execute the victim simultaneously on Monday and Friday, or in some other logically impossible way.
self-contradictory self-referencing statement
Blaming "self-referencing statements" has been a favorite hobby of formal logicists and mathematicians since the late 19th century. In fact, there is no conceptual problem whatsoever with self-referencing statements and no paradox that I'm aware of has ever been shown to be the result of self-reference. Blaming self-reference is always a red flag that the problem simply isn't understood, IMO.
I've scanned a few papers turned up by Google search giving "logical" solutions to the problem and their solutions - if correct - are needlessly complex and do not pierce through to the conceptual issues involved (the relationship between surprisal, information and communication).
"Yields falsehood when preceded by its own quotation" yields falsehood when preceded by its own quotation.
also attributed to him is this autobiography, "I'm so meta, even this acronym"
Clayton, do you have an opinion on Hofstadter?
@Malachi: I've not read GEB though I've flipped through it. My impression is that he touches on lots of topics I find interesting but doesn't explore them in rigorous depth.
An approachable yet fairly rigorous treatment of many of these issues is Rudy Rucker's Infinity and the Mind.
Clayton
And in defense of self-reference - my view is that self-reference is blamed for contradictions when they are frequently seen in association with proof-by-contradiction arguments that refute the consistency of axioms that motivated believers just believe must be true.
Let me give an example.
Proposition 1: Every (well-formed) proposition is either true or false
Is Proposition 1 actually true? It seems plausible on the surface. But, using self-reference, it is easy to construct a proof-by-contradiction that demonstrates that no matter how much you would love for Proposition 1 to be true, it simply is not.
Proposition X: Proposition X is false
Is Proposition X true or false? If we say it is true, then it is false, but then it is true, ad nauseum. Hence, there exists a well-formed proposition which is neither true nor false, namely, Proposition X. Therefore, Proposition 1 is false.
Naturally, logicians and mathematicians were skeptical that you could actually formulate propositions like Proposition X formally - it was felt that something like the human brain was required to be able to "self-ponder" or something. But it turns out that you can use a sneaky trick to number propositions and then have a proposition refer to its own proposition number, thus formalizing the self-reference.
Godel first worked this out - an amazing feat of ingenuity. But it was later extended by Turing and many others. The extent of the consequences of incompleteness discovered by Godel have been best demonstrated by mathematician Gregory Chaitin. As he puts it, "almost all true mathematical facts are true for no reason." This statement should not be confused as a statement of logical nihilism - whatever is true is true (and not false). It's just that - for almost all true mathematical facts - there's no reason why they are true!