R04-B-問2

問2

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

$$\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0& 0.5\\ 0.5& 0.5& 0& 0\\ 0& 0& \gamma & 1-\gamma \end{array}\right)$$

で与えられたとする．ここで, $(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\}$ 的简单马尔可夫信息源, 其状态转移概率矩阵如下:

$$\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0& 0.5\\ 0.5& 0.5& 0& 0\\ 0& 0& \gamma & 1-\gamma \end{array}\right)$$

其中 $(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=\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0& 0.5\\ 0.5& 0.5& 0& 0\\ 0& 0& \gamma & 1-\gamma \end{array}\right)$$

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

题目设定：

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

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\stackrel{0.5}{\to }1$ 和 $1\stackrel{0.5}{\to }2$。

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

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

• 行 4 (i=4):
  $P(4\to 3)=\gamma ,P(4\to 4)=1-\gamma$，其余为 0。
  即：$4\stackrel{\gamma }{\to }3$ 和 $4\stackrel{1-\gamma }{\to }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,\text{即}{\pi }_j=\sum _{i=1}^4{\pi }_{i}P(i\to j),j=1,2,3,4.$$

令 $\pi =({\pi }_1,{\pi }_2,{\pi }_3,{\pi }_4)=(\frac{1}{8},\frac{1}{4},\frac{1}{8},\frac{1}{2})$。

(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 =\frac{1}{2}\gamma .$$

但题目给出 ${\pi }_3=\frac{1}{8}$，故

$$\frac{1}{8}=\frac{1}{2}\gamma ⟹\gamma =\frac{1}{4}.$$

(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 )=\left(\frac{1}{4}\right)\times 0.5+\left(\frac{1}{2}\right)\times (1-\gamma ).$$

题目给定 ${\pi }_4=\frac{1}{2}$，又我们已知 $\gamma =\frac{1}{4}$，代入则

$$\text{左边}=\frac{1}{2};\text{右边}=\frac{1}{4}\times 0.5+\frac{1}{2}\times (1-\frac{1}{4})=\frac{1}{8}+\frac{1}{2}\times \frac{3}{4}=\frac{1}{8}+\frac{3}{8}=\frac{1}{2}.$$

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

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

---

3. 在 $\gamma =\frac{1}{4}$ 时，这个马尔可夫源的熵率

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

$$H(\text{源})=\sum _{i=1}^4{\pi }_{i}H(P(\cdot \mid i))=\sum _{i=1}^4{\pi }_i(-\sum _{j}P(i\to j){\log }_{2}P(i\to j)),$$

其中对 $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=-(0.5{\log }_{2}0.5+0.5{\log }_{2}0.5)=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 =\frac{1}{4},P(4\to 4)=1-\gamma =\frac{3}{4}$。
  分布 $(0,0,\frac{1}{4},\frac{3}{4})$ 的熵为

  $$\begin{array}{rl}{H}_4& =-(\frac{1}{4}{\log }_2\frac{1}{4}+\frac{3}{4}{\log }_2\frac{3}{4})\\ & =-(\frac{1}{4}\times (-2)+\frac{3}{4}{\log }_2(0.75))\\ & =\frac{1}{2}-\frac{3}{4}{\log }_2(0.75).\end{array}$$

  数值上，${\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{array}{rl}H(\text{源})& ={\pi }_1{H}_1+{\pi }_2{H}_2+{\pi }_3{H}_3+{\pi }_4{H}_4\\ & =\frac{1}{8}\times 1+\frac{1}{4}\times 1+\frac{1}{8}\times 1+\frac{1}{2}\times 0.8113\\ & =(\frac{1}{8}+\frac{1}{4}+\frac{1}{8})\times 1+\frac{1}{2}\times 0.8113\\ & =\frac{1}{8}+\frac{2}{8}+\frac{1}{8}+0.40565\\ & =\frac{4}{8}+0.40565=0.5+0.40565=0.90565\text{ bits (近似)}.\end{array}$$

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

$$\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=\frac{1}{8},p_2=\frac{1}{4},p_3=\frac{1}{8},p_4=\frac{1}{2},$$ 进行 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,s_2=1/4,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 =\frac{1}{4}$。
3. 熵率：在 $\gamma =1/4$ 时，用
   $H(\text{源})={\sum }_i{\pi }_{i}H(P(\cdot \mid i))$
   计算可得约 $0.906$ bits。
4. Huffman 编码：对出现概率 $\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{8}$ 的 4 个符号，构造出的经典二叉 Huffman 码可为 $$4\mapsto 1,2\mapsto 01,1\mapsto 000,3\mapsto 001.$$