結果の確率アルゴリズム

StackOverflow https://stackoverflow.com/questions/3519395

質問

確率の問題がありますが、これを合理的な時間でシミュレートする必要があります。単純化された形式では、30の不公正なコインがあり、それぞれ異なる確率があります。次に、「正確に12がヘッドになる確率はどれくらいですか？」や「少なくとも5が尾になる確率は何ですか？」などのことを尋ねたいと思います。

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

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

役に立ちましたか？

解決

動的プログラミングアプローチを使用できます。

たとえば、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はi'th coinがヘッドである可能性です）。

この関係を動的プログラミングアルゴリズムで使用できるようになりました。 0..12のIの場合はp（n -1、i）を表す13の確率（p（n -1、i）を表します）を持っています。上記の再発関係を使用して、p（n、i）用に13の新しいベクトルを構築します。 n = 30になるまで繰り返します。もちろん、n = 0のベクトル（1、0、0、0、...）から始めます（コインがないため、頭を獲得しないでください）。

このアルゴリズムを使用する最悪のケースは、指数ではなくO（n^2）です。

他のヒント

これは実際に興味深い問題です。私は、それについて詳細にカバーしているブログ投稿を書くことに触発されました。公正なコインは、各コインに異なる確率を持つというOPの状況に至ります。多項式時間にこの問題を解決するために、動的プログラミングと呼ばれる手法が必要です。

一般的な問題： 与えられた c, 、 シリーズ n コイン p1 に pn どこ p私 の確率を表します 私- 頭の上に来るコイン、の確率は何ですか k すべてのコインを投げることから来る頭？

これは、次の再発関係を解決することを意味します。

p(n,k,c,私) = p私 バツ p(n-1,k-1,c,私+1) + (1-p私） バツ p(n,k,c,私+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私 に pn 含む k 頭。

二項確率のより深い紹介と動的プログラミングの適用方法に関する議論については、 コイントス、二項、動的プログラミング.

pseudocode：

    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）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top