結果概率算法

我有一個概率問題，我需要在合理的時間內進行模擬。簡單的說，我有30個不公平的硬幣，每個硬幣有不同的已知概率。然後我想問一些問題，比如「什麼是正確的12的概率？」，或者「至少5會是尾巴的概率是多少？」。我知道基本的概率論，所以我知道我可以枚舉所有（30選擇x）的可能性，但這不是特別的可擴展性。最壞的情況（30選15）有超過1.5億組合。從計算的角度來看，有沒有更好的方法來處理這個問題？結果概率算法

任何幫助非常感謝，謝謝！ :-)

來源

2010-08-19 Kenny

你正在尋找一個封閉形式的表達情況= O（KN）？ – dirkgently 2010-08-19 06:53:02

請參閱更新後的帖子。 – cletus 2010-08-20 03:55:24

您可以使用動態編程方法。例如，爲了計算30個硬幣中12個頭的概率，設P（n，k）爲來自前n個硬幣的k個頭的概率。

然後P（N，K）= P_N * P（N - 1，K - 1）+（1 - P_N）* P（N - 1，k）的

（這裏P_I是概率我的硬幣是頭）。

您現在可以在動態編程算法中使用此關係。有一個13個概率的向量（表示在0..12中，i代表P（n-1，i））。使用上述遞歸關係爲P（n，i）構建一個新的向量13。重複，直到n = 30。當然，你從n = 0的矢量（1,0,0,0，...）開始（因爲沒有硬幣，你一定沒有頭）。

使用此算法的最壞情況是O（n^2）而不是指數。

來源

2010-08-19 06:59:06

這正是我所期待的！非常感謝！ :-) – Kenny 2010-08-19 08:10:33

其他算法沒有O（n！）複雜度而不是指數？ – 2010-08-20 14:58:08

不，我敢肯定它就像保羅說的那樣是O（n^2），因爲你使用動態編程方法利用了以前每次迭代的工作。 – Kenny 2010-08-20 17:00:07

這實際上是一個有趣的問題。我受到啓發，寫了一篇關於它的博客文章，詳細介紹了公平與不公平投幣一直拋到OP對每枚硬幣有不同概率的情況。你需要一種稱爲動態規劃的技術來解決多項式時間的問題。

一般問題：鑑於Ç，一系列Ñ硬幣p到p_Ñ其中p_我表示概率i -th co在即將到來的頭腦中，拋擲所有硬幣的概率是多少？

這意味着求解以下遞推關係：

P（Ñ，ķ，Ç，我）= p_我 X P（ n -1，k -1，Ç，我 1）+（1-p_我）×P（Ñ，ķ，Ç，我 1）

這是一個Java代碼片段：

private static void runDynamic() { 
    long start = System.nanoTime(); 
    double[] probs = dynamic(0.2, 0.3, 0.4); 
    long end = System.nanoTime(); 
    int total = 0; 
    for (int i = 0; i < probs.length; i++) { 
    System.out.printf("%d : %,.4f%n", i, probs[i]); 
    } 
    System.out.printf("%nDynamic ran for %d coinsin %,.3f ms%n%n", 
     coins.length, (end - start)/1000000d); 
} 

private static double[] dynamic(double... coins) { 
    double[][] table = new double[coins.length + 2][]; 
    for (int i = 0; i < table.length; i++) { 
    table[i] = new double[coins.length + 1]; 
    } 
    table[1][coins.length] = 1.0d; // everything else is 0.0 
    for (int i = 0; i <= coins.length; i++) { 
    for (int j = coins.length - 1; j >= 0; j--) { 
     table[i + 1][j] = coins[j] * table[i][j + 1] + 
      (1 - coins[j]) * table[i + 1][j + 1]; 
    } 
    } 
    double[] ret = new double[coins.length + 1]; 
    for (int i = 0; i < ret.length; i++) { 
    ret[i] = table[i + 1][0]; 
    } 
    return ret; 
}

什麼本正在做的是構造一個表，示出了硬幣從P A序列_我到p_Ñ包含ķ頭的概率。

有關二項概率的更深入介紹以及關於如何應用動態規劃的討論，請參閱Coin Tosses, Binomials and Dynamic Programming。

來源

2010-08-19 19:30:40 cletus

感謝您的答案和您的博客文章，我現在相信瞭解動態編程:) – Konerak 2011-02-26 17:25:49

僞代碼：

procedure PROB(n,k,p) 
/* 
    input: n - number of coins flipped 
      k - number of heads 
      p - list of probabilities for n-coins where p[i] is probability coin i will be heads 
    output: probability k-heads in n-flips 
    assumptions: 1 <= i <= n, i in [0,1], 0 <= k <= n, additions and multiplications of [0,1] numbers O(1) 
*/ 

A =()() //matrix 
A[0][0] = 1 // probability no heads given no coins flipped = 100% 

for i = 0 to k                //O(k) 
    if i != 0 then A[i][i] = A[i-1][i-1] * p[i] 
    for j = i + 1 to n - k + i            //O(n - k + 1 - (i + 1)) = O(n - k) = O(n) 
     if i != 0 then A[i][j] = p[j] * A[i-1][j-1] + (1-p[j]) * A[i][j-1] 
     otherwise  A[i][j] = (1 - p[j]) * A[i][j-1] 
return A[k][n] //probability k-heads given n-flips

最差

來源

2010-11-23 07:35:00 Brian

結果概率算法

回答

相關問題