http://www.matrix67.com/blog/archives/366

考慮一個事件，它有兩種概率均等的結果。比如擲硬幣，出現正面和反面的機會是相等的。現在我們希望知道，如果我不斷拋擲硬幣，需要多長時間才能得到一個特定的序列。

序列一：反面、正面、反面
序列二：反面、正面、正面

????首先，我反復拋擲硬幣，直到最近的三次拋擲結果形成序列一，然后我記下這次我拋擲了多少次才得到了我要的序列。重復執行這個過程，我可以算出得到序列一平均需要的拋擲次數。同樣地，反復拋擲硬幣直到序列二產生，它所需要的次數也有一個平均值。你認為這兩個平均值哪一個大哪一個小？換句話說，出現序列一平均所需的拋擲次數少還是出現序列二平均需要的次數少？


????大多數人會認為，兩個序列會以同樣快的速度出現，因為在所有“正”和“反”的8種三元組合里，“反正反”和“反正正”各占1/8，其概率是均等的。而事實上，我們將會看到擲出序列二所需的次數更少一些。不妨考慮這樣一個問題：在由“正”和“反”構成的n位01序列中，有多少個序列以序列一結尾但之前不曾出現過序列一？有多少個序列以序列二結尾但之前不曾出現過序列二？當n比較小時，兩者答案是一樣的（例如n=3時符合要求的情況都是唯一的），但到后來n越大時，兩者的差距越明顯：后者的個數總比前者的個數要多一些。不妨看一看n=6的情況。對于序列一，只有以下5個序列是符合要求的：

• 反反反反正反
  
• 反正正反正反
  
• 正正正反正反
  
• 正反反反正反
  
• 正正反反正反

????但對于序列二來說，符合條件的序列就有7個：

• 反反反反正正
  
• 反正反反正正
  
• 反反正反正正
  
• 正反反反正正
  
• 正正反反正正
  
• 正正正反正正
  
• 正反正反正正

????你可以通過計算機編程枚舉，計算一下n為其它值的情況。計算結果和剛才也一樣：在n位01序列中，以序列二結尾但之前不含序列二的情況不會少于以序列一結尾但之前不含序列一的情況。這說明，拋擲第n次硬幣后恰好出現了序列二，其概率不會小于恰好出現序列一的概率。顯然，當n漸漸增大時，這個概率應該呈下降趨勢；同時，隨著n的增長，兩個序列各自出現的概率由相等開始慢慢拉開差距，第n次拋擲產生序列二的概率下降得要緩慢一些，或者說更多的情況集中發生在n更小的時候。因此總的來說，出現序列二所需要的拋擲硬幣次數的期望值更小。
????雖然我們通過一系列的觀察驗證了這個結論，并且我們也相信這個結論是正確的（雖然沒有嚴格的證明），但我們仍然不是很接受這個結論。這種情況是有悖于我們的直覺的，它與我們的生活經驗不相符合。此刻，我們迫切需要一個解釋，來說明這種出人意料的反常現象產生的原因。




????如果不親自做幾次試驗的話，你很難體會到這種微妙的差距。考慮整個游戲的實際過程，“反正正”序列顯然會出現得更早一些。假如某一次我們得到了序列“反正”。如果我們需要的是“反正反”序列，那么下一次拋擲結果為反面將結束本輪的拋擲，而下一次是正面則前功盡棄，你必須再次從零開始。如果我們需要的是“反正正”序列，那么下一次拋擲結果為正面將結束本輪的拋擲，而下一次是反面的話我至少不會慘到一切歸零，這相當于我已經有了一個反面作為新的開頭，只需再來兩個正面即可。這樣看的話，提前擲出“反正正”的可能性更大一些。
????反復體會上面的想法，了解KMP算法的網友會恍然大悟：這就是KMP算法的基本思路！考慮這樣一個問題：我們在當前字串中尋找子串“反正正”第一次出現的位置。假如當前已經能匹配模式串的前兩個字“反正”，主串中的下一個字是“正”則匹配成功，主串的下一個字是“反”則將使模式串的當前匹配位置退到第一個字。考慮一個更復雜的例子：我們希望在主串中尋找子串abbaba，現在已經在主串中找到了abbab。如果主串下一個字符是a，則成功匹配；如果主串下一個字符是b，則模式串最多能匹配到的位置退到了第三個字符，我只需要從abb開始繼續匹配，而不必一切從頭再來。
????我們可以用KMP算法完美地解決上面的問題。首先預處理出一個數組c，c[i,0]表示模式串匹配到了第i個字符，主串下一個字符為0（反）時，模式串的匹配位置將退到哪里；同樣地，c[i,1]表示模式串匹配到了第i個字符，主串下一個字符為1（正）時，新的模式串匹配位置在什么地方。設f[i,j]表示第i次拋擲硬幣后恰好匹配到模式串第j位有多少種情況，則f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k滿足c[k,0]=j，l滿足c[l,1]=j。將f[i,j]除以2的i次方，我們就得到了相應的概率值。或者更直接地，設P[i,j]表示第i次拋擲硬幣后，最遠能匹配到的模式串位置是第j位的概率，則P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我們還應該添加一種特殊的概率值P[i,*]，它表示在主串第i個字符以前已經成功匹配過的概率，這樣的話下表中每一列的和才能為1。

????來看一看程序的輸出結果：
Pattern 1: s[]="aba"
主串位置?????? 1????????2?????? 3?????? 4?????? 5?????? 6?????? 7?????? 8?????? 9??????10
匹配到s[0]??0.5000??0.2500??0.2500??0.2500??0.2188??0.1875??0.1641??0.1445??0.1270??0.1113
匹配到s[1]??0.5000??0.5000??0.3750??0.3125??0.2813??0.2500??0.2188??0.1914??0.1680??0.1475
匹配到s[2]??0.0000??0.2500??0.2500??0.1875??0.1563??0.1406??0.1250??0.1094??0.0957??0.0840
匹配到s[3]??0.0000??0.0000??0.1250??0.1250??0.0938??0.0781??0.0703??0.0625??0.0547??0.0479
已找到匹配??0.0000??0.0000??0.0000??0.1250??0.2500??0.3438??0.4219??0.4922??0.5547??0.6094

Pattern 2: s[]="abb"
主串位置?????? 1????????2?????? 3?????? 4?????? 5?????? 6?????? 7?????? 8?????? 9??????10
匹配到s[0]??0.5000??0.2500??0.1250??0.0625??0.0313??0.0156??0.0078??0.0039??0.0020??0.0010
匹配到s[1]??0.5000??0.5000??0.5000??0.4375??0.3750??0.3125??0.2578??0.2109??0.1719??0.1396
匹配到s[2]??0.0000??0.2500??0.2500??0.2500??0.2188??0.1875??0.1563??0.1289??0.1055??0.0859
匹配到s[3]??0.0000??0.0000??0.1250??0.1250??0.1250??0.1094??0.0938??0.0781??0.0645??0.0527
已找到匹配??0.0000??0.0000??0.0000??0.1250??0.2500??0.3750??0.4844??0.5781??0.6563??0.7207

????這下我們可以清楚地看到，序列二提前出現的概率要大得多。注意到，根據我們的概率定義，表格中每一列的數字之和都是1。同時，倒數第二行的數字之和（有無窮多項）也應該為1，因為最后一行的概率就是倒數第二行的概率值累加的結果，而根據最后一行概率的定義，主串無窮長時已找到匹配的概率應該為1。因此，我們也可以把倒數第二行看作是模式串在主串第i個位置首次匹配成功的概率。我們可以根據這一結果近似地計算出拋擲次數的期望值。

Matrix67原創
轉貼請注明出處

總結

以上是生活随笔為你收集整理的KMP算法与一个经典概率问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。