Stuck on Penney's game question Suppose we have a game that assumes we have a fair coin. Two people who are playing can pick two patterns of coin flips. The players then flip a large coin a number of times and record each of the individual flips.
After the flips, they pay attention to the record of flips and decide which pattern came first in the sequence.
Using simulations, we can find:

*

*HHT comes before THH about 1/4th of the time

*THH comes before TTH about 1/3rd of the time

*TTH comes before HTT about 1/4th of the time

*HTT comes before HHT about 1/3rd of the time

Can someone explain to me why this is and what the intuition behind this game is?

This type of problem relates to "string-counts", which in turn relate to deterministic finite automata (DFAs) for strings (see this related question).  The simplest way to understand these problems is to construct a DFA for the "language" of interest in the problem (i.e., the set of strings being counted).  In the figure below I show the minimised DFA for your first case, with heads represented by the blue arrows and tails represented by the red arrows.  There are seven different states in the minimised DFA, and the final states of interest are at the bottom of the figure.  As you can see from the picture, the transitions in the DFA are not symmetric with respect to these final states.

As you can see from the figure, there are a substantial number of transitions into the state T in this DFA, and this is the main reason why the the state THH tends to occur before the state HHT.  The first string is a more "forgiving" string on the first run (i.e., starting from the null state); once you are in the state T you are guaranteed to reach the state THH before the state HHT.  If you would like some more insight into this, consider the number of transitions into these two states from the NULL state, noting that each transition of head/tails is equiprobable under your model.

Implementation in R: Below I implement the first of these string-count problems in my own custom DFA function in R (to be released at a later date).  This output shows the transition table for the DFA (matching the arrows in the figure) and shows the transition probability matrix and steady state for the DFA.  As you can see, the two outcomes of interest to you will occur with equal probability in the steady state, and will therefore tend to occur in roughly the same proportions in the long run.  However, the state THH tends to occur before the state HHT due to the large number of transitions into the early components of that string.
Deterministic Finite Automaton (DFA) 

DFA for a language containing 2 strings 

---------------------Transitions and final states---------------------- 
 
         | H T | F[1] F[2]
State[0] | 2 1 | 0    0   
State[1] | 3 1 | 0    0   
State[2] | 4 1 | 0    0   
State[3] | 5 1 | 0    0   
State[4] | 4 6 | 0    0   
State[5] | 4 6 | 0    1   
State[6] | 3 1 | 1    0   

-------------------------Symbol probabilities-------------------------- 

              H   T
Probability 0.5 0.5

--------------------Stationary state probabilities--------------------- 
 
           State[0] State[1] State[2] State[3] State[4] State[5] State[6]
Stationary        0    0.375        0     0.25    0.125    0.125    0.125

---------------------Transition probability matrix--------------------- 

         State[0] State[1] State[2] State[3] State[4] State[5] State[6]
State[0]        0      0.5      0.5      0.0      0.0      0.0      0.0
State[1]        0      0.5      0.0      0.5      0.0      0.0      0.0
State[2]        0      0.5      0.0      0.0      0.5      0.0      0.0
State[3]        0      0.5      0.0      0.0      0.0      0.5      0.0
State[4]        0      0.0      0.0      0.0      0.5      0.0      0.5
State[5]        0      0.0      0.0      0.0      0.5      0.0      0.5
State[6]        0      0.5      0.0      0.5      0.0      0.0      0.0

-------------------Alphabet and language information------------------- 

The alphabet contains 2 symbols 
 H T 
 
String[1] contains 3 symbols 
 H H T 

String[2] contains 3 symbols 
 T H H 

-----------------------------------------------------------------------

