algorithm - learning - ¿Método eficiente para calcular la probabilidad de un conjunto de resultados?

algoritmos de machine learning en r

Question

Digamos que estoy jugando 10 juegos diferentes. Para cada juego, sé la probabilidad de ganar, la probabilidad de empatar y la probabilidad de perder (cada juego tiene diferentes probabilidades).

A partir de estos valores, puedo calcular la probabilidad de ganar X juegos, la probabilidad de perder X juegos y la probabilidad de atar X juegos (para X = 0 a 10).

Estoy tratando de descubrir la probabilidad de ganar juegos W , empatar T y perder L luego de jugar los 10 juegos ... y con suerte hacerlo mejor que O (3 ^ n). Por ejemplo, ¿cuál es la probabilidad de ganar 7, perder 2 y vincular 1?

¿Algunas ideas? ¡Gracias!

Editar: aquí hay algunos datos de ejemplo para si hubiera solo 2 juegos:

Juego 1:

• ganar: 23.3%
• empate: 1.1%
• perder: 75.6%

Juego 2:

• ganar: 29.5%
• empate: 3.2%
• perder: 67.3%

En base a esto, podemos calcular la probabilidad después de jugar 2 juegos de:

• 0 victorias: 54.0%
• 1 victoria: 39.1%
• 2 victorias: 6.9%

• 0 vínculos: 95.8%
• 1 empate: 4.2%
• 2 ataduras: 0.0%

• 0 pérdidas: 8.0%
• 1 pérdida: 41.1%
• 2 pérdidas: 50.9%

Con base en estos números, ¿existe una fórmula genérica para encontrar la probabilidad de W wins, T ties y L pérdidas? Los posibles resultados (WLT) serían:

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

Answer 1

Esto se puede hacer con programación dinámica, no estoy seguro de si hay un método mejor ya que los juegos son independientes.

Tener una matriz 4-D, de victorias, derrotas, empates y juegos. Puede limitar las ganancias / pérdidas / vínculos al número que desee (sean W, L, T, W + L + T = G), la complejidad del tiempo será O (W * L * T * G), que está limitado por O (G⁴).

El algoritmo es básicamente:

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]

editar)

Podemos hacer esto en O (W * L * T * G / max (W, L, T)), es decir O (G³). Tenga en cuenta que si tenemos W gana y T empata después de G juegos, entonces debemos tener L pérdidas.

// 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]

Tal vez sea posible hacer esto de manera significativamente más rápida, calculando las probabilidades de x victorias / empates / pérdidas por separado (O (G)), y luego sumar / restar de manera inteligente, pero no he encontrado la manera de hacerlo.

Answer 2

Mi área, estadísticas!

Debe calcular las probabilidades de una permutación, lo que se puede hacer de la siguiente manera:

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

donde numWin, numLose y numTie son 7, 2 y 1, según su ejemplo.

Ahora multiplica por las permutaciones para ganar, que es:

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

luego perder:

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

luego atar:

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

Ahora, O es la probabilidad de que ganes juegos numWin, perdiendo juegos numLose y atando juegos numéricos de 10 juegos.

Answer 3

Para su ejemplo, debe considerar las posibles formas en que puede ocurrir el resultado.

Para ganar 7, perder 2, empate 1. ¡Hay 10! / (2!*7!) 10! / (2!*7!) O 360 formas posibles. Así que multiplique todos los resultados como lo hizo, luego multiplique por esa cantidad de permutaciones de los resultados.

Para todas las ganancias, puedes multiplicar porque hay exactamente una permutación de diez victorias. Para una mezcla, debes considerar la permutación.

En general, para este problema las permutaciones serán 10!/(w!*l!*t!) Donde w es el número de victorias, l es el número de pérdidas, y t es el número de lazos.

Editar 1 Tenga en cuenta que lo anterior solo indica cómo contar las permutaciones. La probabilidad total es el número de permutaciones veces (pw ^ w * pl ^ l * pt ^ t) donde pw es la probabilidad de una victoria, una pérdida, un empate. w, l y t, son los recuentos de cada uno.

Edit 2 OK, a la luz de la nueva información, no sé de una manera general de hacer esto. Tendrá que computar individualmente cada resultado a mano y agregarlos juntos. Con tu ejemplo de dos juegos arriba. Si quieres encontrar la probabilidad de 1 victoria y 1 empate, tendrás que encontrar todas las formas posibles de obtener exactamente 1 victoria y exactamente una corbata (solo hay dos) y sumarlas.

Para diez juegos con el ejemplo inicial, tendrá 360 resultados que cumplan con sus criterios. Tendrás que hacer cada permutación y sumar las probabilidades. (wwwwwwwllt, wwwwwwwltl, etc.) Desafortunadamente, no conozco una mejor manera de hacer esto.

Además, en su ejemplo de dos juegos, para una victoria y un empate, debe agregar la probabilidad de ganar el primer juego y vincular el segundo a la probabilidad de empatar primero y luego ganar.

Entonces, hay nueve resultados independientes:

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

Answer 4

Si no desea ejecutar más de 3 ^ n opciones, puede aproximar la respuesta mediante el muestreo : decidir en N, el número de veces que desea probar. Ejecute N muestras y cuente cuántos resultados de cada tipo tenía (0 triunfos, 1 victoria, etc.). La probabilidad aproximada de cada resultado es number_of_samples_resulting_this_outcome / N.

Answer 5

NOTA

La respuesta a continuación solo es válida cuando las probabilidades de ganar / perder se fijan a través de la serie de juegos. Yo malentendí las condiciones. Lo dejo de todos modos como una solución para el caso más simple.

Obtuve esta fórmula para W wins, L lose y NWL ties:

Complejidad de la computación

Cada uno de los poderes y factoriales tiene como máximo un orden de N, por lo que el valor puede calcularse en tiempo lineal , a menos que me falte algún requisito.

El siguiente código Java funciona para mí. También validé que las probabilidades suman 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;
}