Effiziente Methode zur Berechnung der Wahrscheinlichkeit von einem Set von Outcomes?

StackOverflow https://stackoverflow.com/questions/3848285

Frage

Lassen Sie uns sagen ich spiele 10 verschiedene Spiele. Für jedes Spiel, ich kenne die Wahrscheinlichkeit zu gewinnen, ist die Wahrscheinlichkeit der Bindung, und die Wahrscheinlichkeit zu verlieren (jedes Spiel unterschiedliche Wahrscheinlichkeiten hat).

Aus diesen Werten kann ich die Wahrscheinlichkeit des Gewinnens X Spiele berechnen, um die Wahrscheinlichkeit von X-Spiele zu verlieren, und die Wahrscheinlichkeit von X Spiele binden (für X = 0 bis 10).

Ich bin nur versuchen, die Wahrscheinlichkeit zu gewinnen, um herauszufinden, W Spiele, binden T Spiele und verlieren L Spiele schließlich spielen 10 Spiele ... und hoffentlich besser als O (3 ^ n). Zum Beispiel, was die Wahrscheinlichkeit von 7 zu gewinnen, zu verlieren 2 und binden 1?

Irgendwelche Ideen? Dank!

Bearbeiten - hier einige Beispieldaten für wenn es nur 2 Spiele:

Spiel 1:

  • gewinnen: 23,3%
  • Krawatte: 1,1%
  • verlieren: 75,6%

Spiel 2:

  • gewinnen: 29,5%
  • Krawatte: 3,2%
  • verlieren: 67,3%

Auf dieser Basis können wir die Wahrscheinlichkeit nach dem Spielen 2 Spiele berechnen:

  • 0 Siege: 54,0%
  • 1 Sieg: 39,1%
  • 2 Siege: 6,9%
  • 0 Krawatten: 95,8%
  • 1 Krawatte: 4,2%
  • 2 Krawatten: 0,0%
  • 0 Verluste: 8,0%
  • 1 Verlust: 41,1%
  • 2 Niederlagen: 50,9%

Auf der Grundlage dieser Zahlen gibt es eine allgemeine Formel für das Finden der Wahrscheinlichkeit von W Siegen, T Krawatten und L Verluste? Die möglichen Ergebnisse (W-L-T) wäre:

  • 2-0-0
  • 1-1-0
  • 1-0-1
  • 0-1-1
  • 0-2-0
  • 0-0-2
War es hilfreich?

Lösung

Dies kann mit dynamischer Programmierung erfolgen, bin ich sicher nicht, wenn es eine bessere Methode als die Spiele unabhängig sind.

Haben Sie ein 4-D-Array von Gewinnen, Verlusten, Krawatten und Spielen. Sie können Gewinne / Verluste / Bindungen an die Nummer, die Sie möchten (lassen Sie diese auch sein W, L, T, W + L + T = G), Zeitkomplexität begrenzen O (W * L * T * G) sein, die begrenzt ist von O (G4).

Der Algorithmus ist im Grunde: 

A[][][][] = new double[G+1][W][T][L]
// A[g][w][t][l] is the probability of have w wins, t ties, l losses
// after g games. This can be computed from A[g-1].
// Let P[g][o] be the probability of outcome o for game g
//everything else is initially 0.
A[0][0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   for l=0..L
    A[g][w][t][l] = A[g-1][w-1][t][l]*P[g][win] // assume out of bounds
                   +A[g-1][w][t-1][l]*P[g][tie] // reference returns 0
                   +A[g-1][w][t][l-1]*P[g][lose]
return A[G][W][T][L]

Bearbeiten)

Wir können dies tun, in O (W * L * T * G / max (W, L, T)), das heißt O (G³). Beachten Sie, dass, wenn wir W Siegen und T Bindungen nach G-Spiele haben, dann müssen wir L Verluste haben. 

// we should pick the conditions we loop to be the smallest two.
// here we just use wins and ties.
A[][][][] = new double[G+1][W][T]
A[0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   A[g][w][t] = A[g-1][w-1][t]*P[g][win] // assume out of bounds
               +A[g-1][w][t-1]*P[g][tie] // reference returns 0
               +A[g-1][w][t]*P[g][lose]
return A[G][W][T]

Vielleicht ist es möglich, dies deutlich schneller zu machen, indem die Berechnung der Wahrscheinlichkeiten von x Siege / Riegel- / Verluste separat (O (G)), und dann das Hinzufügen / sie intelligent subtrahieren, aber ich habe festgestellt, keinen Weg, dies zu tun .

Andere Tipps

Mein Bereich, Statistiken!

Sie müssen die Chancen einer Permutation berechnen, die als so getan werden kann: 

O = chanceWin^numWin * chanceTie^numTie * chanceLose^numLose

wo numWin, numLose und numTie sind 7, 2 und 1, wie pro Ihr Beispiel.

Nun multiplizieren mit den Permutationen zu gewinnen, das ist: 

O *= 10! / ((10-numWin)! * numWin!)

dann verlieren: 

p = 10-numWin
O *= p! / ((p-numLose)! * numLose!)

dann binden: 

p = 10-(numWin+numLose)
O *= p! / ((p-numTie)! * numTie!)

Jetzt O ist die Wahrscheinlichkeit, dass Sie numWin Spiele gewinnen, verlieren numLose Spiele und binden numTie Spiele von 10 Spielen.

Für Ihr Beispiel müssen Sie die Möglichkeiten berücksichtigen, dass das Ergebnis auftreten kann.

Für win 7, verlieren 2, Krawatte 1. Es gibt 10! / (2!*7!) oder 360 mögliche Wege. So multiplizieren alle Ergebnisse, wie Sie getan haben, dann vermehren sich durch, dass viele Permutationen der Ergebnisse.

Für alle Gewinne, können Sie einfach multiplizieren, weil es genau eine Permutation von zehn Siegen. Für eine Mischung, müssen Sie die Permutation berücksichtigen.

In der Regel für dieses Problem der Permutationen 10!/(w!*l!*t!) sein, wo w Anzahl der Siege ist, l ist die Anzahl der Verluste, und t ist die Anzahl der Verbindungen.

Bearbeiten 1 Beachten Sie, dass die oben nur gibt an, wie die Permutationen zu zählen. Die Gesamtwahrscheinlichkeit ist die Anzahl von Permutationen Zeiten (pw ^ w ^ * PL * l ^ pt t) wobei Pw Wahrscheinlichkeit eines Gewinns, PL ein Verlust, pt einer Bindung. w, l und t sind die Zählungen von jedem.

Edit 2 OK, im Lichte der neuen Informationen, ich weiß nicht, von einer allgemeinen Art und Weise, dies zu tun. Sie werden jedes Ergebnis von Hand einzeln Computer haben und sie zusammen addieren. Mit Ihrem zwei Spiel Beispiel oben. Wenn Sie die Wahrscheinlichkeit von 1 Sieg und 1 Krawatte finden wollen, müssen Sie jeden möglichen Weg, um genau 1 Sieg und genau eine Krawatte (es gibt nur zwei), und fügen Sie gestalten müssen.

Für zehn Spiele mit dem Anfang Beispiel werden Sie 360 ??Ergebnisse haben, die Ihre Kriterien entsprechen. Sie werden jede Permutation zu tun haben, und die Wahrscheinlichkeiten zu addieren. (Wwwwwwwllt, wwwwwwwltl, etc.) Leider weiß ich nicht einen besseren Weg, dies zu tun.

Ferner wird in Ihrem Zwei-Spiel Beispiel für einen Sieg und eine Krawatte, müssen Sie die Wahrscheinlichkeit zu gewinnen das erste Spiel hinzufügen und bindet den zweiter auf die Wahrscheinlichkeit zunächst zu binden, dann gewinnen.

So gibt es neun unabhängige Ergebnisse: 

W W
W T
W L
T W
T T
T L
L W
L T
L L

Wenn Sie nicht möchten, dass die 3 ^ laufen über n Optionen, können Sie ungefähre die Antwort unter Verwendung von Probenahme : auf N entscheiden, die Anzahl der Zeiten, die Sie möchten Probe. Run N Proben und zählen, wie viele Ergebnisse jeder Art Sie hatten (0 Siege, 1 Sieg, etc). Die ungefähre Wahrscheinlichkeit jedes Ergebnis ist number_of_samples_resulting_this_outcome / N.

Hinweis

Die Antwort unten ist nur gültig, wenn der Gewinn / verlieren Wahrscheinlichkeiten sind fixed durch die Reihe von Spielen. Ich falsch verstanden die Bedingungen. Ich lasse es trotzdem als Lösung für den einfacheren Fall.

Ich habe diese Formel für W Siege, L verliert, und N-W-L Bindungen:

alt text

Die Komplexität der Berechnung

Jeder der Befugnisse und factorials hat höchstens eine Größenordnung von N, so kann der Wert in berechnet werden lineare Zeit , wenn ich irgendeine Anforderung fehle.

Der folgende Java-Code funktioniert für mich. Ich validiert auch, dass die Wahrscheinlichkeiten zu 1 summieren: 

public static double p(int w, int l, int t, double pw, double pl) {
    double r = factorial(w+l+t) * Math.pow(pw,w) * Math.pow(pl,l) * Math.pow(1-pw-pl, t);
    r /= factorial(w) * factorial(l) * factorial(t);
    return r;
}

private static long factorial(int n) {
    long res = 1;
    for(int i = 2; i <= n; i++)
        res *= i;

    return res;
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top