The problem comes from a very famous Ted Talk:
You are flipping a fair coin. What is the expected times of tosses you need to see the first “HTH” appears? What is that for the first “HTT” appears?
Suppose $latex N_1$ is the random variable which counts the number of flips till we get first “HTH”. $latex N_2$ is the random variable which counts the number of flips until we get first “HTT”. Intuitively, $latex E[N_1] > E[N_2]$. Here is why:
Suppose you want to get sequence “HTH”. When you already see “HT” sequence, you get excited because the next flip is important. If the next flip is “H”, you stop and return the count. However, if the next flip is “T”, your excitement has to cease and start over. You will only start to get excited again when you see next “H” or “HT”.
Now, suppose you want to get sequence “HTT”. Again, when you already see “HT” sequence, you become excited. If the following flip is “T”, you stop and return the count. If the next flip is “H”, your excitement also goes down but not totally ceases. Because at least you have an “H”, the first letter of the sequence you want to see. So your excitement does not need to start over completely.
Since you are more easily to get close to obtain “HTT” than “HTH”, $latex E[N_1]>E[N_2]$.
We can get exact solutions by many methods. Let me introduce first a probability method, which can be referred from here:
Let $latex X$ be the random variable which counts the number of flips till we get a “T” (tail).
$latex E[X] = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot (1 + E[X]) \\ \Rightarrow E[X]=2 &s=2$
In the RHS of the first line formula: the first term is for when we get a “T” on the first flip; the second term is if we get a “H” on the first flip, which means we are effectively starting over with another extra flip.
Another way to calculate $latex X$ is from the fact that $latex X$ follows a geometric distribution or a negative binomial distribution with mean equal to 2. See here for derivation.
Now, assume $latex Y$ the random variable which counts the number of flips until we get a “HT” sequence.
$latex E[Y] = \frac{1}{2} \cdot (1+E[Y]) + \frac{1}{2} \cdot (1+E[X]) \\ \Rightarrow E[Y]=4 &s=2$
In the RHS of the first line formula: the first term is if we get a “T” on our first flip, which means we are effectively starting over with 1 extra flip. The second term is if we get a “H” on our first flip, then all we want is a “T”. What we want to count is 1+expected number of flips to get a “T”, the latter is exactly $latex E[X]$.
In the same spirit, if we suppose $latex Z$ is the random variable which counts the number of flips until we get a “TT” sequence, then:
$latex E[Z]=\frac{1}{2} \cdot (E[X]+1) + \frac{1}{2} \cdot (E[T]+1+E[TT]) \\ \Rightarrow E[Z]=6 &s=2$
Now for the sequence “HTH”, we have:
$latex E[N_1] = \frac{1}{2} \cdot (E[Y]+1) + \frac{1}{2} \cdot (E[Y] + 1 + E[N_1]) \\ \Rightarrow E[N_1]=10 &s=2$
In the RHS of the first line formula: the first term is if we get a “HT” on our first two flips followed by a “H”; the second term is if we get a “HT” followed by a “T”, then we have to start over.
For the sequence “HTT”, we have:
$latex E[N_2] = \frac{1}{2} \cdot (E[Y]+1) + \frac{1}{2} \cdot (E[Y]+1+E[Z]) \\ \Rightarrow E[N_2] = 8 &s=2$
In the RHS of the first line formula: the first term is if we get a “HT” on our first two flips followed by a “T”; the second term is if we get a “HT” followed by a “H”, then we have to count the flips until next “TT” happens.
We can also use Markov Chain to solve this problem. I am just showing you the solution for “HTT”. We construct 4 states as below:
$latex E[N_2]$ is actually called the mean first passage time of state “HTT” from state “start”. We can get the mean first passage time using pykov package:
import pykov
d = {('start', 'H'): 0.5, ('start', 'start'): 0.5, ('H', 'H'): 0.5, ('H', 'HT'): 0.5, ('HT', 'H'): 0.5, ('HT', 'HTT'): 0.5, ('HTT', 'HTT'): 1}
T = pykov.Chain(d)
T.mfpt_to('HTT')
# result
# Vector([('H', 6.0), ('HT', 4.0), ('start', 8.0)])
Another way to solve this problem is called finite state automata: http://stats.stackexchange.com/questions/12174/time-taken-to-hit-a-pattern-of-heads-and-tails-in-a-series-of-coin-tosses/12196#12196