終于寫到重頭戲了，如果說前面的微分積分還屬于基礎(chǔ)理論，而與我們?nèi)粘５乃惴ㄔO(shè)計距離有點遠的話，那么后面的概率、矩陣、空間立體幾何，可就是和應(yīng)用息息相關(guān)了。

  為什么要有概率
  概率是個數(shù)學(xué)概念，但它在計算機軟件設(shè)計上有很多應(yīng)用，數(shù)學(xué)概念是留給數(shù)學(xué)系的人討論的事情，我們這里側(cè)重的它的應(yīng)用。那么為什么會在應(yīng)用中用到概率，概率真正體現(xiàn)的是什么呢？我個人理解，概率的本質(zhì)是體現(xiàn)了一種模糊的思想，既可以是A、又可以是B，甚至本身概率的值就是模糊的，因為沒有人知道真正的概率是什么，我會在后面解釋這句讓人暈的話。
  理解了概率要表達模糊的思想后，我們會發(fā)現(xiàn)世界上絕對的事太少，甚至就是0、1寫入都存在微小的寫錯概率，說不好的事情太多，也就決定了概率絕對是大有用處。

  概率的內(nèi)容
  目前市面本科的概率書的標題一般為“概率和數(shù)理統(tǒng)計”，表明了概率實際分為兩部分內(nèi)容：概率和統(tǒng)計。統(tǒng)計是在概率分布的基礎(chǔ)上，而單純的概率統(tǒng)計不是這里要講的重點，所以下面主要把概率理論部分分成了兩塊，“概率的計算”和“概率的分布”。
 
  概率的計算
  概率的求解絕對是數(shù)學(xué)的東西，這里不討論，什么全概率、獨立時間、貝葉斯公式，書上都有。這里舉幾個實際的例子，首先概率在算法設(shè)計分析時會碰到，就像我們在積分那節(jié)舉的例子，計算出的公式幾乎都基于vector里面的對象分布完全隨機的，也就是每個對象在各個位置的概率都一樣導(dǎo)出的，如果概率不一樣呢？結(jié)果當然會不一樣，有關(guān)計算不詳加討論。談到了分布的概率，TAOCP《計算機程序設(shè)計藝術(shù)》在動態(tài)分配內(nèi)存那章的課后題專門有一題討論了，最佳匹配分配內(nèi)存的一個最大弱點，最后的結(jié)果就是分配完空間的出現(xiàn)概率不平均。再有，BM字符串匹配比KMP算法的一個重要改進，就是假設(shè)字符串比較時，從后位首先出現(xiàn)不一樣的概率比從頭起出現(xiàn)字符不一樣的概率大。甚至在搜索引擎里，pagerank的那個0.85都是模擬了用戶從瀏覽器直接跳轉(zhuǎn)的概率（盡管客觀上起到了，避免矩陣奇異的效果）。
  概率計算很多都是基于經(jīng)典的模型（后面會說明模型的思想在概率起到重要作用），高中數(shù)學(xué)排列組合上讓我記憶猶新的一個模型就是問什么人排成一隊，怎么分法時，會想象每人之間一個空格，然后對空格取組合運算。值得一提的計算模型是生日模型，由此引申的計算可以應(yīng)用到判斷hash的沖突的概率，比如做人機博弈時，每次alpha beta剪枝搜索（也可以不同次）需要對棋盤做hash，然后在每次再對棋局評估時，利用hash值看該棋局是否已經(jīng)被評估過。應(yīng)用概率，我們可以設(shè)計合理的hash code長度，然后利用生日模型，估算出該hash code長度下，棋盤的沖突概率，然后把概率限制在可接受的范圍內(nèi)。 因為這個計算模型太重要了，所以寫一下，將M個球，放入到N個(N>M)桶時，每個桶的沖突概率是：1-N*(N-1)*(N-2)....(N-M+1)/power(N,M)，可以看出，當N個足夠大時，沖突概率幾乎為0。
  最后說一個曾經(jīng)讓我犯暈的小題，看你完全理解概率計算沒？
 
  題一：打雷后下雨的概率是80%，而打閃電后下雨的概率是70%，那么即打雷又打閃電后下雨的概率是多少？不會計算沒關(guān)系，直覺告訴我們肯定比80%高，恩，沒錯，把這題改一改變成另外一題
 
  題二：打雷后下雨的概率是80%，但是沒打閃電后下雨的概率是20%，那么打雷了但沒打閃電后下雨的概率是多少？不會計算沒關(guān)系，直覺告訴我們肯定位于80%和20%之間。

  哦？？？暈了，怎么兩個題產(chǎn)生的效果不一樣，一個是比最高的高，一個是兩個概率之間，我們的直覺錯了嗎，還是忽略什么重要的東西，請獨立思考1分鐘再看答案。
 
  相信直覺沒錯的，看第一題怎么解：
  解=1-又打雷又閃電但沒下雨的概率= 1 - 0.2 *0.3 = 94%
  第二題：
  解=0.8 *0.2 /( 0.8 *0.2 +(1-0.8)*(1-0.2) )= 0.16/0.32= 50%
  與直覺一樣，相當于大家互相拖了一下后腿，而大家的力量一樣，所以扯平了，哈哈，我故意沒寫第二題解的說明，你是否明白了呢？
 
  其實真正忽悠人的地方在于對獨立事件的理解，題一中的打雷下雨是獨立事件，類似于我踢一腳門塌的概率是80%，你踢一腳的概率是70%，我們同踢時門塌的概率是94%，但是如果我不踢，對你踢有影響嗎？沒影響，所以結(jié)果相當于一個合力。
  題二里的事件，并不是獨立事件，相當于考慮利益去做某事的概率是80%，考慮危險去做該事的概率是20%，兩個是互相影響的，隱含了這個條件，你考慮了利益決定不去做這事而又考慮了危險，這時去做該事的概率是0!!!同理，你考慮了危險決定不去做這事，但是你又考慮了利益，但結(jié)果仍然去做該事的概率是0!!!實際上是一個類似單票否決的機制，最后的概率只由兩部分構(gòu)成，考慮了利益考慮了危險做的概率和考慮了利益又考慮了風(fēng)險但不做的概率，那么做的概率就是做的概率比這兩個加起來的概率的值。
  題二的關(guān)鍵我們的潛意識在作崇，類似于認為廠長就是男的那種，所以這題也有腦筋急轉(zhuǎn)彎的類型。
  BTW：這道題的思考來源網(wǎng)上的一篇著名的文章“貝葉斯過濾垃圾郵件”，該文章中有一個類似的公式，但啥都沒說明直接就說叫聯(lián)合概率公式，后來我查書發(fā)現(xiàn)沒這個公式，所以才反復(fù)思考這個公式是怎么出來的。

  概率的分布
  前面提過，概率的分布是另一個大部分，而且是極其龐大的部分，總體上可以分為連續(xù)變量分布和離散變量分布，對計算機應(yīng)用來說，離散研究得更多一些，不過由于理論深度太高，我的水平不允許我在這里推導(dǎo)公式，所以建議大家去看書，這里只提一提正態(tài)分布，隨機變量合符合正態(tài)分布，這是一個極為有用的結(jié)論。用瀏覽器瀏覽頁面，可以有前進和后退，那么在N次瀏覽后，應(yīng)該是按照初始的URL呈正態(tài)分布，那么多維的正態(tài)分布怎樣呢，比如前進到頁面里的URL每個的概率是1/N,那么瀏覽和后退N次后，呈現(xiàn)的分布是什么呢？是不是預(yù)示某些閱讀習(xí)慣呢？我也不知道，留做思考吧：）

  （非常）+重要的定理：大數(shù)定理
  這里采用正則語法，表明再怎么重要也不過分。前面提到過一句話，就是概率本身的值表達的意思是個模糊的含義，甚至該值都是模糊的?，F(xiàn)在作出解釋，事實上一個事件的概率，我們根本不知道，Miller投中一個三分的概率是什么？沒人知道，也沒法測量，所以說所謂的概率都是近似值，因為真值不存在，這好象是講哲學(xué)了。不管你接受不接受這樣的觀點，大數(shù)定理是同樣為我們解決這個問題來準備的。
  大數(shù)定理說明：當事件發(fā)生足夠多次時，它的發(fā)生頻率就是它單次發(fā)生的概率。
  不用去管它怎么證明，我們還是要驚呼，這個看似常識的定理為宇宙把概率模型和統(tǒng)計模型兩大世界聯(lián)系了起來!!!讓我們知道了對概率的分析可以用統(tǒng)計的方法去解決，這個定理，就是搭起統(tǒng)計和概率的橋梁。Miller的三分命中率終于可以算了，讓他投1000個，看他進了幾個:)


  還有一個公式，也可以起到橋梁作用，那就是貝葉斯公式，P(A/B)=P(B/A)*p(A)/P(B)，這個公式太深奧，以至都創(chuàng)立了兩大學(xué)術(shù)派，我只有用的份，不敢多作半點解釋，那么這唯一半點解釋就是建立正推反推的模型，我們會在后面的三維概率模型中用到它。

概率的三維空間模型：
  這是我寫的概率應(yīng)用的重點，重在應(yīng)用舉例，首先說明一點，為什么要用三維空間模型呢，是因為我考慮任何問題都愛往矩陣上靠，一想到矩陣自然而然就聯(lián)想到了空間模型，如果你不接受這個觀點，沒關(guān)系，看看有沒有空間的味道。

概率一維空間模型的應(yīng)用：
  從概率點說起?？臻g模型里最低級的就是一個點, 那么在概率世界里，點就是一個概率值，不管概率怎么得出的，反正有個23%的概率，那么它就是一個點了，它可以代表任何東西，數(shù)或者一個事件的概率，甚至一系列的事件的概率，總之，只要你想把它看成一個封裝的點，它就是點。
  有了點，自然需要線，也就是一維概率模型的內(nèi)容：線。一個點到另一個點有一個概率，那么把這樣的一些點連起來，就形成了一條線。A推B，B推C，C推D....，那A能不能推C呢？當然可以了，但是推了，就不是一維模型了，我們會在后面的二維模型里講。這樣依此串成串后，會發(fā)現(xiàn)和一個大名鼎鼎的名字能聯(lián)系一起，那就是馬爾可夫鏈，沒錯，這就是馬爾可夫鏈了。
  馬爾可夫鏈有什么用？哇塞，用處太多了，按照書上的理論，可以做個簡單的聊天機器人，完全基于統(tǒng)計模型。利用大數(shù)定理，建立統(tǒng)計頻率等于概率的思想，我們統(tǒng)計上萬篇文章，按語素分詞（如何按語素分詞？不是我要講的重點），例如“今吃了嗎？”分成“今”和“吃了嗎”兩部分，然后我們發(fā)現(xiàn)在這上萬篇文章里，”今吃了嗎“后面跟的最多就是“吃了”和“沒吃”，那么我們?nèi)∽疃嗟陌l(fā)生頻率的回答隨機做出回答，比如回答“沒吃”。接下來，語素變成了“吃了嗎”和“沒吃”，然后再在上萬篇里發(fā)現(xiàn)“吃了嗎-沒吃”后面跟的“沒吃回家吃去吧”最多，那么我們就把這句話選成回答。呼呼，好簡單，是地，這就是模型的威力，有了模型，萬事不難。

  上面的例子是經(jīng)典書籍的例子，我再舉一個我真實解決的例子。
  研二的時候，我的上鋪去給一家手機游戲公司兼職，我對做手機游戲也很有興趣，不免時常和他探討一下。他做的街頭對打游戲，雙緩沖呀切圖啊這些自然不在話下，不過在測試階段遇到一個問題，游戲里面的NPC太傻。NPC和PC有很多動作，比如跑，跳，橫拳，下蹲，防，下防等等，他設(shè)計是基礎(chǔ)是隨機出招，然后會根據(jù)NPC與PC的距離調(diào)整一個好斗值，當然這個好斗值也會跟血有關(guān)，當NPC的血快沒時，它會過多采用進攻動作。而在時間快結(jié)束，如果NPC發(fā)現(xiàn)自己的血多于PC時會降低好斗值，反之增加，而好斗值直接關(guān)系它發(fā)招的進攻招的比例。但這么設(shè)計有個很重要的弱點，當PC用些固定招術(shù)取勝時，NPC就會變得像傻子一樣，比如PC跳起落下再掃堂腿，NPC就掛，結(jié)果PC反復(fù)使這招，結(jié)果NPC反復(fù)掛。如此的現(xiàn)象，讓我不得不想起曾經(jīng)的FC游戲，魂斗羅啊，赤色要素啊，我每次遇到大BOSS的時候，BOSS發(fā)子彈時，我都會躲到一個固定角落貓起來，每次都打不到我，此時多自豪自己為人類啊。
  為了影響玩家感受的自豪感，游戲NPC必須克服這個缺點，那怎么辦呢？概率一維模型coming!!!
  我們?yōu)镻C動作建立4元組馬爾可夫鏈，比如對動作A,B,C,D,E建立兩個四元組(A,B,C,D)和(B,C,D,E)，以此類推。在游戲中維護該一堆四元組，隨著游戲的進行，就會出現(xiàn)一些重復(fù)項了，比如B到C到D到E的出現(xiàn)次數(shù)很多，也就是從B到C到D到E的概率很高，OK，我們記下，那么也會隨著游戲的進程，各種各樣的四元組越來越多，那么就把頻率（概率）的小的刪除，始終把四元組們維持在一個在手機內(nèi)存里可接受的范圍內(nèi)，（怎么存儲四元組來使存取最快，與我談的主線無關(guān)）。哈哈，我們達到目的了，我們可以記錄下游戲中NPC的一些習(xí)慣了，那么下一步呢？那就是預(yù)測唄，如前假設(shè)，B到C到D到E的概率很高，當PC再次在游戲中打出B+C+D的連招時，NPC提前可以預(yù)測出PC的下一招極有可能是E，于是就采用對E的防御招術(shù)。NPC終于智慧了，好興奮啊，試試吧，把代碼一往原程序一加，效果確實比原來好多了。
  一維概率模型是這么厲害啊!!