3
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Are you assuming the probabilities of each game are the same, because I don't think the sum is normally distributed when you have different probabilities of winning each game. $\endgroup$ – Tyler Mar 31 '16 at 19:46
  • $\begingroup$ no. The sum of any large set of random variables with finite variance resembles a normal distribution. $\endgroup$ – Doug M Mar 31 '16 at 19:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.