algorithm - Probabilidad de algoritmo de resultados
optimization probability (3)
Tengo un problema de probabilidad, que necesito simular en un tiempo razonable. En forma simplificada, tengo 30 monedas desleales, cada una con una probabilidad conocida diferente. Entonces quiero preguntar cosas como "¿cuál es la probabilidad de que exactamente 12 sean cabezas?" O "¿cuál es la probabilidad de que AL MENOS 5 sean colas?".
Conozco la teoría de la probabilidad básica, así que sé que puedo enumerar todas las posibilidades (30 eligen x), pero eso no es particularmente escalable. El peor de los casos (30 eligen 15) tiene más de 150 millones de combinaciones. ¿Hay una mejor manera de abordar este problema desde un punto de vista computacional?
¡Cualquier ayuda es muy apreciada, gracias! :-)
Puede usar un enfoque de programación dinámica.
Por ejemplo, para calcular la probabilidad de 12 caras de 30 monedas, sea P (n, k) la probabilidad de que haya k cabezas de las primeras n monedas.
Entonces P (n, k) = p_n * P (n - 1, k - 1) + (1 - p_n) * P (n - 1, k)
(Aquí p_i es la probabilidad de que la i-ésima moneda sea cara).
Ahora puede usar esta relación en un algoritmo de programación dinámica. Tener un vector de 13 probabilidades (que representan P (n - 1, i) para i en 0..12). Construya un nuevo vector de 13 para P (n, i) usando la relación de recurrencia anterior. Repite hasta n = 30. Por supuesto, comienzas con el vector (1, 0, 0, 0, ...) para n = 0 (ya que sin monedas, seguro que no tienes cabezas).
El peor caso que utiliza este algoritmo es O (n ^ 2) en lugar de exponencial.
Este es en realidad un problema interesante. Me inspiré para escribir una publicación en un blog sobre el tema, que cubría en detalle monedas justas e injustas hasta la situación del PO de tener una probabilidad diferente para cada moneda. Necesita una técnica llamada programación dinámica para resolver este problema en tiempo polinomial.
Problema general: Dada C , una serie de n monedas p 1 a p n donde p i representa la probabilidad de que la i -ésima moneda salga cara, ¿cuál es la probabilidad de que k cabezas salgan lanzando todas las monedas?
Esto significa resolver la siguiente relación de recurrencia:
P ( n , k , C , i ) = p i x P ( n -1, k -1, C , i +1) + (1- p i ) x P ( n , k , C , i +1)
Un fragmento de código Java que hace esto es:
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;
}
Lo que está haciendo es construir una tabla que muestre la probabilidad de que una secuencia de monedas de p i a p n contenga k cabezas.
Para una introducción más profunda a la probabilidad binomial y una discusión sobre cómo aplicar la programación dinámica, eche un vistazo a Coin Tosses, Binomials y Dynamic Programming .
Pseudocódigo:
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
Peor caso = O (kn)