# The mean waiting time of the pattern from coin tossing

Toss a coin at time-points t = 1, 2, . . .. Denote the outcome of each toss head-facing-up and tail-facing-up by a 0 and a 1, respectively. Let $$\Lambda=(0\ 0\ 1)$$ and $$N$$ be the waiting time for $$\Lambda$$. Find the mean waiting time $$E[N]$$ with the probability of each toss of the head-facing-up is $$\frac{1}{3}$$.
The following is my thinking:
Conditioning on the outcome of the first coin toss and second coin toss, let $$N= \begin{cases} 2+N^\prime& if X_{t=1}=0 \ \&\ X_{t=2}=1\\ 2+N^* & if X_{t=1}=1 \ \&\ X_{t=2}=0\\ 2+N^{**} & if X_{t=1}=1 \ \&\ X_{t=2}=1\\ 2+N^{***} & if X_{t=1}=0 \ \&\ X_{t=2}=0\\ \end{cases}$$
Here, $$N^{**}$$ and $$N^\prime$$ have the same distribution as $$N$$.
$$N^*$$ and $$N^{***}$$ have the same distribution.
$$E[E[N \mid X_1,X_2]]=E[N]=(2+E[N^\prime]) \times \frac{2}{9}+(2+E[N^*])\times \frac{2}{9}+(2+E[N^{**}])\times \frac{4}{9}+(2+E[N^{***}])\times \frac{1}{9}$$
However, I don't know how to describe the distribution of $$N^*$$ and $$N^{***}$$. If I know their distribution, I can obtain the answer.

To change the notation for clearer understanding, we want the waiting time for getting the first sequence of HHT
I shall use an approach proceeding step by step

Let $$s$$ be the starting state, $$h_1$$ the state where we have just tossed a head and $$h_2$$ the state where we have tossed two consecutive heads, then

With one toss from start, we either toss a head with $$Pr = \frac13,\;$$ or remain where we are with $$Pr =\frac23\;$$ as shown in equation $$[I]$$

Framing equations step by step, we get
$$\displaylines{s = \frac13(1+h_1) +\frac23(1+s)\;\;[I] \\h_1 = \frac13(1+h_2) +\frac23(1+s)\;\;[II]\\h_2 = \frac23\times 1 + \frac13(1+h_2)\;\;[III] }$$

The last equation tells that from $$HH,$$ with $$Pr=\frac23,\,$$ we toss a tail and are done, or with $$Pr=\frac13$$, we remain poised at $$HH$$

Solve to get $$s = 13.5$$

Maybe the equations will be clearer if written in a different form

$$\displaylines {s = 1+ \frac13h_2 +\frac23h_1\;\;[I]\\h_1= 1+\frac13h_2 +\frac23 s\;\;[II]\\h_2= 1+\frac13h_2\;\;[III]}$$

The first equation now tells very clearly that from start, one step (or time unit) either leads to the first H in the desired chain with $$Pr= \frac13$$, or back to square one with $$Pr = \frac23$$
Similarly, the last equation means that with one step, either you go back to a HH situation with $$Pr=\frac23$$, or are done.

The technique is called first step analysis, which you can look up if you want further explanation or examples, also look at this answer here which addresses a somewhat more complex problem, and contrasts it with a stochastic matrix approach.

• I still can't realize the meaning of $s$. What does the starting state mean?
– user998168
Apr 13, 2022 at 9:34
• The starting state is when you haven't yet tossed the coin, or when , say, you haven't achieved HHT and the chain has been broken, eg if you toss T, or HT, you are back to a state where you still require the first H of the HHT chain you want. Square $1$, so to say. Apr 13, 2022 at 13:13
• How do you generate the equation above? Do you use markov chain? But the form doesn't seem like the markov chain I have seen before.
– user998168
Apr 14, 2022 at 19:53
• Yes, it is a Markov chain, I will add the equations in a different form, maybe that will help Apr 14, 2022 at 20:51