Cubs Win-Strings and a Risk-Free Bet

The Riddler for September 30, 2016, in the autumn the Cubs finally won it all. The Express counts the paths to a title; the Classic builds a sequence of even bets that hedges a championship.

Riddler Express

The Cubs’ road to the World Series title is a best-of-five series followed by two best-of-seven series. How many unique strings of wins and losses could the Cubs assemble if they make their way through the playoffs and win the championship? For example, one possible string is WWWWWWWWWWW (three straight sweeps); another is WWWWWWWLLLWWWW.

The Riddler, FiveThirtyEight, September 30, 2016(original post)

Solution

The three series are independent stretches of the string, and a won series always ends on a win, so we can count each series’ winning strings on its own and multiply.

Take a best-of-$2k{-}1$ series that the Cubs win, needing $k$ wins. The clinching win is the last game played, so it is fixed; what varies is how the earlier games fall. If the series lasts $n$ games (with $k \le n \le 2k-1$), the first $n-1$ games hold exactly $k-1$ wins among them, in any order, which is $\binom{n-1}{k-1}$ strings. Summing over the possible lengths, $$\#\{\text{winning strings}\} = \sum_{n=k}^{2k-1}\binom{n-1}{k-1}.$$ For the best-of-five ($k=3$): $\binom{2}{2}+\binom{3}{2}+\binom{4}{2} = 1+3+6 = 10$. For each best-of-seven ($k=4$): $\binom{3}{3}+\binom{4}{3}+\binom{5}{3}+\binom{6}{3} = 1+4+10+20 = 35$. The full run is one best-of-five and two best-of-sevens, so $$10 \times 35 \times 35 = \boxed{12{,}250}$$ distinct championship strings.

The computation

Encode the rule directly: generate every sequence of wins and losses for each series, keep those the Cubs win (reaching $k$ wins, never $k$ losses), and multiply the counts. This counts the strings without using the binomial formula.

from itertools import product
def winning_strings(k):                 # best-of-(2k-1) the Cubs win
    total = 0
    for n in range(k, 2*k):             # series length n
        for s in product("WL", repeat=n):
            w = s.count("W"); l = s.count("L")
            if w == k and l < k and s[-1] == "W":   # clinch on the last game
                # and no earlier prefix already reached k wins
                if all(s[:i].count("W") < k for i in range(n)):
                    total += 1
    return total
b5, b7 = winning_strings(3), winning_strings(4)
print("best-of-5:", b5, " best-of-7:", b7, " product:", b5 * b7 * b7)
# best-of-5: 10  best-of-7: 35  product: 12250

Riddler Classic

You are a gambler and a Cubs fan. The Cubs play a seven-game series, first to four wins. Your bookie takes any even-odds bet on any individual game. Can you construct a series of bets so that, whatever happens, you win $100 if the Cubs take the series and lose $100 if the Red Sox take it?

The Riddler, FiveThirtyEight, September 30, 2016(original post)

Solution

Yes. The trick is to decide, for every possible score, exactly how much wealth you want to be holding when you walk into that game, and then let each bet carry you between those targets. Work backwards from the end.

Let $W(a,b)$ be the bankroll you aim to hold entering a game when the Cubs have $a$ wins and the Red Sox have $b$. The targets at the end of the series are forced: if the Cubs have reached four wins you must be holding $+\$100$, and if the Red Sox have, $-\$100$: $$W(4,b) = +100, \qquad W(a,4) = -100 .$$ Now suppose you enter a game at $(a,b)$ holding $W(a,b)$ and bet $x$ on the Cubs at even odds. A Cubs win leaves you with $W(a,b)+x$, and you want that to equal next game’s target $W(a+1,b)$; a Cubs loss leaves $W(a,b)-x$, which should equal $W(a,b+1)$. Those two demands solve at once: $$\begin{aligned} W(a,b) &= \tfrac12\bigl(W(a+1,b) + W(a,b+1)\bigr),\\ x(a,b) &= \tfrac12\bigl(W(a+1,b) - W(a,b+1)\bigr). \end{aligned}$$ Each entering target is the average of the two it can lead to, and the bet is half their gap. Rolling this average back from the $\pm 100$ edges, the start of the series sits exactly at the midpoint, $$W(0,0) = 0,$$ so you stake nothing of your own and end at $\pm\$100$. The opening wager is $$x(0,0) = \frac{W(1,0) - W(0,1)}{2} = \boxed{\$31.25},$$ and every later bet follows from the same averaging. The full schedule of opening-through-final bets, in dollars, is $$\begin{array}{c|cccc} a \backslash b & 0 & 1 & 2 & 3\\\hline 0 & 31.25 & 31.25 & 25.00 & 12.50\\ 1 & 31.25 & 37.50 & 37.50 & 25.00\\ 2 & 25.00 & 37.50 & 50.00 & 50.00\\ 3 & 12.50 & 25.00 & 50.00 & 100.00 \end{array}$$ The pattern is intuitive once you see it: bet more as the series nears its end, and more when the score is close, because those are the games that swing the title hardest. The decisive game seven at $3$-$3$ is a flat $\$100$ bet, the whole prize on one coin.

The computation

Encode the guarantee, not the formula: build the bets by the backward averaging, then play out every possible series and check the final bankroll is exactly $+\$100$ on a Cubs title and $-\$100$ on a Red Sox one.

from functools import lru_cache
@lru_cache(None)
def W(a, b):
    if a == 4: return 100.0
    if b == 4: return -100.0
    return (W(a+1, b) + W(a, b+1)) / 2
def bet(a, b): return (W(a+1, b) - W(a, b+1)) / 2

paths = [0]; fails = [0]
def play(a, b, bankroll):                 # recurse over every game outcome
    if a == 4 or b == 4:
        paths[0] += 1
        target = 100.0 if a == 4 else -100.0
        fails[0] += abs(bankroll - target) > 1e-9
        return
    x = bet(a, b)
    play(a+1, b, bankroll + x)            # Cubs win this game
    play(a, b+1, bankroll - x)            # Red Sox win this game
play(0, 0, 0.0)
print("opening bet :", bet(0, 0))
print("series paths:", paths[0], " mispaid:", fails[0])
# opening bet : 31.25
# series paths: 70  mispaid: 0