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!