Probability of Outcomes Algorithmus

Question

Ich habe ein Wahrscheinlichkeitsproblem, das ich in einer angemessenen Zeit simulieren muss. In vereinfachter Form habe ich 30 unfaire Münzen mit jeweils unterschiedlicher bekannter Wahrscheinlichkeit. Ich möchte dann Dinge wie "Wie hoch ist die Wahrscheinlichkeit, dass genau 12 Köpfe sein werden?" Oder "Wie groß ist die Wahrscheinlichkeit, dass MINDESTENS 5 Schwänze sein werden?" Stellen.

Ich kenne grundlegende Wahrscheinlichkeitstheorie, also weiß ich, dass ich alle (30 wähle x) Möglichkeiten aufzählen kann, aber das ist nicht besonders skalierbar. Der schlimmste Fall (30 wählen 15) hat über 150 Millionen Kombinationen. Gibt es einen besseren Weg, um dieses Problem von einem rechnerischen Standpunkt aus anzugehen?

Jede Hilfe wird sehr geschätzt, danke! :-)

Answer 1

Sie können einen dynamischen Programmieransatz verwenden.

Um beispielsweise die Wahrscheinlichkeit von 12 Köpfen aus 30 Münzen zu berechnen, sei P (n, k) die Wahrscheinlichkeit, dass von den ersten n Münzen K-Köpfe kommen.

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

(hier ist p_i die Wahrscheinlichkeit, das Die Münze ist Kopf.

Sie können diese Beziehung jetzt in einem dynamischen Programmieralgorithmus verwenden. Habe einen Vektor von 13 Wahrscheinlichkeiten (die P (n - 1, i) für i in 0..12 darstellen). Erstellen Sie einen neuen Vektor von 13 für P (n, i) unter Verwendung der obigen Wiederholungsbeziehung. Wiederholen Sie dies bis n = 30. Sie beginnen natürlich mit dem Vektor (1, 0, 0, 0, ...) für n = 0 (da Sie ohne Münzen keine Köpfe bekommen).

Der schlimmste Fall bei Verwendung dieses Algorithmus ist O (n^2) und nicht exponentiell.

Answer 2

Das ist eigentlich ein interessantes Problem. Ich wurde inspiriert, einen Blogbeitrag darüber zu verfassen, der im Detail faire von unfairen Münzwürfen bis hin zur Situation des OP mit einer unterschiedlichen Wahrscheinlichkeit für jede Münze behandelt. Sie benötigen eine Technik namens dynamische Programmierung, um dieses Problem in polynomieller Zeit zu lösen.

Allgemeines Problem: Gegeben C eine Reihe von n Münzen p zu p_n wo p_i stellt die Wahrscheinlichkeit von der i -th co im Kopf kommt, was ist die Wahrscheinlichkeit von k Köpfe aus dem Werfen aller Münzen kommen?

Dies bedeutet, die folgende Rekursionsformel Lösung:

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)

Ein Java-Codefragment, das Folgendes enthält:

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

Was dies tut, wird eine Tabelle erstellt, die die Wahrscheinlichkeit zeigt, dass eine Folge von Münzen aus p _i zu p _nk Köpfe enthalten.

Für eine tiefere Einführung in die Binomialwahrscheinlichkeit und eine Diskussion darüber, wie man dynamische Programmierung anwenden kann, werfen Sie einen Blick auf Coin Tosses, Binomials and Dynamic Programming.

Answer 3

Pseudocode:

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 

Worst case = O (kn)