It’s that time of year again—the NHL Stanley Cup Playoffs. Being Canadian, I’ve grown to have a great appreciation for the game, despite not being much of a sports buff. I play in an intramural league every now and then, seeing it as a great way to let off some steam. At the professional level, however, the game becomes a very different sport. I have a tremendous amount of respect for the abilities of these athletes and the speeds at which they play; it makes for some very entertaining hockey.

I’ve always been a bigger fan of playoff games than regular season games, but perhaps that’s just because I enjoy the “elimination” aspect of tournament-style games. It feels like there’s more at stake than your typical regular season game.

Of course, another interest with hockey—and any game for that matter—is guessing which team is going to win. While using statistics about teams to predict the outcome of a series obviously has its limitations, it is nonetheless an interesting exercise to actually calculate the probability of a particular team winning a best-of-x series.

The Problem

Suppose you were able to determine that between teams $A$ and $B$, team $A$ had probability $p$ of winning a single game against team $B$ (we’re going to assume that this probability does not change over the course of the series). In a best-of-x series, where $x = 2n - 1$, the first team to win $n$ games wins the series. From this definition, you might deduce that you can calculate the chance of team $A$ winning by simply finding $p^n$, hence finding the chance of team $A$ winning $n$ consecutive games. The problem is that you’d be incorrect, as team $A$ could just as well lose one or two (in fact, up to $n - 1$) games to team $B$ before eventually emerging victorious.

Thus in order to find the probability of winning, we need to consider all the possible orderings of wins and losses that result in team $A$ winning. If we let $k$ be the number of losses, then the number of possible orderings given $k$ losses would be $n + k - 1$ choose $k$, since we can order the $k$ losses amongst $n + k - 1$ games (-1 because the last game has to be a win for team $A$, so we don’t consider it in ordering the losses). If we sum over all the possible outcomes (i.e. team $A$ loses zero times all the way up to $n - 1$ times) and multiply by the respective probabilities of winning and losing, we have:

What Does This Have to Do With Programming?

At first glance this doesn’t seem terribly interesting, and for all practical purposes this formula is a perfectly valid solution. However, consider the situation when $n$ is large—our formula won’t be as easily calculable due to the implicit factorial in the choose operator (especially without a big number library). We could write an implementation of the choose operator that doesn’t use factorials, but this still won’t scale very well (try it). So let’s switch gears a bit, and see if there’s a different approach we can take.

Define $F(a, b)$ as the probability that team $A$ will win the series given that team $A$ needs to win $a$ more games and team $B$ needs to win $b$ more games. We want to calculate $F(n, n)$, or the probability of team $A$ winning the series. If we picture $(a, b)$ as a state, there are only two transitions out of this state: either $A$ wins with probability $p$ (we transition to $(a - 1, b)$), or $B$ wins with probability $1 - p$ (we transition to $(a, b - 1)$). There are two kinds of states where we know with certainty the probability of team $A$ winning: states where $A$ has already won ($(0, b)$ for all $b > 0$) and so $F(0, b) = 1$, or states where $B$ has already won ($(a, 0)$ for all $a > 0$) and so $F(a, 0) = 0$.

If dynamic programming hasn’t popped into your mind yet, hopefully mentioning it now helps click everything into place. We have two base cases, as well as a way to relate one state to two other states. Thus we can work from the end of the series where team $A$ has either won or lost, all the way back to the beginning of the series where neither team has won a game yet. This translates into a short Python program:

n = int(raw_input("Number of games needed to win series (n): "))
p = float(raw_input("Probability of team A winning a game (p): "))
F = [[0 for b in range(n + 1)] for a in range(n + 1)]

for b in range(1, n + 1):
    F[0][b] = 1

for a in range(1, n + 1):
    for b in range(1, n + 1):
        F[a][b] = p*F[a - 1][b] + (1 - p)*F[a][b - 1]

print F[n][n]

For large $n$, this approach scales much better, as it runs in $O(n^2)$ time, and doesn’t require any big number libraries—though you’ll probably lose a little bit of precision using standard floating point arithmetic.

So next time you find yourself betting on which team will win a best-of-999 game tournament, remember to use dynamic programming to find the answer faster than your friends!