1
$\begingroup$

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.

$\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$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.