# Homework Help: Dynamic Programming - World Series Probability Example

1. Mar 19, 2012

### dba

1. The problem statement, all variables and given/known data
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)

2. Relevant equations
p+q+r=1

3. 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.