Алгоритм вероятности исходов
У меня есть проблема вероятности, который мне нужно смоделировать в разумные сроки. В упрощенном виде у меня есть 30 недобросовестных монет с различной известной вероятностью. Затем я хочу спросить что-то вроде «какова вероятность того, что именно 12 будет головами?» Или «какова вероятность, что по крайней мере 5 будут хвостами?».
Я знаю основную теорию вероятностей, поэтому я знаю, что Можно перечислить все (30 вариантов выбора x), но это не особенно масштабируемо. В худшем случае (30 выбирают 15) более 150 миллионов комбинаций. Есть ли лучший способ подойти к этой проблеме с вычислительной точки зрения?
Любая помощь очень ценится, спасибо! : -)
2 ответа
Вы можете использовать подход динамического программирования.
Например, чтобы вычислить вероятность выпадения 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) для i в 0..12). Постройте новый вектор из 13 для P (n, i), используя указанное выше рекуррентное соотношение. Повторяйте до n = 30. Конечно, вы начинаете с вектора (1, 0, 0, 0, ...) для n = 0 (поскольку без монет вы наверняка не получите орла).
Наихудший случай использования этого алгоритма - O (n ^ 2), а не экспоненциальный.
Это на самом деле интересная проблема. Я был вдохновлен написать об этом статью в блоге, подробно описывающую честное и нечестное бросание монет, вплоть до ситуации ОП, когда вероятность для каждой монеты разная. Для решения этой проблемы за полиномиальное время вам понадобится техника, называемая динамическим программированием.
Общая проблема: Дана C, серия из n монет p1 - pn где pi представляет собой вероятность того, что i-я монета окажется головой, какова вероятность того, что k голов окажется головой при подбрасывании всех монет?
Это означает решение следующего рекуррентного соотношения:
P(n,k,C,i) = pi x P(n-1,k-1,C, i+1) + (1-pi) 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;
}
Что это делает, так это строит таблицу, которая показывает вероятность того, что последовательность монет от pi до pn содержит k голов.
Для более глубокого введения в биномиальную вероятность и обсуждения применения динамического программирования посмотрите Жеребьевки, биномы и динамическое программирование.