A coin is tossed several times and the outcomes are being recorded in a string of H and T. How long - on average - will you have to wait for an "TTH?"

Question

Problem. A coin is tossed several times and the outcomes are being recorded in a string of H (heads) and T (tails). For example, that is recorded as "HHTTTHTH," so, how long - on average - will you have to wait for an "TTH ?"

I need to a plan of solving by simulation via python. Here is the algorithm:

First make a while loop for flipping coins. Then make booleans for each of the states $s_{0}, s_{1}, s_{2}, s_{3}:$
$s_{i}$ means that we have made $i$ progress on getting "TTH." For example, $s_{2}$ means that our last 2 flips were "TT."
If $E_{i}$ is the expected number of flips until we get to $s_{3}$ given that we are on $s_{i},$ then we are looking for the value of $E_{0}.$
We have the following system using states $$E_{0}= 1+ \frac{1}{2}E_{1}+ \frac{1}{2}E_{0}$$ $$E_{1}= 1+ \frac{1}{2}E_{0}+\frac{1}{2}E_{2}$$ $$E_{2}= 1+ \frac{1}{2}E_{2}+ 0$$ This means $$E_{2}= 2$$ $$E_{0}- E_{1}= 2$$ $$2E_{1}- E_0= 4$$ $$E_{1}= 6$$ $$\boxed{E_{0}= 8}$$ Now just simulate the progress the flip makes toward the final state by changing the values of each of the booleans until it gets to the final state.
Also you would have to repeat this process a sufficient number of trials and take the average number of flips of all trials.
Edit. What is the probability of it takes 8 trials to wait for an "TTH ?" Hope can you help... thanks a real lot !

Answer 1

You can go your way by adapting the below code for the own taste. The written code should work in both Python2 and Python3. (Well, in py2 one should better use xrange at that one point instead of range. That unused variable trial may become an underscore.) The states are declared as strings, i do not see the point of encoding them as integers, the (needed) passages are encoded in a dictionary dic.

import random

random.seed(2021)

states = ['', 'T', 'TT', 'TTH']
T, H = 'T', 'H'
dic = { (T, '') : 'T', (T, 'T') : 'TT', (T, 'TT') :  'TT', 
        (H, '') :  '', (H, 'T') :   '', (H, 'TT') : 'TTH', }

N, totalsteps = 10**6, 0    # trials
for trial in range(N):
    state, steps = '', 0.0
    while state != 'TTH':
        toss = random.choice('TH')    # either T or H
        steps += 1
        state = dic[ (toss, state) ]
    totalsteps += steps

print('Statistic expectation is {}'.format(totalsteps/ N))

The simulation above has N steps, feel free to adjust this number. This time i've got (for the specified random seed - just comment it and rerun some times for diversity)...

Statistic expectation is 8.012544

Answer 2

I wrote the simulation for the algorithm :-)

from random import randint

last_three = []
waiting = [0,0,1] # sequence TTH
s = 0

for x in range(1000) : # 1000 trials

    v = 0 # number of flips in one trial

    while True :

        v += 1
        
        if len(last_three) < 3 : last_three.append(randint(0,1)) 

        else : # keep just the last three values
            last_three.pop(0) 
            last_three.append(randint(0,1))

        if last_three == waiting : break

    s += v 

print(s/(x+1)) # Expected value

It's easy to modify this code to obtain the expected value for any sequence of $T$ and $H$ if you are interested to do it.

Answer 3

Another way to do this would be make one big list of flips and search for instances of TTH:

n = 100000000;
ps = SequencePosition[
   RandomChoice[{"T", "H"}, n],
   {"T", "T", "H"},
   Overlaps -> False
];
expectedFlips = ps[[-1, 2]]/Length@ps