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

Question

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

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

Любая помощь очень ценится, спасибо!:-)

Answer 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 - вероятность того, что монета - головы).

Теперь вы можете использовать это отношение в алгоритме динамического программирования. Иметь вектор из 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

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

Общая проблема: Данный С, серии н монеты п₁ к п_н где п_я представляет собой вероятность я-я монета выпадет орлом, какова вероятность того, что к головы поднимаются от бросания всех монет?

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

п(н,к,С,я) = п_я Икс п(н-1,к-1,С,я+1) + (1-п_я) Икс п(н,к,С,я+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;
}

При этом создается таблица, показывающая вероятность того, что последовательность монет из п_я к п_н содержать к головы.

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

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)