京都大学 情報学研究科 知能情報学専攻 2019年2月実施 専門科目 F2-1

Author

itsuitsuki

Description (English)

In a game of two players, Alice is trying to guess a secret 4-bit number chosen by Bob. Alice gets information about the secret number by proposing a 4-bit number. Bob replies by indicating how many 1s in the proposed number are in the same position as in the secret number. For example, if Bob chose the 4-bit secret number 1110 and Alice proposes 1100, she will get the reply "two 1s in correct position" from Bob. If Alice then proposes 0100, she will get the reply "one 1 in correct position." And for 1110, she will get the reply "three 1s in correct position."

Q.1

When Alice proposes the number , let us denote with the number of 1s in the same position as in the secret number. If we assume that Bob chooses the secret number according to a uniform distribution, then each can be seen as a random variable and we can compute its entropy. The entropy of is . Compute the entropy of , , and . (You can use the approximation .)

Q.2

What is the mutual information of and ? What is the conditional entropy of given ? What is the mutual information of and ?

Q.3

Using the result of question 1.1, prove that any strategy for finding Bob's number correctly will require Alice to propose at least three numbers in the worst case.

Q.4

It is actually possible for Alice to always correctly guess Bob's number using at most three propositions. One possible strategy is to always propose the numbers 1110, 1001 and 0011. If, for a given secret number, we have , and , what is the secret number?

Q.5

According to question 1.1, proposing 1111 gives the most information on average to Alice (i.e. has the highest value). However it can be proven that no optimal strategy for Alice involve proposing 1111 (i.e. if Alice proposes 1111, she will still need to make three additional propositions to find the correct number in the worse case). Explain how this seemingly paradoxical situation can happen, in terms of Information Theory and Mutual Information?

Kai

Q.1