Алгоритм вероятности исходов

Question

У меня есть проблема вероятности, которую мне нужно смоделировать за разумное время. В упрощенном виде у меня есть 30 недобросовестных монет с различной известной вероятностью. Затем я хочу спросить что-то вроде «какова вероятность, что ровно 12 будет головами?» Или «какова вероятность, что по крайней мере 5 будут хвостами?».

Я знаю базовую теорию вероятностей, поэтому знаю, что могу перечислить все (30 вариантов выбора x), но это не особенно масштабируемо. В худшем случае (30 выбирают 15) более 150 миллионов комбинаций. Есть ли лучший способ подойти к этой проблеме с вычислительной точки зрения?

Любая помощь с благодарностью, спасибо! : -)

Answer 1

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

Например, чтобы вычислить вероятность 12 голов из 30 монет, пусть 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-я монета - голова).

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

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

Answer 2

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

Общая проблема: Дано 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 , к , 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 голов.

Для более глубокого знакомства с биномиальной вероятностью и обсуждения того, как применять динамическое программирование, взгляните на Брошюры монет, биномы и динамическое программирование .

Answer 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)