Probabilidad de los resultados del algoritmo

Question

I tiene un problema de probabilidad, que necesito para simular en una cantidad razonable de tiempo. En forma simplificada, tengo 30 monedas desleales cada uno con una diferente probabilidad conocida. entonces yo quiero preguntar cosas como "¿cuál es la probabilidad de que exactamente 12 habrá cabezas?", o "¿cuál es la probabilidad de que al menos el 5 habrá colas?".

sé teoría básica de probabilidad, así que sé que puedo enumerar los (30) Seleccione X posibilidades, pero eso no es todo escalable. El peor de los casos (30 elegir 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! : -)

Answer 1

Se puede utilizar un enfoque de programación dinámica.

Por ejemplo, para calcular la probabilidad de 12 cabezas de 30 monedas, sea P (n, k) la probabilidad de que hay cabezas k a partir de los primeros n monedas.

A continuación, 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 moneda i-ésimo es cabezas).

Ahora puede utilizar 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). Construir un nuevo vector de 13 para P (n, i) utilizando la relación de recurrencia anteriormente. Repita hasta que n = 30. Por supuesto, se empieza con el vector (1, 0, 0, 0, ...) para n = 0 (ya que sin monedas, usted está seguro de obtener sin cabeza).

El peor de los casos el uso de este algoritmo es O (n ^ 2) en lugar de exponencial.

Answer 2

Esto es en realidad un problema interesante. Me inspiré para escribir un post al respecto que cubre en detalle justo frente a la moneda injusta lanza hasta el final a la situación de la OP de tener una probabilidad diferente para cada moneda. Se necesita una técnica llamada programación dinámica para resolver este problema en tiempo polinómico.

General Problema: Dada C , una serie de n monedas p ₁ a p _n donde p _i representa la probabilidad de que los i de la moneda salga cara -ésimo, ¿cuál es la probabilidad de k cabezas que suben de tirar todas las monedas?

Este medio de resolución de la siguiente relación de recurrencia:

P ( n , k , C , i ) = < em> p _i x P ( n -1, k -1, C , i 1) + (1- p _i ) x P ( n , k , C , i 1)

Una de Java fragmento de código 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 esto hace es construir una tabla que muestra la probabilidad de que una secuencia de monedas de p _i a p _n contiene k cabezas.

Para una introducción más profunda de probabilidad binomial y una discusión sobre cómo aplicar la programación dinámica echar un vistazo a Coin lanzamientos, binomios y Programación dinámica .

Answer 3

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 de los casos = O (kn)