Algorithm/formula for computing the probability of winning a range of games

Question

As of this post, the Golden State Warriors have 68 wins and need to win at least 5 of their remaining 7 games to break the record for most wins in a season. This article estimates the Warriors' chance of winning each of those 7 games and ultimately gives them an 85% chance of breaking the record.

That got me thinking of how to efficiently solve the general version of this problem. That is, suppose a team has $n$ games with a probability $P_i$ of winning the $i$th game, $1 \leq i \leq n$, with the outcome of the games independent of each other. What is the probability of the team winning between $m_1$ and $m_2$ games where $0\leq m_1\leq m_2 \leq n$?

The naive approach would be to sum the probabilities of each valid combination of games, but that would be computationally inefficient. Another approach would be to run a Monte Carlo simulation, but that does not give you an exact result. I'm looking for an efficient algorithm/formula that would give you the exact answer to this problem; however, I am inclined to believe that this problem is NP Complete.

Answer 1

An efficient way to do the computation is to multiply out the polynomial

$$\prod_{i=1}^n ((1-p_i) + p_i x)$$

where $p_i$ is the probability of a win in game $i$. Then the coefficient of $x^k$ in the product will be the probability of $k$ wins. Each factor is the probability generating function of a Bernoulli random variable.

In the Warriors' case with the probabilities provided in the article you link to, this polynomial is $$(0.108 + 0.892x) (0.099 + 0.901x) (0.044 + 0.956x) (0.343 + 0.657x) (0.173 + 0.827x) (0.674 + 0.326x) (0.066 + 0.934x)$$ which is, after expansion, $0.000 + 0.000 x + 0.002 x^2 + 0.020 x^3 + 0.116 x^4 + 0.335 x^5 + 0.400 x^6 + 0.127 x^7$ and so you have, for example, probability $0.335$ of winning exactly 5 games, and probability $0.335 + 0.400 + 0.127 = 0.862$ of winning at least 5 games.

You'll notice that the probabilities I get here are slightly different from those given in the table "Chance Warriors finish with:" at the article you linked to. This is because FiveThirtyEight's predictions are based on probabilities are altered after each game and as a result the games are not quite independent.

As for the complexity of doing the multiplication, you can multiply a degree-n polynomial by a degree-m polynomial with $(n+1)(m+1)$ multiplications (and some additions). To compute this product you have to multiply a degree-1 polynomial by a degree-1, then a degree-2 by a degree-1, and so on up to a degree-$(n-1)$ by a degree-1. This takes $(2)(2) + (3)(2) + \ldots (n)(2) \approx n^2$ multiplications. (There may be more efficient ways to arrange the multiplication, so this is just an upper bound.)

Answer 2

As far as I am aware, you would have to individually compute the probability of every valid combination and sum them, as you mentioned, even though this may be a bit time consuming.

Obviously, if the probability of winning every game was equal, it would be a simple binomial distribution.

Answer 3

For a small number of games, I would go with brute force and run through all of the scenarios.

If were a large number of games. Each game can be thought of as a binomial distributed random variable with mean $P_i$ and variance $(P_i)(1-P_i)$.

The sum of a large number of games then is approximately a normally distributed random variable with mean = sum of the means, and variance = sum of the variances.