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

數學之美番外篇：進化論中的概率論              劉未鵬
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的那個枚舉策略顯然不符合自然選擇的工作方式，自然狀況下，每一個基因位（「字母」）都可能發生變異（獨立分佈，不過變異概率未必一樣），而對變異基因的擇優篩選則發生在「遺傳」這一個環節（嚴格來說是發生在遺傳過程中的「差異繁殖率」上）。

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

再多申請幾個黃牌就停賽三天了？
別的地兒沒問題的，在這裡經常貼不上貼子，還不明原因。
傻蛋吞椰酥 發表於 2009-3-20 16:16

用Firefox試試？

62# 金寶


你還是少找老大麻煩為好，老大不說了嗎。
傻蛋吞椰酥 發表於 2009-3-20 16:18

是你們找俺哥哥的麻煩。如果你們不罵銀，不損銀，俺們鐵定不會罵。

禁言沒啥，俺已經反映過了：俺們哥們兒收到的11個警告大部分都是因為那些後來又被班長解禁了的帖子而得的。並非全部因為俺發言不當，群眾的眼睛是亮的，自然看得清楚。

俺很高興，傻蛋哥們兒也不罵銀了，繼續努力。

62# 金寶


你還是少找老大麻煩為好，老大不說了嗎。

再多申請幾個黃牌就停賽三天了？

另外
別的地兒沒問題的，在這裡經常貼不上貼子，還不明原因。

60# 金寶


你回去看看黑幕的帖子再來瞎掰。

關於「無恥」「莽撞」「出醜」算不算罵人，我看到批神創論書籍的文獻里都有這類話語。不多評論。

請小貓多多現眼！
傻蛋吞椰酥 發表於 2009-3-20 00:11

傻蛋你說了不算，俺要問斑竹：菜班長，傻蛋的意思是「無恥」「莽撞」「出醜」「現眼」應該不算罵人，也就是說這些不是髒話，你認為如何？俺是不是也可以使用這些辭彙？而且如果這不算是髒話，那麼弱智、人渣、敗類、混混、這廝、禿XX、X子.....等同類語言是不是也不算髒話了呢？
班長給個標準，俺們也好在論壇里凈化一下語言。
俺也歡迎各位哥們兒姐兒妹兒講講你們的看法。

俺在改革開放初期見過一幫子倒匯的在興高采烈的計算他們們的盈利，算來算去能賺兩萬元，哥兒幾個正高興呢，一人提醒他們：這賺的利潤是日元，不是人民幣..!@#$%&^?....
俺的意思是：不管你用什麼方法來計算，可如果大前提錯了，算得再精也只能是瞎掰了。

你們的問題是只會做題，卻忘了這計算的是啥東西了。不能總是「哭了半天還不知誰死了」吧。

你們數學得分再高，能算得出自己生命的長短嗎？更何況還是地上萬物的生命，就種類來說俺們都不知道俺們數過來了沒有。

樓上小貓接著現眼！
傻蛋吞椰酥 發表於 2009-3-19 23:22

你有理說理，用不著說廢話。

你也許可以用隨機概率解釋生物起源，但你怎樣又概率來解釋這些最初的生物體怎麼會有遺傳因子的。
罵人沒用，不能證明你比俺就強到哪兒去了；俺罵起人來也並不比你差。
不過剛剛答應過靈MM和菜版，不輕易說髒話了。希望你也配合配合。

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

大多數突變是不良的，致命的。然而其中也有良性的有益的突變。自然選擇就是淘汰不良的突變，保留良性突變。
異鄉 發表於 2009-3-11 03:37

俺不是搞數學的，也不是學生物的。
但是俺提醒哥們兒JJ和MM們一下：儘管你們可能認為世間第一個生命單位（如：蛋白質、細胞等）是碰巧隨機產生的，可即使根據進化論，也可以看出每一個帶有生命的細胞實際上都是有生物智能的。這些生物智能自動記憶、維繫以及傳遞生命信息，細胞在我們不知不覺之中從事著我們數不過來（成百萬計）的各種工作，如果有一種工作不能持續完成，這些細胞組成的肌體就有可能喪失生命。
那麼我們可不可以說：第一個生命體，且不管它是怎麼來的（創造抑或進化），它都必須具備了這樣的「生物智能」，以便這一組類得以生存、進化或延續下去。
如果這一邏輯成立，那麼生命的開始是不是有些奇怪了呢，請看：在生命生成之前的一霎那，還沒有任何「生物智能」，因為還沒有生命。可是，一旦「偶然」有了生命的單位，它卻突然會從事自己複製、維繫和遺傳....這一系列錯綜複雜的生命智能功能了。而這可不是僅僅用機械性的概率能夠講得清楚的吧。
創造論和進化論的距離並不大：神創論相信在宇宙生內命產生之前已經有了生命和智慧----即：上帝的存在；進化論的邏輯應當支持在生命體產生的一霎那，智慧就產生了。這中間的距離應當僅以「毫秒」來計算。
這中間的關係，數學概率又該怎麼著手計算呢？

有條件的概率呢？
信仰天地 發表於 2009-3-18 19:46

概率裡面的條件概率是指當一定的事件A發生之後，另一個事件B發生的概率。這裡的條件和我們通常說的條件有點不一樣，是指事件A的發生。

用概率來證明進化，實在是件太艱難的任務。成功的概率很低。

我上面介紹的文章也只是對智設論者用概率來挑戰進化論提出批評，指出哪裡有問題；而沒有用概率統計來說明進化的合理性。如果確有這方面的文章，我會很感興趣。

54# homepeace
哦，還以為你們在討論45和46樓。如果假設每人只買一張，那每人中獎的概率就等於中獎數字出現的概率。
自由之靈 發表於 2009-3-18 21:58

由我41樓引起的

我第一句回答的是37樓，第二句是閑聊了一下40樓。表達不清楚， 了homepeace

54# homepeace
哦，還以為你們在討論45和46樓。如果假設每人只買一張，那每人中獎的概率就等於中獎數字出現的概率。

1/62,891,499 是7個數都對的概率，並不是每個人贏彩票的概率。比如有一個人很富，他一下子拿出$62,891,499 把所有的數組合都買了，那麼這個人贏的概率就是100%。這是個極端的例子。如果你只花一元，那你贏彩票的 ...
自由之靈 發表於 2009-3-18 18:30

大家討論的是37樓的問題，自然假設你只買一張彩票。

「不是6千多萬個組合都有人買到（選到），也不是每個組合只賣了一次，很多人也不是單單買了一組」。你再想想，所有這些好像只跟你中獎的獎金有關，而和你中獎的概率無關。
homepeace 發表於 2009-3-18 16:57

1/62,891,499 是7個數都對的概率，並不見得是每個人贏彩票的概率。比如有一個人很富，他一下子拿出$62,891,499 把所有的數組合都買了，那麼這個人贏的概率就是100%。這是個極端的例子。如果你只花一元，那你贏彩票的概率就是1/62,891,499；如果你花兩元買兩個不同的數，贏的概率就是2/62,891,499 ... n元錢買n個不同的彩票就有 n/62,891,499 的贏獎概率。即每個人的贏獎概率和花多少錢有關係。另外與人合夥買不同的數字也可以提高贏的概率。

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

有條件的概率呢？

如果你講的是實際獎金的分配概率，那就全對了。
homepeace 發表於 2009-3-18 19:07

好像喧賓奪主了

我指的就是買彩票的人（不是一個組合）的實際中獎概率（獎金的分配概率,之前的表達是太模糊了 ）；6千多萬分之一是每組號碼的中獎幾率，就是每買一組數字有可能中獎的幾率。有很多人在研究「彩票公式」呢(不 ...
bearbee82 發表於 2009-3-18 15:02

如果你講的是實際獎金的分配概率，那就全對了。

所有這些好像只跟你中獎的獎金有關

我指的就是買彩票的人（不是一個組合）的實際中獎概率（獎金的分配概率,之前的表達是太模糊了 ）；6千多萬分之一是每組號碼的中獎幾率，就是每買一組數字有可能中獎的幾率。

有很多人在研究「彩票公式」呢(不單單是彩民）

不是6千多萬個組合都有人買到（選到），也不是每個組合只賣了一次，很多人也不是單單買了一組，而球掉下來的數字順序不是固定的等等因素都有影響（影響到6千多萬這個基數）。一般來講中獎幾率會比6千多萬分之一高
bearbee82 發表於 2009-3-18 13:02

「不是6千多萬個組合都有人買到（選到），也不是每個組合只賣了一次，很多人也不是單單買了一組」。你再想想，所有這些好像只跟你中獎的獎金有關，而和你中獎的概率無關。