结果算法的可能性

Question

我有一个概率问题,我需要在合理的时间内模拟.在简化形式中,我有30个不公平的硬币,每个硬币具有不同的已知概率.然后我想问一些事情,比如"12个将成为头部的概率是多少？",或者"至少5个尾部的概率是多少？".

我知道基本概率理论,所以我知道我可以枚举所有(30选择x)的可能性,但这不是特别可扩展的.最坏的情况(30选择15)有超过1.5亿组合.从计算的角度来看,是否有更好的方法来解决这个问题？

非常感谢任何帮助,谢谢!:-)

Answer 1

您可以使用动态编程方法.

例如,为了计算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)而不是指数.

Answer 2

这实际上是一个有趣的问题.我受到启发,写了一篇关于它的博客文章,详细介绍了公平与不公平的硬币投掷,一直到OP的每个硬币具有不同概率的情况.您需要一种称为动态编程的技术来在多项式时间内解决此问题.

一般问题:给定C,一系列n个硬币p ₁到p _n,其中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;
}

这是做一个表格,显示从p _i到p _n的一系列硬币包含k个头的概率.

有关二项式概率的更深入介绍以及如何应用动态编程的讨论,请参阅Coin Tosses,Binomials和Dynamic Programming.