Эффективный метод расчета вероятности набора результатов?

Question

Допустим, я играю в 10 разных игр.Для каждой игры я знаю вероятность выигрыша, вероятность выигрыша и вероятность проигрыша (каждая игра имеет разные вероятности).

Из этих значений я могу вычислить вероятность выигрыша X игр,вероятность проигрыша X игр и вероятность связывания X игр (для X = от 0 до 10).

Я просто пытаюсь выяснить вероятность выигрыша W игр, связывая T игр и проигрыш L игр после игры во все 10 игр ... и, надеюсь, лучше, чем O (3 ^ n).Например, какова вероятность выиграть 7, потерять 2 и связать 1?

Есть идеи?Спасибо!

---

Правка - вот некоторые примеры данных, если было только 2 игры:

Игра 1:

• победа: 23,3%
• ничья: 1,1%
• проигрыш: 75,6%

Игра 2:

• победа: 29,5%
• ничья:3,2%
• проигрыш: 67,3%

Исходя из этого, мы можем рассчитать вероятность после игры в 2 играх:

---

• 0 побед: 54,0%
• 1 победа: 39,1%
• 2 победы: 6,9%

---

• 0: 95,8%
• 1 ничья: 4,2%
• 2 ничьи: 0,0%

---

• 0 потерь: 8,0%
• 1 потеря: 41,1%
• 2 проигрыша: 50,9%

---

На основании этих чисел существует ли общая формула для определения вероятности W побед, T связи, L потери?Возможные результаты (WLT) будут:

• 2-0-0
• 1-1-0
• 1-0-1
• 0-1-1
• 0-2-0
• 0-0-2

Answer 1

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

Имейте 4-D массив, с выигрышами, проигрышами, связями и играми. Вы можете ограничить количество выигрышей / проигрышей / ничьих желаемым числом (пусть это будут W, L, T, W + L + T = G), сложность по времени будет O (W * L * T * G), что ограничено O (G⁴).

Алгоритм в основном:

A[][][][] = new double[G+1][W][T][L]
// A[g][w][t][l] is the probability of have w wins, t ties, l losses
// after g games. This can be computed from A[g-1].
// Let P[g][o] be the probability of outcome o for game g
//everything else is initially 0.
A[0][0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   for l=0..L
    A[g][w][t][l] = A[g-1][w-1][t][l]*P[g][win] // assume out of bounds
                   +A[g-1][w][t-1][l]*P[g][tie] // reference returns 0
                   +A[g-1][w][t][l-1]*P[g][lose]
return A[G][W][T][L]

редактировать)

Мы можем сделать это в O (W * L * T * G / max (W, L, T)), то есть O (G³). Обратите внимание: если после G-игр у нас будет W побед и T ничьих, то у нас должно быть L потерь.

// we should pick the conditions we loop to be the smallest two.
// here we just use wins and ties.
A[][][][] = new double[G+1][W][T]
A[0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   A[g][w][t] = A[g-1][w-1][t]*P[g][win] // assume out of bounds
               +A[g-1][w][t-1]*P[g][tie] // reference returns 0
               +A[g-1][w][t]*P[g][lose]
return A[G][W][T]

Может быть, возможно сделать это значительно быстрее, вычислив вероятности x побед / связей / потерь отдельно (O (G)), а затем разумно сложив / вычтя их, но я не нашел способа сделать это .

Answer 2

Примечание

Ответ ниже действителен только тогда, когда вероятности выигрыша / проигрыша фиксированы в серии игр. Я неправильно понял условия. Я все равно оставляю это как решение для более простого случая.

Я получил эту формулу для W побед, L проигрышей и N-W-L ничьих:

Сложность вычислений

Каждая из степеней и факториалов имеет не более порядка N, поэтому значение можно вычислить за линейное время , если я не пропущу некоторые требования.

Следующий код Java работает для меня. Я также подтвердил, что вероятности составляют 1:

public static double p(int w, int l, int t, double pw, double pl) {
    double r = factorial(w+l+t) * Math.pow(pw,w) * Math.pow(pl,l) * Math.pow(1-pw-pl, t);
    r /= factorial(w) * factorial(l) * factorial(t);
    return r;
}

private static long factorial(int n) {
    long res = 1;
    for(int i = 2; i <= n; i++)
        res *= i;

    return res;
}

Answer 3

Если вы не хотите использовать 3 ^ n опций, вы можете приблизить ответ, используя выборка : выберите N, сколько раз вы хотитеобразец.Запустите N образцов и посчитайте, сколько результатов каждого типа у вас было (0 побед, 1 победа и т. Д.).Примерная вероятность каждого исхода равна number_of_samples_resulting_this_outcome / N.

Answer 4

Моя область, статистика!

Вам нужно рассчитать шансы одной перестановки, что можно сделать так:

O = chanceWin^numWin * chanceTie^numTie * chanceLose^numLose

где numWin, numLose и numTie равны 7, 2 и 1, в соответствии с вашим примером.

Теперь умножьте на перестановки для выигрыша, а это:

O *= 10! / ((10-numWin)! * numWin!)

затем проиграл:

p = 10-numWin
O *= p! / ((p-numLose)! * numLose!)

затем завязывание:

p = 10-(numWin+numLose)
O *= p! / ((p-numTie)! * numTie!)

Теперь вы можете выиграть numWin, проиграть numLose и связать numTie из 10 игр.

Answer 5

Для вашего примера вам нужно рассмотреть возможные пути достижения результата.

Для победы 7 проиграть 2, ничья 1. Есть 10! / (2!*7!) или 360 возможных способов.Так что умножьте все результаты, как вы, а затем умножьте на это количество перестановок результатов.

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

В общем случае для этой задачи перестановки будут 10!/(w!*l!*t!), где w - количество выигрышей, l - количество проигрышей, а t - количество связей.

Редактировать 1 Обратите внимание, что выше только указывает, как подсчитать перестановки.Общая вероятность - это количество перестановок, умноженное на (pw ^ w * pl ^ l * pt ^ t), где pw - вероятность выигрыша, pl проигрыша, pt ничья.w, l и t - количество каждого.

Edit 2 ОК, в свете новой информации, я не знаю общего способа сделать это.Вам нужно будет вручную обработать каждый результат и сложить их вместе.С вашим примером из двух игр выше.Если вы хотите найти вероятность 1 выигрыша и 1 ничьей, вам нужно будет найти все возможные способы получить ровно 1 выигрыш и ровно одну ничью (их всего два) и сложить их.

Длядесять игр с первоначальным примером, у вас будет 360 результатов, которые соответствуют вашим критериям.Вы должны будете сделать каждую перестановку и сложить вероятности.(wwwwwwwllt, wwwwwwwltl и т. д.) К сожалению, я не знаю лучшего способа сделать это.

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

Итак, есть девять независимых результатов:

W W
W T
W L
T W
T T
T L
L W
L T
L L