Penney's Game and Conway's Leading Number Algorithm

Scenario

Two players, Alice and Bob, play Penney's Game. Alice chooses a binary coin sequence $A \in \{H, T\}^L$ of length $L = 3$. Bob then chooses a distinct sequence $B \in \{H, T\}^L$. A fair coin is repeatedly tossed until one of the two sequences appears as a consecutive subsequence; the player whose pattern appears first wins.

Your Task

1. Define Conway's leading number correlation algorithm $(X Y)$ for sequences $X, Y$.
2. Using martingale stopping theory, state Conway's formula for the winning odds ratio $\frac{\mathbb{P}(B \text{ wins})}{\mathbb{P}(A \text{ wins})}$.
3. State Bob's optimal counter-strategy for any length-3 sequence $A = (a_1, a_2, a_3)$.
4. Compute the exact winning probabilities when Alice chooses $HHT$ and Bob responds optimally with $THH$.

Constraints

• Fair independent coin tosses with $p(H) = p(T) = 0.5$.

Examples If Alice picks $HHT$, Bob picks $THH$. $(HHT, HHT) = 4$, $(HHT, THH) = 1$, $(THH, THH) = 4$, $(THH, HHT) = 3$. Bob wins with probability $3/4 = 75\%$.