Book Proofs

Define our quantity of interest:
\[
a_{n,m} = \left\{\begin{array}{l}
\text{Maximum guaranteed winnings assuming there}\\
\text{are $n$ games remaining, we know our team}\\
\text{will win exactly $m$ of them, and we start with \$1.}
\end{array}\right\}
\]Also let $k_{n,m}$ be the fraction of our money we should bet that achieves the maximum guaranteed winnings. We use negative bets to indicate that we are betting for the other team to win. To illustrate, if we currently have $x$ dollars, we can bet any fraction $-1 \leq k \leq 1$, and the possible cases are:

• If our team wins, we gain $k x$, so we now have $(1+k)x$.
• If our team loses, we lose $k x$, so we now have $(1-k)x$.

Due to the homogeneous nature of the problem, if we were to start with $x$ dollars instead, then our winnings would just be $x \cdot a_{n,m}$.

Let’s start by looking at some edge cases.

• If $m=0$ and $n=0$, we have the trivial case where the season is over, so we can say $a_{0,0} = 1$. In other words, we keep all our money.
• If $m=n$, we know with certainty that our team will win all its remaining games. Therefore, we can safely bet all our money on them: $k_{n,n} = 1$ and $a_{n,n} = 2a_{n-1,n-1}$ (we will double our money).
• If $m=0$, we know with certainty that our team will lose all its remaining games. Therefore, we can safely bet all our money against them: $k_{n,0}=-1$ and $a_{n,0} = 2a_{n-1,0}$.

In the general case, $0\lt m \lt n$, and we must think a bit more carefully. If we bet $k_{n,m}$, the two possible outcomes are:

• If our team wins, we now have $a_{n,m} = (1+k_{n,m})a_{n-1,m-1}$. This is because after a win, there are only $m-1$ wins remaining.
• If our team loses, we now have $a_{n,m} = (1-k_{n,m})a_{n-1,m}$. This is because after a loss, we must still win $m$ more times.

We should pick $k_{n,m}$ to maximize the minimum winnings of both possible outcomes, because we are looking at the worst-case. In other words, we want:
\[
a_{n,m} = \max_k\, \min\bigl\{ (1+k)a_{n-1,m-1}, (1-k)a_{n-1,m} \bigr\}
\]As functions of $k$, these are two linear functions; one with positive slope and one with negative slope. The optimal $k$ occurs when the lines cross, that is, when $(1+k)a_{n-1,m-1}=(1-k)a_{n-1,m}$. Solving this equation, we obtain:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}, &
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
\end{align}Combining our recursion for $a_{n,m}$ with the edge cases derived earlier:
\begin{align}
a_{0,0}&=1 \\
a_{n,0}&=2a_{n-1,0} && \text{for }n=1,2,\dots \\
a_{n,n}&=2a_{n-1,n-1} && \text{for }n=1,2,\dots \\
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}} &&\text{for }0\lt m \lt n
\end{align}There is a neat trick we can use to solve this recursion. Express everything in terms of the inverse of the minimum winnings. The equations then become linear!
\begin{align}
a_{0,0}^{-1}&=1 \\
a_{n,0}^{-1}&=\frac{1}{2} a_{n-1,0}^{-1} && \text{for }n=1,2,\dots \\
a_{n,n}^{-1}&=\frac{1}{2} a_{n-1,n-1}^{-1} && \text{for }n=1,2,\dots \\
a_{n,m}^{-1}&=\frac{1}{2}\left( a_{n-1,m}^{-1} + a_{n-1,m-1}^{-1} \right) &&\text{for }0\lt m \lt n
\end{align}Solving for the first few terms and arranging them in a pyramid where each row is a different value of $n$, we obtain:
\begin{gather}
a_{0,0}^{-1}=\frac{1}{2^0}\\[2mm]
a_{1,0}^{-1}=\frac{1}{2^1} \qquad a_{1,1}^{-1}=\frac{1}{2^1} \\[2mm]
a_{2,0}^{-1}=\frac{1}{2^2} \qquad a_{2,1}^{-1}=\frac{2}{2^2} \qquad a_{2,2}^{-1}=\frac{1}{2^2} \\[2mm]
a_{3,0}^{-1}=\frac{1}{2^3} \qquad a_{3,1}^{-1}=\frac{3}{2^3} \qquad a_{3,2}^{-1}=\frac{3}{2^3} \qquad a_{3,3}^{-1}=\frac{1}{2^3}\\[2mm]
a_{4,0}^{-1}=\frac{1}{2^4} \qquad a_{4,1}^{-1}=\frac{4}{2^4} \qquad a_{4,2}^{-1}=\frac{6}{2^4} \qquad a_{4,3}^{-1}=\frac{4}{2^4} \qquad a_{4,4}^{-1}=\frac{1}{2^4}
\end{gather}The denominators in each row are increasing powers of two, and the numerators are the sums of the two numerators above! In other words, it’s a scaled Pascal’s triangle! This leads us to the formula:
\[
a_{n,m}^{-1} = \frac{1}{2^{n}} \binom{n}{m},\quad\text{or:}\quad
a_{n,m} = \frac{2^{n}}{\binom{n}{m}}
\]What should our optimal policy be? We can use the formula for $k_{n,m}$ derived earlier and substitute the formula we just found for $a_{n,m}$:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
= \frac{2m}{n}-1
\end{align}

Therefore, we have the following minimax-optimal strategy:

$\displaystyle
\begin{array}{l}
\text{If there are $n$ games left to play and our team will} \\
\text{win exactly $m$ of the remaining games, we should}\\
\text{bet a fraction $\frac{2m}{n}-1$ of our money, and we will}\\
\text{multiply our money by at least $\frac{2^n}{\binom{n}{m}}$ by the end.}
\end{array}
$

We can check the edge cases: If $m=0$, we should bet $k_{n,0}=-1$ (bet it all against our team), and we will win $2^n$ (double our money for every remaining game). Similarly, if $m=n$, we should bet $k_{n,n}=1$ (bet it all for our team), and we will again win $2^n$.

To address the original question, if there are $n=12$ games remaining and we will win exactly $m=8$ of them, then starting with $\$100$ and using the optimal betting strategy, we are guaranteed to finish the season with at least $100 \cdot 2^{12} / \binom{12}{8} =\frac{100\cdot 4096}{495} \approx \$827.48$.

We can say something even stronger. This optimal betting strategy will always win exactly $\$827.48$! To understand why, we need to dig a little deeper…

Deeper down the rabbit hole

When using the “optimal” strategy derived earlier, something curious happens. Not only are we guaranteed to win at least $2^n/\binom{n}{m}$ by the end of the season, we are guaranteed to win exactly this much! No matter how the wins and losses are arranged, we will always win the same amount after all games have been played!

We will prove this surprising result in two parts. First, we will show that every arrangement wins the same amount under the optimal betting strategy. Second, we will show that this amount is equal to $2^n/\binom{n}{m}$, the same as the previously derived “lower bound”.

To prove all arrangements win the same amount, imagine two arrangements of wins and losses that only differ by swapping one adjacent win-loss pair. For example, if $n=12$ and $m=8$, we could have:
\begin{gather}
\begin{bmatrix}
W & L & W & \textcolor{blue}{W} & \textcolor{red}{L} & W & L & W & W & W & L & W
\end{bmatrix}\\[2mm]
\begin{bmatrix}
W & L & W & \textcolor{red}{L} & \textcolor{blue}{W} & W & L & W & W & W & L & W
\end{bmatrix}
\end{gather}Suppose that right before the swap occurs, we have $x$ dollars, and there are $n_0$ games remaining, and $m_0$ wins remaining.

• In the first case, we bet $\frac{2m_0}{n_0}-1$ and we win. There are now $n_0-1$ games remaining and $m_0-1$ wins remaining. We bet $\frac{2(m_0-1)}{n_0-1}-1$, but this time we lose. So our net winnings after the win and loss are:
  \[
  \small
  \left( 1-\left(\frac{2(m_0-1)}{n_0-1}-1\right)\right)\left(1+\left(\frac{2m_0}{n_0}-1\right)\right)x
  =\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
  \]

• In the second case, we bet $\frac{2m_0}{n_0}-1$ and we lose. There are now $n_0-1$ games remaining and $m_0$ wins remaining. We bet $\frac{2m_0}{n_0-1}-1$, and this time we win. So our net winnings after the loss and win are:
  \[
  \small
  \left( 1+\left(\frac{2m_0}{n_0-1}-1\right)\right)\left(1-\left(\frac{2m_0}{n_0}-1\right)\right)x
  =\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
  \]

Since swapping an adjacent win-loss pair does not change how much we win, and we can get from any arrangement of $m$ wins and $n-m$ losses to any other arrangement via a suitable sequence of adjacent win-loss swaps, this shows that every arrangement obtains the exact same result!

In particular, we might as well assume we win our first $m$ games, and lose the rest. Let’s calculate how much we win in this simple scenario.

• For the first $m$ games, we win every time, so our winnings are:
  \[
  \frac{2m}{n} \cdot \frac{2(m-1)}{(n-1)} \cdot \frac{2(m-2)}{(n-2)} \cdots \frac{2(1)}{(n-m+1)}
  =\frac{2^m m!(n-m)!}{n!}
  \]

• For the remaining $n-m$ games, we are in an edge case. Our team will lose all remaining games, so we bet against them every time and double our money. This multiplies our money by $2^{n-m}$.

Therefore, our total winnings are:
\[
\frac{2^m m!(n-m)!}{n!} \cdot 2^{n-m} = \frac{2^n}{\binom{n}{m}}
\]This is the same result as the lower bound we found in the first part of the solution! Therefore, we can conclude that using the optimal betting strategy yields exactly the same outcome no matter how the wins and losses are ordered, and this amount is $2^n/\binom{n}{m}$.

The key observation is that we can think of betting strategies as bets on outcomes rather than bets on individual games. For example, if $n=2$, there are four possible outcomes (ignore for now the fact that we have future knowledge about the win-loss record):
\[
LL,LW,WL,WW
\]If I bet all my money on $LW$ and I’m right, then I will double my money twice. If I’m wrong, then I lose everything.

In general, if there are $n$ games, there will be $2^n$ possible outcomes. I don’t have to bet everything on one outcome; I can distribute my $x$ dollars however I like. But only one of these outcomes will come true. The money I bet on that outcome will get multiplied by $2^n$ and all my other bets will be lost.

In the worst case, the outcome with the smallest bet will come true. So if we want a strategy that maximizes the worst-case losses, I should bet an equal amount on each possible outcome.

Now we can use our advance knowledge that our team will win exactly $m$ of the $n$ games. Therefore, only $\binom{n}{m}$ of the $2^n$ outcomes are possible. So the optimal strategy is to distribute our bets equally among all $\binom{n}{m}$ possible outcomes. With this strategy, no matter which outcome comes true, we will always multiply our initial dollar amount by exactly $2^n/\binom{n}{m}$.

I skipped some details here; I didn’t explain why every strategy can be decomposed as a combination of pure strategies, but this post is already quite long so I won’t write out the details. As a partial explanation, the result uses the fact that the earnings are a linear function of the bets. For example, if $n=1$, our strategy consists of the single bet $k$, and the outcome is:
\[
(k) : \begin{cases}
(1+k)x & \text{if W} \\
(1-k)x & \text{if L}
\end{cases}
\]There are also two pure strategies:
\[
(1) : \begin{cases}
0 & \text{if W} \\
2x & \text{if L}
\end{cases}
\qquad\text{and}\qquad
(-1): \begin{cases}
2x & \text{if W} \\
0 & \text{if L}
\end{cases}
\]We can decompose $k$ as a combination of $+1$ and $-1$, which yields:
\[
(k) = \left(\frac{1-k}{2}\right)(1) + \left(\frac{1-k}{2}\right)(-1)
\]In other words, using the bet $k$ is the same as betting $\left(\frac{1-k}{2}\right)x$ of our money on a loss and betting the remaining $\left(\frac{1+k}{2}\right)x$ on a win. Exactly one of those two outcomes will come true, so the amount we bet correctly gets doubled and the amount we bet incorrectly is lost.