Guessing Games

Information Theory is the study of how to quantify information. First proposed by Claude Shannon in 1948, in the context of exploring the limitations of data compression, Information Theory plays an important role in many modern technologies, in terms of both what can and cannot be done with data. Information Theory also forms the basis of many purely recreational activities such as magic tricks (one popular example is here though there are many others. Maybe someday I will write a note about some others) and games. (Ever play MasterMind? Twenty Questions? P.I.? Hanabi?)

In the following sequence of problems I have tried to illustrate some of the simplest principles of Information Theory through a sequence of guessing games.

The fundamental unit of information is a bit. A bit (as you probably know) is something than can take one of two values, 0 or 1. (Or, if your want to look at it from the signal process/electrical engineering angle, On or Off. Or True or False, to take a Boolean Logic perspective.) If you are trying to distinguish between $2^{n}$ different things, then you require $n$ bits to describe the distinction.

But wait a minute! Alice's answers above could be one of three things, "too small", "too big" or correct. This is true. However, the only advantage you gain from a response of "correct" is that you can stop asking questions. So effectively, for all but the last question, the answers have only possibilities, "too small" and "too big", and Bob's best strategy is to make guesses that divide the space of possible answers into two intervals as equally as possible. Indeed if Alice's answers took the form "guess < hidden number" or "guess $\ge$ hidden number", the choice is truly binary, and the resulting game is nearly (but not exactly) the same.

In both the above problems, some of the power comes from adaptivity. Bob gets to tailor his next guess based on Alice's answer to the previous one. If Bob cannot do that, then it turns out the only way he can "guess" Alice's number is by guessing all the numbers. However, guessing a number that splits the interval into two intervals is only one kind of binary question Bob could ask. If Bob were allowed to ask a different kind of binary question, things could be different.

What about missing information? How can we deal with that?

In the above problem, Bob can deal with one missing bit. Erasure codes (about which I will write a note someday...) study how to encode messages so as to be able to recover them even when some of the bits may be "erased".

But what if some of the information were to be "corrupted" rather than "erased"? That is, instead of seeing a blank for some piece of information, you see an incorrect answer. The problem is that when your answer choices are binary, an incorrect answer looks just like a correct answer, so you don't even have a helpful clue as to where the problem has occurred. Perhaps surprisingly, there are still ways to add redundancy to the information so that one can recover from a small number of corruptions. The next two problems ask you to come up with a scheme for recovering from one corruption. The general design of such redundancy and the its limitations comes under the topic of Error Correcting Codes.

\frac1{1000}

\frac1{100}

\frac1{10}

\frac14

\frac12

1

Correct!

40% of people got this right.

Alice: "Hey Bob, I'm in the mood for some sneakiness. Want to play a variant of 'Guess a Number'?"
Bob: "Sure."
Alice: "Let's play the two-round version where you submit a list of yes/no questions, then I answer them, and then you guess one number. This time I will answer all of your questions."
Bob: "Good!"
Alice: "But on one of the questions (of my choosing) I may lie. Or maybe I won't."
Bob: "Okay, I think I can do this."

So, Alice thinks of a number between 1 and 1000, and Bob makes up a list of 15 questions.

Alice then receives the list, answers all of the questions with yes or no, with the guarantee that at least 14 are answered truthfully, and returns the list to Bob.

Now, Bob must guess Alice's number.

What is the maximum probability that Bob correctly guesses Alice's number? (Assume that he chose an optimal set of 15 questions.)

Clarification: Bob may not ask self-referential questions (e.g. "Is your answer to this question a lie?"). No logical paradoxes, please! Questions asking about the truthfulness of answers to other questions are allowed.

Follow up to this problem.
From Guessing Games

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Guessing Games

Correct! The answer is 14.

Correct! The answer is 21.

Correct! The answer is 9.

Correct! The answer is 11.

Correct!

Correct!

Comments

Correct!
The answer is 14.

Correct!
The answer is 21.

Correct!
The answer is 9.

Correct!
The answer is 11.