World Series odds Consider two teams, A and B, playing a series of games until one of the teams wins n games. Assume that the probability of A winning a game is the same for each game and equal to p, and the probability of A losing a game is q = 1 - p. (Hence, there are no ties.) Let P (i, j ) be the probability of A winning the series if A needs i more games to win the series and B needs j more games to win the series.
a. Set up a recurrence relation for P (i, j ) that can be used by a dynamic programming algorithm.
b. Find the probability of team A winning a seven-game series if the probability of it winning a game is 0.4.
c. Write pseudocode of the dynamic programming algorithm for solving this problem and determine its time and space efficiencies.