Pattern Waiting Time

You toss a fair coin repeatedly and wait for a specific pattern to appear as a consecutive run. Start with the pattern $\text{HTH}$. 1. Model the process as a Markov chain where each state represents the length of the longest suffix of your flip history that matches a prefix of $\text{HTH}$. Write down the transition matrix, set up the first-step equations for the expected waiting time $E[T]$, and solve for $E[T]$. 2. Now generalize. For an arbitrary binary pattern $P = p_1 p_2 \cdots p_L$ with a fair coin, explain how to construct the corresponding automaton (with states $0, 1, \ldots, L$), and derive a closed-form formula for $E[T]$ in terms of the pattern's self-overlap structure.