进化中的概率论

数学, 算法 - Written by 刘未鹏 on Sunday, December 2, 2007 18:55 - 4,551 views - 3 Comments数学之美番外篇：进化论中的概率论Tags: 数学, 概率论, 算法save it4 saved 李笑来老师在 blog 上转了一篇宏文， “15 Answers to Creationist Nonsense”；然后余晟同学（顺便推荐余晟同学译的精通正则表达式 （第 3 版） ）把它给译了出来。漂亮的文章加上漂亮的翻译，当然是要拜读的:-)进化论从其诞生以来受到的非难不计其数。这里提到的这篇便收集了广为神创论者提出以及广为大众误解的一些观点。其中有一点尤其引起了我的兴趣，如下：8. 严格说起来，我们很难相信复杂如蛋白质的物质能偶然出现，更不用说人或是活细胞了。偶然性在进化中确实存在（例如，偶然性的突变可以产生新的特征） ，但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最主要机制，却会明确保留“需要的” （能适应的）特性，消除“不需要的” （无法适应的）特性。只要选择的影响力存在，自然选择就能把进化向一个方向推进，在出乎意料的短时间内产生复杂的结构。举个例子，现有由 13 个字母构成的序列“TOBEORNOTTOBE ”，假设有几百万只猴子，每只猴子每秒钟挑一条短语，需要 78,800 年才能从 2613 种可能中选出这样的排列。不过，Glendale College的 Richard Hardison 在 20 世纪 80 年代写过一个程序，它能够在随机产生序列的同时，保证那些已经出现在正确位置上的字母不会变化（这样做倒有点汉姆雷特 的味道。译注：这个句子看了大半天才明白，嘿嘿） 。这个程序平均只需要 336 次迭代就能生成上文提到的短语，时间少于 90 秒。更神奇的是，把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。关于这个随机枚举特定的 13 字母的单词的问题有点意思。如果是纯粹随机枚举的话，由于长度为 13 的单词一共有2613 个不同的（假设所有组合都是有效单词的话） ，其中只有一个跟目标单词一样，也就是说平均（数学期望）枚举2613 次才能枚举出目标串来。我们不妨把人类的 DNA 链当成一个长长的单词。突变是产生随机枚举的动力。那么根据上面的分析，要枚举出我们现在用的 DNA，需要的迭代次数将是跟 DNA 链上的“字母数” （碱基对）成指数关系的。枚举一个 13 个字母的单词就需要 2613 次方了，上亿碱基对，需要多少次迭代？更不要说人类的一代更迭就平均要耗上十来二十年了。从这个角度来看，作为生命只有短短几十年的我们，似乎的确很难理解像眼睛这么复杂精妙的结构是如何从随机的突变中产生出来的。而这也恰恰是神创论者最经常用来非难进化论的论点之一。那么，这个貌似有力的论点到底正确与否呢？其实，在达尔文同学的物种起源中就已经进行了一定程度的驳斥。达尔文同学列举了一系列的比我们人类眼睛简单的眼睛结构，从复杂逐渐到简单，其中最简单的“眼睛”只由一些聚集在一起的感光细胞构成；并且，达尔文同学还雄辩了为什么眼睛的复杂性并非是不可归约（irreducible）的。然而，达尔文同学毕竟不是专业的理工科出生（在大学里面是学神学的） ，虽然其实践精神是每个科学家的楷模，虽然在物种起源中他运用了一系列的证据和推理，某种程度上论证了随机突变加上自然的选择之手，的确能够进化出如眼睛这么复杂的结构。然而他并没有从数学上加以证明，为什么定向选择能够导致在短得多的时间内产生复杂结构，以及这个时间与纯随机枚举相比到底短到什么程度？我们仍以那个 13 个字母的单词为例 TOBEORNOTTOBE。如果是纯随机枚举的话，平均需要 2613 次方才能枚举出一个来。那么，自然中的进化过程也是这样的吗？并非如此。虽然每一个基因位都可能发生变异，然而自然选择之手会将那些“好”的部分留下来，差的部分剔掉（因为突变出来的好基因比差基因更有生存繁殖优势，于是渐渐就会在种群中通过遗传扩散开来） 。反映在我们枚举单词的过程中就是，一旦我们枚举出了某个或某些特定位上的字母，那么这个字母就确定下来，不再变动，只需继续枚举剩下来的字母。这样，直觉上需要枚举的次数就会大大减少。而实际上也正是如此，引文中提到的 Richard 同学写的一个程序便说明了这一点：本来需要 78,800 年，现在只需 90 秒。差异何等巨大！现在，我们关心的问题是，按照后一种枚举方法，能从数学上精确计算出来，要枚举出这个目标单词需要的迭代次数的数学期望吗？（即，平均枚举多少次，才能枚举出它呢？）Richard 同学写的那个程序显示需要平均 336 次；然而，问题是他写的是一个程序，而不是用数学来计算到底需要多少次。336 次是数学期望吗？不是。它是一个实践值。实际上，我也写了一个这样的程序，然而结果显示却是大约 82 次左右。那么到底谁的正确呢？要检验这个结论，更重要的问题是，应该有一个数学方法能够计算出按照这种方法，可（数学）期望通过迭代多少次就迭代出目标串。为了从数学上解决这个问题。我们需要用到一点基本的概率论知识：如果一个随机变量 X 的值为 xi 的几率是 Pi，那么 X 的数学期望 Ex 就等于xiPi。举个例子，假设小明的考试成绩为90 分的概率为 30%，为 80 分的概率为 70%，那么小明的成绩的数学期望便是 9030%+8070%=83（虽然 83 其实是个不可能的成绩） 。回到我们要求解的问题：我们想知道需要枚举多少次才能枚举出目标单词。要求解这个问题，我们可以反过来思考：平均每枚举一次能正确枚举出目标单词上的几个字母（这里“正确”的意思当然是要满足“在相同位置上的字母也相同” ，比如目标单词是 TUBE 的话，一旦枚举出 POTE，我们就说正确枚举出了最后一个字母 E，而 T 由于位置不对应，因此就不能算是正确的了） 。很显然，平均一次能正确枚举出的字母数目是一个随机变量，不妨令为 X。该随机变量依赖于在这次枚举中，目标单词上的每一个位置上的字母是否被正确枚举出来了，于是我们设目标单词第 i 位上的字母被枚举的结果（即是否枚举中只有“中”或“不中”两种结果，因而是一个二元随机变量）为随机变量 Xi；Xi 只有“中”或“不中”两种可能，我们将“中”的值量化为 1， “不中”为 0。由于每一位上枚举中的概率都是独立同分布的，因此对于任意一个Xi 来说，为 0（“不中” ）的概率皆为 25/26；为 1（“中” ）的概率皆为 1/26。这很容易理解，因为字母表中一共有26 个字母，随机选择一个，跟目标字母相同的概率自然是 1/26，不同的概率则是 25/26。有了 Xi，我们进一步发现，X 其实是 Xi 的函数：X = Xi。这个式子这样理解：如果在位置 i 处枚举中了，那么 Xi便是 1，这样就给总共枚举中的位数 X 贡献了 1；否则 Xi 则为 0，即没有贡献。现在，我们回过头审视我们想要求得的东西：我们想求得是枚举一次能正确枚举出目标单词上的字母数目的数学期望。也就是 X 的数学期望 EX。由于 X = Xi。于是 EX = E(Xi) = EXi。而 EXi对每个 Xi 是相同的（独立同分布嘛） ，都是 025/26 + 11/26 = 1/26。因此 EX = nEXi（其中 n 是目标单词的长度本例中是 13）= 131/26 = 1/2。综上，我们得出结论：随机枚举一次可（数学）期望枚举中目标单词上的 1/2 个字母。1/2 个字母？是不是开玩笑？哪有 “半个字母”的说法？实际上，因为是数学期望，而数学期望的值很可能并非所有可能值中的任一个，而是它们的概率加权平均，所以半个字母的说法在数学期望上是说得通的；更关键的是，这个期望值给我们提供了一个极其重要的信息，那就是要想枚举中其中的一位，我们（数学期望上）需要枚举 2 次才行（因为每次枚举中 1/2 位） 。一旦枚举中了其中的一位，那么后面的随机枚举过程便不需要考虑这一位，只需要考虑剩下的了。换句话说，目标单词中的字母便被剔掉了一个，只剩 12 个字母。而在 12 个字母的单词中，要想再枚举中一位，需要多少次迭代呢？重用上面的推导过程，EX 仍然还是等于 nEXi。EXi 没变，而 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/26n。同理，需要两次才能命中其中一个字母的概率是(25/26)n1/26n(25/26)(n-1)以此类推。而命中其中一个字母所需枚举次数 X 的数学期望是：1一次就中的概率 + 2二次才中的概率 + 3三次才中的概率 + 也就是：1/26n(25/26)(n-1) 1 + 2(25/26)n + 3(25/26)2n + 4(25/26)3n 左边方括号内的无穷级数求和的形式为 1+2q+3q2+4q3+，结果为 1/(1-q)2（利用类似等比级数求和的技巧错位相减） ，所以上式求和简化后的结果为：n25(n-1)26n/(26n-25n)2即，当目标单词长为 n 时，平均需要n25(n-1)26n/(26n-25n)2次枚举才能命中其中一个字母；而一旦命中一个字母之后，该字母就会被从单词当中剔掉，并继续枚举第二个字母，此时 n 减少了 1，因而上式的值也发生了变化。简言之，长度为 N 的单词，需要 n 25(n-1)26n/(26n-25n)2次（其中 n 从 1 变化到 N）迭代便能够完全枚举出来。现在我们回到原来的问题：一个长为 13 的单词，TOBEORNOTTOBE ，究竟需要枚举多少次才能够完全枚举出来呢？按照以上的式子，得出的结果是 82.39。而采用前面的不精确近似，计算的结果 82.68。跟我自己写的一个枚举程序运行一万次平均之后的结果刚好相符，后者也是在 82 左右徘徊。不过，以上两种做法其实都建立在一个假设之上，即我们是一个一个地枚举出目标单词中的字母的。不是两个，也不是三个。然而实际当中可能一次就枚举出多个乃至全部的字母。因此，其实以上两种做法计算出的都是一个不精确的值，这也是为什么它们的结果相近但不一样的原因（真正的结果只有一个） 。然而，如果想给出精确表达式或计算方法就非常复杂了，或者说至少我没有想到更简单的表达方法，如果你有不妨告诉我:-)小结本文介绍了隐藏在自然选择中的概率论，并说明了为什么自然选择能够在相对（与纯随机枚举相比）极短的时间内塑造出复杂的有机体；简而言之，选择之手总是不断地将生物的基因向某个方向推进，一旦基因中变异出有益的片段，该片段就会被选择保留下来并逐渐在种群中蔓延开来，反映到文中讨论的枚举单词的例子中就是，一旦某个位上的字母被枚举出来，便会被保留住，不再受到后续变异的影响（除非是更好的变异） （通过一个数学示例，我们看到，原本需要 2613 次迭代才能产生的目标序列，只需 82 次居然就进化出来了，其间的差距是无法估计的；事实上，计算机算法上就有使用进化思想来实现算法的，也就是所谓的进化算法） ；再则，加以种群中数量巨大的个体（每个个体都是一个单独的枚举器） ，我们就不难理解为什么自然选择能够进化出复杂如眼睛的结构了。Update 2007-12-3：徐宥同学指出，在 Richard 原来写的那个程序中，是采用的“挨个枚举”办法。即先枚举出第一个字母（期望需要 26 次） ，然后枚举第二个，如此直到把所有字母枚举完。如此需要的时间为 1326=338；符合文中给出的值。如此说来，之所以我得出的结果跟 Richard 的不一样，是因为采用的枚举策略不一样，我将“一次枚举 ”定义为“枚举整个单词” ，而非“枚举其中某个字母” 。不过我感觉 Richard 的那个枚举策略显然不符合自然选择的工作方式，自然状况下，每一个基因位（“字母” ）都可能发生变异（独立分布，不过变异概率未必一样） ，而对变异基因的择优筛选则发生在“遗传”这一个环节（严格来说是发生在遗传过程中的“差异繁殖率”