Efficient Method for Calculating the Probability of a Set of Outcomes?

Question

Let's say I'm playing 10 different games. For each game, I know the probability of winning, the probability of tying, and the probability of losing (each game has different probabilities).

From these values, I can calculate the probability of winning X games, the probability of losing X games, and the probability of tying X games (for X = 0 to 10).

I'm just trying to figure out the probability of winning W games, tying T games, and losing L games after playing all 10 games... and hopefully do better than O(3^n). For example, what is the probability of winning 7, losing 2, and tying 1?

Any ideas? Thanks!

---

Edit - here's some example data for if there were only 2 games:

Game 1:

• win: 23.3%
• tie: 1.1%
• lose: 75.6%

Game 2:

• win: 29.5%
• tie: 3.2%
• lose: 67.3%

Based on this, we can calculate the probability after playing 2 games of:

---

• 0 wins: 54.0%
• 1 win: 39.1%
• 2 wins: 6.9%

---

• 0 ties: 95.8%
• 1 tie: 4.2%
• 2 ties: 0.0%

---

• 0 losses: 8.0%
• 1 loss: 41.1%
• 2 losses: 50.9%

---

Based on these numbers, is there a generic formula for finding the probability of W wins, T ties, and L losses? The possible outcomes (W-L-T) would be:

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

Answer 1

This can be done with dynamic programming, I'm not sure if there is a better method as the games are independent.

Have a 4-D array, of wins, losses, ties, and games. You can limit wins/losses/ties to the number you want (let these be W, L, T, W+L+T=G) , time complexity will be O(W*L*T*G), which is bounded by O(G⁴).

The algorithm is basically:

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)

We can do this in O(W*L*T*G/max(W,L,T)), i.e. O(G³). Note that if we have W wins and T ties after G games, then we must have L losses.

// 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]

Maybe it's possible to do this significantly faster, by computing the probabilities of x wins/ties/losses separately (O(G)), and then adding/subtracting them intelligently, but I haven't found a way to do this.

Answer 2

My area, statistics!

You need to calculate the odds of one permutation, which can be done as so:

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

where numWin, numLose and numTie are 7, 2 and 1, as per your example.

Now multiply by the permutations for winning, which is:

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

then losing:

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

then tying:

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

Now O is the odds of you winning numWin games, losing numLose games and tying numTie games out of 10 games.