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

标签：

• Kyoto-University
• Entropy
• Conditional-Entropy
• Mutual-Information
• Information-Theoretic-Lower-Bound

Author

itsuitsuki

Description

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 $n$, let us denote with $X_n$ 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 $X_n$ can be seen as a random variable and we can compute its entropy. The entropy of $X_{1111}$ is $H(X_{1111}) \approx 2.025$. Compute the entropy of $X_{0000}$, $X_{1000}$, $X_{1100}$ and $X_{1110}$. (You can use the approximation $\frac{3}{4} \log_2 3 \approx 1.19$.)

Q.2

What is the mutual information of $X_{1010}$ and $X_{0101}$? What is the conditional entropy of $X_{1100}$ given $X_{1000}$? What is the mutual information of $X_{1000}$ and $X_{1100}$?

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 $X_{1110} = 1$, $X_{1001} = 0$ and $X_{0011} = 1$, what is the secret number?

Q.5

According to question 1.1, proposing 1111 gives the most information on average to Alice (i.e. $H(X_{1111})$ 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?

题目描述

Bob 均匀随机选择一个秘密 4 位数。Alice 每次提出一个 4 位数，Bob 只回答所提数字中有多少个 1 与秘密数中的 1 位于同一位置。例如秘密数为 1110 时，提 1100 得 2，提 0100 得 1，提 1110 得 3。

Alice 提出数字 $n$ 时，以随机变量 $X_n$ 表示正确位置上的 1 的个数。已知 $H(X_{1111})\approx2.025$，并可使用 $\frac34\log_2 3\approx1.19$。回答：

1. 计算 $H(X_{0000})$、$H(X_{1000})$、 $H(X_{1100})$、$H(X_{1110})$。
2. 求 $X_{1010}$ 与 $X_{0101}$ 的互信息；求给定 $X_{1000}$ 时 $X_{1100}$ 的条件熵；求 $X_{1000}$ 与 $X_{1100}$ 的互信息。
3. 利用第 1 问结果证明：任何保证正确找出秘密数的策略，在最坏情况下至少需要提出三个数字。
4. 三次固定提问 1110、1001、0011 足以总能确定秘密数。若回答分别为 $X_{1110}=1$、$X_{1001}=0$、$X_{0011}=1$，求秘密数。
5. 虽然提 1111 的平均信息量最大，但可证明任何包含该提问的策略之后仍需再提三个数字，因而最优策略不会使用它。用信息论与互信息解释为何平均信息量最大并不与最坏情形下不最优矛盾。

考点

• 熵、条件熵与互信息：从均匀秘密位的联合分布计算各回答变量的信息量及变量间依赖。
• 信息论下界：用每次回答熵上界与 4 位秘密的 4 比特不确定性，证明最坏提问次数下界。
• 查询编码与可辨识性：由三次计数回答联立恢复各比特，并区分平均信息增益与最坏分支划分质量。

Kai

Q.1