ENGG5301 Information Theory 2025 Midterm Exam P3：Causal Encoding

题目为回忆版，解答是 GPT-5 写的。

考试时 (1) 问就想偏了，考后看到 GPT-5 的答案很气，不等式想不到直接 (1)(2)(3) 连跪，搞的 (4)(5) 问也没做。

从初中就开始烂完的不等式水平又发力了，但这课确实没啥心思去刷教材/习题，符合预期。

Problem

Let random variables \(X_1,\dots,X_n\) be i.i.d. with distribution \(p_X\).

We define an encoding sequence \(M_1,\dots,M_n\) subject to the following causality constraints:

• \(M_i\) is a function of \(X_1,\dots,X_i\), i.e., \(M_i = f_i(X_1,\dots,X_i)\);
• \(X_i\) is a function of \(M_1,\dots,M_i\), i.e., \(X_i = g_i(M_1,\dots,M_i)\).

Answer the following:

1. Find the minimum value of \(\sum_{i=1}^n H(M_i)\) in terms of \(p_X\).

2. Show that, under the optimal encoding, \(M_1,\dots,M_n\) are mutually independent.

3. Show that, under the optimal encoding, \(H(M_i \mid X_i) = 0\).

4. If we drop optimality but require causal encoding and cross-codeword prefix-free constraint
   (i.e., \(\forall i \neq j, M_i\) is not a prefix of \(M_j\)), show that there exists an encoding such that

   \[\mathbb{E}\!\left(\frac{1}{n}\sum_{i=1}^n L(M_i)\right) < H(p_X) + 1. \]

5. Under the same causal and cross-codeword prefix-free constraint, show that for any \(\varepsilon>0\), there exists an encoding such that

   \[\mathbb{E}\!\left(\frac{1}{n}\sum_{i=1}^n L(M_i)\right) < H(p_X) + \varepsilon. \]

---

Solution

(a) Minimum of \(\sum_i H(M_i)\) under optimal encoding

Result:

\[\min \sum_{i=1}^n H(M_i) = n\,H(p_X). \]

Proof:

By the data processing inequality and lossless reconstruction,

\[H(X_1,\dots,X_n) \le H(M_1,\dots,M_n) \le \sum_{i=1}^n H(M_i). \]

Since \(X_1,\dots,X_n\) are i.i.d.,

\[H(X_1,\dots,X_n) = n H(X). \]

Thus,

\[\sum_{i=1}^n H(M_i) \ge n H(X). \]

Choosing \(M_i=f(X_i)\), i.e., encoding each symbol separately, achieves \(H(M_i)=H(X)\) and satisfies both causality and recoverability, hence the bound is tight.

---

(b) Independence of \(M_1,\dots,M_n\) under optimal encoding

Result:
Under the optimal encoding, \(M_1,\dots,M_n\) are mutually independent (and thus pairwise independent).

Proof:

Equality in part (a) requires that

\[\sum_{i=1}^n H(M_i) = H(M_1,\dots,M_n). \]

Equality between the sum of marginal entropies and the joint entropy holds if and only if the variables are mutually independent.
Hence, the optimal \(M_1,\dots,M_n\) are independent.

---

(c) Determinism: \(H(M_i\mid X_i)=0\) under optimal encoding

Result:
Under the optimal scheme, \(M_i\) is a deterministic function of \(X_i\).

Proof:

From the reconstruction condition,

\[H(X_i\mid M_1,\dots,M_i) = 0. \]

Since \(X_i\) is independent of previous messages \((M_1,\dots,M_{i-1})\),

\[H(X_i\mid M_1,\dots,M_{i-1}) = H(X_i). \]

Hence the mutual information satisfies

\[I(X_i; M_i \mid M_1,\dots,M_{i-1}) = H(X_i) - 0 = H(X_i). \]

On the other hand,

\[I(X_i; M_i \mid M_1,\dots,M_{i-1}) = H(M_i \mid M_1,\dots,M_{i-1}) - H(M_i \mid X_i, M_1,\dots,M_{i-1}). \]

Under the optimal encoding, \(H(M_i\mid M_1,\dots,M_{i-1}) = H(X_i)\), so

\[H(M_i\mid X_i, M_1,\dots,M_{i-1}) = 0. \]

Because \(M_i\) is independent of \((M_1,\dots,M_{i-1})\), it follows that

\[H(M_i\mid X_i)=0. \]

Therefore, each \(M_i\) is a deterministic function of \(X_i\).