背景
前两天有同事分享看到信息熵的公式觉得非常巧妙，一下子把我的回忆带回到了15年的前本科时代，那时候学习过一门很有意思的课程信息论。信息论基本上就是祖师爷Claude Shannon一篇无比经典的论文A Mathematical Theory of Communication 安排的明明白白。本科时候我准备尝试去看这个论文，结果卡在第一处后就不了了之了，至今记忆犹新。
后来在Pivotal时期开发Greenplum，某个时段我花了大量时间学习Analytical Combinatorics, 由同事的话头起，我感觉这就是一个简答的组合问题，尤其是，如果用Symbolic Method的话，就会跟搭积木一样简单。
问题描述
考虑离散信源，基础符号集合是一个有限的离散集，并且假设每一个符号出现的概率是一样的。传输这些信号，需要用某种信道，研究信道的第一反应就是，打满的情况，信息的流动最大速度是多少呢？即容量问题。
再考虑容量问题之前，香农简单快捷的给出了信息的度量办法（引用了前人的成果，他自己做了总结）：对离散等概信源，就是丰富程度（基数）然后取对数。
综上很自然的可以给出容量的统计意义上的定义:
C = \lim_{T \to \infty} \frac{log N(T)} {T}那么接下来问题的全部，就是如何得到丰富程度N(T)渐近结果(Asymptotic Results)下面我们用Analytical Combinatorics的办法。
Analytical Combinatorics: Symbolic Method
我们考虑问题的时间刻度是可数的。则信源符号的有限离散集合是\{S_i | 1 \le i \le K\}, 共计有K个符号。符号S_i单据的时间单元是n_i, n_i\in \mathbb{N}。记每个时间单元的Symbol是\circ，则根据符号的占据时间，可以写出每个信源符号的表示：S_i: \text{SEQ}_{n_i} (\circ)。整个信息流的组合结构是: \text{SEQ}(\bigcup _{i=1}^{K} \text{SEQ}_{n_i} (\circ)) 。有了这个组合结构的符号表达，我们一步到位就可以写出对应的生成函数(Generating Function):
\text{SEQ}(\bigcup _{i=1}^{K} \text{SEQ}_{n_i} (\circ)) \implies \\
N(z) = \frac{1}{1- (z^{n_1} + z^{n_2} + \dots + z^{n_K})} = \frac{1}{1-\sum_{i=1}^K z^{n_i}}这时候可以先用 https://www.wolframalpha.com/ 快速验证下对不对（因为论文里Shannon给了一个具体例子）:
直接代入常量，让wolframalpha做泰勒展开，选择比较大的项的系数，比如我们选择第484项：
C \sim \frac {\log (N(484))}{484} = \log_2(882495924884724\\
5033458959038942672599691386\\
04480534483900696503496493707818285)/484 = 0.535第484项已经和Shannon结果接近了。
Analytical Combinatorics: Asymptotic Analysis
这种生成函数很容易分析，是Rational functions，这里的是没有零点，只有极点，极点就是多项式的根，其中最重要的极点，决定了它的最终渐近结果。
参考 https://ac.cs.princeton.edu/online/slides/AC04-Poles.pdf 的内容进行复分析（渐近分析）：
信道容量的渐近结果是：
\lim_{n\to \infty} \frac{\log (C \beta ^ {n} n^{v-1})}{n} = \lim_{n \to \infty} \frac{\log (C)}{n} + \log(\beta) + (v-1) \frac{\log n}{n} = log(\beta)用上面的结果再做一次Shannon论文里给的具体例子，画出极点位置
其中极半径最小的是实根z = 0.688278，那么对应的\beta = \frac{1}{0.688278} = 1.4529，则信道容量的渐进结果是: \log(1.4529) = 0.5389 和论文里一致。
杂记
- “不是不报，时候未到”。一直坚持思考和学习，曾经很“吓人”的问题，说不定就可以会。
- 比如Hyperloglog的解析：https://kainwen.com/2020/06/21/a-tour-of-understanding-hyperloglog/
- 比如我儿子的玩具，原理竟然和一年多以前看的Knuth的论文有关：https://kainwen.com/2022/12/31/ghost_hunter/
- Analytical Combinatorics非常有趣！https://kainwen.com/category/analytical-combinatorics/