數學之美番外篇：進化論中的概率論

數學之美番外篇：進化論中的概率論              劉未鵬
Tags: 數學, 概率論, 演演算法
save it1 saved

李笑來老師在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的值為xi的幾率是Pi，那麼X的數學期望Ex就等於∑xiPi。舉個例子，假設小明的考試成績為90分的概率為30%，為80分的概率為70%，那麼小明的成績的數學期望便是90×30%+80×70%=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是相同的（獨立同分佈嘛），都是0×25/26 + 1×1/26 = 1/26。因此EX = n×EXi（其中n是目標單詞的長度——本例中是13）= 13×1/26 = 1/2。

綜上，我們得出結論：隨機枚舉一次可（數學）期望枚舉中目標單詞上的1/2個字母。

1/2個字母？是不是開玩笑？哪有「半個字母」的說法？實際上，因為是數學期望，而數學期望的值很可能並非所有可能值中的任一個，而是它們的概率加權平均，所以半個字母的說法在數學期望上是說得通的；更關鍵的是，這個期望值給我們提供了一個極其重要的信息，那就是要想枚舉中其中的一位，我們（數學期望上）需要枚舉2次才行（因為每次枚舉中1/2位）。

一旦枚舉中了其中的一位，那麼後面的隨機枚舉過程便不需要考慮這一位，只需要考慮剩下的了。換句話說，目標單詞中的字母便被剔掉了一個，只剩12個字母。而在12個字母的單詞中，要想再枚舉中一位，需要多少次迭代呢？重用上面的推導過程，EX仍然還是等於n×EXi。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/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 2007-12-3：徐宥同學指出，在Richard原來寫的那個程序中，是採用的「挨個枚舉」辦法。即先枚舉出第一個字母（期望需要26次），然後枚舉第二個，如此直到把所有字母枚舉完。如此需要的時間為13×26=338；符合文中給出的值。如此說來，之所以我得出的結果跟Richard的不一樣，是因為採用的枚舉策略不一樣，我將「一次枚舉」定義為「枚舉整個單詞」，而非「枚舉其中某個字母」。不過我感覺Richard的那個枚舉策略顯然不符合自然選擇的工作方式，自然狀況下，每一個基因位（「字母」）都可能發生變異（獨立分佈，不過變異概率未必一樣），而對變異基因的擇優篩選則發生在「遺傳」這一個環節（嚴格來說是發生在遺傳過程中的「差異繁殖率」上）。

不過，總而言之，儘管計算機模擬的選擇演演算法不同，總的思想是一樣的，即一旦加入了「選擇之手」，就能夠極大地加快進化的速度。

哈哈，數學家犯起傻來也挺可愛的。

2# 自由之靈

你看的懂？我是不懂。

小朋友看不懂，就去補習補習數學
報紙上補習班廣告很多！從小學到高中都有

原來是高中的數學，容我仔細看看。

那自由之靈提數學家幹什麼，數學家都教中學去了，文革好象是很久以前的事了。

用概率論來解釋進化，只能得出相反的結論－－即進化論是不成立的。因為概率的研究對象主要是隨機事件，或偶然事件．而生命在地球上的出現（從無機物到有機物），以及從低級生命到高級生命的進化，決不是偶然或隨機的．它一定是在某種外界條件下的必然產物．只要看看蛋白質分子＂偶然＂產生的概率就夠了：10的300次方分之1！

這篇文章已經承認＂進化並不依賴偶然性來產生新的器官、蛋白質或其他實體。截然相反的是，自然選擇，作為進化中已知的最主要機制，卻會明確保留「需要的」（能適應的）特性，消除「不需要的」（無法適應的）特性。只要選擇的影響力存在，自然選擇就能把進化向一個方向推進，在出乎意料的短時間內產生複雜的結構。＂．再來論述偶然隨機的大小，有點本末顛倒．

6# 自由之靈

高中數學夠用嗎？

3# sousuo
我也看不懂！

7# sousuo
國內高中講概率只講一點點，主要是幾個經典模式和簡單統計。這篇文章里引用的公式和方法是大學概率課上的東西。

異鄉兄，懂了也不要看不起不懂的人呦。

10# sousuo

靜下心來慢慢看，應該是能看懂的。
我現在心還沒靜下來。

原文稍有點深度

舉個例子來說，假定一種生物有 13 個染色體，每個染色體可以有 26 中變異。這種生物較原始的祖先的染色體是"AAAAAAAAAA"(以下稱A13)，而經過一定時期進化成的後代的染色體是"TOBEORNOTTOBE"(以下稱TOBE)，那麼從 A13 演化到TOBE，需要多少次變異？概率有多大？

乍一看，變異的次數最多需要 26^13 等於 2.48 x 10 的 18 次方，才會從 A13 演化到TOBE，發生概率就是 2.48x10e18 分之一，概率確實小得出奇。如果再假定說一個染色體的變異一年發生一次，那麼從A13到TOBE，至少要2481億億年，是目前已知宇宙年齡的20億倍。

但是，進化並不是一蹴而就，因此計算進化的概率，應該一步一步來。


首先，為了簡化計算，我們在一定時期內，只考察一個染色體發生的變異。這一假定是偏於保守的。

其次，同樣假定 TOBE 就是最優的變異結果，自然選擇總是優勝劣汰。


第一步來考察最先發生變異的染色體。在一定時期，最先發生變異的染色體（可以是A13中任何一個染色體，但是假定就是第一個）可以有 26 種變異。其中之一是 A-> T。
現在想想，第一個染色體發生變異之後會怎麼樣？自然選擇就起作用了。其他變異會被淘汰，而 T 就保留下來了。因此現在染色體就變成了 TAAAAAAAAAAAA。

第二步來考察接下來發生變異的染色體。假定就是第二個染色體變異了，同樣可能有26種變異，而其中之一是 A->O。
現在想想，現在再次經過自然選擇，其他變異會被淘汰，而 TO 就保留下來了。因此現在染色體就變成了 TOAAAAAAAAAAA。

如此重複十三次，可以得到，從 A13 到 TOBE，需要 26 + 26 + 26 + 26 ... = 26 X 13 = 338 次變異。如果一年發生一次變異，那麼 300 多年一個新物種就出現了！

這是枚舉所有情況而得出的結果。

當然了，這是簡化的模型。實際情況要複雜得多。

有人會問，為什麼需要的變異次數會從 26^13 變成 26x13 ?

因為自然選擇淘汰了一些變異，排除了這些變異所有後續變異的可能性。所以優化的變異的概率就大大提高了。

從這裡可以看到自然選擇的作用。

6# 自由之靈 高中數學夠用嗎？
sousuo 發表於 2009-3-10 08:41

可以用高中數學做個例子，假如英語一共只有3個字母，A,B,C. 看隨機抽三次各排列的概率。如果不知答案為ABC，得ABC排列的概率是1/（3x3x3）=1/27.
如果知答案為ABC，得ABC排列的概率是1/3！=1/6. 概率大了許多。這例子不很確切，但原理和樓主的貼是一樣的。
如有不對，請大師們指正。

數學我不懂，染色體倒略之一二。染色體上包含大幾百基因，每個基因大幾百鹼基，而突變多發生在鹼基水平，染色體水平的突變致死的可能性更大。

所以，突變不是１３對２６。至於概律該怎麼算，我就又不懂了。

例子而已，又不是哪個生物真的只有13個染色體，每個染色體又只能有26種變異。

大多數突變是不良的，致命的。然而其中也有良性的有益的突變。自然選擇就是淘汰不良的突變，保留良性突變。

16# 異鄉

只是差的遠了點，一條染色體上可突變的點有１３０００也不一定，那概率算起來會有很大區別吧？

概率是普遍的。其實所有的事件都是可以用概率來說明。該文不過是用一個例子來說明普遍存在的現象：所謂的確定性，不過概率經過規則的篩選后的結果。

比如說，化學反應, H2 和 O2，CO2在自然狀態下，3種分子都在相互碰撞，為何結果是H2O的比例越來越高，CH2O（我猜想的物質）很少。這裡的因素就是化學反應的規則的存在：H和O的結合比C，H，O的結合物穩定。所有的化學反應都是分子間隨機碰撞的結果，但化學和物理的規則和決定了什麼樣的分子產生，比例是多少，壽命有多長。

16# 異鄉

只是差的遠了點，一條染色體上可突變的點有１３０００也不一定，那概率算起來會有很大區別吧？
sousuo 發表於 2009-3-11 04:05

從N^13000變化成N X 13000，前者是「不可能」，而後者就變成了「很可能」了。

哈哈，數學家犯起傻來也挺可愛的。
自由之靈 發表於 2009-3-10 22:18

不知道你讀了他的C++系列和Google的吳軍的數學系列沒有？
我反正現在是茶不思，飯不想，蒙古MM也不理。