# Probability — How many games to decide the best-of-N series

Discussion in 'Physics & Math' started by rpenner, Jun 5, 2017.

1. ### rpennerFully WiredValued Senior Member

Messages:
4,833
Let N be an odd, positive number. A best-of-N series of games is played until one team has won a majority of the N maximum possible games in the series. Let p be the probability that team A wins any such game. In a series of up to N games, where each game is won either by A or B (no ties), what is the expectation for how many games will be played to decide the best-of-N series? What is the distribution of number of games?

This is a generalization of the Riddler Express problem posted here:

https://fivethirtyeight.com/features/how-much-should-you-bid-for-that-painting/

Messages:
8,124
N

5. ### rpennerFully WiredValued Senior Member

Messages:
4,833
Expansion of $(p+(1-p))^n$
$\begin{array}{c} & & & & & & & 1 & & & & & & & \\ & & & & & & p & & (1-p) & & & & & & \\ & & & & & p^2 & & 2 p (1-p) & & (1-p)^2 & & & & & \\ & & & & p^3 & & 3 p^2 (1-p) & & 3 p (1-p)^2 & & (1-p)^3 & & & & \\ & & & p^4 & & 4 p^3 (1-p) & & 6 p^2 (1-p)^2 & & 4 p (1-p)^3 & & (1-p)^4 & & & \\ & & p^5 & & 5 p^4 (1-p) && 10 p^3 (1-p)^2 && 10 p^2 (1-p)^3 && 5 p (1-p)^4 && (1-p)^5 & & \\ & p^6 && 6 p^5 (1-p) & & 15 p^4 (1-p)^2 && 20 p^3 (1-p)^3 && 15 p^2 (1-p)^4 && 6 p (1-p)^5 && (1-p)^6 & \\ p^7 & & 7 p^6 (1-p) & & 21 p^5 (1-p)^2 & & 35 p^4 (1-p)^3 & & 35 p^3 (1-p)^4 & & 21 p^2 (1-p)^5 & & 7 p (1-p)^6 & & (1-p)^7 \end{array}$
A wins and B wins after n games.
$\begin{array}{c} & & & & & & & (0,0) & & & & & & & \\ & & & & & & (1,0) & & (0,1) & & & & & & \\ & & & & & (2,0) & & (1,1) & & (0,2) & & & & & \\ & & & & (3,0) & & (2,1) & & (1,2) & & (0,3) & & & & \\ & & & (4,0) & & (3,1) & & (2,2) & & (1,3) & & (0, 4) & & & \\ & & (5,0) & & (4,1) && (3,2) && (2,3) && (1,4) && (0,5) & & \\ & (6,0) && (5,1) & & (4,2) && (3,3) && (2,4) && (1,5) && (0,6) & \\ (7,0) & & (6,1) & & (5,2) & & (4,3) & & (3,4) & & (2,5) & & (1,6) & & (0,7) \end{array}$
Game which decides best-of-N series:
$\begin{array}{c} & & & & & & & N/A & & & & & & & \\ & & & & & & 1 & & 1 & & & & & & \\ & & & & & 3 & & N/A & & 3 & & & & & \\ & & & & 5 & & 3 & & 3 & & 5 & & & & \\ & & & 7 & & 5 & & N/A & & 5 & & 7 & & & \\ & & 9 & & 7 && 5 && 5 && 7 && 9 & & \\ & 11 && 9 & & 7 && N/A && 7 && 9 && 11 & \\ 13 & & 11 & & 9 & & 7 & & 7 & & 9 & & 11 & & 13 \end{array}$

7. ### rpennerFully WiredValued Senior Member

Messages:
4,833
Thus to decide a best-of-1 series, exactly one game is played taking us from state (0,0) to (1,0) with probability p or to state(0,1) with probability (1-p).
To decide a best-of-3 series, after 2 games we have state (2,0) with probability p^2, state (1,1) with probability 2 p (1-p) or state (0,2) with probability (1-p)^2. If the game isn't decided after 2 games, the third will decide it.
So the distribution is 2 games with probability p^2 + (1-p)^2 = 1 - 2p + 2p^2 and 3 games with probability 2 p - 2 p^2.
The expectation is 2 + 2 p - 2 p^2 games.

Generalizing, the expectation is the sum of all expansion terms corresponding to undecided states.
$E = \sum_{i=0}^{2i -1 < N} \sum_{j=0}^{2j -1 < N} { {i+j} \choose i } p^i (1-p)^j$

8. ### SeattleValued Senior Member

Messages:
8,124
So, the Warriors right?

9. ### rpennerFully WiredValued Senior Member

Messages:
4,833
Let $n = \frac{N-1}{2} \geq 0$
Then our expectation value goes like this:
$E = \sum_{i=0}^{2i -1 < N} \sum_{j=0}^{2j -1 < N} { {i+j} \choose i } p^i (1-p)^j = \sum_{i=0}^{n} \sum_{j=0}^{n} { {i+j} \choose i } p^i (1-p)^j = (n+1) \sum_{k=0}^{n} \frac{1}{k+1} { {2k} \choose k } \left( p (1-p) \right)^k$

For p = 1/2 this is approximately $E \approx 2(n + 1) - \frac{8 n + 3}{4 \sqrt{\pi n} }$ for large n
For p = 3/5 this is approximately $E \approx \frac{5}{3}(n+1)$ for large n
For p = 7/10 this is approximately $E \approx \frac{10}{7}(n+1)$ for large n

10. ### SeattleValued Senior Member

Messages:
8,124
Is this a blog?

11. ### TheFroggerBannedValued Senior Member

Messages:
2,175
...or how many possible games are there? In a game of chess we may number each possible game, and allow the computer to choose which game to play.

12. ### The GodValued Senior Member

Messages:
3,546
Let N be the positive odd number, so the winning player has to win (N+1)/2 games. And the number of games required to be played can be anything between (N+1)/2 to N depending on the strength of players.

Unless the relative strength (or some kind of past statistics of games played between these players) is given, finding out the probability as asked in the OP, is a futile exercise.

13. ### rpennerFully WiredValued Senior Member

Messages:
4,833
But it is given in the OP as "p". The expectation takes the largest value for p = 1/2, because as post #6 shows the expected number of games played is a polynomial in $p(1-p)$ (with maximum value for p=1/2) with all positive coefficients.

Last edited: Jun 13, 2017
14. ### The GodValued Senior Member

Messages:
3,546
Sorry, missed that.
Of course it will stretch to maximum when both players are at par strength.

15. ### Confused2Registered Senior Member

Messages:
609
For a best of 5 series
With a 50-50 probability of winning (like tossing a coin)
For the first 4 games
LSB is the first game
0000<play 3 games
0001<play 4 games
0010<play 4 games
0011<play 5 games
0100<play 4 games
0101<play 5 games
0110<play 5 games
0111<Play 3 games
1000<Not played
1001<play 5 games
1010<play 5 games
1011<play 4 games
1100<play 5 games
1101<play 4 games
1110<play 4 games
1111<Not played

I'm not sure where to go from here, maybe take all the outcomes and divide them by the sum of possible outcomes. Or crash.
Crashing...
FWIW I reckon...
Expect a winner after 3 games on 6 occasions (18)
Expect a winner after 4 games on 6 occasions (24)
Expect a winner after 5 games on 6 occasions (36)

16. ### Confused2Registered Senior Member

Messages:
609
Continuing the above post but ignoring the last bit
I reckon...
In a best of 5 series with equally matched teams.
2 end after 3 games with 1/7 chance of victor being declared
6 end after 4 games with 3/7 chance of victor being declared
6 end after 5 games with 3/7 chance of victor being declared
So the winner will normally (4/7) be declared without
playing all 5 possible matches.

17. ### TheFroggerBannedValued Senior Member

Messages:
2,175
You'll just have to play the games to discover the answer.