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

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

  1. rpenner Fully Wired Staff 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/
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Seattle Valued Senior Member

    Messages:
    2,200
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. rpenner Fully Wired Staff 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} \)
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. rpenner Fully Wired Staff 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. Seattle Valued Senior Member

    Messages:
    2,200
    So, the Warriors right?
     
  9. rpenner Fully Wired Staff 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. Seattle Valued Senior Member

    Messages:
    2,200
    Is this a blog?
     
  11. Counter Registered Senior Member

    Messages:
    431
    ...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 God Valued 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. rpenner Fully Wired Staff 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 God Valued Senior Member

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

    Messages:
    424
    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. Confused2 Registered Senior Member

    Messages:
    424
    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. Counter Registered Senior Member

    Messages:
    431
    You'll just have to play the games to discover the answer.
     

Share This Page