Algorithm/formula for computing the probability of winning a range of games 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.
 A: 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. 
A: 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.
A: 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.)
