No Information Can Be Conveyed By Certain Events:
The Case of the Clever Widows of Fornicalia
And the Stobon Oracle

Anand Venkataraman
Computer Science
Massey University
New Zealand
mailto:A.Raman@massey.ac.nz

1. Introduction

In a certain village on the remote plains of Fornicalia there exist some men who are having affairs with the wives of other men. Now there is a gruesome custom in this village which requires a woman to kill her husband the morning after she discovers that he is having an affair with another woman. It also happens that every woman knows whether every other man is having an affair or not except her own husband.¹ So life in this village goes on peacefully since no woman can know for sure that her own husband is cheating on her. Unfortunately, an Oracle from the pure and untainted shores of distant Stobon visits the village one day and proclaims that at least one man in this village is having an affair. What happens after this?

Readers are urged to think of a solution themselves before proceeding further. We first present the solution and its proof and finally go on to discuss the information theoretic aspects of this remarkable problem.² A similar treatment of this and some other aspects of the puzzle can also be found in Moses et al. (1986) and Halpern and Moses (1990), both of which also cite other sources where further discussion of the topic can be found.

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!

2. Proof

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.

2.1 BASIS

2.2 THE INDUCTIVE STEP

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

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.

3. The Information Content of the Oracular Proclamation

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.

4. 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)

1. A further important fact that is often not emphasized in most renditions of this puzzle is that not only does each woman know the character of every other man in the village except her own husband, she also knows this to be true of all the women in the village. It is also assumed that the women in this village possess the intelligence required to make logical inferences and that they recognize this ability in each other.

2. Ray Solomonoff has remarked that ``In older kinder times, descriptions of problems of this sort were less grisly. A person would have a black spot painted on his forehead or not. No mirrors exist in the community, so each person would know if another had a black spot, but he could not {\em directly} know about himself.''

3. Imagine the even more lamentable case when there is exactly one unfaithful man and his wife also happens to be the only free thinking secret rebel in the village who doesn't believe in its gruesome custom. Suppose she demonstrates her recalcitrance by not killing her husband on the morning of the first day after the Oracle's proclamation. What happens then?

Copyright © May 31, 1999 Anand Raman

---

hits since 31 May 1999.