幾率演算法

1. 概率怎麼算啊

【概率的定義】 隨機事件出現的可能性的量度。概率論最基本的概念之一。人們常說某人有百分之多少的把握能通過這次考試，某件事發生的可能性是多少，這都是概率的實例。 ■概率的頻率定義 隨著人們遇到問題的復雜程度的增加，等可能性逐漸暴露出它的弱點，特別是對於同一事件，可以從不同的等可能性角度算出不同的概率，從而產生了種種悖論。另一方面，隨著經驗的積累，人們逐漸認識到，在做大量重復試驗時，隨著試驗次數的增加，一個事件出現的頻率，總在一個固定數的附近擺動，顯示一定的穩定性。R.von米澤斯把這個固定數定義為該事件的概率行侍雀，這就是概率的頻率定義。從理論上講，概率的頻率定義是不夠嚴謹的。A.H.柯爾莫哥洛夫於1933年給出了概率的公理化定義。 ■概率的嚴格定義 設E是隨機試驗，S是它的樣本空間。對於E的每一事件A賦於一個實數，記為P(A)，稱為事件A的概率。這里P(·)是一個集合函數，P(·)要滿足下列條件：（1）非負性：對於每一個事件A，有P(A)≥0;（2）規范性：對於必然事件S，有P(S)=1;（3）可列可加性：檔早設A1，A2……是兩兩互不相容談判的事件，即對於i≠j，Ai∩Aj=φ，（i,j=1,2……），則有P（A1∪A2∪……）=P（A1）+P（A2）+……

2. 概率演算法

最近做了一個活動抽獎需求，項目需要控制預算，概率需要分布均勻，這樣才能獲得所需要的概率結果。
例如抽獎得到紅包獎金，而每個獎金的分布都有一定概率：

現在的問題就是如何根據概率分配給用戶一定數量的紅包。

演算法思路 ：生成一個列表，分成幾個區間，例如列表長度100，1-40是0.01-1元的區間，41-65是1-2元的區間等，然後隨機從100取出一個數，看落在哪個區間，獲得紅包區間，最後用隨機函數在這個紅包區間內獲得對應紅包數。

時間復雜度 ：預處理O(MN)，隨機數生成O(1)，空間復雜度O(MN)，其中N代表紅包種類，M則由最低概率決定。

優缺點 ：該方法優點是實現簡單，構造完成之後生成隨機類型的時間復雜度就是O(1)，缺點是精李鎮度不夠高，佔用空間大，尤其是在類型很多的時候。

演算法思路 ：離散演算法通過概率分布構造幾個點[40, 65, 85, 95,100]，構造的數組的值就是前面概率依次累加的概率之和。在生成1~100的隨機數，看它落在哪個區間，比如50在[40,65]之間，就是類型2。在查找時，可以採用線性查找，或效率更高的二分查找。

演算法復雜度 ：比一般演算法減少佔用空間，還可以採用二分法找出R，這樣，預處理O(N)，隨機數生成O(logN)，空間復雜度O(N)。

優缺點 ：比一般演算法佔告飢用空間減少，空間復雜度O(N)。

演算法思路 ：Alias Method將每種概率當做一列，該演算法最終的結果是要構造拼裝出一個每一列合都為1的矩形，若每一列最後都要為1，那麼要將所有元素都乘以5（概率類型的數量）。

此時會有概率大於1的和小於1的，接下來就是構造出某種演算法用大於1的補足小於1的，使每種概率最後都為1，注意，這里要遵循一個限制：每列至多是兩種概率的組合。

最終，我們得到了兩個數組，一個是在下面原始的prob數組[0.75,0.25,0.5,0.25,1]，另外就是在上面補充的Alias數組，其值代表填充的那一列的序號索引，（如果這一列上不需填充，那麼就是NULL），[4,4,0,1,NULL]。當然，最終的結果可能不止一種，你也可能得到其他結果。

舉例驗證下，比如取第二列，讓prob[1]的值與一個隨機小數f比較，如果f小於prob[1]，那麼結果就是2-3元，否則就是Alias[1]，即4。

我們可以來簡單驗證一下，比如隨機到第二列的概率是0.2，得到第三列下半部分的概率為0.2 * 0.25，記得襪擾返在第四列還有它的一部分，那裡的概率為0.2 * (1-0.25)，兩者相加最終的結果還是0.2 * 0.25 + 0.2 * (1-0.25) = 0.2，符合原來第二列的概率per[1]。

演算法復雜度 ：預處理O(NlogN)，隨機數生成O(1)，空間復雜度O(2N)。

優缺點 ：這種演算法初始化較復雜，但生成隨機結果的時間復雜度為O(1)，是一種性能非常好的演算法。

3. (六) 概率演算法

前面所討論演算法的每一計算步驟都是確定的，而本次所討論的概率演算法允許演算法在執行過程中隨機地選擇下一個計算步驟。在許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。

概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下， 可將概率演算法大致分為四類：數值概率演算法、蒙特卡羅(MonteCarlo) 演算法、拉斯羨孝陵維加斯(Las Vegas) 演算法和舍伍德(Sherwood) 演算法。

隨機數在隨機化演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在隨機化演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
線性同餘法 是產生偽隨機數的最常用的方法。由線性同餘法產生的隨機序列 滿足

其中 。d稱為該隨機序列的種子。如何選取該方法中的常數b、c和m直接關繫到所產生的隨機序列的隨機性能。這是隨機性理論研究的內容，已超出本書討論的范圍。從直觀上看，m應取得充分大，因此可取m為機器大數，另外應取 ，因此可取b為一素數。

為了在設計概率演算法時便於產生所需的隨機數，建立一個隨機數類RandomNumber：該類包含一個需由用戶初始化的種子randSeed。給定初始種子後，即可產生與之相應的隨機序列。種子randSeed是一個無符號長整型數， 可由用戶選定也可用系統時間自動產生。函數Random的輸入參數 是一個無符號長整型數，它返回 范圍內的一個隨機整數。函數fRandom返回[0，1) 內的一個隨機實數。

數值概率演算法常用於數值問題的求解。這類演算法所得到的往往是近似解。且近似解的精度隨計算時間的增加而不斷提高。在許多情況下，要計算出問題的精確解是不可能的或沒有必要的，因此用數值概率演算法可得到相當滿意的解。

當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時

舍伍德演算法就是一種利用隨機演算法改造確定性演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞情形行為與特定實例之間的關聯性。

思想：利用隨機演算法改造已有演算法，使得演算法的性能盡量與輸入數據無關，即平滑演算法的性能。它總能求得問兄戚題的一個解，且求得的解總是正確的。

演算法的性能 =平均性能 + 一個很小的隨機值。 舍伍德演算法是為了得到好的平均性能。

一個演算法，對於不同的輸入數據，其演算法的性能是不一樣的。比如快排演算法，每次選擇第一個元素作為基準，慎帶對序列從小到大排序：

拉斯維加斯演算法不會得到不正確的解。一旦用拉斯維加斯演算法找到一個解，這個解就一定是正確解。但有時用拉斯維加斯演算法會找不到解。

與蒙特卡羅演算法類似，拉斯維加斯演算法找到正確解的概率隨著它所用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯演算法反復對該實例求解足夠多次，可使求解失效的概率任意小。

蒙特卡羅演算法用於求問題的准確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為「是」或「否」，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是准確的，一個整數的近似因子沒有任何意義。

用蒙特卡羅演算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於演算法所用的時間。演算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅演算法的主要缺點也在於此。一般情況下，無法有效地判定所得到的解是否肯定正確。

在實際應用中常會遇到一些問題，不論採用確定性演算法或隨機化演算法都無法保證每次都能得到正確的解答。蒙特卡羅演算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。

有些蒙特卡羅演算法除了具有描述問題實例的輸入參數外，還具有描述錯誤解可接受概率的參數。這類演算法的計算時間復雜性通常由問題的實例規模以及錯誤解可接受概率的函數來描述。

參考鏈接： http://www.ruanyifeng.com/blog/2015/07/monte-carlo-method.html

數值概率演算法的應用

舍伍德演算法的應用

拉斯維加斯演算法的應用

蒙特卡羅演算法的應用

4. 概率計算公式是什麼

條件概率：

條件概率：已知事件B出現的條件下A出現的概率，稱為條件概率，記作：P(A|B)

條件概率計算公式：

當P(A)>0，P(B|A)=P(AB)/P(A)

當P(B)>0，P(A|B)=P(AB)/P(B)

乘法公式：

P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

推廣：P(ABC)=P(A)P(B|A)P(C|AB)

全概率公式：

設：若事件A1，A2，…，An互不相容，且A1+A2+…+An=Ω，則稱A1，A2，…，An構成一個完備事件組。

概率演算法：概率演算法的一個基本特徵是，對所求問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。

隨機數在概率演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。

5. 體彩一等獎概率演算法

體彩大樂透中一等獎幾率是1/21425712，演算法是這樣的：前區35選5個=（35*34*33*32*31）/(5*4*3*2*1)=324632；後區12選2個=(12*11)/(2*1)=66，兩個相乘，就是總和注數共21425712注，所以中一等獎幾率是1/21425712，中獎的幾率很底喲！

6. 概率計算方法 概率計算方法是什麼

1、頻次演算法。即分別考慮每種事件發生的頻次，單個事件頻次除總頻次，即是概率值，或者單個事件頻次除以其他事件頻次，然後再轉化為概率值昌腔。

2、集合對應法。舉例：半徑為1的圓，通過上面一點做弦，弦長小於根號2的概率多少。通過畫圖顯示，直觀就能判斷，弦的數目對應圓上的點，這些點的集合就是弧長，因此弦的數目可以用弧長對應，小於根號2的弦和所有弦的數目就是弧長和圓周長的比值。有了這種對應關系，很容易計算出概率值50%。

3、反向演算法。有些場悄猛合，正面去計算比較耐運衫麻煩，如果從反面去計算，即先計算它的相斥事件的概率，再用1去減就可以得出概率值。

7. 概率計算公式是什麼

概率公式是褲旁：P(A∪B)=P(A)+P(B)－P(AB)。

定理：設A、B是互不相配洞容事件（AB=φ），則：P（A∪B）=P（A）+P（B）-P（AB）。

推論1：設A1、 A2、…、 An互不相容，則：P(A1+A2+...+ An)= P(A1) +P(A2) +…+ P(An)。

推論2：設A1、 A2、…、 An構成完備事件組，則：P(A1+A2+...+An)=1。

相關信息

條件概率：已知事件B出現的條件下A出現的概率，稱為條培純枯件概率，記作：P(A|B)。

條件概率計算公式：

當P(A)>0，P(B|A)=P(AB)/P(A)。

當P(B)>0，P(A|B)=P(AB)/P(B)。

P(AB)=P(A)×P(B|A)=P(B)×P(A|B)。

推廣：P(ABC)=P(A)P(B|A)P(C|AB)。

8. 概率計算公式

1、C 3 10 = (10*9*8)/(1*2*3)

A 3 10=10*9*8

2、A(n,m)=n*(n-1)*(n-2)……（n-m+1)，也就是由n往下每個數連乘。

C（n,m）=A(n,m)/A(m,m)。一般地，從n個不同的元素中，任取m（m≤n）個元素為一組，叫作從n個不同元素中取出m個元素的一個組合。

(8)幾率演算法擴展閱讀：

概率的加法法則

定理：設A、B是互不相容事件（AB=φ），則：

P（A∪B）=P（A）+P（B）

推論1：設A1、握讓 A2、…段灶局、 An互不相容，則：P(A1+A2+...+ An)= P(A1) +P(A2) +…+ P(An)

推論2：設A1、 A2、…、 An構成完備事件組，則：P(A1+A2+...+An)=1

推論3：為事件A的對立事件。

推論4：若B包含A，則P(B－A)= P(B)－P(A)

推論5（廣義加法公式）：對任意兩個事件A與B，有P(A∪B)=P(A)+P(B)－P(AB)[1]

條件概率

條件概率：已知事件B出現的條件下A出現的概率，稱為條件概率，記作：P(A|B)

條件概率計算公式：

當P(A)>0，P(B|A)=P(AB)/P(A)

當P(B)>0，P(A|B)=P(AB)/P(B)

乘法公式

P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

推廣：P(ABC)=P(A)P(B|A)P(C|AB)[1]