Probability of Outcomes Algorithm

Question

ich eine Wahrscheinlichkeit Problem haben, die ich in einer angemessenen Zeit simulieren müssen. In vereinfachter Form habe ich 30 unfaire Münzen jeweils mit einer anderen bekannten Wahrscheinlichkeit. Ich mag dann die Dinge fragen, wie „Was ist die Wahrscheinlichkeit, dass genau 12 werden Köpfe sein?“ Oder „Was ist die Wahrscheinlichkeit, dass mindestens 5 Schwanz sein?“.

ich grundlegende Wahrscheinlichkeitstheorie kennen, so dass ich weiß, dass ich alle aufzählen kann (30 wählen x) Möglichkeiten, aber das ist nicht besonders skalierbar. Der schlimmste Fall (30 wählten 15) verfügt über mehr als 150 Millionen Kombinationen. Gibt es einen besseren Weg, um dieses Problem aus einem rechnerischen Standpunkt zu nähern?

Jede Hilfe ist sehr geschätzt, Dank! : -)

Answer 1

Sie können einen dynamischen Programmieransatz verwenden.

Beispiel von 30 Münzen, die Wahrscheinlichkeit von 12 Köpfen zu berechnen, seien P (n, k) die Wahrscheinlichkeit, dass es k Köpfe von den ersten n-Münzen.

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

(hier p_i ist die Wahrscheinlichkeit, die i-te Münze Köpfe).

Sie können nun diese Beziehung in einem dynamischen Programmieralgorithmus verwenden. Haben einen Vektor von 13 Wahrscheinlichkeiten (P, die repräsentieren (n - 1, i) für i in 0..12). Baue einen neuen Vektor von 13 für P (n, i) unter Verwendung des vorstehenden Rekursionsformel. Wiederholen, bis n = 30. Natürlich beginnen Sie mit dem Vektor (1, 0, 0, 0, ...) für n = 0 (da ohne Münzen, sind Sie sicher, keine Köpfe zu bekommen).

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

Answer 2

Dies ist eigentlich ein interessantes Problem. Ich war inspiriert einen Blogeintrag zu schreiben über sie im Detail Messe bedeckt vs unfaire Münze des ganzen Weg wirft, um die Lage des OP von einer anderen Wahrscheinlichkeit für jede Münze hat. Sie benötigen eine Technik namens dynamische Programmierung dieses Problem in polynomialer Zeit zu lösen.

Allgemein Problem: Da C , eine Reihe von n Münzen p ₁ auf p _n , wobei p _i stellt die Wahrscheinlichkeit der i -te Münze Köpfe kommen, was die Wahrscheinlichkeit von k Köpfe aus werfen alle Münzen kommen?

Das bedeutet folgende Rekursion Lösung:

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)

Ein Java-Code-Snippet, das dies tut, ist:

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 ist eine Tabelle konstruieren, dass zeigt die Wahrscheinlichkeit, dass eine Folge von Münzen von p _i auf p _n enthält k Köpfe.

Für eine tiefere Einführung in der binomischen Wahrscheinlichkeit und eine Diskussion darüber, wie die dynamische Programmierung nimmt unter Münzwürfen, Binomen und 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)