Fiddler - Book Proofs

Pancake race

This week’s Fiddler is a logic puzzle about getting home as fast as possible.

Alice, Bob, and Carey start together and each walk home at a different constant speed. Once all three get home, they can have pancakes! Alice can walk home in 10 minutes, Bob can do it in 20, and Carey in 30. Fortunately, any of them can carry any of the others on their back without reducing their own walking speed. Assume that they can pick someone up, set someone down, and change direction instantaneously. What is the fastest they can get to eat pancakes?

Extra Credit
There is now a fourth: Dee. Dee is the slowest, needing 60 minutes to walk home. As before, anyone can carry anyone else, and they won’t get pancakes until everyone gets home. What is the fastest this can happen?

My solution:
[Show Solution]

This seems like a logic puzzle at first glance, but it carries a nice geometric intuition. Specifically, imagine time on the $x$-axis and distance from home on the $y$-axis. If Alice, Bob, and Carey (I’ll just call them A, B, C from now on) walk at a constant speed, their paths show up as straight lines.

For the first problem, the optimal thing to do is as follows:

A+C ride together, and B rides alone.
At some point, A drops off C and returns to meet with B.
C continues home alone.
A meets up with B, picks them up, and A+B ride home together.

The optimal thing to have happen is for A,B,C to all arrive home at the same time, as illustrated in the diagram below. If C arrived home before A+B, then A should have dropped them off earlier and hence arrived home earlier with B. Likewise, if C arrived home after A+B, then A should have dropped them off later so they could arrive home sooner.

In the diagram, blue lines have “A slope” $\pm 1$, green lines have “B slope” $\pm\frac{1}{2}$, and red lines have “C slope” $\pm\frac{1}{3}$. The points of interest are F, G, H, as shown. I wrote in their coordinates in terms of unknowns $p,q,r$ in units of 10 minutes. We now have three equations:

FG has slope $1$, therefore $p-\tfrac{1}{2}q = q-p$
GH has slope $-1$, therefore $1-\tfrac{1}{2}q = r-q$
FH has slope $-\frac{1}{3}$, therefore $1-p=\tfrac{1}{3}(r-p)$

Solving these equations, we obtain
\[
p=\frac{3}{4},\quad q=1,\quad r=\frac{3}{2}.
\]Since I used units of 10 minutes, the arrival time is $10r = 10 \cdot \frac{3}{2}$ minutes, or exactly 15 minutes.

Note: I’d like to thank commenter TLK for pointing out an error in a previous version of my solution. I was a bit hasty in my first write-up and presumed that A would carry C all the way home before returning to fetch B!

Extra credit

For the extra credit, the solution is quite a bit more complicated:

A+D ride together, and B+C ride together
At some point, A drops off D and returns to meet with B.
D continues toward home.
A meets up with B, returns home with B, and C continues alone.
A+B meet up with D, B carries D home and A turns back.
A meets up with C and carries C home.

Once again, the optimal thing to have happen is for A,B,C,D to all arrive home at the same time. Here is the corresponding diagram.

This time, we have more equations and more variables.

FG has slope $1$, therefore $p-\tfrac{1}{2}q = q-p$.
FH has slope $-\tfrac{1}{6}$, therefore $H = (p+s,1-p-\tfrac{1}{6}s)$ for some $s$.
GJ has slope $-\tfrac{1}{3}$, therefore $J = (q+r,1-\tfrac{1}{2}q-\tfrac{1}{3}r$.
GH has slope $-1$, therefore $p+s-q=p+\tfrac{1}{6}s-\tfrac{1}{2}q$
HJ has slope $1$, therefore $q+r-p-s=p+\tfrac{1}{6}s-\tfrac{1}{2}q-\tfrac{1}{3}r$.
HK has slope $-\tfrac{1}{2}$, therefore $1-p-\tfrac{1}{6}s = \tfrac{1}{2}(t-p-s)$.
JK has slope $-1$, therefore $1-\tfrac{1}{2}q-\tfrac{1}{3}r=t-q-r$.

Solving these equations, we obtain:
\[
p= \frac{5}{8},\quad
q= \frac{5}{6},\quad
r= \frac{7}{16},\quad
s= \frac{1}{2},\quad
t= \frac{41}{24}.
\]The arrival time is $10t=\frac{205}{12}$ minutes, or 17.0833 minutes,
or exactly 17 minutes and 5 seconds.

Note: I’d like to thank commenter Sanandan Swaminathan for pointing out an error in a previous version of my solution. Once again, I was a bit hasty in my first write-up and presumed that A would pick up C on their first return trip, when in fact it’s better for A to pick up B! Here is a diagram of the previous (sub-optimal) solution I found, which only achieves 17.8125 minutes, or 17 minutes and 48.75 seconds.

Dungeon Master’s Dice

This week’s Fiddler is a probability question about a dice-rolling game.

Two people are sitting at a table together, each with their own bag of six “DnD dice”: a d4, a d6, a d8, a d10, a d12, and a d20. Here, “dX” refers to a die with X faces, numbered from 1 to X, each with an equally likely probability of being rolled. Both people randomly pick one die from their respective bags and then roll them at the same time. For example, suppose the two dice selected are a d4 and a d12. The players roll them, and let’s further suppose that both rolls come up as 3. What luck! What’s the probability of something like this happening? That is, what is the probability that both players roll the same number, whether or not they happened to pick the same kind of die?

Extra Credit
Instead of two people sitting at the table, now suppose there are three. Again, all three randomly pick one die from their respective bags and roll them at the same time. For example, suppose the three dice selected are a d4, a d20, and a d12. The players roll them, and let’s further suppose that the d4 comes out as 4, the d20 comes out as 13, and the d12 comes out as 4. In this case, there are two distinct numbers (4 and 13) among the three rolls. On average, how many distinct numbers would you expect to see among the three rolls?

My solution:
[Show Solution]

Each person performs two actions: selecting a die at random, and rolling that die. In the language of probability, the sample space (the set of all things that can occur) is $(n,d)$, where $d$ is the selected die, and $n$ is the number that is rolled. The probability of picking the die $d$ and rolling a $n$ is given by:
\[
p_{n,d} = \frac{1}{6} \times \begin{cases}
\frac{1}{d} & \text{if }1 \leq n \leq d \\
0 & \text{otherwise}
\end{cases}
\]The $\frac{1}{6}$ comes from the fact that there are six different dice, each equally likely to be picked. Arranging these probabilities in a table, we obtain:
\[
p_{n,d} = \frac{1}{6}\begin{bmatrix}
\frac{1}{4} & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
\frac{1}{4} & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
\frac{1}{4} & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
\frac{1}{4} & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & \frac{1}{6} & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & \frac{1}{8} & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & 0 & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & 0 & \frac{1}{10} & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & 0 & 0 & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & 0 & 0 & \frac{1}{12} & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20} \\
0 & 0 & 0 & 0 & 0 & \frac{1}{20}
\end{bmatrix}
\quad \implies \quad p_n = \begin{bmatrix}
\frac{31}{240} \\ \frac{31}{240} \\ \frac{31}{240} \\ \frac{31}{240} \\
\frac{7}{80} \\ \frac{7}{80} \\ \frac{43}{720} \\ \frac{43}{720} \\
\frac{7}{180} \\ \frac{7}{180} \\
\frac{1}{45} \\ \frac{1}{45} \\
\frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120} \\ \frac{1}{120}
\end{bmatrix}
\]In the matrix on the left, each column corresponds to a different die and each row corresponds to a different number. All the numbers in this table sum to 1 (this is a joint distribution). The column vector on the right is what you get when you sum across rows. These numbers again sum to 1 and form what is called a marginal distribution. This is the probability distribution for the dice rolls regardless of which die was picked. Picking one of the dice at random, then rolling it, is the same as rolling a single weighted 20-sided die whose weights are given by the marginal distribution above. We can plot this distribution as a graph, and we get the following:

From now on, I will write $p_n$ to denote the (marginal) probability of rolling the number $n$.

The first problem

The first problem asks for the probability that both players roll the same number (regardless of which die they chose). The probability that both players roll $n$ is $p_n^2$. Therefore, the probability that they both roll the same number is
\[
\sum_{n=1}^{20} p_n^2 = \frac{3}{32} = 0.09375
\]Therefore, the probability that both players roll the same number is approximately 9%.

The extra credit

We now have 3 players, and we are asked to find the expected number of distinct rolls. We can calculate the probability of each in turn.

The probability of obtaining one distinct number (all three players roll the same number) is similar to the case with two players rolling the same number, except now it’s $p_n^3$. Therefore,
\[
q_1 = \sum_{n=1}^{20}p_n^3 = \frac{32753}{3110400} \approx 0.01053
\]
The probability of obtaining two distinct numbers is a bit more complicated. We have to count how many ways we can pick two players that will have the same number $n$, which is $\binom{3}{2}p_n^2$, and then the third player can have any of the remaining numbers, so we multiply by $(1-p_n)$. Therefore,
\[
q_2 = \sum_{n=1}^{20}\binom{3}{2}p_n^2(1-p_n) = \frac{258847}{1036800} \approx 0.24966
\]
Finally, the probability of obtaining three distinct numbers is the leftover probability after excluding the first two cases above:
\[
q_3 = 1-q_1-q_2 = \frac{1150553}{1555200} \approx 0.73981
\]

We can calculate the expected number of distinct rolls by multiplying each probability above by the number of distinct rolls and summing them up:
\begin{align}
\mathbb{E}(\text{distinct numbers})
&= q_1 + 2q_2 + 3q_3
= \frac{8489153}{3110400}
\approx 2.72928
\end{align}

Therefore, we would expect to see, on average, 2.729 distinct numbers among the three dice rolls.

Don’t flip out

This week’s Fiddler is a probability question about a coin-flipping game.

Kyle and Julien are playing a game in which they each toss their own fair coins. On each turn of the game, both players flip their own coin once. If, at any point, Kyle’s most recent three flips are Tails, Tails, and Heads (i.e., TTH), then he wins. If, at any point, Julien’s most recent three flips are Tails, Tails, and Tails (i.e, TTT), then he wins.

However, both players can’t win at the same time. If Kyle gets TTH at the same time Julien gets TTT, then no one wins, and they continue flipping. They don’t start over completely or erase their history, mind you—they merely continue flipping, so that one of them could conceivably win in the next flip or two.

What is the probability that Kyle wins this game?

Extra Credit
Kyle and Julien write down all eight possible sequences for three coin flips (HHH, HHT, HTH, THH, HTT, THT, TTH, and TTT) on eight different slips of paper. They place these slips into a hat and shake it.

They will each randomly draw slips of paper out of the hat, at which point they will play the same game as previously described, but looking for the sequence specified on the slip of paper they each selected. Kyle draws first and looks at his slip of paper. After doing some calculations, he says: “Well, at this point, it’s about as fair a match as it could possible be.”

Which slip or slips of paper might Kyle have drawn? And what are his chances of winning at this point (i.e., before Julien selects his own slip of paper)?

My solution:
[Show Solution]

The state of each player’s game is determined by their most recent 3 coin flips. So there are 8 possible states:
\[
\textsf{HHH}, \textsf{HHT}, \textsf{HTH}, \textsf{HTT}, \textsf{THH}, \textsf{THT}, \textsf{TTH}, \textsf{TTT}
\]Each turn, each player transitions from one of these states to another, depending on whether they flip Heads or Tails. Therefore, it is a Markov Chain. Here is what it looks like represented graphically:

Each edge has a weight of $\frac{1}{2}$, since we are flipping a fair coin. Mathematically, we can write $P_{ij}$ as the probability of transitioning from state $i$ to state $j$, where the states $1,2,\dots,8$ are ordered in the same order as the list above. (${\small\textsf{HHH}}:1$, ${\small\textsf{HHT}}:2$, etc.) This leads to the following transition matrix:
\[
P = \frac{1}{2}\begin{bmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1
\end{bmatrix}
\]Since both Kyle and Julien are flipping coins independently, what we really have is a Markov chain whose state is the Cartesian product of the states of each player: $(x_\text{Kyle},x_\text{Julien})$. This larger Markov chain has $8\times 8 = 64$ states and its transition matrix is the Kronecker product of two smaller transition matrices: $\hat P = P\otimes P$. The matrix $\hat P$ has the following sparsity pattern

All nonzero entries of $\hat P$ are $\frac{1}{4}$. This is a valid transition matrix because each row sums to 1 since there are exactly four nonzero entries per row. If you’re curious, here is what the graph looks like (yikes!)

In the augmented Markov chain, Kyle wins if we end up in state $(7,j)$ where $j\neq 8$. This corresponds to states numbered:
\[
\mathcal{X}_\text{K} = \{49, 50, 51, 52, 53, 54, 55\}
\]Likewise, Julien wins if we end up in state $(i,8)$ where $i\neq 7$, which corresponds to states:
\[
\mathcal{X}_\text{J} = \{8, 16, 24, 32, 40, 48, 64\}
\]As an additional notation, let’s define the set of all transient nodes, which are the nodes that are not in $\mathcal{X}_\text{K}$ or in $\mathcal{X}_\text{J}$. These are the 50 nodes:
\begin{multline}
\mathcal{X}_\text{T} =
\{1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19,20, \\
21,22,23,25,26,27,28,29,30,31,33,34,35,36,37,38, \\
39,41,42,43,44,45,46,47,56,57,58,59,60,61,62,63\}
\end{multline}Note that the case where both players win at the same time corresponds to $(7,8)$ (state number 56), which is treated as just another transient node, since nothing special happens in this case.

Now that we have the appropriate mathematical framework set up, we can tackle the original problem. We would like to find the probability that Kyle wins the game. Translated to Markov-speak, we want the probability that we first land in $\mathcal{X}_\text{K}$ before first landing in $\mathcal{X}_\text{J}$. Let $v_i$ be the probability of Kyle winning if we start in node $i$. We can make the following observations:

$v_i=1$ whenever $i \in \mathcal{X}_\text{K}$. If we are in Kyle’s winning state, then Kyle must necessarily win before Julien does.
$v_i=0$ whenever $i \in \mathcal{X}_\text{J}$. If we are in Julien’s winning state, then Kyle can’t possibly win before Julien does.
If $i \in \mathcal{X}_\text{T}$, the probability of Kyle winning depends recursively on which states we transition to next:
\[
v_i = \sum_{j = 1}^{64} \hat P_{ij} v_j \qquad\text{if }i \in \mathcal{X}_\text{T}
\]

The above gives us $64$ equations to solve in the $64$ unknowns $v_1,\dots,v_{64}$. Compactly, we can write the solution as:
\begin{align}
v_\text{K} &= 1 \\
v_\text{J} &= 0 \\
v_\text{T} &= \left(I-\hat P_{\text{T},\text{T}}\right)^{-1}
\hat P_{\text{T},\text{K}} \mathbf{1}
\end{align}Since each of the 64 starting states is equally likely, the probability that Kyle wins the game is simply the mean value of the vector $v$. Here is a short Matlab script that computes the solution:

P = 1/2*kron([1;1],kron(eye(4),[1 1]));
s = ["HHH","HHT","HTH","HTT","THH","THT","TTH","TTT"];
Kwin = "TTH";
Jwin = "TTT";
XK = find(kron(s == Kwin, s ~= Jwin));
XJ = find(kron(s ~= Kwin, s == Jwin));
XT = setdiff(1:64,union(XK,XJ));
Phat = kron(P,P);
v = zeros(64,1);
v(XK) = 1;
v(XJ) = 0;
v(XT) = (eye(length(XT)) - Phat(XT,XT)) \ Phat(XT,XK) * ones(length(XK),1);
mean(v)

The result of this computation is $\frac{45667}{71106} \approx 64.22\%$. So Kyle has a 64% chance of winning!

Extra credit

Here, we consider the same game as before, except we vary the winning state for Kyle and Julien. To do this, we loop through all possible combinations of winning states and run the same script as above. This yields the following matrix of probabilities. Rows and columns correspond to Kyle and Julien’s choice of winning sequence, respectively. Entries in the matrix are Kyle’s probability of winning.
\[
\begin{bmatrix}
\frac{1}{2} & \frac{25439}{71106} & \frac{1177}{2850} & \frac{25439}{71106} & \frac{25439}{71106} & \frac{1177}{2850} & \frac{25439}{71106} & \frac{1}{2} \\
\frac{45667}{71106} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{45667}{71106} \\
\frac{1673}{2850} & \frac{23487}{52162} & \frac{1}{2} & \frac{23487}{52162} & \frac{23487}{52162} & \frac{1}{2} & \frac{23487}{52162} & \frac{1673}{2850} \\
\frac{45667}{71106} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{45667}{71106} \\
\frac{45667}{71106} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{45667}{71106} \\
\frac{1673}{2850} & \frac{23487}{52162} & \frac{1}{2} & \frac{23487}{52162} & \frac{23487}{52162} & \frac{1}{2} & \frac{23487}{52162} & \frac{1673}{2850} \\
\frac{45667}{71106} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{1}{2} & \frac{28675}{52162} & \frac{1}{2} & \frac{45667}{71106} \\
\frac{1}{2} & \frac{25439}{71106} & \frac{1177}{2850} & \frac{25439}{71106} & \frac{25439}{71106} & \frac{1177}{2850} & \frac{25439}{71106} & \frac{1}{2}
\end{bmatrix}
\]Or, in numerical form,
\[
\small
\begin{bmatrix}
0.5 & 0.357762 & 0.412982 & 0.357762 & 0.357762 & 0.412982 & 0.357762 & 0.5 \\
0.642238 & 0.5 & 0.54973 & 0.5 & 0.5 & 0.54973 & 0.5 & 0.642238 \\
0.587018 & 0.45027 & 0.5 & 0.45027 & 0.45027 & 0.5 & 0.45027 & 0.587018 \\
0.642238 & 0.5 & 0.54973 & 0.5 & 0.5 & 0.54973 & 0.5 & 0.642238 \\
0.642238 & 0.5 & 0.54973 & 0.5 & 0.5 & 0.54973 & 0.5 & 0.642238 \\
0.587018 & 0.45027 & 0.5 & 0.45027 & 0.45027 & 0.5 & 0.45027 & 0.587018 \\
0.642238 & 0.5 & 0.54973 & 0.5 & 0.5 & 0.54973 & 0.5 & 0.642238 \\
0.5 & 0.357762 & 0.412982 & 0.357762 & 0.357762 & 0.412982 & 0.357762 & 0.5 \\
\end{bmatrix}
\]Note that the $(7,8)$ cell corresponds to the case we solved in the first part. Many of the cells contain $\frac{1}{2}$; these are cases where both Kyle and Julien have equally easy (or difficult) winning states that they are trying to reach. If we don’t know ahead of time which winning sequence Julien will pick, then we should average the rows of this matrix to see Kyle’s average chance of winning the game for each possible choice of winning sequence. This yields:
\[
\begin{array}{ccc}
\text{Kyle’s} & \text{Prob that} & \text{numerical} \\[-1mm]
\text{sequence} & \text{Kyle wins} & \text{approximation} \\ \hline
\textsf{HHH} & \frac{6875419}{16887675} & 0.407126\\
\textsf{HHT} & \frac{508129861}{927257793} & 0.547992\\
\textsf{HTH} & \frac{18467111}{37165425} & 0.496890\\
\textsf{HTT} & \frac{508129861}{927257793} & 0.547992\\
\textsf{THH} & \frac{508129861}{927257793} & 0.547992\\
\textsf{THT} & \frac{18467111}{37165425} & 0.496890\\
\textsf{TTH} & \frac{508129861}{927257793} & 0.547992\\
\textsf{TTT} & \frac{6875419}{16887675} & 0.407126\\
\end{array}
\]Note that several rows are repeated in the matrices above. This is because different choices of winning state can be considered “equivalent” due to the symmetry inherent in this game. Specifically, we can define the following three equivalence classes:
\begin{align}
A &: \{\textsf{HHH},\textsf{TTT}\} \\
B &: \{\textsf{HTH},\textsf{THT}\} \\
C &: \{\textsf{HHT},\textsf{HTT},\textsf{THH},\textsf{TTH}\}
\end{align}We can simplify the table above to:
\[
\begin{array}{ccc}
\text{Equivalence} & \text{Prob that} & \text{numerical} \\[-1mm]
\text{class} & \text{Kyle wins} & \text{approximation} \\ \hline
A & \frac{6875419}{16887675} & 0.407126\\
B & \frac{18467111}{37165425} & 0.496890\\
C & \frac{508129861}{927257793} & 0.547992\\
\end{array}
\]Based on this analysis, it appears that Kyle picking the $B$ equivalence class ($\small\textsf{HTH}$ or $\small\textsf{THT}$) leads to the game being close to 50% on average. This means that if Julien picks his winning sequence at random, the game will be, on average, close to perfectly fair.

Alternative interpretations

Different notions of “close to 1/2” lead to different choices for Kyle. For example, if our notion of fairness is “equal to 1/2 as often as possible”, then Kyle should pick option $C$. In this case, if Julien picks randomly, the game will be perfectly fair 50% of the time. But in option $B$, the game is only perfectly fair 25% of the time.

Alternatively, what if Julien does not pick randomly, but rather is greedy and picks his winning sequence in an effort to maximize his chance of winning? And what if Kyle knows that Julien is doing this, and tries to maximize his chances of winning as well? And what if Julien knows that Kyle knows? (and so on…) Then it becomes a game in the mathematical sense of the word, and the solution is the Nash equilibrium. To find the Nash equilibrium, rewrite the probability of Kyle winning as a reduced $3\times 3$ matrix based on equivalence class:
\[
\begin{bmatrix}
\frac{1}{2} & \frac{1177}{2850} & \frac{25439}{71106} \\
\frac{1673}{2850} & \frac{1}{2} & \frac{23487}{52162} \\
\frac{45667}{71106} & \frac{28675}{52162} & \frac{1}{2}
\end{bmatrix}
\approx
\begin{bmatrix}
0.5 & 0.412982 & 0.357762 \\
0.587018 & 0.5 & 0.45027 \\
0.642238 & 0.54973 & 0.5
\end{bmatrix}
\]
In this game, Kyle picks a row and Julien picks a column. Kyle wants to maximize the resulting number and Julien wants to minimize it. By inspection, we can see that the best choice for both Kyle and Julien is again to pick option $C$.

So perhaps $C$ is a more sensible choice for Kyle after all!

The Likeliest Monopoly Square

This week’s Fiddler is about rolling dice in the board game Monopoly.

We have a square board with 40 individual spaces around it, numbered from 0 to 39. All players begin on space 0 (akin to the “Go” square in Monopoly) and roll a pair of dice to determine how many spaces they advance each turn. However, unlike Monopoly, there is no way to otherwise advance around the board (i.e., there’s no “Chance,” “Community Chest,” going to jail, etc.). In their first pass around the board, which space from 1 to 39 are players most likely to land on at some point (i.e., not necessarily on their first or last roll, but after any number of rolls)?

Extra Credit
The square board has 10 spaces on each side. The first side has spaces 0 through 9, the second side has spaces 10 through 19, the third side has spaces 20 through 29, and the fourth side has spaces 30 through 39. Because you’re rolling two dice, it’s impossible to land on space 1 in your first pass around the board. Several other spaces on the first side of the board are similarly unlikely. Putting that first side of the board aside, which space from 10 to 39 are players least likely to land on at some point during their first pass around the board? (Another question: What if you rolled three dice at a time instead of two?)

My solution:
[Show Solution]

An efficient way to tackle such a problem is via the use of polynomials, or more generally, generating functions. Here is the basic idea. Suppose we roll a single die. Each number $1,\dots,6$ has equal probability $\frac{1}{6}$ of occurring. We will encode this using the polynomial:
\[
q(x) = \tfrac{1}{6}x + \tfrac{1}{6}x^2 + \tfrac{1}{6}x^3 + \tfrac{1}{6}x^4 + \tfrac{1}{6}x^5 + \tfrac{1}{6}x^6
\]We can interpret the coefficient of $x^k$ as the probability that we will land on the $k^\text{th}$ square. If we roll two dice, the corresponding probability distribution is obtained by taking the product of the polynomials for each die. That is, we have:
\begin{multline}
q(x)^2 =
\tfrac{1}{36}x^2+\tfrac{1}{18}x^3+\tfrac{1}{12}x^4+\tfrac{1}{9}x^5+\tfrac{5}{36}x^6+\tfrac{1}{6}x^7\\+\tfrac{5}{36} x^8+\tfrac{1}{9}x^9+\tfrac{1}{12}x^{10}+\tfrac{1}{18}x^{11}+\tfrac{1}{36}x^{12}
\end{multline}So the probability of rolling a 6 would be $\tfrac{5}{36}$. This works because of how polynomials multiply. We can roll a 6 in several ways:
\[
(1+5), (2+4), (3+3), (4+2), (5+1)
\]Likewise, when we multiply the two polynomials, the coefficient of $x^6$ can be obtained by selecting the same corresponding pairs of terms from the first and second polynomial:
\[
(x^1\cdot x^5),
(x^2\cdot x^4),
(x^3\cdot x^3),
(x^4\cdot x^2),
(x^5\cdot x^1)
\]The probability of each of these occurring is the product of the coefficients from each polynomial, so the net probability is the sum of each such product, i.e. the coefficient of the $x^6$ term in the resulting polynomial.

Since we can also obtain a particular number by rolling 4 dice, 6 dice, 8 dice, etc., what we’re after is the coefficient of $x^n$ in the infinite polynomial:
\[
p(x) = \sum_{k=1}^\infty q(x)^{2k}
= \frac{q(x)^2}{1-q(x)^2}.
\]The compact representation comes from summing the geometric series, but in this case it’s not that helpful because we still need to extract the polynomial coefficients when it is expanded as a series. We can evaluate coefficients numerically in Mathematica and produce a plot of the coefficients of the resulting polynomial. Here is the code:

q = 1/6 (x + x^2 + x^3 + x^4 + x^5 + x^6);
BarChart[
 CoefficientList[Normal[Series[q^2/(1 - q^2), {x, 0, 40}]], x], 
 ChartLabels -> Table[k, {k, 0, 40}], GridLines -> Automatic]

and the resulting plot:

We can now answer all the questions in the original problem.

The likeliest square to land on is 7 (lucky number 7!). The associated probability is $\frac{1417}{7776} \approx 0.182227$.
Excluding squares 0-9, the least likely square to land on is 13 (unlucky number 13!). The associated probability is $\frac{22621045}{181398528} \approx 0.124704$.

If we are rolling three dice instead, we simply change $q(x)^2$ to $q(x)^3$. The resulting plot is:

The reason for this curious oscillating shape is that it comes from summing the distributions for $q(x)^3$, $q(x)^6$, $q(x)^9$, etc. Each of these tends to a normal distribution with increasing variance. Here are the distributions plotted separately (3 dice at once):

Analytic solution

The solution above gives us a way to compute the solution for any $n$ by multiplying and adding polynomials together. But can we obtain an actual formula for the probability of landing on a particular square? Yes! But it will be complicated… It involves rewriting our infinite series as a sum of simpler series using partial fraction decomposition:
\begin{align}
p(x) &= \sum_{k=1}^\infty q(x)^{2k} = \frac{q(x)^2}{1-q(x)^2} \\
&= -1 + \frac{\tfrac{1}{2}}{1-q(x)} + \frac{\tfrac{1}{2}}{1+q(x)}\\
&= -1-\frac{3}{x^6+x^5+x^4+x^3+x^2+x-6}+\frac{3}{x^6+x^5+x^4+x^3+x^2+x+6}\\
&= -1-\frac{3}{(x-1)(x^5+2 x^4+3 x^3+4 x^2+5 x+6)}+\frac{3}{x^6+x^5+x^4+x^3+x^2+x+6}\\
&= -1-\frac{1}{7(x-1)} + \frac{x^4+3 x^3+6 x^2+10 x+15}{7 \left(x^5+2 x^4+3 x^3+4 x^2+5 x+6\right)}+\frac{3}{x^6+x^5+x^4+x^3+x^2+x+6}
\end{align}We continue by breaking up the polynomials even further.
\begin{align}
&\text{Let $\{\eta_k\}$ be the 5 roots of the polynomial $x^5+2x^4+3x^3+4x^2+5x+6$}\\
&\text{Let $\{\zeta_k\}$ be the 6 roots of the polynomial $x^6+x^5+x^4+x^3+x^2+x+6$}
\end{align}Applying yet another partial fraction decomposition, we obtain:
\[
p(x) = -1-\frac{1}{7(x-1)}
+\sum_{k=1}^5 \frac{a_k}{x-\eta_k}+\sum_{k=1}^6 \frac{b_k}{x-\zeta_k}
\]where the $a_k$ and $b_k$ coefficients are given by:
\begin{align}
a_k &= \frac{\eta_k^4+3\eta_k^3+6\eta_k^2+10\eta_k+15}{7\prod_{i\neq k}(\eta_k-\eta_i)}, &
b_k &= \frac{3}{\prod_{i\neq k}(\zeta_k-\zeta_i)}
\end{align}Rearranging the terms of $p(x)$ and expanding each term using the familiar geometric series $\frac{1}{1-rx}=\sum_{n=0}^\infty r^kx^k$, we obtain
\begin{align}
p(x) &= -1 + \frac{1}{7}\left( \frac{1}{1-x} \right)
-\sum_{k=1}^5 \frac{a_k}{\eta_k} \left(\frac{1}{1-\eta_k^{-1}x}\right)
-\sum_{k=1}^6 \frac{b_k}{\zeta_k} \left( \frac{1}{1-\zeta_k^{-1}x} \right) \\
&= -1+\sum_{n=0}^\infty\underbrace{\left(
\frac{1}{7}-\sum_{k=1}^5 \frac{a_k}{\eta_k^{n+1}}-\sum_{k=1}^6\frac{b_k}{\zeta_k^{n+1}} \right)}_{q_n} x^n
\end{align}And that’s it! Our formula for the probability that a player lands on the $n^\text{th}$ square during their first pass around the board (rolling 2 dice at a time) is given by the $q_n$ coefficient in the infinite sum above.

It’s also possible to derive a formula for 3 dice (or any number of dice) at once using the same approach, but the formulas get progressively more complicated as we add more dice.

What about the limit as $n\to\infty$? In other words, what is the probability of landing on any square in the limit as we get very far from the starting point? This can be calculated easily from the formula for $q_n$. As $n\to\infty$, the complicated terms drop out, and we obtain $q_n \to \frac{1}{7}\approx 0.142857$. In the case where we roll 3 dice at once, the probability turns out to be $\frac{2}{21}\approx 0.095238$.

And what about for more dice? The probability $\lim_{n\to\infty}q_n$ if $k$ dice are rolled at once is simply the residue of $p(x)$ for the pole at $x=1$. This follows because all other poles will have roots with magnitude less than 1, so they decay to zero as $n\to\infty$. To calculate the residue, we use the fact that $q(1)=1$ and apply L’Hôpital’s rule:
\begin{align}
&\lim_{x\to 1} (1-x) p(x) \\
&= \lim_{x\to 1} \frac{(1-x)q(x)^k}{1-q(x)^k} \\
&= \lim_{x\to 1} \frac{1-x}{1-\left(\frac{x+x^2+x^3+x^4+x^5+x^6}{6}\right)^k} \\
&= \lim_{x\to 1} \frac{-1}{-k \left(\frac{x+x^2+x^3+x^4+x^5+x^6}{6}\right)^{k-1}\left( \frac{1+2x+3x^2+4x^3+5x^4+6x^5}{6} \right)} \\
&= \frac{2}{7k}
\end{align}And we can see that this formula agrees with what we found for $k=1$ and $k=2$. Now I’m wondering if there isn’t a way to arrive at this formula purely from first principles!

Picking a speaker at random

This week’s Fiddler is about selecting a speaker of the house at random. How long will it take?

There are three candidates who want the job of Speaker. All 221 members of the party vote by picking randomly from among the candidates. If one candidate earns the majority of the votes, they become the next Speaker. Otherwise, the candidate with the fewest votes is eliminated and the process is repeated with one less candidate. If two or more candidates receive the same smallest number of votes, then exactly one of them is eliminated at random. What is the average number of rounds needed to select a new Speaker?

Extra Credit
What if there were 10 candidates running for Speaker?

My solution:
[Show Solution]

We will consider a more general case; suppose there are $n$ candidates and $2m+1$ voting members in the party. We write $2m+1$ since there should be an odd number of party members to break ties. Define the following probability:
\[
p(n,m) = \left\{
\begin{array}{l}
\text{Probability that one of the $n$ candidates} \\
\text{wins a majority of the $2m+1$ votes.}
\end{array}
\right\}
\]Let’s find a formula for $p(n,m)$. For a particular candidate to win $k$ votes, $k$ members must vote for the candidate and the remaining members must vote for one of the other $n-1$ candidates. This occurs with probability $\binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}$. The candidate wins a majority if they garner at least $m+1$ of the $2m+1$ votes. We multiply the final result by $n$ since we are counting the probability that any of the $n$ candidates wins a majority. Therefore,
\[
p(n,m) = n\sum_{k=m+1}^{2m+1} \binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}
\]Note: We can add the probabilities of the different candidates winning as we did because the events are disjoint; it is impossible for two candidates to simultaneously win a majority of the votes. If the criteria allowed for overlap, e.g., one candidate winning at least 40% of the vote, then two candidates could win simultaneously, and we would have to account for this case to avoid double-counting.

Making the change of variables $k \mapsto 2m+1-k$, we obtain

$\displaystyle
p(n,m) = n \sum_{k=0}^m \binom{2m+1}{k} \left(1-\frac{1}{n}\right)^{k}\left(\frac{1}{n}\right)^{2m+1-k}
$

We recognize this as $n$ times the CDF of a binomial distribution with $2m+1$ trials and probability $1-\frac{1}{n}$.

What we’re really after is the expected number of rounds required for a candidate to secure a majority of the vote.
\[
f(n,m) = \left\{
\begin{array}{l}
\text{Expected number of rounds until one of the } \\
\text{that one of the $n$ candidates is elected.}
\end{array}
\right\}
\]This will happen in one round with probability $p(n,m)$. It will happen in $k$ rounds if it does not happen in the first $k-1$ rounds, and happens in the $k^\text{th}$ round. Putting this together, we get:

$\displaystyle
f(n,m) = \sum_{k=1}^{n-1} k\cdot p(n-k+1,m) \prod_{i=0}^{k-1} \bigl( 1-p(n-k+1+i,m) \bigr)
$

Unfortunately, these formulas do not simplify in any meaningful way, so we must evaluate them numerically. The first question asks us to compute $f(3,110)$ and the extra credit asks for $f(10,110)$. Calculating these, we obtain:
\begin{align}
f(3,110) &\approx 1.9999995110943353682 \\
f(10,110) &\approx 8.9999995110943296464
\end{align}These are rational numbers, of course, but $f(3,110)$ and $f(10,110)$ have 105-digit and 1357-digit denominators, respectively, when expressed as irreducible fractions, so I will not write them out here! One thing for sure is that it is very unlikely that the voting will end early. It is a virtual certainty that it will go the full $n-1$ rounds until there are only two candidates remaining.

Bonus: Changing the number of voters

The reason it is so difficult to elect a Speaker early is that there are so many voting members, and therefore it is unlikely that one candidate will obtain a majority of the votes by random chance. We can see how this probability would scale if we changed the number of voting members. Here is a plot of $f(n,m)$ for different values of $n$ (number of candidates), as a function of $2m+1$ (number of voting members). In all cases, we see that the expected number of rounds rapidly approaches $n-1$.

The slow car chase

This week’s Fiddler is a problem about probability and a slow car chase!

You and your pursuer are stopped at traffic lights one block away from each other, as shown below. For both cars, it takes 1 minute to get to each subsequent light, and there is a 50-50 chance any light will be red upon arrival (independent of what happened previously). If a light is red, you must wait one minute before it turns green. What is the probability you will make it to the city limits without being caught by your pursuer?

Extra Credit
In the same scenario as before, imagine there are infinitely many lights. On average, how many minutes will it be until you are ultimately caught?

My solution:
[Show Solution]

Can we escape before getting caught?

Let $P(n)$ be the probability that our pursuer will catch us at the $n^\text{th}$ light. To compute this probability, consider the gap between both cars. Initially, this gap is 1, and every time we reach a new light, depending on whether we got a red light and had to wait, or whether our pursuer got a red light and had to wait, the gap can change. Specifically,

The gap does not change if we both get red lights or both get green lights, which occurs with probability $\frac{1}{4}+\frac{1}{4} = \frac{1}{2}$.
The gap decreases by one if we get a red light and our pursuer gets a green light, which occurs with probability $\tfrac{1}{4}$.
The gap increases by one if we get a green light and our pursuer gets a red light, which occurs with probability $\tfrac{1}{4}$.

Initially, both cars have green lights, and since we get caught on the $n^\text{th}$ light, our final light must be red and our pursuer’s final light must be green. This leaves $n-2$ intermediate lights, at which the distance can either increase, decrease, or stay the same. If the distance could only increase or decrease, the total number of ways would be given by $C_{(n-2)/2}$, where $C_n$ is the $n^\text{th}$ Catalan number (see the interpretation of Catalan numbers as “counting mountain ranges”).

In our case, the gap can also stay constant, which complicates matters slightly. If we assume there are $k$ “ups” and $k$ “downs”, this leaves $n-2-2k$ “flats”. It follows that the total number of mountain ranges that may include plateaus is given by:
\[
\sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor} C_k \binom{n-2}{2k}
\]Each such path has a probability of occurring that depends on the number of flats, namely, it is
\[
\left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]The reason for the $2k+1$ in the first term is that we must account for the “down” at the very end of the path. Putting everything together and substituting the formula for the Catalan number in, we obtain:
\[
P(n) = \sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor}
\frac{1}{k+1}\binom{2k}{k} \binom{n-2}{2k} \left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]Amazingly, this sum has a closed-form formula, which I found using Mathematica. The probability that our pursuer will catch at the $n^\text{th}$ light is given by:

$\displaystyle
P(n) = \begin{cases}
\displaystyle\frac{1}{4^n\bigl(n-\tfrac{1}{2}\bigr)} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$

We can double check that this is a legitimate probability distribution by verifying that $\sum_{n=2}^\infty P(n) = 1$. In other words, we will eventually be caught, it’s just a matter of when. I used Mathematica to evaluate the infinite sum, and it is indeed equal to one!

If we have $n$ lights to go before we reach the city limit, the probability we will escape before getting caught is $1-\sum_{k=2}^n P(k)$, or in other words:
\[
\text{Prob}(\text{escape}) = 1-\sum_{k=2}^n \frac{1}{4^k\bigl(k-\tfrac{1}{2}\bigr)} \binom{2k}{k}
\]Amazingly, this also has a closed-form expression… and thanks again to Mathematica, it is given by:

$\displaystyle
\text{Prob}(\text{escape}) = \begin{cases}
\displaystyle\frac{2}{4^n} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$

This is an embarrassingly simple-looking expression, so there is likely a more elegant solution waiting to be found. The solution includes a denominator $4^n$ which is the total number of ways of assigning $\{\text{red},\text{green}\}$ to each of the $2n$ lights. The numerator is $2\binom{2n}{n}$, which must be the number of light assignments that do not lead to capture. If you can figure this out, please let me know in the comments!

In the original problem, we had 5 lights ahead of us, so substituting $n=5$, we obtain a probability of escape of $\frac{63}{128}$, or approximately 49.2%.

We can also check whether our formula holds up numerically. In the plot below, I compare the empirical probability from running 1,000,000 Monte Carlo simulations, and the analytic formula produced above, and we observe that we have a perfect match.

Note: This problem is somewhat similar to an old Riddler problem from 2017 about a horse race. You can check out my write-up for that problem if you’re interested!

Extra credit: time until caught

It takes at least one minute per light to visit all the lights (possibly more, depending on how many times we stop for red lights). Therefore, whenever we are eventually caught, the number of minutes that elapsed must be at least as much as the number of lights we saw.

We are asked to calculate the expected time elapsed until capture. Based on the argument above, we must have:
\[
\mathbb{E}(\text{lights seen until capture}) \leq
\mathbb{E}(\text{time until capture})
\]Let’s calculate the left-hand side. We already calculated $P(n)$, which is the the probability that we will be captured after seeing exactly $n$ lights. Therefore, the left-hand side is equal to $\sum_{n=2}^\infty n P(n)$. It turns out that this sum does not converge!. To see why, we can use the following asymptotic formula (source), which holds as $n\to\infty$.
\[
\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}
\]This leads us to the approximation
\[
P(n) \sim \frac{1}{\bigl(n-\tfrac{1}{2}\bigr)\sqrt{\pi n}}
\]And now we see why there is no convergence… The function $n P(n)$ decays like $\frac{1}{\sqrt{n}}$, and therefore is not summable (it is a $p$-series with $p=\tfrac{1}{2}$). Since the expected number of lights is unbounded, then the time until capture must also be unbounded.

But does this make any sense? A probability distribution that has no average? Yes! In general, distributions for which some of the moments are unbounded are called heavy-tailed distributions, and there are many well-known examples. In particular, examples of distributions with unbounded first moments (average does not exist) include the Cauchy distribution, the Pareto distribution, and $P(n)$ defined above.

Pinball probability

This week’s Fiddler is a challenging probability question.

You’re playing a game of pinball that includes four lanes, each of which is initially unlit. Every time you flip the pinball, it passes through exactly one of the four lanes (chosen at random) and toggles that lane’s state. So if that lane is unlit, it becomes lit after the ball passes through. But if the lane is lit, it becomes unlit after the ball passes through. On average, how many times will you have to flip the pinball until all four lanes are lit?

Extra credit: Instead of four lanes, now suppose your pinball game has $n$ lanes. And let’s say that $E(n)$ represents the average number of pinball flips it takes until all $n$ lanes are lit up. Now, each time you increase the number of lanes by one, you find that it takes you approximately twice as long to light up all the lanes. In other words, $E(n+1)$ seems to be about double $E(n)$. But upon closer examination, you find that it’s not quite double. Moreover, there’s a particular value of $n$ where the ratio $E(n+1)/E(n)$ is at a minimum. What is this value of $n$?

My solution:
[Show Solution]

Qualitative behavior and derivation of $E(n)$

Let’s fix $n$ for now, and define $T_k$ to be the number of expected additional flips required to light up all lanes given that there are currently $k$ lanes lit up. Our goal is to find $E(n) = T_0$. Two things can happen every time we flip the pinball:

We pass through a lit lane, which causes it to become unlit. This happens with probability $\tfrac{k}{n}$, leaving $k-1$ lit lanes.
We pass through an unlit lane, which causes it to light up. This happens with probability $\tfrac{n-k}{n}$, leaving $k+1$ lit lanes.

The boundary condition is that $T_n=0$, because if all lanes are lit, we have accomplished the goal and there are no more flips required. Putting everything together, we obtain the following recursion for $T_k$:
\begin{align}
T_0 &= T_1 + 1 \\
T_k &= \tfrac{k}{n}T_{k-1} + \tfrac{n-k}{n}T_{k+1} + 1 && \text{for }k=1,\dots,n-1.\\
T_n &= 0
\end{align}This is a set of $n+1$ linear equations in the $n+1$ unknowns $\{T_0,\dots,T_n\}$, so we have enough information to solve the problem and find what we’re after, which is $T_0 = E(n)$.

If you’re thinking “hey wait a minute… isn’t this just MFPT for an Ehrenfest Markov chain?”, I got you! I wanted to solve the problem without bringing in any heavy machinery first. I added a section at the end of this post that explains a bunch of connections to Markov chains.

Ok, back to our system of equations. Let’s start by making the substitution
\[
\Delta_k := T_{k-1}-T_k\qquad\text{for }k=1,\dots,n.
\]Since $T_n=0$, we can write $T_0$ in terms of the $\Delta_k$’s as:
\[
E(n) = T_0 = \Delta_1 + \Delta_2 + \cdots + \Delta_n
\]Meanwhile, we can rewrite the recursion in terms of the $\Delta_k$’s as:
\begin{align}
&& T_k &= \tfrac{k}{n}T_{k-1} + \tfrac{n-k}{n}T_{k+1} + 1\\
\iff && T_k-T_{k+1} &= \tfrac{k}{n} \left( T_{k-1}-T_{k+1} \right) + 1 \\
\iff && \Delta_{k+1} &= \tfrac{k}{n}\left( \Delta_{k}+\Delta_{k+1} \right) + 1 \\
\iff && \left(1-\tfrac{k}{n}\right)\Delta_{k+1} &= \tfrac{k}{n}\Delta_k + 1 \\
\iff && \Delta_{k+1} &= \tfrac{k}{n-k}\Delta_k + \tfrac{n}{n-k}
\end{align}So our simplified recursion looks like:
\begin{align}
\Delta_1 &= 1 \\
\Delta_{k+1} &= \tfrac{k}{n-k}\Delta_k + \tfrac{n}{n-k} && \text{for }k=1,\dots,n-1
\end{align}We can now solve for each $\Delta_k$ by forward substitution. The first few terms look like (rearranged to highlight the pattern):
\begin{align}
\Delta_1 &= \tfrac{n}{n} \\
\Delta_2 &= \tfrac{n}{(n-1)n} + \tfrac{n}{n-1} \\
\Delta_3 &= \tfrac{2\cdot 1 n}{(n-2)(n-1)n} + \tfrac{2n}{(n-2)(n-1)} + \tfrac{n}{n-2} \\
\Delta_4 &= \tfrac{3\cdot 2 \cdot 1n}{(n-3)(n-2)(n-1)n} + \tfrac{3\cdot 2 n}{(n-3)(n-2)(n-1)} + \tfrac{3n}{(n-3)(n-2)} + \tfrac{n}{n-3}
\end{align}The pattern is clear, and we have the following formula in terms of factorials, which we can rewrite in terms of binomial coefficients:
\begin{align}
T_k &= \sum_{i=0}^{k-1} \frac{n(k-1)!/i!}{(n-i)!/(n-k)!} = \sum_{i=0}^{k-1} \frac{\binom{n}{i}}{\binom{n-1}{k-1}}\\
%&= \sum_{i=0}^{k-1} \frac{n(k-1)! (n-k)!}{(n-i)!i!} \\
%&= \sum_{i=0}^{k-1} \frac{n! (k-1)! (n-k)!}{(n-1)!(n-i)!i!} \\
\end{align}Since $E(n)$ is the sum of the $\Delta_k$’s, we can now obtain a compact formula for the average number of pinball flips it takes until all $n$ lanes are lit up.

$\displaystyle
E(n) = \sum_{k=1}^n \sum_{i=0}^{k-1} \frac{\binom{n}{i}}{\binom{n-1}{k-1}}
$

Let’s try to make some sense of this complicated formula. We can manipulate it a bit to first obtain:
\[
E(n) = 2^n \sum_{k=1}^n \underbrace{\frac{1}{\binom{n-1}{k-1}}}_{\alpha_k} \,\underbrace{\sum_{i=0}^{k-1} \frac{1}{2^n}\binom{n}{i} }_{\Phi_k}
\]So we can think of $E(n)$ as a dot product between two sequences $\{\alpha_k\}$ and $\{\Phi_k\}$, scaled by $2^n$. But what do these sequences represent?

Recall that the binomial distribution with $p=1/2$ tends to a normal distribution with mean $n/2$ and variance $n/4$ as $n$ gets large, so we have:
\[
\frac{1}{2^n} \binom{n}{i} \approx \frac{1}{\sqrt{\pi n/2}}\exp\left( -\frac{(i-n/2)^2}{n/2} \right)
\]Therefore, the term $\Phi_k$ is approximately the cumulative distribution function for a normal distribution. Meanwhile, the weights $\alpha_k$ are weights that start at $1$ when $k=1$, reach a minimum when $k=\tfrac{n+1}{2}$, and then increase back to $1$ as $k$ approaches $n-1$. Here is what these sequences look like when $n=\{8,20,50\}$:

As we can see, the weights get steeper and steeper. The last two weights are
\[
\alpha_{n-2} = \binom{n-1}{n-2}^{-1} = \frac{1}{n-1}\qquad\text{and}\qquad
\alpha_{n-1} = \binom{n-1}{n-1}^{-1} = 1
\]Therefore, as $n$ gets large, we have
\[
E(n) \approx 2^n\left(1+\frac{1}{n-1}\right) = 2^n \frac{n}{n-1}
\]
This explains why we can expect that
\[
\lim_{n\to\infty} \frac{E(n+1)}{E(n)} = 2
\]
Unfortunately, I don’t see any way to make meaningful simplifications to the expression for $E(n)$, so we’ll have to proceed numerically to answer the questions asked.

The answer

The first problem asks us to calculate $E(4)$, which is easy enough:

$\displaystyle
E(4) = \frac{64}{3} \approx 21.3333
$

We can confirm the answer is correct via Monte Carlo simulation, and here is the histogram we obtain after $10^7$ trials.

As we can see, the empirical average of $21.3291$ is in good agreement with the true value of $21.3333$ we computed. The histogram only has bars at even values $n$ since it is impossible to go from $0$ to $4$ in an odd number of steps (at every step, we toggle the parity, so since we want to go from an even number to an even number, we must move an even number of times).

Extra credit

We can plot the function $\frac{E(n+1)}{E(n)}$ as a function of $n$, and we obtain:

Sure enough, the values are close to $2$ (I started the plot at $n=4$ to see more detail), and the minimum value occurs at $n=6$. This minimum value is:

$\displaystyle
\frac{E(7)}{E(6)} = \frac{151}{78} \approx 1.9359
$

The solution method above was relatively straightforward, but it turns out this problem has a Markov chain interpretation, and it’s actually a well-studied type of model (enough that it has a name!). If you’re interested, read on…

Markov chain interpretation

We can also interpret this problem as a Markov chain. Here, the state $k\in\{0,1,\dots,n\}$ represents having $k$ lanes lit up. The transition probabilities are represented below:

and the associated transition matrix is:
\[
P = \begin{bmatrix}
0 & 1 & 0 & 0 & \cdots & 0 & 0 \\
\tfrac{1}{n} & 0 & \tfrac{n-1}{n} & 0 & \cdots & 0 & 0 \\
0 & \tfrac{2}{n} & 0 & \tfrac{n-2}{n} & \ddots & \vdots & \vdots \\
0 & 0 & \tfrac{3}{n} & 0 & \ddots & 0 & 0 \\
\vdots & \vdots & \ddots & \ddots & \ddots &\tfrac{2}{n} & 0 \\
0 & 0 & \cdots & 0 & \tfrac{n-1}{n} & 0 & \tfrac{1}{n} \\
0 & 0 & \cdots & 0 & 0 & 1 & 0
\end{bmatrix}
\]This particular transition matrix has a name! It’s called the Ehrenfest Model, and it is used to model diffusion, among other things. The standard setup is that you have two urns, and a total of $n$ marbles. Each marble has a probability of $1/2$ of spontaneously jumping from one urn to the other. In our problem, all $n$ marbles start in the first urn, and we are asked to find the expected number of jumps required before all marbles first simultaneously end up in the other urn.

The expected number of steps required to first reach a given state when starting at another given state in a Markov chain is called the Mean First Passage Time (MFPT). It is also sometimes called the First Hitting Time. The way to calculate the MFPT is to solve the system of equations
\[
\hat{P}x + \mathbf{1} = x,
\]where $\mathbf{1}$ is the vector of 1’s, and $\hat P$ is the transition matrix with rows and columns corresponding to the target set removed. In our case, the target set is the last state, so we should remove the last row and column. Then, $x$ will be the vector of MFPT’s from each of the other states. In our case, we are interested in the first component of $x$. The system of equations above is precisely the one we derived earlier, so nothing new here; just another way to get the same answer!

The weaving loom problem

This week’s Fiddler is a classic problem.

A weaving loom consists of equally spaced hooks along the x and y axes. A string connects the farthest hook on the x-axis to the nearest hook on the y-axis, and continues back and forth between the axes, always taking up the next available hook. This leads to a picture that looks like this:

As the number of hooks goes to infinity, what does the shape trace out?

Extra credit: If four looms are rotated and superimposed as shown below, what is the area of the white region in the middle?

My solution:
[Show Solution]

Suppose the weaving loom has size $1\times 1$. If a given string starts a fraction $\alpha$ away from the origin along the $y$-axis, so at the point $(0,\alpha)$, it will connect to the point $(1-\alpha,0)$ along the $x$-axis. Therefore, the set of all lines have equations:
\[
y = \alpha-\frac{\alpha}{1-\alpha}x
\]Suppose the limiting shape has equation $y = f(x)$. For a given $x$, $f(x)$ is the largest value of $y$ achievable for one of the lines above at that given $x$. This is illustrated in the diagram below:

In other words, we have:
\[
f(x) = \max_{0\leq\alpha\leq 1} \left( \alpha-\frac{\alpha}{1-\alpha}x \right)
\]It’s clear that the maximum will not occur at a boundary point ($\alpha=0$ or $\alpha=1$), so it must occur at a point where the derivative with respect to $\alpha$ is zero. In other words,
\[
\frac{\mathrm{d}}{\mathrm{d}\alpha}\left( \alpha-\frac{\alpha}{1-\alpha}x \right)
= 1-\frac{x}{(1-\alpha)^2} = 0
\]The optimal choice is $\alpha_\star = 1-\sqrt{x}$, and this leads to
\begin{align}
f(x) &= 1-\sqrt{x}-\frac{1-\sqrt{x}}{\sqrt{x}}x \\
&=1-2\sqrt{x}+x \\
&= (1-\sqrt{x})^2
\end{align}A more symmetric way to express this function is to write it implicitly. If $y=f(x)$, the set of points $(x,y)$ that satisfy the equation above are precisely the points that satisfy the equation

$\displaystyle
\sqrt{x} + \sqrt{y} = 1
$

Let’s dig a little deeper and see if we can learn more about the shape of this curve. Squaring both sides, rearranging, and squaring again, we obtain:
\[
x^2+y^2-2xy-2x-2y+1 = 0
\]This is a quadratic expression in $x$ and $y$, which means it is a conic section! So either a circle, ellipse, hyperbola, or parabola. But which one? The easiest way to check is to examine the eigenvalues of the quadratic part (there will be two eigenvalues). Here is a handy table for reference:
\[
\begin{array}{l|l}
\textbf{eigenvalue property} & \textbf{conic section} \\ \hline
\text{equal eigenvalues} & \text{circle} \\
\text{same sign and nonzero} & \text{ellipse} \\
\text{different sign and nonzero} & \text{hyperbola} \\
\text{one zero eigenvalue} & \text{parabola}
\end{array}
\]
In our case, the quadratic terms are:
\[
x^2+y^2-2xy = \begin{bmatrix}x\\y\end{bmatrix}^\mathsf{T}
\begin{bmatrix}1 & -1 \\ -1 & 1\end{bmatrix}
\begin{bmatrix}x\\y\end{bmatrix}
\]This matrix is singular (determinant is zero), so there is a zero eigenvalue, and the conic section must be a parabola! To make this more evident, we can rearrange the equation a bit more to obtain
\[
\left(\frac{x+y}{\sqrt{2}}\right) = \frac{1}{\sqrt{2}}\left(\frac{x-y}{\sqrt{2}}\right)^2 + \frac{1}{2\sqrt{2}}
\]If we imagine rotating our curve by $45$ degrees counterclockwise, this would correspond to the transformation $(x,y)\mapsto\left(\tfrac{x-y}{\sqrt{2}}, \tfrac{x+y}{\sqrt{2}} \right)$, so the equation above in rotated coordinates $(\hat x, \hat y)$ is simply
\[
\hat y = \frac{1}{\sqrt{2}}\hat x^2 + \frac{1}{2\sqrt{2}},
\]which is clearly a parabola.

Tangency. Based on the animation above, it looks like the line that crosses $(x,f(x))$ is also tangent to the curve at that point. To verify this, we can compute the derivative directly and compare it to the slope of the line:
\[
f'(x) = \frac{\mathrm{d}}{\mathrm{d}x}(1-\sqrt{x})^2 = 1-\frac{1}{\sqrt{x}}
\]But the $\alpha_\star$ we found for a point $x$ produces:
\[
\text{(slope of line)} = \frac{-\alpha_\star}{1-\alpha_\star} = \frac{-(1-\sqrt{x})}{1-(1-\sqrt{x})} = 1-\frac{1}{\sqrt{x}},
\]which is a perfect match!

Extra credit

To find the area of the central region, we can break our shape into pieces as shown below.

The point $x_0$ corresponds to the $x$-value of our curve where $y=\frac{1}{2}$. This is given by:
\[
x_0 = \left(1-\sqrt{\frac{1}{2}}\right)^2 = \frac{3}{2}-\sqrt{2} \approx 0.0858
\]The area of the central part is the total area of the square ($1$) minus four times the shaded area, which leads us to the integral:
\begin{align}
A &= 1-4\left( \frac{1}{2}x_0 + \int_{x_0}^{\frac{1}{2}} (1-\sqrt{x})^2\,\mathrm{d}x \right) \\
&= \frac{2}{3}\left(4\sqrt{2}-5\right) \\[2mm]
&\approx 0.4379
\end{align}I decided to spare you the details of the integration because they’re not particularly interesting. So the white area in the middle occupies approximately $43.8\%$ of the area of the square.

Betting on football with future knowledge

This week’s Fiddler is a football-themed puzzle with a twist: you can see the future! Sort of.

You know ahead of time that your football team will win 8 of their 12 remaining games, but you don’t know which ones. You can place bets on every game, placing bets either for or against your team. You can bet any amount up to how much you currently have. You want to implement a betting strategy that guarantees you’ll have as much money as possible after the 12 games are complete. If you did so, then after the 12 games how much money would you be guaranteed to have if you started with $100?

My solution:
[Show Solution]

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}$.

A more elegant alternative solution, due in large part to a clever observation by Vince Vatter.
[Show Solution]

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.

Optimal baseball lineup

This week’s Fiddler is a problem about how to set the optimal baseball lineup.

Eight of your nine batters are “pure contact” hitters. One-third of the time, each of them gets a single, advancing any runners already on base by exactly one base. (The only way to score is with a single with a runner on 3rd). The other two-thirds of the time, they record an out, and no runners advance to the next base. Your ninth batter is the slugger. One-tenth of the time, he hits a home run. But the remaining nine-tenths of the time, he strikes out. Your goal is to score as many runs as possible, on average, in the first inning. Where in your lineup (first, second, third, etc.) should you place your home run slugger?

Extra Credit: Instead of scoring as many runs as possible in the first inning, you now want to score as many runs as possible over the course of nine innings. What’s more, instead of just having one home run slugger, you now have two sluggers in your lineup. The other seven batters remain pure contact hitters. Where in the lineup should you place your two sluggers to maximize the average number of runs scored over nine innings?

My solution:
[Show Solution]

We will attack this problem using dynamic programming. Rather than solving for the average number of runs for a particular configuration (of outs, runners on base, current batter, etc.), we will solve for all possible configurations! To this effect define the following:
\[
V(o,r,b,i) = \left\{
\begin{array}{l}
\text{Expected number of runs at end of}\\
\text{game given that we are currently in}\\
\text{the $i^\text{th}$ inning with $o$ outs, $r$ runners}\\
\text{on base, and the $b^\text{th}$ batter is up.}
\end{array}\right\}
\]Each index can only take on certain values. Define the sets:
\begin{align}
O &= \{0,1,2,3\} && \text{(number of outs)} \\
R &= \{0,1,2,3\} && \text{(runners on base)} \\
B &= \{1,2,\dots,9\} && \text{(batter currently up)} \\
I &= \{1,2,\dots,9\} && \text{(current inning)}
\end{align}Therefore there are $4\times 4\times 9\times 9 = 1296$ possible configurations we must solve for. Finally, some subset of the batters are the sluggers. Let this subset be $S \subseteq B$. The remaining batters are the pure contact hitters, which we denote $\bar S$. Therefore $S\cap \bar S = \emptyset$ and $S \cup \bar S = B$.

Finally, define $p$ to be the on-base average for pure contact hitters, and $q$ to be the slugging percentage for the sluggers. In the problem statement, we have $p=\frac{1}{3}$ and $q=\frac{1}{10}$.

We can now write equations that determine how the various configuration are related to each other:

When we have 3 outs, clear bases and advance to next inning, or end the game if we are in the 9th inning.\begin{align}
V(3,r,b,i) &= V(0,0,b,i+1) && \forall r\in R, b\in B, i\in\{1,\dots,8\}\\
V(3,r,b,9) &= 0 && \forall r\in R, b\in B
\end{align}This is a total of $4\times 9\times 9 = 324$ equations.
When a pure contact hitter is up to bat, they either advance runners (and possibly score if bases are loaded), or they strike out.
\begin{align}
V(o,r,b,i) &= p V(o,r+1,b+1,i) + (1-p) V(o+1,r,b+1,i) && \forall o\in \{0,1,2\}, r\in \{0,1,2\}, b\in \bar S, i\in I \\
V(o,3,b,i) &= p (1+V(o,3,b+1,i)) + (1-p) V(o+1,3,b+1,i) && \forall o\in \{0,1,2\}, b\in \bar S, i \in I
\end{align}This is a total of $3\times 4\times 9\times |\bar S| = 108|\bar S|$ equations.
When a slugger is up to bat, they either hit a home run (and clear the bases), or they strike out.
\begin{align}
V(o,r,b,i) &= q (r+1+V(o,0,b+1,i)) + (1-q) V(o+1,r,b+1,i) && \forall o\in\{0,1,2\}, r\in R, b\in S, i\in I
\end{align}This is a total of $3\times 4\times 9\times |S| = 108|S|$ equations.

In all the equations above, when we write “$b+1$”, we mean that if we get to the end of the order, we should cycle back to the top of the order.
This adds up to a total of $324+108|\bar S|+108|S| = 1296$ equations. We have the same number of equations as variables, which tells us that we accounted for everything!

I used Mathematica to input all the equations programmatically and solve them, and here is what I found.

First part: one inning, one slugger

When looking at a single inning with a single slugger, we pick $I = \{1\}$, and we can choose $S = \{9\}$ for example, and then ask, which batter should bat first to maximize score? this amounts to see which of
\[
V(0,0,b,1),\qquad b=1,2,\dots,9
\]is largest. Using the hitting percentages from the problem ($p=\frac{1}{3}$ and $q=\frac{1}{10}$), we obtain the following bar chart:

So it is best to put the slugger fourth in the batting order. This leads to an expected score of $\frac{3051922249868633}{12708748019768805} \approx 0.240143$ runs scored in the first inning. This is only narrowly better than putting the slugger third, which leads to an average of $0.23937$ runs scored. Overall, here is what we find:
\[
\begin{array}{r|ccccccccc}
\text{slugger position} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
\text{expected runs} & 0.184128 & 0.210732 & 0.23937 & 0.240143 & 0.202726 & 0.156235 & 0.168336 & 0.174246 & 0.176961
\end{array}
\]

By changing $p$ and $q$, we get different solutions. For example, if we make the pure contact hitters better, say $p=\frac{2}{3}$, but we keep the slugging at $q=\frac{1}{10}$, we obtain:

So in this case, the slugger is best placed last, presumably because they get out so much more frequently than the pure contact hitters.

Second part: nine innings, two sluggers

With nine innings and two sluggers, I iterated through all possible two-element subsets $S \subseteq B$, and then computed $V(0,0,1,1)$ for each case. This led to the following picture:

This plot shows the expected number of runs after 9 innings as a function of the two sluggers’ positions in the batting order. The best outcome occurs when the sluggers are 3rd and 4th in the batting order. This is the yellow bar in the (3,4) coordinate, which corresponds to an average of 1.99771 runs per game. Note that the y-axis has a relatively small range; it only ranges from 1.85 to 2.0. This goes to show that over the course of 9 innings, the batting order does not make that much difference. Here is a table showing all the results:

Code

To solve this problem analytically, I used Mathematica to specify each of the equations above, and then called the “Solve” function on that system of equations. Each of the equations can be collected into a list using the “Table” function, which makes it easy to enumerate the equations without having to write each one down manually. You can view my Mathematica code here, or in the window below.