Probability of Game Outcomes (with ties!)

Question

Let's say I'm playing 10 "games". For each game, I know the probability of winning, the probability of tying, and the probability of losing.

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 each outcome after playing all 10 games. For example, what is the probability of winning 7, losing 2, and tying 1?

Any ideas? Thanks!

---

Here's some example data for 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, what is the probability of each outcome? 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

Obviously this is pretty trivial with 2 games, but is there a generic formula for finding the probability of W wins, T ties, and L losses after X games?

Answer 1

Let $p_W$ be the probability of a win, $p_T$ that of a tie, and $p_L$ of a loss. Because the probabilities sum to 1, so does their tenth power. Expanding this out expresses the tenth power as a linear combination of the monomials $p_W^W p_T^T p_L^L$ where each term picks out the probability of $W$ wins, $T$ ties, and $L$ losses.

In more detail,

$$(p_W + p_T + p_L)^{10} = \sum_{W+T+L=10} {W+T+L \choose {W \quad T \quad L}}p_W^W p_T^T p_L^L$$

where the multinomial coefficient is computed as

$${W+T+L \choose {W \quad T \quad L}} = \frac{(W+T+L)!}{W! T! L!}\text{.}$$

For example, the probability of 7 wins, 2 ties, and 1 loss is given by

$$\Pr[W=7, T=2, L=1] = {7+2+1 \choose {7 \quad 2 \quad 1}}p_W^7 p_T^2 p_L^1$$

$$=\frac{10!}{7! 2! 1!}p_W^7 p_T^2 p_L^1 = 360p_W^7 p_T^2 p_L^1\text{.}$$

This is called the Multinomial Distribution.

When the probabilities vary from one game to the other, there is nothing simpler than enumerating all the possible sequences that produce a given number of wins, ties, and losses. The multinomial coefficients count the numbers of such sequences. The value of 360 in the example indicates there are 360 distinct ways you can arrive at 7 wins, 2 ties, and a loss. Each one of those ways contributes its own distinct sequence of probabilities as given by each of the ten games. To obtain a complete table of the 66 possible answers requires computing all $(1+1+1)^{10} = 59049$ products of ten probabilities.

Answer 2

I've figured out how to do this in O(n^3) time (where n is the number of games):

Use a 4-dimensional array: probabilityOfOutcome[gamesLookedAt][wins][losses][ties]

Initially, we have "looked at" zero games. After looking at zero games, there is a 100% probability of being 0-0-0, so set:

probabilityOfOutcome[0][0][0][0] = 1;

"Look at" one additional game at a time, basing each outcome probability on the last step:

for every outcome in probabilityOfOutcome[g-1]:

• consider the probability of winning game g
• consider the probability of losing game g
• consider the probability of tying game g

For g games, there will be (g^2 + 3g + 2)/2 possible outcomes, and you will have to iterate over g games... therefore O(g^3)

I can go into more detail with the for-loop if people still need clarification (it is actually a triple nested for-loop in practice).

:-)