进化中的概率论

1、数学，算法-Writtenby刘未鹏onSunday,December2,200718:55-4,551views-3Comments数学之美番外篇：进化论中的概率论Tags：数学，概率论，算法saveit4saved李笑来教师在blog上转了一篇宏文，“15AnswerstoCreationistNonsensef，；然后余晟同窗（顺便推荐余晟同窗译的精通正那么表达式（第3版）把它给译了出来。漂亮的文章加上漂亮的翻译，固然是要拜读的:-）进化论从其诞生以来受到的非难不可胜数。那个地址提到的这篇便搜集了广为神创论者提出和广为公共误解的一些观点。其中有一点尤其引发了我的爱好，如下：8.严格提及来

2、，咱们很难相信复杂如蛋白质的物质能偶然显现，更不用说人或是活细胞了。偶然性在进化中确实存在（例如，偶然性的突变能够产生新的特点），可是进化并非依托偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最要紧机制，却会明确保留“需要的”（能适应的）特性,排除“不需要的”（无法适应的）特性。只要选择的阻碍力存在，自然选择就能够把进化向一个方向推动，在出乎意料的短时刻内产生复杂的结构。举个例子，现有由13个字母组成的序列“T0BE0RN0TT0BE”，假设有几百万只猴子，每只猴子每秒钟挑一条短语，需要78,800年才能从2613种可能当选出如此的排列。只是，Glendale

3、College的RichardHardison在20世纪80年代写过一个程序，它能够在随机产生序列的同时，保证那些已经出此刻正确位置上的字母可不能转变（如此做倒有点汉姆雷特的味道。译注：那个句子看了大半天才明白，嘿嘿）。那个程序平均只需要336次迭代就能够生成上文提到的短语，时刻少于90秒。更神奇的是，把莎士比亚的整个剧本从头生成一遍也只需要四天半时刻。关于那个随机列举特定的13字母的单词的问题有点意思。若是是纯粹随机列举的话，由于长度为13的单词一共有26U3个不同的（假设所有组合都是有效单词的话），其中只有一个跟目标单词一样，也确实是说平均（数学期望）列举2613次才能列举出目标串来。咱们

4、不妨把人类的DXA链当做一个长长的单词。突变是产生随机列举的动力。那么依照上面的分析，要列举出咱们此刻用的DXA,需要的迭代次数将是跟DNA链上的“字母数”（碱基对）成指数关系的。列举一个13个字母的单词就需要2613次方了，上亿碱基对，需要多少次迭代？更不要说人类的一代更迭就平均要耗上十来二十年了。从那个角度来看，作为生命只有短短几十年的咱们，似乎的确很难明白得像眼睛这么复杂精妙的结构是如何从随机的突变中产生出来的。而这也恰正是神创论者最常经常使用来非难进化论的论点之一。那么，那个貌似有力的论点到底正确与否呢？其实，在达尔文同窗的物种起源中就已经进行了必然程度的驳斥。达尔文同窗列举了一系列的

5、比咱们人类眼睛简单的眼睛结构，从复杂慢慢到简单，其中最简单的“眼睛”只由一些聚集在一路的感光细胞组成；而且,达尔文同窗还雄辩了什么缘故眼睛的复杂性并非是不可归约（irreducible）的。但是，达尔文同窗毕竟不是专业的理工科诞生（在大学里面是学神学的），尽管其实践精神是每一个科学家的表率，尽管在物种起源中他运用了一系列的证据和推理，某种程度上论证了随机突变加上自然的选择之手，的确能够进化出如眼睛这么复杂的结构。但是他并无从数学上加以证明，什么缘故定向选择能够致使在短得多的时刻内产生复杂结构，和那个时刻与纯随机列举相较到底短到什么程度？咱们仍以那个13个字母的单词为例TOBEORNOTTOBE

6、o若是是纯随机列举的话，平均需要26工3次方才能列举出一个来。那么，自然中的进化进程也是如此的吗？并非如此。尽管每一个基因位都可能发生变异，但是自然选择之手会将那些“好”的部份留下来，差的部份剔掉（因为突变出来的好基因比差基因更有生存繁衍优势，于是渐渐就会在种群中通过遗传扩散开来）。反映在咱们列举单词的进程中确实是，一旦咱们列举出了某个或某些特定位上的字母，那么那个字母就确信下来，再也不变更，只需继续列举剩下来的字母。如此，直觉上需要列举的次数就会大大减少。而事实上也正是如此，引文中提到的Richard同窗写的一个程序便说明了这一点：本来需要78,800年，此刻只需90秒。不同何等庞大！此刻，

7、咱们关切的问题是，依照后一种列举方式，能从数学上精准计算出来，要列举出那个目标单词需要的迭代次数的数学期望吗？（即，平均列举多少次，才能列举出它呢？）Richard同窗写的那个程序显示需要平均336次；但是，问题是他写的是一个程序，而不是用数学来计算到底需要多少次。336次是数学期望吗？不是。它是一个实践值。事实上，我也写了一个如此的程序，但是结果显示却是大约82次左右。那么到底谁的正确呢？要查验那个结论，更重要的问题是，应该有一个数学方式能够计算出依照这种方式，可（数学）期望通过迭代多少次就迭代出目标串。为了从数学上解决那个问题。咱们需要用到一点大体的概率论知识：若是一个随机变量X的值为xi

8、的概率是Pi,那么X的数学期望Ex就等于ExiPi。举个例子，假设小明的考试成绩为90分的概率为30%,为80分的概率为70就那么小明的成绩的数学期望即是90X30%+80X70妒83（尽管83实际上是个不可能的成绩）。回到咱们要求解的问题：咱们想明白需要列举多少次才能列举出目标单词。要求解那个问题，咱们能够反过来试探：平均每列举一次能正确列举出目标单词上的几个字母（那个地址“正确”的意思固然是要知足”在相同位置上的字母也相同”，比如目标单词是TUBE的话，一旦列举出POTE,咱们就说正确列举出了最后一个字母E,而T由于位置不对应，因此就不能算是正确的了）。很显然，平均一次能正确列举出的字母数

9、量是一个随机变量，不妨令为X。该随机变量依托于在这次列举中，目标单词上的每一个位置上的字母是不是被正确列举出来了，于是咱们设目标单词第i位上的字母被列举的结果（即是不是列举中一一只有“中”或“不中”两种结果，因此是一个二元随机变量）为随机变量Xi：Xi只有“中”或“不中”两种可能，咱们将“中”的值量化为1,“不中”为0。由于每一名上列举中的概率都是独立同散布的，因此关于任意一个Xi来讲，为0（“不中”）的概率皆为25/26；为1（“中”）的概率皆为1/26。这很容易明白得，因为字母表中一共有26个字母，随机选择一个，跟目标字母相同的概率自然是1/26,不同的概率那么是25/26。有了Xi,咱们

10、进一步发觉，X实际上是Xi的函数：X=EXL那个式子如此明白得：若是在位置i处列举中了，那么Xi即是1,如此就给总共列举中的位数X奉献了1；不然Xi那么为0,即没有奉献。此刻，咱们回过头凝视咱们想要求得的东西：咱们想求得是列举一次能正确列举出目标单词上的字母数量的数学期望。也确实是X的数学期望EX。由于X=SXio于是EX=E（£Xi）:£EXi。而EXi-对每一个Xi是相同的（独立同散布嘛），都是0X25/26+1X1/26=1/26,因此EX二nXEXi（其中n是目标单词的长度本例中是13）=13X1/26二l/2o综上，咱们得出结论：随机列举一次可（数学）期望列举中目

11、标单词上的1/2个字母。1/2个字母？是不是开玩笑？哪有“半个字母”的说法？事实上，因为是数学期望，而数学期望的值极可能并非所有可能值中的任一个，而是它们的概率加权平均，因此半个字母的说法在数学期望上是说得通的；更关键的是，那个期望值给咱们提供了一个极为重要的信息，那确实是要想列举中其中的一名，咱们（数学期望上）需要列举2次才行（因为每次列举中1/2位）。一旦列举中了其中的一名，那么后而的随机列举进程便不需要考虑这一名，只需要考虑剩下的了。换句话说，目标单词中的字母便被剔掉了一个，只剩12个字母。而在12个字母的单词中，要想再列举中一名，需要多少次迭代呢？重用上面的推导进程，EX仍然仍是等于n

12、XEXi。EXi没变，而n变成了12。即迭代一次平均命中12/26个字母，那么要完全命中其中一名字母，便需要26/12（即次）。如此类推，每次减掉其中的一个字母需要特定次数的列举，一直到减至只剩最后一个字母，需要26次。把所有这些列举次数的期望值加起来,即是总共需要列举的次数了。即26/13+26/12+26/11+26/1二次。另一种思路咱们回忆一下上一个解法进程中的核心问题：要命中其中的一个字母，（数学期望上）需要列举多少次，咱们令那个次数为随机变量X。咱们回忆一下数学期望的本质概念：每一个可能的值的概率加权平均。于是，要求得X的数学期望EX,咱们只需明白X所有可能的取值和对应于各个取值的

13、概率。那么，要命中其中一个字母，究竟需要列举多少次呢？可能是一次就中了，也可能需要两次，也可能需要三次你会发觉，有可能需要任意次。只只是随着所需次数的增加，概率也愈来愈小。事实上，这是一个无穷级数求和问题：所幸，你马上就会看到，那个求和其实很简单。所谓一次就命中的意思是，只随机列举一次，就会命中目标单词中的一个且仅一个字母。那个随机事件由三个部份组成，第一是其余n-l个字母不中，然后是剩下的1个字母中了，再然后是那个命中的字母有n种可能的位置。因此，其概率是(25/26)”(n-l)X1/26Xn0同理，需要两次才能命中其中一个字母的概率是(25/26)'nX1/26XnX(25/26

14、)"(n-1)以此类推。而命中其中一个字母所需列举次数X的数学期望是：IX一次就中的概率+2X二次才中的概率+3X三次才中的概率+也确实是：1/26XnX(25/26)"(n-l)1+2X(25/26)，+3X(25/26)-2n+4X(25/26厂3n左侧方括号内的无穷级数求和的形式为l+2q+3q*2+4q*3+-,结果为l/(l-q)*2(利用类似等比级数求和的技术一一错位相减)，因此上式求和简化后的结果为：nX25*(n-l)X26*n/(26*n-25*n)-2即,当目标单词长为n时,平均需要必乂25«11-1)乂26%/(26%-25%)-2次列举才能

15、命中其中一个字母；而一旦命中一个字母以后，该字母就会被从单词当中剔掉，并继续列举第二个字母，现在n减少了1,因此上式的值也发生了转变。简言之，长度为N的单词,需要£nX25«n-l)X26'n/(26.n-25Z(2次(其中n从1转变到N)迭代便能够完全列举出来。此刻咱们回到原先的问题：一个长为13的单词，TOBEORNOTTOBE,究竟需要列举多少次才能够完全列举出来呢？依照以上的式子，得出的结果是。而采纳前面的不精准近似，计算的结果。跟我自己写的一个列举程序运行一万次平均以后的结果恰好相符，后者也是在82左右彷徨。只是，以上两种做法其实都成立在一个假设之上，即咱

16、们是一个一个地列举出目标单词中的字母的。不是两个，也不是三个。但是实际当中可能一次就列举出多个乃至全数的字母。因此，其实以上两种做法计算出的都是一个不精准的值，这也是什么缘故它们的结果相近但不一样的缘故(真正的结果只有一个)。但是，若是想给出精准表达式或计算方式就超级复杂了，或说至少我没有想到更简单的表达方式，若是你有不妨告知我:-)小结本文介绍了隐藏在自然选择中的概率论，并说明了什么缘故自然选择能够在相对（与纯随机列举相较）极短的时刻内塑造出复杂的有机体；简而言之，选择之手老是不断地将生物的基因向某个方向推动，一旦基因中变异出有利的片段,该片段就会被选择保留下来并慢慢在种群中芟延开来，反映到

17、文中讨论的列举单词的例子中确实是，一旦某个位上的字母被列举出来，便会被保留住，再也不受到后续变异的阻碍（除非是更好的变异）（通过一个数学例如，咱们看到，本来需要2613次迭代才能产生的目标序列，只需82次竟然就进化出来了，其间的差距是无法估量的；事实上，运算机算法上就有利用进化思想来实现算法的，也确实是所谓的进化算法）；再那么，加以种群中数量庞大的个体（每一个个体都是一个单独的列举器），咱们就不难明白得什么缘故自然选择能够进化出复杂如眼睛的结构了。Update2007-12-3：徐宥同窗指出，在Richard原先写的那个程序中，是采纳的''挨个列举”方法。即先列举出第一个字母（期望需要26次），然后列举第二个，如此直到把所有字母列举完。如此需要的时刻为13X26=338：符合文中给出的值。如此说来，之因此我得出的结果跟Richard的不一样，是因为采纳的列举策略不一样，我将“一次列举”概念为“列举整个单词”，而非“列举其中某个字母"。只是我感觉Richard的那个列举策略显然不符合自然选择的工作方式，自然状况下，每一个基因位（“字母”）都可能发生变异（独立散布，只是变异概率未必一样），而对变异基因的择优挑选那么发生在“遗传”这一个环节（严格来讲是