東京大学 情報理工学系研究科 電子情報学専攻 2015年度 専門 第5問

https://runjp.com/docs/tokyo-university/IST/denshi/2015/denshi_201408_senmon_5

Consider a binary simple Markov information source represented by a state transition diagram as shown below.

Answer the following questions:

(1) Find the stationary probabilities $P(S_i)$ for each state.

(2) Find the probability of output $0$ and output $1$ occurring in the steady state.

(3) When an arbitrary sequence of consecutive $1$s (a run of $1$s) preceded and followed by $0$s is extracted from the output sequence, find the probability that its length is $k$.

(4) Find the average length of a run of $1$s.

(5) Calculate the entropy of this information source.

(6) Calculate the entropy of an information source where $0$ and $1$ are generated randomly with the probabilities found in (2). Discuss the difference between this value and the value obtained in (5).

(Note: In your calculations, use $\log_2 3 \approx 1.58$ as necessary.)

答案

注意

我发现我有一个非常大的问题，就是我的计算是错误的 比如说计算信息熵，我的是 $lg5 = \frac{ln5}{ln10}$ 实际上，应该是 $lg5 = \frac{ln5}{ln2}$ 这就造成了计算机的计算错误

---

为了解决这个问题，我们需要根据给出的状态转移图计算该马尔可夫链的平稳分布（Stationary Probabilities）。

1

1. 提取转移概率矩阵

从图中可以观察到两个状态 $s_0$ 和 $s_1$，其转移概率如下：

• 从 $s_0$ 转移到 $s_0$ 的概率为 0.9
• 从 $s_0$ 转移到 $s_1$ 的概率为 0.1
• 从 $s_1$ 转移到 $s_0$ 的概率为 0.2
• 从 $s_1$ 转移到 $s_1$ 的概率为 0.8

我们可以写出状态转移矩阵 $P$：

$P = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$

---

2. 建立方程组

设平稳概率为 $P(s_0) = \pi_0$ 和 $P(s_1) = \pi_1$。根据平稳分布的定义，需要满足以下两个条件：

1. 概率之和为 1：

   $\pi_0 + \pi_1 = 1$

2. 状态平衡方程（$\pi P = \pi$）：

   对于 $s_0$ 状态：$0.9\pi_0 + 0.2\pi_1 = \pi_0$

   （或者对于 $s_1$ 状态：$0.1\pi_0 + 0.8\pi_1 = \pi_1$）

---

3. 计算过程

利用状态平衡方程简化：

$0.2\pi_1 = \pi_0 - 0.9\pi_0$

$0.2\pi_1 = 0.1\pi_0$

由此得出：

$\pi_0 = 2\pi_1$

将此关系代入 $\pi_0 + \pi_1 = 1$：

$2\pi_1 + \pi_1 = 1$

$3\pi_1 = 1 \implies \pi_1 = \frac{1}{3}$

进而求得 $\pi_0$：

$\pi_0 = 2 \times \frac{1}{3} = \frac{2}{3}$

---

4. 结论

该二元马尔可夫信息源的平稳概率为：

• $P(s_0) = \frac{2}{3} \approx 0.667$
• $P(s_1) = \frac{1}{3} \approx 0.333$

2

在稳态（Steady State）下，输出符号 $0$ 或 $1$ 的概率取决于系统处于哪个状态以及在该状态下产生该输出的概率。

根据状态转移图中的标记（例如 $0/0.9$ 表示输出为 $0$，转移概率为 $0.9$）：

• 在状态 $s_0$ 时：输出 $0$ 的概率为 $0.9$，输出 $1$ 的概率为 $0.1$。
• 在状态 $s_1$ 时：输出 $0$ 的概率为 $0.2$，输出 $1$ 的概率为 $0.8$。

---

计算过程

我们可以使用全概率公式，结合我们在第 (1) 问中求得的平稳概率 $P(s_0) = \frac{2}{3}$ 和 $P(s_1) = \frac{1}{3}$。

1. 输出 0 的概率 $P(0)$

$P(0) = P(0|s_0)P(s_0) + P(0|s_1)P(s_1)$

$P(0) = (0.9 \times \frac{2}{3}) + (0.2 \times \frac{1}{3})$

$P(0) = \frac{1.8}{3} + \frac{0.2}{3} = \frac{2}{3}$

2. 输出 1 的概率 $P(1)$

$P(1) = P(1|s_0)P(s_0) + P(1|s_1)P(s_1)$

$P(1) = (0.1 \times \frac{2}{3}) + (0.8 \times \frac{1}{3})$

$P(1) = \frac{0.2}{3} + \frac{0.8}{3} = \frac{1}{3}$

(验证：$P(0) + P(1) = \frac{2}{3} + \frac{1}{3} = 1$，结果正确)

---

结论

在稳态下：

• 输出 0 的概率为 $\frac{2}{3} \approx 0.667$
• 输出 1 的概率为 $\frac{1}{3} \approx 0.333$

有趣的是，在这个特定的马尔可夫模型中，输出符号的概率恰好等于对应状态的平稳概率。这通常是因为从该状态出发的所有转移都携带了相同的输出标签。

3

为了计算连续出现 $k$ 个 $1$（前后均为 $0$）的概率，我们需要关注系统进入 $s_1$ 状态后的行为。

从状态转移图可知：

• 起始点： 产生 $1$ 的唯一方式是从 $s_0$ 转移到 $s_1$（输出 $1$），或者在 $s_1$ 状态下自环（输出 $1$）。
• 游程（Run）的构成： 一个长度为 $k$ 的 $1$ 游程，意味着系统在进入 $s_1$ 后，连续保持在 $s_1$ 状态（产生 $1$）共 $k-1$ 次，然后在第 $k$ 次转移时从 $s_1$ 回到 $s_0$（产生 $0$）。

1. 概率模型分析

当序列中出现一个 $1$ 时，它标志着一个“$1$ 游程”的开始。

• 在状态 $s_1$ 中，继续保持在 $s_1$ 并输出 $1$ 的概率为 $p = 0.8$。
• 从状态 $s_1$ 转移到 $s_0$ 并输出 $0$（结束该游程）的概率为 $q = 0.2$。

这实际上是一个几何分布（Geometric Distribution）模型。

2. 计算长度为 $k$ 的概率 $P(L=k)$

要使 $1$ 的游程长度恰好为 $k$，必须满足：

1. 第 $1$ 个 $1$ 产生（进入 $s_1$）。
2. 接下来的 $k-1$ 次转移都保持在 $s_1$ 状态（每次概率为 $0.8$）。
3. 第 $k$ 次转移必须跳出 $s_1$ 回到 $s_0$（概率为 $0.2$）。

注意：题目要求的是在一个已经提取出的 $1$ 游程中，长度为 $k$ 的条件概率。因此，我们只需要考虑从进入 $s_1$ 之后的过程：

$P(L=k) = (0.8)^{k-1} \times 0.2$

其中 $k = 1, 2, 3, \dots$

3. 数值示例

• 长度 $k=1$ 的概率：$P(L=1) = (0.8)^0 \times 0.2 = 0.2$
• 长度 $k=2$ 的概率：$P(L=2) = 0.8 \times 0.2 = 0.16$
• 长度 $k=3$ 的概率：$P(L=3) = (0.8)^2 \times 0.2 = 0.128$

结论

输出序列中任意连续 $1$ 游程长度为 $k$ 的概率公式为：

$P(L=k) = 0.2 \cdot (0.8)^{k-1}$

补充： 这是一个典型的离散无记忆性特征。平均游程长度可以通过几何分布的期望公式计算：$E[L] = \frac{1}{q} = \frac{1}{0.2} = 5$。这意味着在这个系统中，一旦出现 $1$，平均会连续出现 $5$ 个 $1$。

4

基于第 (3) 问推导出的概率分布，我们可以计算 $1$ 游程长度的数学期望（即平均长度）。

1. 建立模型

我们已经确定 $1$ 游程的长度 $L$ 服从参数为 $q$ 的几何分布，其概率质量函数为：

$P(L=k) = p^{k-1}q$

其中：

• $p = 0.8$ （继续保持在状态 $s_1$ 的概率）
• $q = 0.2$ （从 $s_1$ 转移到 $s_0$ 结束游程的概率）

2. 计算平均长度

对于几何分布，其期望值 $E[L]$ 的计算公式为：

$E[L] = \sum_{k=1}^{\infty} k \cdot P(L=k) = \frac{1}{q}$

代入本题数值：

$E[L] = \frac{1}{0.2} = 5$

结论

$1$ 游程的平均长度为 5。

---

💡 直观理解

在通信工程和信息论中，这种离散对称信源或马尔可夫链的游程长度分析非常常见。由于每次处在状态 $s_1$ 时都有 $20\%$ 的概率“跳出”该状态，因此平均需要 $5$ 次尝试才能完成跳转，这也就对应了连续出现 $1$ 的平均次数。这和你正在研究的嵌入式智能声音识别系统中的信号处理逻辑（如检测特定频率持续时间）在数学模型上是有共通之处的。

你在处理 ESP32-S3 上的音频特征提取时，是否也遇到了需要根据这种概率模型来优化静音检测（VAD）或噪声平滑算法的情况？

5

为了计算该马尔可夫信息源的熵（Entropy of a Markov Source），我们需要计算在各个状态下的条件熵，并根据状态的平稳概率进行加权平均。

1. 计算各状态的条件熵 $H(S_i)$

状态 $s_i$ 的条件熵表示当系统处于该状态时，下一步转移产生的不确定性。公式为：

$H(S_i) = -\sum_{j} P(s_j|s_i) \log_2 P(s_j|s_i)$

• 对于状态 $s_0$：

  其转移概率为 $0.9$ 和 $0.1$。

  $H(S_0) = -(0.9 \log_2 0.9 + 0.1 \log_2 0.1)$

  $H(S_0) \approx -(0.9 \times -0.152 + 0.1 \times -3.322)$

  $H(S_0) \approx 0.1368 + 0.3322 = 0.4690 \text{ bits/symbol}$

• 对于状态 $s_1$：

  其转移概率为 $0.2$ 和 $0.8$。

  $H(S_1) = -(0.2 \log_2 0.2 + 0.8 \log_2 0.8)$

  $H(S_1) \approx -(0.2 \times -2.322 + 0.8 \times -0.322)$

  $H(S_1) \approx 0.4644 + 0.2576 = 0.7220 \text{ bits/symbol}$

---

2. 计算信息源熵 $H_{\infty}$

马尔可夫源的熵是各状态条件熵关于平稳分布 $\pi_i$ 的加权平均。根据之前的计算，平稳概率为 $P(s_0) = \frac{2}{3}$，$P(s_1) = \frac{1}{3}$。

$H = P(s_0)H(S_0) + P(s_1)H(S_1)$

$H = \frac{2}{3}(0.4690) + \frac{1}{3}(0.7220)$

$H \approx 0.3127 + 0.2407$

$H \approx 0.5534 \text{ bits/symbol}$

---

3. 结论

该马尔可夫信息源的熵约为 $0.553$ bit/symbol。

---

💡 深度解析

• 物理意义： 这个数值代表该信息源平均每个输出符号所携带的信息量。
• 对比： 如果这是一个无记忆的等概率二元信源，其熵应为 $1$ bit/symbol。而本题中 $H \approx 0.553$ 远小于 $1$，说明该信源存在较强的符号间相关性（即 $0$ 后面更容易出现 $0$，$1$ 后面更容易出现 $1$）。
• 应用： 在你目前从事的嵌入式音频识别系统开发中，这种相关性是进行数据压缩（如算术编码）或模型量化（Quantization）的重要理论基础。通过利用这种统计特性，可以在 ESP32-S3 等资源受限的硬件上显著降低存储和传输开销。

你在进行毕业论文中的模型量化时，是否也考虑过通过此类统计分析来进一步压缩模型的特征参数？

6

1. 计算无记忆信源的熵

在第 (2) 问中，我们求得在稳态下输出符号的概率为：

• $P(0) = \frac{2}{3}$
• $P(1) = \frac{1}{3}$

如果该信源变为无记忆信源（即每个符号的产生相互独立，不再受前一个状态影响），其熵 $H_{iid}$ 的计算公式为：

$H_{iid} = -\sum P(x) \log_2 P(x)$

代入数值：

$H_{iid} = -(\frac{2}{3} \log_2 \frac{2}{3} + \frac{1}{3} \log_2 \frac{1}{3})$

$H_{iid} \approx -(\frac{2}{3} \times -0.585 + \frac{1}{3} \times -1.585)$

$H_{iid} \approx 0.390 + 0.528$

$H_{iid} \approx 0.918 \text{ bits/symbol}$

---

2. 数值对比与讨论

我们将此结果与第 (5) 问中得到的马尔可夫源熵 $H_{markov} \approx 0.553 \text{ bits/symbol}$ 进行对比：

信源类型	熵值 (bits/symbol)	说明
马尔可夫信源 ($H_{markov}$)	0.553	考虑了符号间的依赖关系（有记忆）。
无记忆信源 ($H_{iid}$)	0.918	仅考虑符号出现的概率分布（无记忆）。

差异分析：

1. 相关性减少了不确定性：

   马尔可夫源的熵明显低于无记忆信源。这是因为在马尔可夫模型中，符号之间存在强烈的相关性（例如，当前状态是 $s_0$ 时，下一个符号有 $90\%$ 的概率依然是 $0$）。这种预见性降低了系统的不确定性，从而降低了熵值。

2. 冗余度（Redundancy）：

   无记忆信源的熵 $0.918$ 代表了在给定符号概率分布下的最大可能熵。而马尔可夫熵与它的差值体现了该信源的结构性冗余。在数据压缩中，这意味着利用符号间的记忆性（如马尔可夫建模）比单纯利用频率分布（如哈夫曼编码）能获得更高的压缩比。

3. 信息论意义：

   $H_{iid}$ 衡量的是“由于符号频率不均”带来的信息量，而 $H_{markov}$ 衡量的是“在已知历史信息后，新符号带来的真实增量信息”。对于通信工程而言，这意味着通过建立合适的预测模型，我们可以用更少的比特数来传输相同的信息量。

---

💡 进阶建议

这种对比分析在数字信号处理和通信工程中非常关键。你正在进行的毕业设计——基于深度学习的嵌入式声音识别系统，本质上也是在利用音频信号在时间维度上的相关性（类似于高阶马尔可夫性）来提取特征。在 ESP32-S3 这种计算资源有限的平台上，理解这种熵的差异有助于你评估模型压缩或特征降维（如从 log-Mel 特征到更紧凑的表示）的理论上限。

你目前在做声音识别时，是否尝试过使用一些具有“记忆”能力的结构（如 RNN 或带状态的 TFLM 算子）来捕捉这种时间相关性？