# Rényi's siege problem

### (an introduction to source coding for general penalties)

A Diary on Information Theory (1969), presented as an actual diary found in the classroom of famed information theorist Alfréd Rényi in the late 1960s, is assumed to be a work of fiction by Rényi1, albeit one that doubles as a breezy introduction to a graduate-level field. The diary entry for the first "lecture," in its English translation, states2:

The lecturer indicated that the mathematical theory of information had come into being when it was realized that the flow of information can be expressed numerically in the same way as distance, time, mass, temperature, etc.

He explained this by referring to the game known as "Bar-kochba". (Translator's note: this game is similar to "Twenty Questions".)

One can measure the information needed to guess the message that the others have decided on by the number of questions required to get that information when one is using the most effective system of questioning. "Question", according to the rules of the game, means a question that can be answered with a "yes" or a "no". If we write the answers down by writing 1 for a "yes" and 0 for a "no", the answer-series (which characterizes uniquely the "something or somebody" we have to guess) is replaced by a sign sequences. The procedure is called coding and the sign sequences of 0's and 1's are called codewords. It is well known that every natural number can be expressed with ones and zeroes, i.e., written in the binary system.

The narrator probes further into Ralph Hartley's 1928 paper on information measurements, which is seen as a necessary prelude to the formulation of information theory by Claude Shannon in the 1940s. (Both Hartley and Shannon did this research as electrical engineers at Bell Labs.) Then the narrator returns to the Bar-kochba game:

I did some research on the Bar-kochba game to see who Bar-kochba was and why the game was named after him. In 135 B.C. [sic] the Jews started a war of independence against the Romans under the leadership of Bar Kochba (whose name means "Son of the Star"). The Romans, in superior numbers, laid siege to a fortress which was defended heroically by Bar Kochba at the head of a small garrison.

So far, this is historical fact. It is also said that Bar Kochba sent out a scout to the Roman camp who was captured and tortured, having his tongue cut out. He escaped from captivity and reported back to Bar Kochba, but being unable to talk, he couldn't tell in words what he had seen. Bar Kochba accordingly asked him questions which he could answer by nodding or shaking his head. Thus he acquired from his mute scout the information he needed to defend the fortress.

The only problem with this very persuasive story is that no historical source-book mentions it. The legend was probably made up by the person who invented the game but I couldn't trace who that was. It seems as though it came into being in Budapest at the beginning of this century. At any rate, the game was extremely popular in Budapest at that time, mostly among writers. Both Karinthy and Kosztolányi mention it several times in their writings. They were masters of the game, along with István Szomaházy.

It occurred to me that, if the story of Bar Kochba were true, then he would have been the forefather of information theory. But there is probably no historical foundation to this legend. Still, it would be interesting to find out how long it has been known that all information can be expressed with yes-no answers (can be coded into a sequence of two symbols).

Shannon's information theory uses probabilities, and, for the above problem of binary coding, discusses minimization of the number of bits sent on average, a problem later solved by David Huffman. However, this is not the problem that Simon bar Kochba would have wished to solve; his goal was to maximize the probability of successfully defending the fortress. This differs from the fundamental problem of binary coding in many ways, and the different approaches one must take for this and similar problems formed the basis for my doctoral thesis and subsequent papers.

1 Note that the device of claiming to publish a found document which the named author has only edited has a long tradition in literature, from Cervantes' Don Quixote de la Mancha to J.R.R. Tolkien's The Lord of the Rings.

2 A Diary is long out of print, so I am reproducing a short portion under United States fair use law; for research and scholarship uses only.