Appendix B: Analysis of Unfinished Game Problem

The unfinished game problem (sometimes called the problem of points) grew out of a gambling question posed to Blaise Pascal. It involved a game between two players having the following rules

  1. Both players put the same amount into a pot that will go to the winner.
  2. The players agree on the number of points that will win the game.
  3. To win a point each player roles the dice and the one with the higher total wins the point. In case of a tie the players roll again.
  4. This continues until one of the players reaches the agreed upon number of points. This player then wins the pot.

The following question was presented to Blaise Pascal:

Suppose the game was interrupted before either player reached the point goal. How should the pot be fairly divided among the two players?

Pascal discussed this problem with another mathematician Pierre de Fermat in a series of letters and in the process formed the beginnings of probability theory. The two came up with different approaches to the question that led to the same answer. They both agreed that the past history was not important. All that mattered was the number of points each needed to win. Suppose that the first player needed $m$ points to win and the second player needed $n$ points to win. Both Pascal and Fermat agreed that one of the players would be guaranteed to win in $n+m-1$ additional rounds. To see this we must find the path to a win involving the most rounds. The longest path must eventually lead to the situation where both players need just 1 point to win. For one player must eventually reach the point where he needs 1 point to win. If the other player is not there yet, then there can be more rounds until that player needs 1 point to win. It requires m-1 wins from one player and n-1 wins from the other player or $m+n-2$ rounds to reach the place where both players need 1 point to win. It follows that one of the players will always win in $m+n-1$ rounds.

Fermat's Approach

Fermat's approach was to enumerate the various possibilities for $n+m-1$ additional rounds and then determine the number that represented a win for each player. Consider the case $m=2$ and $n=3$. Then one of them will surely win in $2+3-1=4$ rounds. If F represents a round win for the first player and S represents a round win for the second player, then the 16 possibilities for the four rounds are

FFFF
FFFS
FFSF
FSFF
SFFF
FFSS
FSFS
SFFS
FSSF
SFSF
SSFF
FSSS
SFSS
SSFS
SSSF
SSSS

The first player wins the pot in 11 of the 16 cases and the second player wins the pot in 5 of the 16 cases. Thus, it seems fair to give the first player $11/16$ of the pot and the second player $5/16$ of the pot. Of course the enumeration method of Fermat could be very tedious if $m$ and $n$ are large.

Some objected to extending the game to $n+m-1$ additional rounds when one of the players may win before that. Even though that is true, the full extension is convenient in order to guarantee that each of the outcomes has the same probability. In addition it was argued that the extension would not change the probability of either player winning. This can be seen for the case we just considered in the table below. This table lists the possible ways the first player could win along with the probability of each outcome (the probability of winning or losing a round is $\tfrac{1}{2}$).

Results Probability
$FF$ $1/4$
$FSF$ $1/8$
$SFF$ $1/8$
$FSSF$ $1/16$
$SFSF$ $1/16$
$SSFF$ $1/16$

The sum of these probabilities is $11/16$ which is what we obtained before. Later we will see a different approach by Pascal using recursion in which the logic behind the conclusion is clearer.

Pascal's Refinement of Fermat's Approach

Pascal came up with an alternate way to look at the enumeration method of Fermat using binomial coefficients and a triangle of numbers usually called Pascal's triangle (see appendix A). The number of rounds that contain two $F$'s is given by $\binom{4}{2}$. To see this we can describe each pair of $F$'s by describing their position in a set of four letters. Let $\{1,3\}$ represents an $F$ in the first and in the third position. We do not distinguish between $\{1,3\}$ and $\{3,1\}$. Clearly, the number of all such distinct positions is the number of combinations of the numbers 1, 2, 3, and 4 taken two at a time without respect to order or $\binom{4}{2}$. Similarly, $\binom{4}{3}$ is the number of rounds containing three $F$'s. It follows that the number of rounds containing at least two $F$'s is given by $\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=6+4+1=11$. This is the number we obtained previously by enumeration and counting.

Pascal's Recursion Method

Pascal came up with another method using recursion. Let $e(m,n)$ represent the share due the first player when he has $m$ points to a victory and the other player has $n$ points to a victory. Consider one more hypothetical round. After that round the share of the first player is either $e(m-1,n)$ or $e(m,n-1)$. Since both outcomes are equally likely, it seems fair to set

\begin{equation*} e(m,n)=\tfrac{1}{2} e(m-1,n)+\tfrac{1}{2} e(m,n-1). \end{equation*}

Consider the case where $m=2$ and $n=3$. We then have

\begin{align*} e(2,3)&=\tfrac{1}{2} e(1,3)+\tfrac{1}{2} e(2,2)\\ e(1,3)&=\tfrac{1}{2}e(0,3)+\tfrac{1}{2}e(1,2)\\ e(1,2)&=\tfrac{1}{2}e(0,2)+\tfrac{1}{2}e(1,1) \end{align*}

We start with the last equation and work our way back up to the first equation. Since $e(0,2)=1$ and $e(1,1)=1/2$, we have

\begin{equation*} e(1,2)=1/2+1/4=3/4. \end{equation*}

Since $e(0,3)=1$, it follows that

\begin{equation*} e(1,3)=1/2+3/8=7/8. \end{equation*}

Since $e(2,2)=1/2$, it now follows that

\begin{equation*} e(2,3)=7/16+1/4=11/16. \end{equation*}

This is the same answer that Fermat obtained. The quantity $e$ used by Pascal is what we would now call expected value. This was a new and important concept introduced by Pascal.

+++++