問2

アルファベットが $\{1, 2, 3, 4\}$ である単純マルコフ情報源の遷移確率行列が

$$\begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0.5 & 0.5 & 0 & 0 \\ 0 & 0 & \gamma & 1-\gamma \end{pmatrix}$$

で与えられたとする．ここで, $(i, j)$ 成分は遷移確率 $P(j|i)$ を表し, $0 < \gamma < 1$ とする．以下の問いに答えよ:

1. このマルコフ情報源の状態遷移図を図示せよ．
2. このマルコフ情報源の定常確率分布が $(1/8, 1/4, 1/8, 1/2)$ であるとき, $\gamma$ の値を求めよ．
3. (2) が前問で求めた値となるとき、このマルコフ情報源のエントロピー率を求めよ．
4. このマルコフ情報源に従う確率変数の列 $X_1, X_2, \dots$ を考える．$X_i$ が上述の定常確率分布 $(1/8, 1/4, 1/8, 1/2)$ に従う場合, $(X_1, X_2)$ に対するハフマン符号化を行い, 符号的表示图を示せ．ただし符号語のアルファベットは $\{0, 1\}$ とする．

中文翻译

给定字母表为 $\{1, 2, 3, 4\}$ 的简单马尔可夫信息源, 其状态转移概率矩阵如下:

$$\begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0.5 & 0.5 & 0 & 0 \\ 0 & 0 & \gamma & 1-\gamma \end{pmatrix}$$

其中 $(i, j)$ 元素表示状态 $i$ 转移到状态 $j$ 的概率 $P(j|i)$, $0 < \gamma < 1$.

1. 绘制该马尔可夫信息源的状态转移图.
2. 假设该马尔可夫信息源的平稳分布为 $(1/8, 1/4, 1/8, 1/2)$, 求 $\gamma$ 的值.
3. 在 $\gamma$ 为前述求得的值时, 计算该马尔可夫信息源的熵率.
4. 假设符号序列 $X_1, X_2, \dots$ 服从平稳分布 $(1/8, 1/4, 1/8, 1/2)$, 为 $(X_1, X_2)$ 执行哈夫曼编码, 并绘制编码结果的图. 假设编码字母表为 $\{0, 1\}$.

---

o1

下面给出在修正后转移概率矩阵下的完整解答。修正矩阵为

$$P \;=\; \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\[4pt] 0 & 0.5 & 0 & 0.5 \\[4pt] 0.5 & 0.5 & 0 & 0 \\[4pt] 0 & 0 & \gamma & 1-\gamma \end{pmatrix}$$

其中$P(j\mid i)$是从状态 $i$ 转到 $j$ 的概率。

题目设定：

• 状态(字母)集合为 $\{1,2,3,4\}$。
• 给定平稳(定常)分布 $\pi = \bigl(\tfrac18,\;\tfrac14,\;\tfrac18,\;\tfrac12\bigr)$。
• 需要回答：

1. 状态迁移图
2. 令该链的平稳分布正好是上述 $\pi$ 时，求 $\gamma$。
3. 用(2)求得的 $\gamma$ 代入，计算该马尔可夫源的熵率。
4. 若从该马尔可夫源出发，考虑随机变量 $X_1, X_2, \dots$ 都具有边缘分布 $\pi$（题意里说“$X_i$ 服从 $(1/8,1/4,1/8,1/2)$”），对取值 $\{1,2,3,4\}$ 进行 Huffman 编码，并给出编码树(或“符号→码字”的对应)。

---

1. 状态迁移图

从矩阵的每一行(状态 $i$)出发，看哪些转移概率为正，即可画出如下有向图(圆圈表示状态，箭头表示可能的转移，标注相应的概率)：

• 行 1 (i=1):
  $P(1\to 1)=0.5,\;P(1\to 2)=0.5$，其余转移为 0。
  即：$1 \xrightarrow{0.5} 1$ 和 $1 \xrightarrow{0.5} 2$。

• 行 2 (i=2):
  $P(2\to 2)=0.5,\;P(2\to 4)=0.5$，其余为 0。
  即：$2 \xrightarrow{0.5} 2$ 和 $2 \xrightarrow{0.5} 4$。

• 行 3 (i=3):
  $P(3\to 1)=0.5,\;P(3\to 2)=0.5$，其余为 0。
  即：$3 \xrightarrow{0.5} 1$ 和 $3 \xrightarrow{0.5} 2$。

• 行 4 (i=4):
  $P(4\to 3)=\gamma,\;P(4\to 4)=1-\gamma$，其余为 0。
  即：$4 \xrightarrow{\gamma} 3$ 和 $4 \xrightarrow{1-\gamma} 4$。

可以把这几条箭头在纸上连起来，即得到状态迁移图。示意如下（用“→”画出非零概率的方向，并在箭头上标注对应的 0.5、$\gamma$ 等）：

 (1) --0.5--> (1)
   \          
    \--0.5--> (2) --0.5--> (2)
                     \            
                      \--0.5--> (4) --(1−γ)--> (4)
                                ^             
                                | γ           
                                (3) <--- 0.5 --- (3本身没有自环)
                                  ^ 
                                  | 0.5
                                  (3)
     (3) --0.5--> (1)
           --0.5--> (2)

(文本示意稍显杂乱，实际作图时更易看清：1 的自环、1→2、2 的自环、2→4、3→1、3→2、4→3、4 的自环。)

---

2. 由 $\pi=(1/8,\,1/4,\,1/8,\,1/2)$ 求 $\gamma$

要让 $\pi$ 成为该马尔可夫链的平稳分布，需满足

$$\pi \;=\; \pi\,P, \quad \text{即} \quad \pi_j \;=\; \sum_{i=1}^4 \pi_i \,P(i\to j), \quad j=1,2,3,4.$$

令 $\pi = (\pi_1,\pi_2,\pi_3,\pi_4) = \bigl(\tfrac18,\;\tfrac14,\;\tfrac18,\;\tfrac12\bigr)$。

(a) 求 $\pi_3$ 对应的方程

$$\pi_3 \;=\; \sum_{i=1}^4 \pi_i \,P(i\to 3).$$

从矩阵可知：

• $P(1\to 3)=0$,
• $P(2\to 3)=0$,
• $P(3\to 3)=0$,
• $P(4\to 3)=\gamma$.

因此

$$\pi_3 \;=\; \pi_4 \,\gamma \;=\; \tfrac12\,\gamma.$$

但题目给出 $\pi_3=\tfrac18$，故

$$\tfrac18 \;=\; \tfrac12\,\gamma \quad\Longrightarrow\quad \gamma \;=\; \tfrac14.$$

(b) 求 $\pi_4$ 对应的方程(验证一致性)

$$\pi_4 \;=\; \sum_{i=1}^4 \pi_i \,P(i\to 4).$$

从矩阵可读出：

• $P(1\to 4)=0$,
• $P(2\to 4)=0.5$,
• $P(3\to 4)=0$,
• $P(4\to 4)=1-\gamma$.

所以

$$\pi_4 \;=\; \pi_2 \cdot 0.5 \;+\;\pi_4\,(1-\gamma) \;=\; \bigl(\tfrac14\bigr)\times 0.5 \;+\; \bigl(\tfrac12\bigr)\times(1-\gamma).$$

题目给定 $\pi_4=\tfrac12$，又我们已知 $\gamma=\tfrac14$，代入则

$$\text{左边} = \tfrac12; \quad \text{右边} = \tfrac14 \times 0.5 \;+\;\tfrac12\times\bigl(1-\tfrac14\bigr) = \tfrac18 \;+\;\tfrac12\times\tfrac34 = \tfrac18 + \tfrac38 = \tfrac12.$$

两边相等，一致。其余 $\pi_1,\pi_2$ 对应的方程也会自动满足。由此可知：

$$\boxed{\gamma = \tfrac14 \quad\text{即可让}\;\pi=(1/8,\,1/4,\,1/8,\,1/2)\text{成为平稳分布。}}$$

---

3. 在 $\gamma=\tfrac14$ 时，这个马尔可夫源的熵率

马尔可夫链(离散记忆源)的熵率公式为

$$H(\text{源}) \;=\; \sum_{i=1}^4 \pi_i \;H\bigl(P(\cdot\mid i)\bigr) \;=\; \sum_{i=1}^4 \pi_i \;\Bigl(-\sum_{j} P(i\to j)\,\log_2 P(i\to j)\Bigr),$$

其中对 $P(i\to j)=0$ 的项不计(或视为乘以 0)。下面逐行计算：

• 行 1: $P(1\to 1)=0.5,\;P(1\to 2)=0.5$。
  分布 $(0.5,0.5,0,0)$ 的熵为

  $$H_1 \;=\; -\bigl(0.5\log_2 0.5 + 0.5\log_2 0.5\bigr) = 1\text{ bit}.$$

• 行 2: $P(2\to 2)=0.5,\;P(2\to 4)=0.5$。
  分布 $(0,0.5,0,0.5)$ 的熵同上，也为

  $$H_2 \;=\; 1\text{ bit}.$$

• 行 3: $P(3\to 1)=0.5,\;P(3\to 2)=0.5$。
  分布 $(0.5,0.5,0,0)$，同理也是

  $$H_3 \;=\; 1\text{ bit}.$$

• 行 4: $P(4\to 3)=\gamma=\tfrac14,\;P(4\to 4)=1-\gamma=\tfrac34$。
  分布 $(0,0,\tfrac14,\tfrac34)$ 的熵为

  $$\begin{aligned} H_4 &=\; -\Bigl(\tfrac14\log_2\tfrac14 \;+\;\tfrac34\log_2\tfrac34\Bigr)\\ &=\; -\Bigl(\tfrac14 \times (-2) \;+\;\tfrac34\,\log_2(0.75)\Bigr)\\ &=\; \tfrac12 \;-\; \tfrac34\,\log_2\!(0.75). \end{aligned}$$

  数值上，$\log_2(0.75)\approx -0.4150$，
  因此

  $$H_4 \;\approx\; 0.5 \;-\; 0.75 \times (-0.4150) \;=\; 0.5 \;+\; 0.3113 \;=\; 0.8113\text{ bits (左右)}.$$

将它们按平稳分布加权：

$$\begin{aligned} H(\text{源}) &=\; \pi_1\,H_1 \;+\; \pi_2\,H_2 \;+\; \pi_3\,H_3 \;+\; \pi_4\,H_4\\[6pt] &=\; \tfrac18\times 1 \;+\; \tfrac14\times 1 \;+\; \tfrac18\times 1 \;+\; \tfrac12 \times 0.8113\\[2pt] &=\; \Bigl(\tfrac18+\tfrac14+\tfrac18\Bigr)\times 1 \;+\; \tfrac12\times0.8113\\[4pt] &=\; \tfrac{1}{8}+\tfrac{2}{8}+\tfrac{1}{8} \;+\; 0.40565\\[3pt] &=\; \tfrac{4}{8} + 0.40565 \;=\; 0.5 \;+\; 0.40565 \;=\; 0.90565\text{ bits (近似)}. \end{aligned}$$

如果要求精确到三位小数，可写

$$\boxed{ H(\text{源})\;\approx\;0.906\text{ bits}. }$$

---

4. 按 $\pi=(1/8,1/4,1/8,1/2)$ 对 $\{1,2,3,4\}$ 作 Huffman 编码

题目最后一问常见的作法：

• 视这 4 个符号(或状态)的出现概率分别为

  $$p_1 = \tfrac18,\quad p_2=\tfrac14,\quad p_3=\tfrac18,\quad p_4=\tfrac12,$$

  进行 Huffman 码的构造。

Huffman 码步骤

1. 列出四个符号及其概率：
   $\,s_1=1,\;p_1=1/8;\;s_2=2,\;p_2=1/4;\;s_3=3,\;p_3=1/8;\;s_4=4,\;p_4=1/2.$

2. 选出两个最小概率项合并：

   • 这里最小的是 $s_1$ 和 $s_3$，各 $1/8$。合并得到新节点 $N_{13}$，概率 $1/4$。

3. 此时剩余的节点概率：

   $$N_{13}=1/4,\quad s_2=1/4,\quad s_4=1/2.$$

   再次选出最小的两项合并(现在 $N_{13}$ 和 $s_2$ 并列最小，各 $1/4$)，合并成新节点 $N_{132}$，概率 $1/2$。

4. 最后将 $N_{132}$ (概率 $1/2$) 与 $s_4$ (概率 $1/2$) 合并成根节点(概率 1)。由此生成一棵二叉树。若我们一贯约定“左分支标 0，右分支标 1”，可以得到下面的前缀码(只要保证前缀码唯一即可，小的交换并不影响平均长度)。

得到的编码

• 符号 $4$ ：路径为“根 $\to$ 右”，码字可定为 1。
• 符号 $2$ ：从根 $\to$ 左 $\to$ 右，码字 01。
• 符号 $1$ ：从根 $\to$ 左 $\to$ 左 $\to$ 左右再分，实际上更简单写法是：先与 $3$ 合并，再与 $2$ 合并；一种典型的布置是
  • $1$ 得码字 000，
  • $3$ 得码字 001。

典型 Huffman 编码树可示意为（自上而下）：

       (根)   (概率 1)
       /   \
    0 /     \ 1
     /       \
 (N_{132})   (4)
  (概率1/2)  (概率1/2)
    /   \
  0/     \1
  /       \
(N_{13})  (2)
 (1/4)    (1/4)
  /  \
0/    \1
/      \
(1)    (3)
(1/8)  (1/8)

对应的码字分配(仅举一例)：

• $4$ : 1
• $2$ : 01
• $1$ : 000
• $3$ : 001

这样就完成了对 $\{1,2,3,4\}$ 的 Huffman 编码。在这 4 个符号的概率分布下，该码的平均长度可以算得是最优的。

---

小结

1. 状态图：根据修正矩阵可见
   • $1\to\{1,2\}$、$2\to\{2,4\}$、$3\to\{1,2\}$、$4\to\{3,4\}$，
     且相应概率如前。
2. 求得 $\gamma$：令 $\pi=(1/8,1/4,1/8,1/2)$ 成为不变分布，可解得 $\gamma=\tfrac14$。
3. 熵率：在 $\gamma=1/4$ 时，用
   $\;H(\text{源}) = \sum_{i}\pi_i \,H\bigl(P(\cdot\mid i)\bigr)$
   计算可得约 $0.906$ bits。
4. Huffman 编码：对出现概率 $\tfrac12,\tfrac14,\tfrac18,\tfrac18$ 的 4 个符号，构造出的经典二叉 Huffman 码可为

   $$4\mapsto 1,\quad 2\mapsto 01,\quad 1\mapsto 000,\quad 3\mapsto 001.$$