Probability of winning a competition K games best of series of N games

Question

Consider a 'best of 5' series in sports/competition where the first team to win 3 games wins the series. So N=5, K=3. Where probability w = p(team A winning game) and l = p(team A losing game). Assume these probabilities do not change during the series.

When I first thought about this I mistakenly tried adding the individual probabilities of winning 3/3, 3/4, and 3/5 games:

wrong = function(w) {      
  p = dbinom(3,3,w) + dbinom(3,4,w) + dbinom(3,5,w)       
  return(p)
}

wrong(.9)
# 1.0935

Obviously, the issue is there is redundancy since 3 wins in a row, W-W-W renders any game 4 and 5 results obsolete. i.e. W-W-W-L-W and W-W-W-W-L aren't possible.

After removing redundancies these are the possible permutations:

win = function(w) {
  l = 1-w
  p = w*w*w + 
    w*w*l*w + w*l*w*w + l*w*w*w + 
    l*l*w*w*w+ l*w*l*w*w+ l*w*w*l*w+  
    w*l*l*w*w+ w*l*w*l*w+
    w*w*l*l*w

  return(p)
}

win(.9)
# 0.99144

win(.9) + win(.1)
# 1

Manually typing the permutations gets out of hand quickly with longer series i.e. winning a N = 7 game series, 9 game series, etc. Generally, how does wrong() function need to be modified to get the correct probability?

Answer 1

You can use the negative binomial distribution for this problem.

If X is distributed as NegBin(n, w), then X is the number of games the player loses before winning n of them, if the probability of winning any given game is w.

So, dnbinom(q = 2, size = 2, prob = w) is the probability that the player loses a total of 2 games before winning 2.

Then, pnbinom(q = 2, size = 3, prob = w) is the probability that the player loses 2 or less before they win 3 games. This is equal to the probability of winning a 3 out of 5 series.

In general, the probability of winning a best n-out-of-(2n-1) series can be calculated with pnbinom(q = n-1, size = n, prob = w).

## w is the probability of winning any individual game
## k is the number of wins needed to win the series (3 in a best 3 of 5 series)
win <- function(w, k){
  return (pnbinom(q = k - 1, size = k, prob = w))
}

win(0.9, 3)
## 0.99144

Answer 2

This is interesting. Let's demonstrate using n = 3 where it takes 2 wins to be the winner. We can first determine which combinations are available

n = 3L
lst = replicate(n, 0:1, simplify = FALSE)
combos = do.call(expand.grid, lst)
combos

  Var1 Var2 Var3
1    0    0    0
2    1    0    0
3    0    1    0
4    1    1    0
5    0    0    1
6    1    0    1
7    0    1    1
8    1    1    1

As you noted, some of these combinations are not possible. We are specifically interested when the rowSums() are equal to 2. Using this we can figure out which combinations are actually possible.

possible_combos = combos[rowSums(combos) == ceiling(n / 2), ]
possible_combos

  Var1 Var2 Var3
4    1    1    0
6    1    0    1
7    0    1    1

Our last step is to calculate each contribution from our possible contributions. We know that w^2 will be in each calculation. The l part is more complicated. In our first possible combination, the l contributes nothing. We can use max.col(..., ties.method = "last") to figure how many ls occurred:

losses = max.col(possible_combos, ties.method = "last") - ceiling(n / 2)
losses
# [1] 0 1 1

w = 0.9
l = 1 - w
wins_p = w ^ ceiling(n / 2)
losses_p = ifelse(losses == 0L, 1, l ^ losses)

p = sum(wins_p * losses_p)
p
# [1] 0.972

To generalize this, we can use this as a function based on n and w:

right = function(n, w) {
  lst = replicate(n, 0:1, simplify = FALSE)
  combos = do.call(expand.grid, lst)
  possible_combos = combos[rowSums(combos) == ceiling(n / 2), ]
  losses = max.col(possible_combos, ties.method = "last") - ceiling(n / 2)

  l = 1 - w
  wins_p = w ^ ceiling(n / 2)
  losses_p = ifelse(losses == 0L, 1, l ^ losses)

  sum(wins_p * losses_p)
}

right(5, 0.9)
# [1] 0.99144
right(5, 0.9) + right(5, 0.1)
# [1] 1

Answer 3

Actually you are almost there, but you should be aware of the cases with four and five games to win.

win <- function(w) dbinom(3,3,w)+w*dbinom(2,3,w) + w*dbinom(2,4,w)

or a compact solution

win <- function(w) w*sum(mapply(dbinom,2,2:4,w))

such that

> win(0.9)
[1] 0.99144

Explanation: Given that the number of games needed to win the serial depends on the last win:

• If 3 games are needed: the first two should both wins, such that the prob. is w**3 (equivalently dbinom(3,3,w) or dbinom(2,2,w)*w)

• If 4 games are needed: among the previous three games there should be 2 wins and 1 loss, such that the prob. is choose(4,2)*w**2*(1-w)*w (equivalently dbinom(2,4,w)*w)

• If 5 games are needed: among previous four games there should both 2 wins and 2 losses, such that the prob. is choose(4,2)*w**2*(1-w)**2*w (equivalently dbinom(2,4,w)*w)

---

Update: Generalization of win

With respect to any N (either even or odd), a generalized function win can be defined like below

win <- function(w, N) w*sum(mapply(dbinom,ceiling((N-1)/2),ceiling((N-1)/2):(N-1),w))

However, above is not as efficient for large Ns. Instead, the negative binomial distribution method mentioned by @RyanFrost is preferred for cases with large Ns, i.e.,

win <- function(w, N) pnbinom(floor((N-1)/2), ceiling((N+1)/2), w)

Example

> win(0.9,5) # needs at 3 wins out of 5 games
[1] 0.99144

> win(0.9,6) # needs at 4 wins out of 6 games
[1] 0.98415

Answer 4

It is a binomial distribution:

dbinom(3,5,0.9) + dbinom(4,5,0.9)+dbinom(5,5,0.9) = 0.99144

The reason goes like this, you just need to think about the total space, even if there are already 3 wins or 4 wins, let's imagine the event goes on and we can write the possible events to include as:

w.w.w : w.w.w.w.k , w.w.w.k.k , w.w.w.k.w, w.w.w.w,w
w.w.l.w : w.w.l.w.l, w.w.w.l.w
l.w.w.w : l.w.w.w.1 , l.w.w.w.w

And so on..

And those that have written as containing 3 wins for example (w.w.l.w.l) will be part of 5 choose 3 in a binomial.

Out of the total space of W/L over 5 events, what we need are 3 wins, 4 wins and 5 wins to include all the events that can result in the team winning (even though in real life, the 4th or 5th match will not occur)

Answer 5

Here is a function win that computes the probability to win k out of n games with a probability to win each game w. It implements the idea of this Math.SE post.

win <- function(w, n = 5, k = 3){
  loose <- function(w, n, k){
    l <- 1 - w
    m <- n - k
    s <- seq_len(n - 1)[-seq_len(m - 1)]
    ch <- sapply(s, function(x) choose(x, m))
    w <- w^(seq_along(s) - 1)
    l^m * sum(w*ch)
  }
  if(k >= ceiling(n / 2)){
    1 - loose(w, n, k)*(1 - w)
  }else{
    stop("a minority cannot win.")
  }
}
win(0.9)
#[1] 0.99144

win(0.1)
#[1] 0.00856

win(0.9) + win(0.1)
#[1] 1

Answer 6

What your're asking is a simple math problem. I'll try to explain the math step by step then we'll write our codes with respect of that.

Math

Combination
In mathematics, a combination is a selection of items from a collection and is defined as follows.



Where ! is the factorial operator. For example let's assume we have four rounds and you want to select three wins (or one loose). We have:



Which are: w-w-w-l, w-w-l-w, w-l-w-w, l-w-w-w
But as you mentioned, w-w-w-l is not acceptable because the game is done when 3 wins are accomplished! So take a good look at this point:

If our rounds takes more than 3 (best of 5), the last one must be win if winning probability calculation is desired!

So to correct my calculations I should first select the last round as a win and select 2 other spots (from remaining spots) for winning. Or



And if we show winning probability with w and loosing with l the probability of this state to be happened is

Javascript

Now that you know the concept, let's begin coding!
First I need a function to calculate factorial of n (n!).

let f = (n)=>
{
    let o = 1;
    for(i=1; i<=n; i++)
    {
        o *= i;
    }
    return o;
}

To understand the procedure better, I'll write my codes step by step. So the next step is to define the combination function.

let c = (n,r)=>
{
    return f(n)/(f(r) * f(n-r));
}

And now it's time to calculate r wins probability in a p round game with win probability of w.

let _w = (p,r,w)=>
{
    let o = 1;
    // Selection of win positions
    o *= c(1,1) * c(p-1,r-1);
    // Calculation probability
    o *= Math.pow(w, r) * Math.pow(1-w, p-r);

    return o;
}

Now we are ready to make the BO (Best Of) function with N rounds and K wins.

let BO = (N, K, w)=>
{
    // P is what we wish to find!
    let P = 0;
    for (j=K; j<=N; j++)
    {
        P += _w(j, K, w);
    }
    return P;
}

And some examples:

console.log(BO(5,3,0.9)); // 0.9914400000000001
console.log(BO(7,4,0.9)); // 0.997272
console.log(BO(9,5,0.9)); // 0.99910908