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.

Answer 3

For your example, you need to consider the possible ways that the outcome can occur.

For win 7, lose 2, tie 1. There are 10! / (2!*7!) or 360 possible ways. So multiply all the outcomes as you did, then multiply by that many permutations of the outcomes.

For all wins, you can just multiply because there's exactly one permutation of ten wins. For a mix, you need to consider the permutation.

In general for this problem the permutations will be 10!/(w!*l!*t!) where w is number of wins, l is number of losses, and t is number of ties.

Edit 1 Note that the above only indicates how to count the permutations. The total probability is the number of permutations times (pw^w*pl^l*pt^t) where pw is probability of a win, pl a loss, pt a tie. w, l, and t, are the counts of each.

Edit 2 OK, in light of the new information, I don't know of a general way to do this. You'll have to individually computer each outcome by hand and add them together. With your two-game example above. If you want to find the probability of 1 win and 1 tie, you'll have to find every possible way of getting exactly 1 win and exactly one tie (there are only two) and add them up.

For ten games with the initial example, you'll have 360 outcomes that meet your criteria. You'll have to do each permutation and add up the probabilities. (wwwwwwwllt, wwwwwwwltl, etc) Unfortunately, I don't know of a better way to do this.

Further, in your two-game example, for one win and one tie, you must add the probability of winning the first game and tying the second to the probability of tying first, then winning.

So, there are nine independent outcomes:

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

Answer 4

If you don't want to run over the 3^n options, you can approximate the answer by using sampling: decide on N, the number of times you wish to sample. Run N samples, and count how many results of each type you had (0 wins, 1 win, etc). The approximate probability of each outcome is number_of_samples_resulting_this_outcome / N.

Answer 5

NOTE

The response below is only valid when the win/lose probabilities are fixed through the series of games. I misunderstood the conditions. I leave it anyway as a solution for the simpler case.

I got this formula for W wins, L loses, and N-W-L ties:

Complexity of computation

Each one of the powers and factorials has at most an order of N, so the value can be computed in linear time, unless I am missing some requirement.

The following Java code works for me. I also validated that the probabilities sum to 1:

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