Effiziente Methode zur Berechnung der Wahrscheinlichkeit einer Reihe von Ergebnissen?

Question

Sagen wir, ich spiele 10 verschiedene Spiele. Für jedes Spiel kenne ich die Wahrscheinlichkeit zu gewinnen, die Wahrscheinlichkeit zu binden und die Wahrscheinlichkeit zu verlieren (jedes Spiel hat unterschiedliche Wahrscheinlichkeiten).

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

Ich bin nur die Wahrscheinlichkeit zu versuchen, herauszufinden, W Spiele zu gewinnen, zu binden T Spiele und verlieren L Spiele nach alle 10 Spiele ... zu spielen und hoffentlich besser als O (3^n). Zum Beispiel, wie hoch ist die Wahrscheinlichkeit, 7 zu gewinnen, 2 zu verlieren und 1 zu binden?

Irgendwelche Ideen? Vielen Dank!

---

Bearbeiten - hier einige Beispieldaten für, wenn es nur zwei Spiele sind:

Spiel 1:

• win: 23,3%
• Bindung: 1,1%
• verlieren: 75.6%

Spiel 2:

• win: 29,5%
• Bindung: 3,2%
• verlieren: 67,3%

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

---

• 0 gewinnt: 54,0%
• 1 gewinnen: 39 0,1%
• 2 Siege: 6,9%

---

• 0 Krawatten: 95,8%
• 1-Bindung: 4,2%
• 2 Bindungen: 0,0%

---

• 0 Verluste: 8,0%
• 1 Verlust: 41,1%
• 2 Verluste: 50.9%

---

auf der Grundlage dieser Zahlen gibt es eine allgemeine Formel, um die Wahrscheinlichkeit von W gewinnt für die Suche, T Bindungen und L Verluste? Die möglichen Ergebnisse (WLT) wäre:

• 2-0-0
• 1-1-0
• 1-0-1
• 0-1-1
• 0-2 -0
• 0-0-2

Answer 1

Dies kann mit dynamischer Programmierung erfolgen, ich bin mir nicht sicher, ob es eine bessere Methode gibt, da die Spiele unabhängig sind.

Haben Sie ein 4-D-Array von Gewinnen, Verlusten, Bindungen und Spielen. Sie können Gewinne/Verluste/Bindungen auf die gewünschte Zahl begrenzen (seien Sie W, L, T, W + L + T = G), die Zeitkomplexität ist O (W * L * T * G), was begrenzt ist durch O (G⁴).

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] 

edit)

Wir dies in O tun können (W * L * T * G/max (W, L, T)), dh O (G³). Beachte, dass wir, wenn wir W-Gewinne und T-Bindungen nach G-Spielen haben, L-Verluste haben müssen.

// 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 tun, indem Sie die Wahrscheinlichkeiten von x Berechnung Gewinne/Riegel-/Verluste separat (O (G)), und dann das Hinzufügen/sie intelligent subtrahieren, aber ich habe keine gefunden Weg, dies zu tun.

Answer 2

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

Für gewinnen 7, verlieren 2, Krawatte 1. Es gibt 10!/(2!*7!) oder 360 Möglichkeiten. Also multipliziere alle Ergebnisse wie du, multipliziere dann mit diesen vielen Permutationen der Ergebnisse.

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

Im Allgemeinen werden für dieses Problem die Permutationen 10!/(w!*l!*t!) sein, wobei w die Anzahl der Gewinne, l die Anzahl der Verluste und t die Anzahl der Bindungen ist.

Bearbeiten 1 Beachten Sie, dass das obige nur angibt, wie die Permutationen gezählt werden. Die Gesamtwahrscheinlichkeit ist die Anzahl der Permutationszeiten (pw^w * pl^l * pt^t), wobei pw die Wahrscheinlichkeit eines Gewinns, pl ein Verlust, pt eine Bindung ist. w, l und t sind die Zählimpulse von jedem.

Bearbeiten 2 OK, im Lichte der neuen Informationen, ich kenne keine allgemeine Möglichkeit, dies zu tun. Sie müssen jedes Ergebnis einzeln per Computer berechnen und zusammenfügen. Mit deinem Zwei-Spiele-Beispiel oben. Wenn Sie die Wahrscheinlichkeit von 1 Sieg und 1 Unentschieden finden wollen, müssen Sie jeden möglichen Weg finden, um genau einen Sieg und genau ein Unentschieden zu erhalten (es gibt nur zwei) und addieren sie.

Für zehn Spiele mit dem ersten Beispiel haben Sie 360 ​​Ergebnisse, die Ihre Kriterien erfüllen. Sie müssen jede Permutation durchführen und die Wahrscheinlichkeiten addieren. (wwwwwwwlllt, wwwwwwwltlt, etc) Leider kenne ich keinen besseren Weg, dies zu tun.

Weiter, in Ihrem Zwei-Spiel-Beispiel, für einen Sieg und ein Unentschieden, müssen Sie die Wahrscheinlichkeit des Gewinnens des ersten Spiels und das Binden des zweiten an die Wahrscheinlichkeit des Bindens zuerst und 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 

Answer 3

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 gewinnen numWin-Spiele, verlieren NumLose Spiele und binden Anzahl Spiele aus 10 Spielen.

Answer 4

Wenn Sie möchten, um die 3^n Optionen nicht überfahren, Sie unter Verwendung Sampling ungefähre kann die Antwort: entscheiden, auf N, die Anzahl der Sie wollen probieren. Führen Sie N Stichproben aus und zählen Sie, wie viele Ergebnisse jedes Typs Sie hatten (0 Siege, 1 Sieg usw.). Die ungefähre Wahrscheinlichkeit jedes Ergebnis ist number_of_samples_resulting_this_outcome/N.

Answer 5

HINWEIS

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

bekam ich diese Formel für W Siege, L verliert und NWL Bindungen:

Komplexität der Berechnung

Jede der Kräfte und factorials hat höchstens einen Auftrag von N, so kann der Wert in lineare Zeit berechnet werden, es sei denn, ich fehlen einige Anforderungen.

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