Probabilità di Outcomes Algorithm

Question

ho un problema di probabilità, che ho bisogno di simulare in un ragionevole lasso di tempo. In forma semplificata, ho 30 monete sleali ciascuno con una probabilità nota diversa. Io poi voglio chiedere cose come "qual è la probabilità che esattamente 12 sarà teste?", O "qual è la probabilità che almeno il 5 sarà la coda?".

Lo so teoria della probabilità di base, quindi so che posso elencare tutti (30 scelgono x) possibilità, ma non è particolarmente scalabile. Il caso peggiore (30 scelgono 15) ha più di 150 milioni di combinazioni. C'è un modo migliore per affrontare questo problema da un punto di vista computazionale?

Ogni aiuto è molto apprezzato, grazie! : -)

Answer 1

È possibile utilizzare un approccio di programmazione dinamica.

Ad esempio, per calcolare la probabilità di 12 teste di 30 monete, sia P (n, k) la probabilità che ci sia teste k dal primo n monete.

Allora P (n, k) = p_n * P (n - 1, k - 1) + (1 - p_n) * P (n - 1, k)

(qui p_i è la probabilità la moneta-esimo è testa).

È ora possibile utilizzare questo rapporto in un algoritmo di programmazione dinamica. Avere un vettore di 13 probabilità (che rappresentano P (n - 1, i) per i in 0..12). Costruire un nuovo vettore di 13 per P (n, i) utilizzando la relazione di ricorrenza sopra. Ripetere fino a quando n = 30. Naturalmente, si inizia con il vettore (1, 0, 0, 0, ...) per n = 0 (in quanto senza monete, siete sicuri di ottenere senza testa).

Il caso peggiore che utilizza questo algoritmo è O (n ^ 2) anziché esponenziale.

Answer 2

Questo è in realtà un problema interessante. Sono stato ispirato a scrivere un post sul blog su di esso copre in dettaglio fiera vs moneta ingiusto lancia fino alla situazione del PO di avere una probabilità diversa per ogni moneta. Hai bisogno di una tecnica chiamata programmazione dinamica di risolvere questo problema in tempo polinomiale.

Generale Problema: Data C , una serie di n monete p ₁ a p _n , dove p _i rappresenta la probabilità dei i moneta -esimo dare testa, qual è la probabilità di k teste provenienti dal tirare tutte le monete?

Questo significa risolvere la seguente relazione di ricorrenza:

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)

Un frammento di codice Java che fa questo è:

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;
}

Quello che sta facendo è la costruzione di una tabella che mostra la probabilità che una sequenza di monete da p _i a p _n contiene k teste.

Per un'introduzione più profonda alla probabilità binomiale e una discussione su come applicare programmazione dinamica dare un'occhiata a Coin lanci, binomi e dinamica Programmazione .

Answer 3

Pseudocodice:

    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

Caso peggiore = O (kn)