Combinatorics Problems solved by Pascal in 1654

Feb 2015
9
0
Dusseldorf
Players A and B play a sequence of games. The first one to win 10 games is the overall winner. A won 8 games so far B won 7 games so far. Assuming that each player wins a game independent of previous outcomes with probability 1/2, what is the probabilty of each player becoming the overall winner?

1st solution (intuitive one):

AA, ABA, ABBA, BAA, BABA, BBAA -> A wins
BBB, BBAB, BABB, ABBB -> B wins

calculate probabilities to each sequence and add up per player

2nd solution (counterintuitive):

Game will end in at most 4 games:
AAAA -> A wins
AAAB AABA ABAA BAAA -> A wins
AABB ABAB ABBA BAAB BABA BBAA -> A wins
ABBB BABB BBAB BBBA -> B wins
BBBB -> B wins

#combos a player wins/total number of 4 game combos (16) yields the same solution.

Solution 2 gives me troubles. Can you give me an intuition why it is valid and why it is equivalent to solution one?

Thanks
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
Hey stollenm.

Basically you know that there is only a maximum of four games left to play to get a winner. If you have the worst case scenario which is a 2/2 split then player A will win since he has 10-8 or 2 games left.

So the rest is looking at every combination of four games and then relating to them to the event that either A wins or B wins.

You look at these and then you add up all the frequencies or probabilities to get an answer.
 
Feb 2015
9
0
Dusseldorf
Thank you for your answer. Unfortunately I still don't fully grasp the idea of looking at all 4 games-left combinations. In my mind it feels like we are "double counting" some ways for A to win. For example AAAA and AAAB. Both correspond to the game being stopped after AA (A winning two additional times).
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
They are basically looking at the worst case and working backwards.

If you want to go conditional I guess you could and you could show that you don't have as many possibilities. You definitely have a point since conditional probabilities change later probabilities (and thus frequencies).

In this case you should get a reduction not only in frequencies for A and B but also total numbers of combined frequencies.

It is a good point you raise.
 

Plato

MHF Helper
Aug 2006
22,492
8,653
Thank you for your answer. Unfortunately I still don't fully grasp the idea of looking at all 4 games-left combinations. In my mind it feels like we are "double counting" some ways for A to win. For example AAAA and AAAB. Both correspond to the game being stopped after AA (A winning two additional times).
I suspect your doubt comes from not knowing the history of this question. It is perhaps the most famous problem in the history of probability. It is know as The problem of Points, the question of interrupted games or division of the stakes. The question goes back to at least the eleventh century North Africa. Here is the setup: two tribes would come together on neutral ground to play a series of games. Each tribe puts up half the prize money, say 100 gold coins. Now the first side to win ten games takes the whole bucket of coins. But the games may be interrupted, called off, for a great many valid reasons.

If called off, when one side has eight wins and the other has seven, it seems that a reasonable division of the 'pot' could be agreed to; even if one side had nine and the other had two. However there did not seem to be any agreement on a split of say seven to three. The best mathematicians worked out various splits over the next four centuries. None of which quite worked. Here is the link to early solutions.

Now enter Pascal and Fermat. Fermat was the first to realize that the solution was in the games yet to be played. Pascal worked out the logic and calculation for the short cuts. It is all worked out in the link. Most History of Mathematics textbooks discuss this question. The are many places to find write-ups.
 
  • Like
Reactions: 1 person