Алгоритм вероятностей результатов

Ответ 1

Вы можете использовать подход динамического программирования.

Например, чтобы вычислить вероятность 12 головок из 30 монет, пусть P (n, k) - вероятность того, что k голов из первых n монет.

Тогда P (n, k) = p_n * P (n - 1, k - 1) + (1 - p_n) * P (n - 1, k)

(здесь p_i - вероятность того, что i-я монета - голова).

Теперь вы можете использовать это соотношение в алгоритме динамического программирования. Имейте вектор из 13 вероятностей (представляющих P (n - 1, i) для я в 0..12). Постройте новый вектор 13 для P (n, i), используя вышеупомянутое рекуррентное отношение. Повторяйте до n = 30. Конечно, вы начинаете с вектора (1, 0, 0, 0,...) для n = 0 (так как без монет, вы наверняка не получите голов).

В худшем случае, используя этот алгоритм, O (n ^ 2), а не экспоненциальный.

Ответ 2

Это действительно интересная проблема. Я был вдохновлен написать сообщение в блоге об этом, подробно освещающее справедливую и несправедливую монету, вплоть до ситуации с ОП, имеющей различную вероятность для каждой монеты. Для решения этой проблемы в полиномиальное время вам понадобится технология динамического программирования.

Общая проблема: С учетом C, серия из n монет p ₁ в p _n, где p _i представляет вероятность того, что i-я монета поднимается вверх, какова вероятность того, что k голов поднимаются из всех монет?

Это означает решение следующего рекуррентного соотношения:

P (n, k, C, i) = p _i x P (n-1, k-1, C, я + 1) + (1-p _i) x 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 _i в p _n содержит k голов.

Для более глубокого ознакомления с биномиальной вероятностью и обсуждения того, как применять динамическое программирование, посмотрите Coin Tosses, Binomials и Dynamic Programming.

Ответ 3

псевдокод:

    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)