2
$\begingroup$

I'm in a computer algorithms course and have a question about basic probability. My math background includes no more than discrete math and a little calculus, so this probability question left me completely stumped. I checked for similar questions but didn't see any. If this question has been answered already I apologize in advance but I don't even know the correct terms to search to find an answer.

The question goes like this:

Suppose you're playing a set of games and the first to win 10 games 
wins the set. Each player has an even chance (1/2) of winning a 
game. What is the probability that the first player will win if she 
has already won i games and the second player has already won j 
games? How do you calculate this for different values of i and j? 

Please word the explanation for a non-maths student. I need to provide a recursive formulation for a function that computes this probability then solve it using dynamic programming. No worries on recursion or dynamic programming. I can solve that once I understand how to solve for probability.

$\endgroup$
5
  • $\begingroup$ This problem occupied some of the finest minds of the seventeeth century. See en.wikipedia.org/wiki/Gambler's_ruin $\endgroup$ Oct 20, 2014 at 12:09
  • $\begingroup$ Oh shoot, I misread the OP's rule. (I would delete my previous comment, but for some reason the delete option is unavailable to me.) $\endgroup$ Oct 20, 2014 at 12:11
  • $\begingroup$ No worries, I thought it didn't look quite right because gambler's ruin states that "two players begin with fixed stakes, transferring points until one or the other is 'ruined' by getting to zero points." Nothing is transferred here. $\endgroup$
    – MNRC
    Oct 20, 2014 at 12:15
  • 1
    $\begingroup$ Great replies, now I will try to understand the answers! $\endgroup$
    – MNRC
    Oct 20, 2014 at 12:17
  • $\begingroup$ @yulia-v I'll check the 'accept answer' once I figure out your explanations. I'd like to upvote for both answers but just joined this site and don't have enough reputation points yet :( Thanks for posting the python code! $\endgroup$
    – MNRC
    Oct 20, 2014 at 12:51

2 Answers 2

3
$\begingroup$

You can solve it using a backwards iteration.

Let $P(i,j)$ be the probability that the first player wins given current score, $i$ and $j$ for the first and the second teams respectively.

Your initial condition is: $P(i,10)=0 \; \forall i \in \{0,\dots,9\}$ and $P(10,j)=1 \; \forall j \in \{0,\dots,9\}$.

The next step would be to determine $P(9,j)$ and $P(i,9)$ for $i,j \in \{0,\dots,9\}$. We have $$P(9,j)=\frac{1}{2} P(10,j) + \frac{1}{2} P(9,j+1)$$ and $$P(i,9)=\frac{1}{2} P(i,10) + \frac{1}{2} P(i+1,9)$$

This comes from the fact that

$$P(i,j)=\frac{1}{2} P(i+1,j) + \frac{1}{2} P(i,j+1)$$

This is because, once you have outcome $(i,j)$, the next game can be either won by the first team with probability $\frac{1}{2}$, in which case the score moves to $(i+1,j)$ and the probability that the first team wins the series of games becomes $P(i+1,j)$, or by the second one, in which case the score becomes $(i,j+1)$ and the probability that the first team wins the series of games becomes $P(i,j+1)$.

Going backwards wrt $i$ and $j$, we will find these probabilities for all arguments.

Code in Python is below. Please let me know if you have any questions. Note that result is preformatted to copy it into LaTeX.

def GetFootballProbabilities(probabiliryFirstTeamWinsOneGame, numberWins):
    probabilities = [[-1 for _ in range(numberWins+1)] for _ in range(numberWins+1)]
    for smallIndex in range(numberWins-1, -1, -1):
        probabilities[numberWins][smallIndex] = 1.0
        probabilities[smallIndex][numberWins] = 0.0  
    for bigIndex in range(numberWins-1, -1, -1):
        probabilities[bigIndex][bigIndex] = (probabiliryFirstTeamWinsOneGame * probabilities[bigIndex+1][bigIndex]
            + (1.0-probabiliryFirstTeamWinsOneGame) * probabilities[bigIndex][bigIndex+1])
        for smallIndex in range(bigIndex-1, -1, -1):
            print smallIndex, bigIndex
            probabilities[smallIndex][bigIndex] = (probabiliryFirstTeamWinsOneGame * probabilities[smallIndex+1][bigIndex]
                + (1.0-probabiliryFirstTeamWinsOneGame) * probabilities[smallIndex][bigIndex+1])                        
            probabilities[bigIndex][smallIndex] = (probabiliryFirstTeamWinsOneGame * probabilities[bigIndex+1][smallIndex]
                + (1.0-probabiliryFirstTeamWinsOneGame) * probabilities[bigIndex][smallIndex+1])

    return probabilities

if __name__ == '__main__':
    probabilities = GetFootballProbabilities(probabiliryFirstTeamWinsOneGame = 0.5, numberWins = 10)
    print '{r|' + '|'.join('l' for _ in range(11)) + '} \hline'
    print '&' + '&'.join(str(r) + 'W' for r in range(11)) + '\\\\ \hline'
    i=0
    for row in probabilities:
        print str(i) + 'W&' + '&'.join(("%.3f" % r) for r in row) + '\\\\ \hline'
        i=i+1

Resulting table of probabilities is

$$\begin{array} {r|l|l|l|l|l|l|l|l|l|l|l} \hline &0W&1W&2W&3W&4W&5W&6W&7W&8W&9W&10W\\ \hline 0W&0.500&0.407&0.315&0.227&0.151&0.090&0.046&0.019&0.006&0.001&0.000\\ \hline 1W&0.593&0.500&0.402&0.304&0.212&0.133&0.073&0.033&0.011&0.002&0.000\\ \hline 2W&0.685&0.598&0.500&0.395&0.291&0.194&0.113&0.055&0.020&0.004&0.000\\ \hline 3W&0.773&0.696&0.605&0.500&0.387&0.274&0.172&0.090&0.035&0.008&0.000\\ \hline 4W&0.849&0.788&0.709&0.613&0.500&0.377&0.254&0.145&0.062&0.016&0.000\\ \hline 5W&0.910&0.867&0.806&0.726&0.623&0.500&0.363&0.227&0.109&0.031&0.000\\ \hline 6W&0.954&0.927&0.887&0.828&0.746&0.637&0.500&0.344&0.188&0.062&0.000\\ \hline 7W&0.981&0.967&0.945&0.910&0.855&0.773&0.656&0.500&0.312&0.125&0.000\\ \hline 8W&0.994&0.989&0.980&0.965&0.938&0.891&0.812&0.688&0.500&0.250&0.000\\ \hline 9W&0.999&0.998&0.996&0.992&0.984&0.969&0.938&0.875&0.750&0.500&0.000\\ \hline 10W&1.000&1.000&1.000&1.000&1.000&1.000&1.000&1.000&1.000&1.000&-\\ \hline \end{array}$$

$\endgroup$
8
  • $\begingroup$ I this question again and someone said the probability of winning is always 1/2 because winning a game is independent of winning a previous one. So, if player A has won 5 games and player B has won 7 games, the probability of player A winning the next game is still 1/2. Do you think this is right? $\endgroup$
    – MNRC
    Oct 21, 2014 at 8:16
  • $\begingroup$ @MNRC: yes, this is right, according to the statement of the problem. It is similar to tossing the coin: regardless if the number of heads and tails you have observed in the past, the probability that the next flip yields tails is 1/2. $\endgroup$
    – Yulia V
    Oct 21, 2014 at 8:56
  • $\begingroup$ Would this mean that there is nothing to solve for and that each calculation of P(i, j) is just 1/2 no matter what value i or j is? If this is the case, I am not sure what my professor is looking for. We are supposed to use dynamic programming to solve this problem, which is just to find a recursive solution and save it into a table so the program can look up that value and use it to solve another subproblem. But it looks like every value of the table would be 1/2, so there is nothing to save to a table. $\endgroup$
    – MNRC
    Oct 21, 2014 at 9:17
  • 1
    $\begingroup$ @MNRC: no, it would not, only the main diagonal values will be 1/2. Our boundary conditions are not symmetric (1 in top row, 0 in right column), thus the resulting table won't be symmetric. You can run the script and see for yourself, or I can run it for you if you need to see the exact numbers. $\endgroup$
    – Yulia V
    Oct 21, 2014 at 9:23
  • $\begingroup$ Oh, btw, math.stackexchange says I need 15 reputation points to upvote an answer and I only have 8 right now :/ Otherwise, I'd upvote your answer. $\endgroup$
    – MNRC
    Oct 21, 2014 at 9:23
3
$\begingroup$

Let $P(i, j)$ be the probability that plyer $1$ wins the set if he's already won $i$ games, and player $2$ has won $j$ games.

We have $$ \cases{P(10, j) = 1 & for $0\leq j < 10$\\ P(i, 10) = 0 & for $0\leq i < 10$\\ P(i, j) = \frac{1}{2}P(i+1, j) + \frac{1}{2} P(i, j+1) & for $0 \leq i, j < 10$} $$ Of course, $P(10, 10)$ is absurd.

The reason is the following: For $P(10, j)$ and $P(i, 10)$, the set has been decided, so those are clear. For any other game state $(i, j)$, there is a $50\%$ probability that player $1$ will lose the next game, and from there, the probability that he'll win is $P(i, j+1)$. Therefore the probability that he'll win the whole set from the state $(i, j)$ gets the contribution $\frac{1}{2}P(i, j+1)$. Same reasoning for the other term.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .