Consider a game which is played in 2 halves between two teams, A and B. The outcome of the 2nd half of the game is independent of the outcome of the 1st half.

Each team can score between 0 and N points in each half, and the probability of scoring exactly M is known and equal to $P_1^A(M)$ for team A and $P_1^B(M)$ for team B in the first half, and $P_2^A(M)$ and $P_2^B(M)$ respectively in the 2nd half.

The final score is the sum of each teams' scores. So, if team A scores once in the first half and twice in the 2nd, while team B score twice in the first and not at all in the 2nd half, then the final score will be 2-2. Thus the lowest possible scoring match is 0-0 and this an only occur when the first half is 0-0 and the 2nd half is 0-0. Similar logic applies where, if $N=4$ for example, the final score is 8-8

However, there are many possible combinations for final scores between 0-0 and 8-8. I wish to compute the probabilities for every possible final score.

I know that there are $(N+1)^4$ possible combinations in total, but the only way I have been able to work out the probabilities of each combination is by hand in a spreadsheet with actual numbers. For example, I know when N=4 there are 10 possible ways of making a final score of 7-4 (which is Not the same as 4-7 obviously) can occur in 10 ways, so I just compute the product of those 10 probabilities (3-0 and 4-4, 3-1 and 4-3, 3-2 and 4-2, 3-3 and 4-1, 3-4 and 4-0, 4-0 and 3-4, 4-1 and 3-3, 4-2 and 3-2, 4-3 and 3-1, 4-4 and 3-0).

I would like to find a way to do this more easily, and feel that there should be some formulas I can apply, just from knowing $N$ and each of the underlying probabilities, but so far I didn’t find anything.

BTW this isn't homework, it's just something i am interested in.

  • $\begingroup$ "The final score is the sum of each teams' scores. So if team A scores once in the first half and twice in the 2nd, while team B score twice in the first and not at all in the 2nd half, then the final score will be 2-2."—shouldn't the final score be 3-2? ... and ... "Similar logic applies where the final score is 8-8."—are you taking $N=4$? $\endgroup$ – Greg Martin Aug 24 '18 at 16:14
  • $\begingroup$ @GregMartin yes ! Sorry, I will update the questions... $\endgroup$ – Joe King Aug 24 '18 at 17:53

Since the scoring for $A$ and $B$ are independent, we can treat them independently, and then multiply the results after.

For $P(A)$, the total probability of getting score $M$ across the board is $$\sum\limits_{n=0}^M P_1^A(n)\cdot P_2^A(M-n)$$

So the total answer is $$\bigg(\sum\limits_{n=0}^M P_1^A(n)\cdot P_2^A(M-n) \bigg)\cdot \bigg(\sum\limits_{n=0}^M P_1^B(n)\cdot P_2^B(M-n)\bigg)$$

Note that if $n>N$, then $P_1^A(n)=P_2^A(n)=P_1^B(n)=P_2^B(n)=0$. This should address @JoeKing's concerns.

  • $\begingroup$ Thank you, this looks great, but I perhaps haven't understood it properly. If we let $N=2$ and set all probabilities equal for each half, and we want the probability for the final score P(0-0), doesn't this give (0.25 x 0.25) x (0.25 x 0.25) which doesn't seem right ? Also, surely the formula should include $N$ ? $\endgroup$ – Joe King Aug 24 '18 at 19:16
  • $\begingroup$ @JoeKing It shouldn't matter, since we would obviously set the probability of $n>N$ to be 0, as in my edit. Additionally, where did you get the probability of 0.25 from? This was not specified! $\endgroup$ – Don Thousand Aug 24 '18 at 19:27
  • $\begingroup$ I was just using the example of N=2, so that there are 4 possible outcomes in each half, so that the probability of each outcome in each half is 0.25 (same for the 2nd half) $\endgroup$ – Joe King Aug 24 '18 at 19:33
  • $\begingroup$ @JoeKing There are only three possibilities...0,1,2...I don't understand $\endgroup$ – Don Thousand Aug 24 '18 at 19:34
  • $\begingroup$ I'm sure it's just me beeing stupid, but I though like this. N=1, so first half results can be one of 0-0, 0-1, 1-0, and 1-1, and I am giving equal probablity (0,25 each) to them to keep it simple. I must be just mising something obvious !# $\endgroup$ – Joe King Aug 24 '18 at 19:36

Let $P_1(K,L)$ be the probability that team A scores $K$ in the the first half and team B scores $L$ in the first half; then we have the generating function identity $$ \sum_{K=0}^N \sum_{L=0}^N P_1(K,L) x^K y^L = \bigg( \sum_{K=0}^N P_1^A(K) x^K \bigg) \bigg( \sum_{L=0}^N P_1^B(L) y^L \bigg) $$ (which is just a fancy way of saying that $P_1(K,L) = P_1^A(K) P_1^B(L)$). A similar formula applies for $P_2(K,L)$, the probability that team A scores $K$ in the the second half and team B scores $L$ in the second half.

Since the total scores are the sum of these two subscores, the corresponding generating functions multiply. In other words, if $P(S,T)$ is the probability that team A scores $S$ in total and team B scores $T$ in total, then \begin{align*} \sum_{S=0}^{2N} \sum_{T=0}^{2N} P(S,T) x^S y^T &= \bigg( \sum_{K=0}^N \sum_{L=0}^N P_1(K,L) x^K y^L \bigg) \bigg( \sum_{K=0}^N \sum_{L=0}^N P_2(K,L) x^K y^L \bigg) \\ &= \bigg( \sum_{K=0}^N P_1^A(K) x^K \bigg) \bigg( \sum_{K=0}^N P_2^A(K) x^K \bigg) \bigg( \sum_{L=0}^N P_1^B(L) y^L \bigg) \bigg( \sum_{L=0}^N P_2^B(L) y^L \bigg). \end{align*} One simply has to expand the polynomial on the right-hand side to determine any particular coefficient $P(S,T)$.

Of course, this gives the formula from Rushabh Mehta's answer. But this is probably an easier calculation to code in some languages, especially if you want many probabilities $P(S,T)$; and it always helps to understand where these formulas come from and how helpful generating functions can be.

  • 1
    $\begingroup$ Generating Functions are the bomb in counting questions $\endgroup$ – Don Thousand Aug 24 '18 at 16:58
  • 1
    $\begingroup$ Aaaaaah Generating Functions ! It seems like this is what I have been missing. Thank you ! $\endgroup$ – Joe King Aug 24 '18 at 17:57
  • $\begingroup$ I am slightly confused about how to apply these formula (with x and y). I might be reminded of the binomial theorem form a previous life (is there a connection? I feel like I am on the cusp of "getting it" but there is just that breakthrough needed hah $\endgroup$ – Joe King Aug 24 '18 at 19:19

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.