Dynamic Programming - World Series Probability Example

[dba]

Homework Statement

Two teams A and B play at most 2n-1 games. For any match there is a constant probability p that A wins and a constant probability q=1-p that B wins.
P(i,j) is the probability that A wins; A needs i more wins to win and b needs j more wins to win.
At the begin the probability for team A to win is P(n,n) and both teams need n wins to win.
If A needs 0 more wins, a already won, P(0,j). The same for B P(i,0)

So we can write
P(i,j) = pP(i-1,j) + qP(i, j-1)

Now we need to add a probability r for the game to be a tie (it counts as a win for nobody)

Homework Equations

p+q+r=1

The Attempt at a Solution

Let k be the number of games the teams still need to play. If we have n=4 we would have 8 games to play i+j=k
P(i,j) = pP(i-1,j) + qP(i, j-1)
So after one game played we still have 7 games. i-1+j =k-1 and i+j-1 = k-1
I am not sure how to implement r so that I get my k-1=7
P(i,j) = pP(i-1,j) + qP(i, j-1) + rP(i,j)
because P(i,j) would still result in k not in k-1

Thanks for any hint.

 

[KataKoniK]

Thank you for your question. It seems like you are on the right track with your solution. To include the probability of a tie, we can modify the equation as follows:

P(i,j) = pP(i-1,j) + qP(i, j-1) + rP(i-1,j-1)

This accounts for the possibility of a tie in both teams needing to win one less game. In your example with n=4, we would have k-1=7 games left to play, and the equation would become:

P(i,j) = pP(i-1,j) + qP(i, j-1) + rP(i-1,j-1)
= pP(i-2,j) + qP(i-1, j-1) + rP(i-2,j-1) + pP(i-1,j-1) + qP(i, j-2) + rP(i-1,j-2) + rP(i-2,j-2)

This takes into account all possible scenarios for the remaining games, including ties. I hope this helps. Good luck with your research!