18

妥当な時間内にシミュレートする必要がある確率の問題があります。簡単に言うと、確率が異なる既知のコインが 30 枚あります。次に、「ちょうど 12 個が表になる確率は?」または「少なくとも 5 個が裏になる確率は?」などの質問をしたいと思います。

私は基本的な確率論を知っているので、すべて (30 個の x を選択) の可能性を列挙できることはわかっていますが、それは特にスケーラブルではありません。最悪のケース (30 が 15 を選択) では、1 億 5000 万を超える組み合わせがあります。計算の観点からこの問題にアプローチするより良い方法はありますか?

どんな助けでも大歓迎です、ありがとう！:-)

4

3 に答える 3

19

動的計画法のアプローチを使用できます。

たとえば、30 枚のコインのうち 12 回表が出る確率を計算するには、最初の n 枚のコインから k 回表が出る確率を P(n, k) とします。

次に、P(n, k) = p_n * P(n - 1, k - 1) + (1 - p_n) * P(n - 1, k)

(ここで p_i は、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-19T06:59:06.003 に答える
15

これは実際には興味深い問題です。コインごとに確率が異なるというOPの状況に至るまで、公正なコインと不公正なコインのトスを詳細にカバーするブログ投稿を書くように促されました。この問題を多項式時間で解決するには、動的計画法と呼ばれる手法が必要です。

一般的な問題：C、一連のn個のコインp1からpnが与えられた場合、p iはi番目のコインが頭に浮かぶ確率を表します。k個の頭がすべてのコインを投げることから浮かび上がる確率はどれくらいですか？

これは、次の漸化式を解くことを意味します。

P（n、k、C、i）= p i x P（n -1、k -1、C、i +1）+（1- p i）x P（n、k、C、i +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;
}

これが行っているのは、 piからpnまでのコインのシーケンスにk個のヘッドが含まれている確率を示すテーブルを作成することです。

二項確率のより深い紹介と動的計画法の適用方法に関する議論については、コイントス、二項式、および動的計画法を参照してください。

于 2010-08-19T19:30:40.133 に答える
0

擬似コード:

    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

最悪の場合 = O(kn)

于 2010-11-23T07:35:00.547 に答える