熵率

熵率是要探讨信源编码的长期平均速率的极限。现在我们先要复习一些概率论基础，我本来是不想在这边写这些的，但是我没单独写概率论，所以还是提一下。以后的内容均在一定程度上依赖于基础实分析。

随机过程

• 严格的来说我也没修过随机过程这门课，所以这里我们只谈信源编码的随机过程。设想这样的场景：给定某一信源，其每次发送一个信息，用随机变量 表示。这样我们得到了一个随机变量的序列： 每一个 都可能依赖于先前的 。以下我们都只关注这样的随机过程。

  我们称一个随机过程是稳态，当且仅当其的任意子集的联合分布具备下标的平移不变性。

  对于随机过程 ，我们称其为马尔可夫过程，当且仅当： 我们称马尔可夫过程具备时间不变性（或齐次），当且仅当相邻随机变量的条件分布相同，即： 若无特别说明，以下我们均只考虑齐次马尔可夫过程。我们定义马尔可夫过程的转移矩阵为： 若记 的分布为 是一行向量，则： 而当初始分布 满足 时，该马尔可夫过程是稳态随机过程。

熵率

• 对于描述信源编码的随机过程，我们定义其熵率为： 即平均熵的极限。下面我们考察稳态随机过程的熵率的存在性。注意到： 考虑 ，有： 这说明 是关于 单减的。而熵是非负的，因此其必然收敛于一定值，记其为： 显然 ，因此稳态随机过程的熵率必然存在。而对于稳态马尔可夫过程，其熵率恰为 。¹

• 特别值得一提的是，对于独立同分布的信源，通过块编码，我们是可以逼近熵率这一下界的²。即： 比起以后将要介绍的典型集编码，块编码其实更加简单一些，不过典型集编码具备更大的理论价值。

---

1. 另外 Slides 上也有介绍隐马尔可夫模型，但是比较复杂，而且分析比较繁琐，就懒得写了。↩︎

2. 我们先承认，熵率是无损编码的码率下界。↩︎