3
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the help! I do have different probabilities for each game, which makes this method inefficient for calculating outcome probabilities. However, I have come up with a way to enumerate all outcomes without having to check all 3^10 possibilities by using dynamic programming! $\endgroup$ – Kenny Oct 3 '10 at 19:57
  • $\begingroup$ If you're enumerating all outcomes you're looking at all 3^10 possibilities. There's no free lunch here ;-). $\endgroup$ – whuber Oct 4 '10 at 2:05
  • $\begingroup$ You're right, I'm not actually enumerating all individual game outcomes, just overall outcomes AFTER 10 games. I'm looking at the possible outcomes for only one category, and then adding the new possible outcomes with each new additional category (one at a time). With this method, you're able to find the probability of all (W,L,T) outcomes after X games in polynomial time: O(n^3) :-) $\endgroup$ – Kenny Oct 4 '10 at 5:09
  • $\begingroup$ Are you sure it's not O(3^n)? $\endgroup$ – whuber Oct 4 '10 at 13:34
  • $\begingroup$ Yes I'm sure :-) $\endgroup$ – Kenny Oct 6 '10 at 2:11
0
$\begingroup$

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).

:-)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the clarification. The point is that at each stage you only have to consider the probability distribution over (W,L,T) and not how it was derived. $\endgroup$ – whuber Oct 6 '10 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy