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

标签：

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

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Bob chooses a secret four-bit number. Alice proposes a four-bit number, and Bob replies with the number of 1 bits in Alice's proposal that are also 1 in the same positions of the secret. For example, for secret 1110, proposals 1100, 0100, and 1110 receive replies $2$, $1$, and $3$, respectively.

When Alice proposes $n$, let $X_n$ denote Bob's reply. Assume that Bob's secret is uniformly distributed over all $16$ four-bit numbers. The entropy of $X_{1111}$ is given as approximately $2.025$ bits. You may use $\frac34\log_2 3\approx1.19$.

1. Compute $H(X_{0000})$, $H(X_{1000})$, $H(X_{1100})$, and $H(X_{1110})$.
2. Compute $I(X_{1010};X_{0101})$, $H(X_{1100}\mid X_{1000})$, and $I(X_{1000};X_{1100})$.
3. Prove that every strategy guaranteed to determine Bob's number requires at least three proposals in the worst case.
4. The three fixed proposals 1110, 1001, and 0011 always determine the secret. If $X_{1110}=1$, $X_{1001}=0$, and $X_{0011}=1$, find the secret.
5. Although 1111 has the largest response entropy, no optimal strategy uses it: after proposing 1111, three additional proposals are still required in the worst case. Explain this apparent paradox using information theory and mutual information.

题目描述

Bob 均匀随机选择一个秘密四位二进制数。Alice 每次提出一个四位数，Bob 只回答所提数字中有多少个 1 与秘密数的 1 处于相同位置。以 $X_n$ 记提出 $n$ 时的回答。

1. 计算 $H(X_{0000})$、$H(X_{1000})$、$H(X_{1100})$、$H(X_{1110})$。
2. 求 $I(X_{1010};X_{0101})$、$H(X_{1100}\mid X_{1000})$、$I(X_{1000};X_{1100})$。
3. 证明任何保证确定秘密数的策略，最坏情况至少需要三次提问。
4. 已知固定提问 1110、1001、0011 总能确定秘密数。在回答依次为 $1,0,1$ 时，求秘密数。
5. 解释为何 1111 的单次平均信息量最大，却不会出现在优化最坏提问数的最优策略中。

Kai

Let the secret bits be independent variables $S_1,S_2,S_3,S_4\sim\operatorname{Bernoulli}(1/2)$. If a proposal contains $k$ ones, its reply is the sum of the corresponding $k$ secret bits and therefore has distribution $\operatorname{Binomial}(k,1/2)$.

Q.1.1

Proposal	$k$	Reply distribution	Entropy (bits)
0000	0	$(1)$	$0$
1000	1	$(1/2,1/2)$	$1$
1100	2	$(1/4,1/2,1/4)$	$3/2$
1110	3	$(1/8,3/8,3/8,1/8)$	$3-\frac34\log_2 3$

Hence

$$\boxed{ H(X_{0000})=0,\quad H(X_{1000})=1,\quad H(X_{1100})=\frac32,\quad H(X_{1110})=3-\frac34\log_2 3\approx1.81 }.$$

Q.1.2

The variables

$$X_{1010}=S_1+S_3,\qquad X_{0101}=S_2+S_4$$

depend on disjoint independent bits, so they are independent. Thus

$$\boxed{I(X_{1010};X_{0101})=0}.$$

Also $X_{1000}=S_1$ and $X_{1100}=S_1+S_2$. Once $S_1$ is known, $S_1+S_2$ is in one-to-one correspondence with the still-uniform bit $S_2$. Therefore

$$\boxed{H(X_{1100}\mid X_{1000})=1}.$$

Finally,

$$\boxed{ I(X_{1000};X_{1100}) =H(X_{1100})-H(X_{1100}\mid X_{1000}) =\frac32-1=\frac12 }.$$

Q.1.3

Suppose the first proposal contains $k$ ones. If its reply is $r$, then exactly

$$2^{4-k}\binom{k}{r}$$

secrets are compatible with that reply. For every $k\in\{0,1,2,3,4\}$, some reply leaves at least six candidates:

$k$	0	1	2	3	4
Largest candidate set	16	8	8	6	6

Choose such a worst-case reply. Any second proposal has at most five possible replies, namely $0,1,2,3,4$. It cannot assign six remaining candidates to six different replies. By the pigeonhole principle, at least two secrets remain indistinguishable after two proposals, even if the second proposal is chosen adaptively. Hence

$$\boxed{\text{at least three proposals are necessary in the worst case}.}$$

Q.1.4

Write the secret as $S_1S_2S_3S_4$. The replies give

$$S_1+S_2+S_3=1,\qquad S_1+S_4=0,\qquad S_3+S_4=1.$$

The second equation gives $S_1=S_4=0$; the third then gives $S_3=1$, and the first gives $S_2=0$. Thus

$$\boxed{S_1S_2S_3S_4=0010}.$$

Q.1.5

Let $S$ be the secret and $R_i$ the $i$-th reply. Since a reply is a deterministic function of $S$ and the chosen proposal,

$$I(S;R_1)=H(R_1).$$

Thus maximizing $H(R_1)$ maximizes the average immediate information gained. It does not minimize the largest branch of the decision tree. Proposal 1111 reveals only the Hamming weight of the secret; in its worst branch, reply $2$ leaves all six weight-two secrets and gives no positional information among them.

Information accumulated over several replies obeys the chain rule

$$I(S;R_1,\ldots,R_t) =I(S;R_1)+\sum_{i=2}^{t}I(S;R_i\mid R_1,\ldots,R_{i-1}).$$

Later replies may be redundant with the first one, so their conditional mutual information can be small even when the first marginal entropy is large. An optimal worst-case strategy instead chooses proposals whose joint replies distinguish candidates in balanced, complementary ways. Hence maximum one-step entropy and minimum worst-case number of proposals need not select the same first question.

To verify the worst branch after an initial 1111, condition on reply $2$. There are six weight-two secrets. A next proposal with two ones has a reply-1 branch containing four secrets; a final reply has at most three values on weight-two secrets, so it cannot distinguish all four. A proposal with one or three ones has a three-secret branch in which one bit is fixed and the position of one remaining 1 (or 0) is unknown. Any final proposal splits these three positions into at most two response classes. Proposals with zero or four ones provide no information. Thus two further proposals cannot suffice, whereas three single-bit proposals determine a weight-two secret. An initial 1111 therefore needs four proposals in the worst case.

This conclusion concerns the first proposal. A three-proposal strategy may use 1111 in a later, smaller branch: after 1110 receives reply 0, only 0000 and 0001 remain, and 1111 distinguishes them immediately. On the other branches, the fixed proposals 1001 and 0011 still finish within three proposals.