What's the probability of $HTHT$ occuring before $HHTT$ in a stream of $H$'s and $T$'s (both equally likely) that will stop if either of those occur? What's the mean number of throws such that $HHTT$ occurs?
Hello, I figured out that this is an instance of Penney's game.
This question is also related. What makes this question hard for me is the fact that I have to somehow account for the fact that $HTHT$ occures before $HHTT$. I have to solve this using Markov chains, does someone have an idea?
This solution is an elaboration on the comment by @MatthewH.
Let $P_i$ denote the probability of hitting $HTHT$ first when in state $i$. The equations relating the probabilities are
\begin{align*} P_{\emptyset} &= \frac 12(P_H + P_{\emptyset}) \\ P_H &= \frac 12 (P_{HH}+P_{HT}) \\ P_{HT} &= \frac 12 (P_{HTH}+P_{\emptyset}) \\ P_{HH} &= \frac 12 (P_{HH} + P_{HHT}) \\ P_{HTH} &= \frac 12 (P_{HH} + P_{HTHT}) \\ P_{HHT} &= \frac 12 (P_{HTH} + P_{HHTT}) \\ P_{HTHT} &= 1 \\ P_{HHTT} &= 0. \end{align*} This is a large linear system, but it can be solved fairly easily by substitution. The solution I found is \begin{align*} P_{\emptyset} = P_H &= \frac 49 \\ P_{HT} &= \frac 59 \\ P_{HH} &= \frac 13 \\ P_{HTH} &= \frac 23 \\ P_{HHT} &= \frac 13, \end{align*} but please double check to make sure I didn't make a mistake.
