def get_expected_value(n_player1_wins, n_player2_wins, n_goal, p_player1_wins=0.5):
"""Return the probability that player 1 wins given that player 1 currently
has `n_player1_wins` and player 2 has `n_player2_wins` and that the game is won when they
reach `n_goal` number of wins. Optionally, we can change the probability that
player1 will win each game.
"""
if (n_player1_wins == n_goal):
return 1
elif (n_player2_wins == n_goal):
return 0
next1 = get_expected_value(n_player1_wins + 1, n_player2_wins, n_goal, p_player1_wins)
next2 = get_expected_value(n_player1_wins, n_player2_wins + 1, n_goal, p_player1_wins)
return (next1 * p_player1_wins) + (next2 * (1 - p_player1_wins))
trials = [
# n_player1_wins, n_player2_wins, n_goal
[7, 5, 10],
[17, 15, 20],
[2, 1, 3],
[5, 3, 6]
]
for n_player1_wins, n_player2_wins, n_goal in trials:
p_win = get_expected_value(n_player1_wins, n_player2_wins, n_goal)
print(f"| {n_player1_wins:7d} | {n_player2_wins:7d} | {n_goal:4d} | {p_win:.6f} |")4 Problem of Points
4.1 Overview
My brother once told me about a story from the early days of probability theory. It involved Blaise Pascal and Pierre de Fermat writing letters to each other in 1654 about how to settle a theoretical game that was prematurely ended before a winner could be declared. In one variation of the game, two gamblers have each wagered 32 pistoles (gold pieces) in a game where the first person to win 3 rounds wins. Each player has a 50/50 chance of winning each round, but the game is prematurely ended at a point where one player has 2 wins and the other has 1 win. The problem is: what is the fairest way to divide the 64 pistoles?
This question of how to divide the winnings of an unfinished game is called “the problem of points” or “the division of the stakes”. There is a good Wikipedia article on it here. The article mentions that a naive solution such as “divide the winnings based on the proportion each player has won so far” is flawed because a player who has won only a single game will get the entire reward if his opponent has not won at all. This will be true even if there are many games left to play such that the overall advantage the first player has won is negligible.
Intuitively, it is reasoned that the answer must be based on the number of games left to play and the relative advantage one player has over the other. For instance, in a game to 10, if the first player has won 7 times and the second player has won 5 times, the situation is essentially the same as a game to 20 where the first player has 17 and the second has 15. In each case the first player needs to win 5 games to win and the second player needs to win 7. These are the numbers that intuitively should matter and the division of winnings should be the same in both of these scenarios.
4.2 Solution
The solution can be found by exploring every possible way that the remaining games could be played out and seeing how many of these result in each player winning. This was the method that Fermat used in his solution. We can write a simple recursive function in Python to compute this:
This yields the following solutions for some of the cases we have discussed:
| P1 Wins | P2 Wins | Goal | Pr(P1 Wins All) |
|---|---|---|---|
| 7 | 5 | 10 | 0.773438 |
| 17 | 15 | 20 | 0.773438 |
| 2 | 1 | 3 | 0.750000 |
| 5 | 3 | 6 | 0.875000 |
In general, you can also use the following equation to find the probability of player 1 winning if player 1 has \(s_1\) rounds left to win and player 2 has \(s_2\) rounds left to win where \(p_1\) is the probability of player 1 winning a game and \(p_2\) is the probability of player 2 winning:
\[ \sum\limits_{k=s_1}^{s_1+s_2-1}{\frac{s_1+s_2-1}{k}(p_{1})^{k}(p_{2})^{s_1+s_2-1-k}} \]
4.3 Inferring a Player’s Advantage
In the classical form of the problem, we assume that each player has an equal chance of winning a round, but what if that was not the case? If we are playing to 1,000 and one player has won 750 times to the other player’s 100, should we infer that the first player is actually better than the second and more likely to win future matches?
This problem is essentially identical to the coin flipping problem when we suspected the coin was biased towards a certain outcome. We want to estimate the probability of each player winning future rounds based on their past performance. We can use the maximum likelihood estimate that simply uses the percentage of past wins as the predictor of future probabilities. We could also start with a Bayesian prior and update that based upon the observed data. In this case there are an infinite number of ways to setup the prior probabilities, and thus an infinite number of ways to solve this problem based upon not only the observed data but our prior expectations about how fairly matched the players are.
We won’t go through all the different variations of that again. Instead, we’ll just note that if we infer that the probability player 1 wins is equal to percentage of times he has won in the past (which is the maximum likelihood estimate), we get much different probabilities for the scenarios above:
print("| P1 Wins | P2 Wins | Goal | Pr(P1 Wins All) |")
print("|--------:|--------:|-----:|----------------:|")
for n_player1_wins, n_player2_wins, n_goal in trials:
p_win_once = n_player1_wins / (n_player1_wins + n_player2_wins)
p_win = get_expected_value(n_player1_wins, n_player2_wins, n_goal, p_win_once)
print(f"| {n_player1_wins:7d} | {n_player2_wins:7d} | {n_goal:4d} | {p_win:.6f} |")This outputs:
| P1 Wins | P2 Wins | Goal | Pr(P1 Wins All) |
|---|---|---|---|
| 7 | 5 | 10 | 0.886710 |
| 17 | 15 | 20 | 0.821448 |
| 2 | 1 | 3 | 0.888889 |
| 5 | 3 | 6 | 0.947266 |
4.4 Historical Notes
The actual text of the letters between Pascal and Fermat can be found here. There is also a good overview in the American Physical Society’s article “This Month in Physics History” subtitled “July 1654: Pascal’s Letters to Fermat on the Problem of Points”(Volume 18, Number 7, July 2009). This goes into more detail about how the problem was first proposed in 1494 by an Italian monk named Luca Paccioli. The question was being pondered in 1654 by an amateur mathematician who enjoyed gambling named Antoine Gombaud. It was Gombaud who asked his friend Pascal, who also had taken an interest in gambling, and it was this question that spurred the letters.
The original question that Paccioli asked concerned a game of “balla”, which requires six goals to win the game. Paccioli asked how the game should be settled if the game is stopped when one player has 5 goals and the other has 3. As noted above, there are a variety of statistically valid answers to this question.