aBlog

The initial part of this short note will be of use as a reading for undergraduate Computer Science students learning its foundations. The latter part deals with Information Theory and is likely to be useful to graduate students or computing professionals being exposed to Information Theory for the first time. In any case, the article is bound to be of interest to anyone with a problem-solving bent of mind.

The answer to the above question is that n killings will take place on the morning of the nth day after the Oracle's seemingly innocuous but ultimately catastrophic proclamation, where n is the number of unfaithful men. If there are 100 unfaithful men, for example, then nothing will happen for 99 days, but on the 100th morning, all 100 of the unfaithful men will be killed!

Proof

Let a woman be said to ``know'' that her husband is unfaithful when she has reason to believe beyond doubt that he is having an affair. Since she can never have first-hand knowledge about the character of her own husband it follows that her knowledge in this matter is necessarily inferred fact. In the absence of this knowledge, she is forced to subscribe to what we call ``the conservative hypothesis'' that one's own husband is faithful. If a woman rejects the conservative hypothesis, then it follows that she has determined her husband is unfaithful and will thus kill him the next morning.

Here is the inductive assertion we make on i, the number of unfaithful men in the village:

S(i): If there are i unfaithful men in the village, then i-1 mornings after the Oracle's proclamation, each of the i wives of the i unfaithful men will have conclusive evidence to dismiss the conservative hypothesis about their husbands.

BASIS

Consider the case when there is exactly one unfaithful man A in the village. Until the Oracle's visit, A's wife has no reason to believe that her own husband is unfaithful and will thus continue to subscribe to the conservative hypothesis. Immediately after the Oracle's visit, however, A knows that at least one man in the village is unfaithful. Since it cannot be any of the others whom A knows to be faithful, A infers that it must be her own husband and so kills him on the morning of the first day following the Oracle's visit. It has taken A's wife exactly 0 mornings to determine whether her husband was faithful or not. The basis case is therefore true.

THE INDUCTIVE STEP

Assume that our assertion S(i) is true for all numbers of unfaithful men less than n, i.e. for 0 < i < n. Now suppose that the village has n unfaithful men. We prove by complete induction on n that S(i) still holds.

When i=n, there are two possible implications that could result from the conservative hypotheses of the Fornicalian women:

1. n-1 men in the village are unfaithful
2. n men in the village are unfaithful

Statement 1 is the implication of the conservative hypothesis held by the wives of each of the n unfaithful men, since they know n-1 other unfaithful men and have no reason to believe their own husbands are unfaithful. Statement 2 is the implication of the conservative hypothesis held by the rest of the women in the village.

By the inductive hypothesis, the believers of statement 1 will expect n-1 killings to take place on the morning of the n-1st day after the Oracle's visit. However, this doesn't happen since each of the n women will expect to see the husbands of the other n-1 women dead and not their own. Therefore, on the morning when this expected killing doesn't take place, they are forced to reject their conservative hypothesis and conclude there must be more than n-1 unfaithful men in the village. Since each of the women know that exactly n-1 other men are unfaithful, each concludes that the only possibility is that n men must be unfaithful and that the nth unfaithful man must be her own husband. She thus kills him on the morning of the nth day. It has taken the n wives of the n unfaithful men exactly n-1 mornings to determine that their husbands were unfaithful. This completes the inductive step and so S(i) is true for all n.

The Information Content of the Oracular Proclamation

Surprisingly, the mathematical proof presented above requires the Oracle to very much be an essential part of this situation. If not for the Oracle, the basis case fails. Yet, it seems on a first reading that the Oracle's statement contains no useful information in a village that has more than one unfaithful man. Consider the village that has two unfaithful men, for example. Every woman in the village knows at least one unfaithful man. Thus the Oracle's proclamation is at best, one could say, ``stating the bleeding obvious.'' A foundational result in Information Theory due to Shannon and Weaver (1949) shows that when the term information is sensibly defined, the information content of a symbol is equal to the negative logarithm of its probability. We also point the reader at another seminal work, Hamming (1980), where the former interesting result is more accessibly discussed at length, and at the URL: http://cm.bell-labs.com/cm/ms/what/shannonday/ from where a copy of Shannon's original paper can be downloaded. This latter document, however, doesn't contain Weaver's lucid discussion of the significance of Shannon's results.

Claiming that the information content of a symbol is related to the negative logarithm of its probability is tantamount to claiming that no useful information can be conveyed by a certain event. The more uncertain and therefore surprising an event is, the more information it contains. If we told you, for example, that the Sun rose in the East this morning, you will hopefully not benefit much from this fact by virtue of your already attaching a very high probability to this event. However, if we were to tell you instead that the Sun happened to rise in the West, that information, assuming it is true, will be of utmost interest and use to you. In general the information content in an event i, is -log p_i where p_i is the probability of the event.

Now suppose again that there are at least two unfaithful men in the village. Every wife in the village knows at least one unfaithful man and so the subjective probability she will assign to the event that there is at least one unfaithful man in the village is 1.0. It follows, therefore, that the information contained for her in the oracular statement that claims this certain event is -log 1 = 0. So how can this event, seemingly void of information, cause such a catastrophic result? Let us rephrase the problem to make it even more explicit. The Oracle has not told the women of Fornicalia anything new that they didn't already know. So why was its proclamation critical in determining the subsequent course of events in the village? Pondering this question, more than any other, promises to be most instructive for someone just being introduced to the subtleties of Information Theory. Again, we urge the reader at this point to ponder why this is so before proceeding further.

It turns out that the Oracle's proclamation did indeed bear no useful information for any woman. And this is precisely the reason that no killing takes place on the first day following this event. But a fact about the proclamation itself bears useful information for just the wives of the two unfaithful men in the village. In particular, it is the meta-fact that the oracular proclamation had zero information for every woman in the village. In other words, although every woman knew that the village had at least one unfaithful man, not every woman knew that ``every woman knew that the village had at least one unfaithful man''. Consequently, these women will attach a non-unitary probability to this event and will thus find it useful. Let's review the case when there are exactly two unfaithful men in the village. Call their wives A and B. Every woman in the village knows at least one unfaithful man. But not every woman knows that every woman knows at least one unfaithful man. To be precise, A and B know only one unfaithful man in the village and A does not know that B knows that there exists at least one unfaithful man and vice-versa. Thus the fact that B does know this comes as a surprise to A after the first morning. In general, one can make the following assertion for any number, i > 0, of unfaithful men in the village:

T(i): If there are i unfaithful men in the village, then the wives of these i men don't know (that every woman knows)^i-1 that there exists at least one unfaithful man in the village.

where the superscripted index denotes i-1 repetitions of the parenthesized phrase. It is easy to prove T(i) by induction along the lines of our previous proof in the first section. Thus those women who don't know the above fact will attach a subjective probability p < 1 to it's being true and consequently find it of informative value. So the Oracle is an integral part of the situation after all. Had it not visited the village, the catastrophe wouldn't have been triggered off and the village would have continued to exist as a harmonious society in which no woman can conclusively nail down her husband. Alas, however, that being not the case, thus ends the lamentable tale of the clever widows of Fornicalia and the Stobon Oracle.³ The men's lives wouldn't have been lost in vain if their story has inspired in new students a deep and lasting love for Information Theory.

References

1. Halpern, J. Y. & Y. Moses. (1990). Knowledge and common knowledge in a distributed environment, JACM, 37(3), 549-587.

2. Hamming, R.W. (1980). Coding and information theory (2nd edition). Prentice-Hall, Englewood Cliffs, NJ.

3. Moses, Y., D. Dolev, & J. Y. Halpern. (1986). Cheating husbands and other stories: A case study of knowledge, action, and communication, Distributed Computing, 1, 167-176.

4. Shannon, C.E., & W. Weaver. (1949). The mathematical theory of communication. University of Illinois Press, Urbana.

Notes: (Use the BACK button to return)