From the answer to this question (Expected Number of Coin Tosses to Get Five Consecutive Heads) it is clear that the expected number of flips of a fair coin till we see three tails in a row is 14. I wrote a computer simulation that again confirmed this, however when I altered the simulation to look for the expected number of flips until the pattern T-H-T occurred (instead of T-T-T), the expectation dropped to 10. Why is this? I'd prefer an answer that avoids Markov chains if at all possible.
1
$\begingroup$
$\endgroup$
-
1$\begingroup$ The difference is that an initial T-H makes you start all over when watching for T-T-T, while an initial T-T lets you make use of the pattern-breaking T as the start of the next chance at T-H-T. $\endgroup$ – mjqxxxx Apr 3 '16 at 21:54
-
2$\begingroup$ The conceptual reason, such as it is, is this: for the case $TTT$ suppose you already have a $T$. Then getting another $T$ advance you but getting an $H$ sets you back to the start. In the case $THT$, by contrast, if you already have a $T$ then getting $H$ advances you while getting another $T$ leaves you where you are. I can write out a state space argument if you like (though this is basically the same as a Markov chain argument). $\endgroup$ – lulu Apr 3 '16 at 21:55
-
$\begingroup$ So, in the style of the top rated answer to the linked question where $e$ is the expected number of tosses, I'd have $$ e = \frac{1}{2}(e + 1) + \frac{1}{4}(e + 1) + \frac{1}{8}(e + 3) + \frac{1}{8}(3)$$ which evaluates to $e = 12.$ Where am I going wrong? $\endgroup$ – Jimmy Xiao Apr 3 '16 at 22:03
1
$\begingroup$
$\endgroup$
Let $L$ be the set of strings over $\Sigma=\{H,T\}$ which contain $THT$ as a substring. Then $L$ is a regular language, described by the regular expression $R = (H,T)^* THT (H,T)^*$ or by the deterministic finite automaton with states $S=\{\varepsilon, T, TH, T\}$ and transition function $\delta:S\times\Sigma\to S$ defined by
\begin{array}{l|l|l} \delta(s,a) & H & T\\\hline \varepsilon &\varepsilon & T\\ T &TH &T\\ TH & \varepsilon & THT\\ THT & THT & THT \end{array} Suppose at each time $n$ we flip a coin and feed the result to the machine. Let $\tau_s$ be the expected number of flips until reaching state $THT$, given that the machine is in state $s$. Then \begin{align} \tau_\varepsilon &= 1 + \frac12\tau_\varepsilon + \frac12\tau_T\\ \tau_T &= 1 + \frac12\tau_{TH}+\frac12\tau_T\\ \tau_{TH} &= 1 + \frac12\tau_\varepsilon. \end{align} Solving these equations yields $\tau_\varepsilon=10, \tau_T = 8, \tau_{TH} = 6$, so the expected number of flips until $THT$, starting from the beginning, is $10$.
