You've got be flipping kidding me!

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?

This game, like many coin flipping problems of its ilk, can be modeled as a Markov chain. There are two absorbing states, let's call them, $\textsf{WinJ}$ and $\textsf{WinK}$, and nine transient states, call them, $(i, j)$ where $i, j \in \{0, T, TT\},$ represent the state where Julien is in state $i$ and Kyle is in state $j.$ State $(0,0),$ which represents both the starting space and the case that both Julien and Kyle just flipped H and that Kyle's last three flips were not TTH, can transition to $(T,0)$, $(0,T)$, $(T,T)$ or itself, each with equal probability. On the other hand, we see that due to the tie breaker procedures, state $(TT, TT)$ can transition to $(0,0)$, $\textsf{WinJ}$, $\textsf{WinK}$ and $(TT,0),$ each with equal probability. We can similarly build up all of the other transitions Let's represent the probabilistic state of the system as $\pi = (p_\textsf{WinJ}, p_\textsf{WinK}, p_{(0,0)}, p_{(0,T)}, p_{(0,TT)}, p_{(T,0)}, p_{(T,T)}, p_{(T,TT)}, p_{(TT,0)}, p_{(TT,T)}, p_{(TT,TT)} ) \in [0,1]^{11},$ then the probability transition matrix can be represented as

$$P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0 & 0 & 0 \\ 0 & 0.5 & 0.25 & 0 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0.25 & 0 \\ 0 & 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0 & 0.25 \\ 0 & 0.5 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \\ 0.5 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.5 & 0 & 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \end{pmatrix}.$$ We can subdivide the transition matrix into the resolving states, $$R = \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0.5 \\ 0 & 0 \\ 0 & 0 \\ 0 & 0.5 \\ 0.5 & 0 \\ 0.5 & 0 \\ 0.25 & 0.25 \end{pmatrix}$$ and the transitory states $$T = \begin{pmatrix} 0.25 & 0.25 & 0 & 0.25 & 0.25 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0.25 & 0.25 & 0 & 0.25 & 0 & 0 & 0 \\ 0.25 & 0 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0.25 & 0.25 & 0 \\ 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0.25 & 0 & 0.25 \\ 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \\ 0.25 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.25 & 0 & 0 & 0 & 0 & 0 & 0.25 & 0 & 0 \end{pmatrix}$$ such that we can represent the transition matrix $P$ in block form as $P = \begin{pmatrix} I & 0 \\ R & T \end{pmatrix}.$ If we start at particular state, say $\pi_0,$ then by the $n$th step, our probabilistic state is $$\pi_n = \pi_0 P^n = \pi_0 \begin{pmatrix} I & 0 \\ (I + T + T^2 + \dots + T^{n-1}) R & T^n \end{pmatrix}.$$ If we let $n \to \infty,$ then since $T^n \to 0$ and $I + T + T^2 + \dots + T^{n-1} \to (I - T)^{-1},$ we have that the ultimate transition matrix is $$\pi_\infty = \pi_0 \begin{pmatrix} I & 0 \\ (I - T)^{-1} R & 0 \end{pmatrix}.$$

Here, the probability that Kyle wins is given by the $p_\textsf{WinK}$ (2nd) entry in $\pi_\infty.$ Since we are starting at $\pi_0 = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),$ and we are only concerned with $p_\textsf{WinK}$ we can instead of solving the entire matrix inverse of $I - T$ rather just solve the system of equations

$$(I - T) x = R \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.25 \end{pmatrix}$$ and then taking the first coordinate. Choosing your favorite matrix alegbra software, programming language or, due to certain foibles with which you are burdened, a bunch of loose leaf paper and loads of patience, you get to the probability that Kyle will win as $$p_\textsf{WinK} = \frac{36367}{74368} = 48.9014....\%$$