数学之美番外篇：进化论中的概率论

数学之美番外篇：进化论中的概率论

By 刘未鹏(pongba)

C++的罗浮宫(http://blog.csdn.net/pongba)

李笑来老师在blog上转了一篇宏文，“15 Answers to Creationist Nonsense”；然后余晟同学（顺便推荐余晟同学译的《精通正则表达式》（第3版））把它给译了出来。漂亮的文章加上漂亮的翻译，当然是要拜读的:-)

进化论从其诞生以来受到的非难不计其数。这里提到的这篇便收集了广为神创论者提出以及广为大众误解的一些观点。其中有一点尤其引起了我的兴趣，如下：

8. 严格说起来，我们很难相信复杂如蛋白质的物质能偶然出现，更不用说人或是活细胞了。

偶然性在进化中确实存在（例如，偶然性的突变可以产生新的特征），但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最主要机制，却会明确保留“需要的”（能适应的）特性，消除“不需要的”（无法适应的）特性。只要选择的影响力存在，自然选择就能把进化向一个方向推进，在出乎意料的短时间内产生复杂的结构。举个例子，现有由13个字母构成的序列“TOBEORNOTTOBE”，假设有几百万只猴子，每只猴子每秒钟挑一条短语，需要78,800年才能从26^13种可能中选出这样的排列。不过，Glendale College的Richard Hardison在20世纪80年代写过一个程序，它能够在随机产生序列的同时，保证那些已经出现在正确位置上的字母不会变化（这样做倒有点《汉姆雷特》 的味道。译注：这个句子看了大半天才明白，嘿嘿）。这个程序平均只需要336次迭代就能生成上文提到的短语，时间少于90秒。更神奇的是，把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。

关于这个随机枚举特定的13字母的单词的问题有点意思。如果是纯粹随机枚举的话，由于长度为13的单词一共有26^13个不同的（假设所有组合都是有效单词的话），其中只有一个跟目标单词一样，也就是说平均（数学期望）枚举26^13次才能枚举出目标串来。

我们不妨把人类的DNA链当成一个长长的单词。突变是产生随机枚举的动力。那么根据上面的分析，要枚举出我们现在用的DNA，需要的迭代次数将是跟DNA链上的“字母数”（碱基对）成指数关系的。枚举一个13个字母的单词就需要26^13次方了，上亿碱基对，需要多少次迭代？更不要说人类的一代更迭就平均要耗上十来二十年了。

从这个角度来看，作为生命只有短短几十年的我们，似乎的确很难理解像眼睛这么复杂精妙的结构是如何从随机的突变中产生出来的。而这也恰恰是神创论者最经常用来非难进化论的论点之一。那么，这个貌似有力的论点到底正确与否呢？其实，在达尔文同学的《物种起源》中就已经进行了一定程度的驳斥。达尔文同学列举了一系列的比我们人类眼睛简单的眼睛结构，从复杂逐渐到简单，其中最简单的“眼睛”只由一些聚集在一起的感光细胞构成；并且，达尔文同学还雄辩了为什么眼睛的复杂性并非是不可归约（irreducible）的。

然而，达尔文同学毕竟不是专业的理工科出生（在大学里面是学神学的），虽然其实践精神是每个科学家的楷模，虽然在《物种起源》中他运用了一系列的证据和推理，某种程度上论证了随机突变加上自然的选择之手，的确能够进化出如眼睛这么复杂的结构。然而他并没有从数学上加以证明，为什么定向选择能够导致在短得多的时间内产生复杂结构，以及这个时间与纯随机枚举相比到底短到什么程度？

我们仍以那个13个字母的单词为例TOBEORNOTTOBE。如果是纯随机枚举的话，平均需要26^13次方才能枚举出一个来。那么，自然中的进化过程也是这样的吗？并非如此。虽然每一个基因位都可能发生变异，然而自然选择之手会将那些“好”的部分留下来，差的部分剔掉（因为突变出来的好基因比差基因更有生存繁殖优势，于是渐渐就会在种群中通过遗传扩散开来）。反映在我们枚举单词的过程中就是，一旦我们枚举出了某个或某些特定位上的字母，那么这个字母就确定下来，不再变动，只需继续枚举剩下来的字母。这样，直觉上需要枚举的次数就会大大减少。而实际上也正是如此，引文中提到的Richard同学写的一个程序便说明了这一点：本来需要78,800年，现在只需90秒。差异何等巨大！

现在，我们关心的问题是，按照后一种枚举方法，能从数学上精确计算出来，要枚举出这个目标单词需要的迭代次数的数学期望吗？（即，平均枚举多少次，才能枚举出它呢？）

Richard同学写的那个程序显示需要平均336次；然而，问题是他写的是一个程序，而不是用数学来计算到底需要多少次。336次是数学期望吗？不是。它是一个实践值。

实际上，我也写了一个这样的程序，然而结果显示却是大约82次左右。那么到底谁的正确呢？

要检验这个结论，更重要的问题是，应该有一个数学方法能够计算出按照这种方法，可（数学）期望通过迭代多少次就迭代出目标串。

为了从数学上解决这个问题。我们需要用到一点基本的概率论知识：

如果一个随机变量X的值为x_i的几率是P_i，那么X的数学期望Ex就等于∑x_iP_i。举个例子，假设小明的考试成绩为90分的概率为30%，为80分的概率为70%，那么小明的成绩的数学期望便是90×30%+80×70%=83（虽然83其实是个不可能的成绩）。

回到我们要求解的问题：我们想知道需要枚举多少次才能枚举出目标单词。要求解这个问题，我们可以反过来思考：平均每枚举一次能正确枚举出目标单词上的几个字母（这里“正确”的意思当然是要满足“在相同位置上的字母也相同”，比如目标单词是TUBE的话，一旦枚举出POTE，我们就说正确枚举出了最后一个字母E，而T由于位置不对应，因此就不能算是正确的了）。

很显然，平均一次能正确枚举出的字母数目是一个随机变量，不妨令为X。该随机变量依赖于在这次枚举中，目标单词上的每一个位置上的字母是否被正确枚举出来了，于是我们设目标单词第i位上的字母被枚举的结果（即是否枚举中——只有“中”或“不中”两种结果，因而是一个二元随机变量）为随机变量X_i；X_i只有“中”或“不中”两种可能，我们将“中”的值量化为1，“不中”为0。由于每一位上枚举中的概率都是独立同分布的，因此对于任意一个X_i来说，为0（“不中”）的概率皆为25/26；为1（“中”）的概率皆为1/26。这很容易理解，因为字母表中一共有26个字母，随机选择一个，跟目标字母相同的概率自然是1/26，不同的概率则是25/26。

有了X_i，我们进一步发现，X其实是X_i的函数：X = ∑X_i。这个式子这样理解：如果在位置i处枚举中了，那么X_i便是1，这样就给总共枚举中的位数X贡献了1；否则X_i则为0，即没有贡献。

现在，我们回过头审视我们想要求得的东西：我们想求得是枚举一次能正确枚举出目标单词上的字母数目的数学期望。也就是X的数学期望EX。由于X = ∑X_i。于是EX = E(∑X_i) = ∑EX_i。而EX_i­对每个X_i是相同的（独立同分布嘛），都是0×25/26 + 1×1/26 = 1/26。因此EX = n×EX_i（其中n是目标单词的长度——本例中是13）= 13×1/26 = 1/2。

综上，我们得出结论：随机枚举一次可（数学）期望枚举中目标单词上的1/2个字母。

1/2个字母？是不是开玩笑？哪有“半个字母”的说法？实际上，因为是数学期望，而数学期望的值很可能并非所有可能值中的任一个，而是它们的概率加权平均，所以半个字母的说法在数学期望上是说得通的；更关键的是，这个期望值给我们提供了一个极其重要的信息，那就是要想枚举中其中的一位，我们（数学期望上）需要枚举2次才行（因为每次枚举中1/2位）。

一旦枚举中了其中的一位，那么后面的随机枚举过程便不需要考虑这一位，只需要考虑剩下的了。换句话说，目标单词中的字母便被剔掉了一个，只剩12个字母。而在12个字母的单词中，要想再枚举中一位，需要多少次迭代呢？重用上面的推导过程，EX仍然还是等于n×EX_i。EX_i没变，而n变成了12。即迭代一次平均命中12/26个字母，那么要完全命中其中一位字母，便需要26/12（即2.17次）。

如此类推，每次减掉其中的一个字母需要特定次数的枚举，一直到减至只剩最后一个字母，需要26次。把所有这些枚举次数的期望值加起来，便是总共需要枚举的次数了。即26/13 + 26/12 + 26/11 + … + 26/1 ~= 82.68次。

另一种思路

我们回顾一下上一个解法过程中的核心问题：要命中其中的一个字母，（数学期望上）需要枚举多少次，我们令这个次数为随机变量X。我们回顾一下数学期望的本质定义：每个可能的值的概率加权平均。于是，要求得X的数学期望EX，我们只需知道X所有可能的取值以及对应于各个取值的概率。

那么，要命中其中一个字母，究竟需要枚举多少次呢？可能是一次就中了，也可能需要两次，也可能需要三次…你会发现，有可能需要任意次。只不过随着所需次数的增加，概率也越来越小。实际上，这是一个无穷级数求和问题；所幸，你马上就会看到，这个求和其实很简单。

所谓一次就命中的意思是，只随机枚举一次，就会命中目标单词中的一个且仅一个字母。这个随机事件由三个部分组成，首先是其余n-1个字母不中，然后是剩下的1个字母中了，再然后是那个命中的字母有n种可能的位置。因此，其概率是[(25/26)^(n-1)]×1/26×n。同理，需要两次才能命中其中一个字母的概率是(25/26)^n×1/26×n×[(25/26)^(n-1)]…以此类推。

而命中其中一个字母所需枚举次数X的数学期望是：

1×一次就中的概率 + 2×二次才中的概率 + 3×三次才中的概率 + …

也就是：

1/26×n×(25/26)^(n-1) [1 + 2×(25/26)^n + 3×(25/26)^2n + 4×(25/26)^3n … ]

左边方括号内的无穷级数求和的形式为1+2q+3q^2+4q^3+…，结果为1/(1-q)^2（利用类似等比级数求和的技巧——错位相减），所以上式求和简化后的结果为：

[n×25^(n-1)×26^n]/[(26^n-25^n)^2]

即，当目标单词长为n时，平均需要[n×25^(n-1)×26^n]/[(26^n-25^n)^2]次枚举才能命中其中一个字母；而一旦命中一个字母之后，该字母就会被从单词当中剔掉，并继续枚举第二个字母，此时n减少了1，因而上式的值也发生了变化。

简言之，长度为N的单词，需要∑[n×25^(n-1)×26^n]/[(26^n-25^n)^2]次（其中n从1变化到N）迭代便能够完全枚举出来。

现在我们回到原来的问题：一个长为13的单词，TOBEORNOTTOBE，究竟需要枚举多少次才能够完全枚举出来呢？按照以上的式子，得出的结果是82.39。而采用前面的不精确近似，计算的结果82.68。跟我自己写的一个枚举程序运行一万次平均之后的结果刚好相符，后者也是在82左右徘徊。

不过，以上两种做法其实都建立在一个假设之上，即我们是一个一个地枚举出目标单词中的字母的。不是两个，也不是三个。然而实际当中可能一次就枚举出多个乃至全部的字母。因此，其实以上两种做法计算出的都是一个不精确的值，这也是为什么它们的结果相近但不一样的原因（真正的结果只有一个）。然而，如果想给出精确表达式或计算方法就非常复杂了，或者说至少我没有想到更简单的表达方法，如果你有不妨告诉我:-)

小结

本文介绍了隐藏在自然选择中的概率论，并说明了为什么自然选择能够在相对（与纯随机枚举相比）极短的时间内塑造出复杂的有机体；简而言之，选择之手总是不断地将生物的基因向某个方向推进，一旦基因中变异出有益的片段，该片段就会被选择保留下来并逐渐在种群中蔓延开来，反映到文中讨论的枚举单词的例子中就是，一旦某个位上的字母被枚举出来，便会被保留住，不再受到后续变异的影响（除非是更好的变异）（通过一个数学示例，我们看到，原本需要26^13次迭代才能产生的目标序列，只需82次居然就进化出来了，其间的差距是无法估计的；事实上，计算机算法上就有使用进化思想来实现算法的，也就是所谓的进化算法）；再则，加以种群中数量巨大的个体（每个个体都是一个单独的枚举器），我们就不难理解为什么自然选择能够进化出复杂如眼睛的结构了。

Update <chsdate w:st="on" isrocdate="False" islunardate="False" day="3" month="12" year="2007">2007-12-3</chsdate>：徐宥同学指出，在Richard原来写的那个程序中，是采用的“挨个枚举”办法。即先枚举出第一个字母（期望需要26次），然后枚举第二个，如此直到把所有字母枚举完。如此需要的时间为13×26=338；符合文中给出的值。如此说来，之所以我得出的结果跟Richard的不一样，是因为采用的枚举策略不一样，我将“一次枚举”定义为“枚举整个单词”，而非“枚举其中某个字母”。不过我感觉Richard的那个枚举策略显然不符合自然选择的工作方式，自然状况下，每一个基因位（“字母”）都可能发生变异（独立分布，不过变异概率未必一样），而对变异基因的择优筛选则发生在“遗传”这一个环节（严格来说是发生在遗传过程中的“差异繁殖率”上）。

不过，总而言之，尽管计算机模拟的选择算法不同，总的思想是一样的，即一旦加入了“选择之手”，就能够极大地加快进化的速度。

下期预告？

本来打算写写Google Pagerank算法的，但那玩意往细了写太麻烦，总找不出动力，所以索性先写篇短的:-) Google Pagerank算法是数学与工程的完美结合，其中蕴含了数学的纯粹和工程的务实，实在值得欣赏，所以，强烈推荐下面这篇：

How Google Finds Your Needle in the Web's Haystack，那么这篇有多火呢？del.icio.us上save的人竟有1,774人！可见一斑。

注：

1. 最近Feedburner抓取feed似乎出问题了，然而还有近200位同学通过Feedburner订阅了C++的罗浮宫（本来用FB的时候没预料到“墙”的问题，sigh~），所以，麻烦用FB订阅的同学转为用下面的feedsky订阅:-)

http://feed.feedsky.com/pongba

又或者你也可以直接订阅原始rss：

http://blog.csdn.net/pongba/rss.aspx

2. CSDN Blog终于支持全文rss输出了，从昨天开始，C++的罗浮宫改为全文输出。

3. As Always，欢迎加入我们的讨论组——TopLanguage（http://groups.google.com/group/pongba），自从8月份建立以来，我们已经吸引了三百位同学，二千五百多条讨论，想知道我们讨论些什么，参见TopLanguage讨论精选[一]，精选[二]，精选[三]，加入前请看这里。