Question on coin tossing - probability

Question

When considering an infinite sequence of tosses of a fair coin, how long will it take on an average until the pattern H T T H appears?

I tried to break the problem into cases where ultimately the pattern HTTH appears, but that makes things complex. Any insight would be helpful.

Answer 1

(I'm working with HTTH as desired pattern.) Distinguish the five states $$s_0=\emptyset,\quad s_1=H,\quad s_2=HT,\qquad s_3=HTT,\quad s_4=HTTH\ ,$$ whereby the written letters denote the last tosses insofar as useful. Let $E_k$ $(0\leq k\leq4)$ be the expected number of additional tosses when you are in state $s_k$. Then of course $E_4=0$. Furthermore we have the following equations: $$E_0=1+{1\over2}E_0+{1\over2}E_1,\quad E_1=1+{1\over2}E_1+{1\over2}E_2,\quad E_2=1+{1\over2}E_1+{1\over2}E_3,\quad E_3=1+{1\over2}E_0\ .$$ Now solve this system; then $E_0$ is the solution to your problem.

Answer 2

I like Christian's answer better as it is simple. But I worked out another solution so I just added it for reference.

Let:

$H_n$ be the event of no "HTTH" in n flips and ends with "H"

$T_n$ the event of no "HTTH" in n flips and ends with "T"

$p_n = \text{Prob}(H_n)$

$q_n = \text{Prob}(T_n)$

So, $p_1=p_2=p_3=q_1=q_2=q_3=1/2$

It is not hard to verify $\left[ \begin{array}{c} p_{n+1}\\q_{n+1} \end{array}\right] = A \left[ \begin{array}{c} p_{n}\\q_{n} \end{array}\right]$, where the matrix $A = \left[\begin{array}{cc}\frac{1}{2} & \frac{3}{8}\\\frac{1}{2} & \frac{1}{2} \end{array} \right]$.

The desired expectation is given by

$E = \left[0, \frac{1}{8}\right] \left\{\sum_{n=4}^{\infty} nA^{n-4}\right\}\left[ \begin{array}{c} p_{n}\\q_{n} \end{array}\right]$

One can further prove the matrix power series $\sum_{n=4}^{\infty}nA^{n-4} = (4I-3A)(I-A)^{-2} = \left[\begin{array}{cc}136 & 114\\ 152 & 136 \end{array} \right]$

Therefore $E = \frac{1}{16} (152+136) = 18 $

Answer 3

Here's yet another way of doing this.

We can be in one of $5$ states, according to the number $0\le k\le4$ of consecutive “correct” results that we currently have; e.g. $k=2$ means the last two results were HT. Let's make a graph with the transitions between these states:

The labels on the vertices are the values of $k$. We'll get to the edge weights in a bit. In addition to the two possible transitions from each of the nodes with $0\le k\le3$, I added an edge from $4$ to $0$ to complete a round trip from $0$ to $4$ and back.

The idea is to choose the edge weights such that at each vertex all outgoing edges have the same weight and the sums of incoming and outgoing edge weights are equal. For instance, start at $3$ and arbitrarily assign weight $1$ to its outgoing edges; then work your way around the graph, e.g. it follows that the edge $4\to0$ also has weight $1$, the edge $2\to3$ has weight $2$, thus the edge $2\to1$ also has weight $2$, and so on. You barely have to compute anything.

Now consider a process on the edges where in each step we go from the current edge to its terminal vertex and then uniformly randomly choose one of its outgoing edges. Then the equilibrium distribution on the edges is given by the edge weights, normalized by their sum, since by construction that lets the same probability flow into and out of each vertex in each step.

We're looking for the expected time to reach $4$ from $0$. After we reach $4$, we always go to $0$ in a single step. Thus, the time we want is $1$ less than the expected time for a round trip from $0$ to $4$ and back. On such a round trip, we spend exactly $1$ step on the edge $4\to0$. But then the expected time for the round trip must be the reciprocal of the equilibrium probability of being on edge $4\to0$. Since that edge conveniently has weight $1$, the expected time for the round trip is just the sum of the edge weights, which is $19$. Thus the expected time to get from $0$ to $4$ is $1$ less, $18$.