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.


1 Answer 1


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$

Additional Material

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.

  • $\begingroup$ I still can't realize the meaning of $s$. What does the starting state mean? $\endgroup$
    – user998168
    Apr 13, 2022 at 9:34
  • $\begingroup$ 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. $\endgroup$ Apr 13, 2022 at 13:13
  • $\begingroup$ 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. $\endgroup$
    – user998168
    Apr 14, 2022 at 19:53
  • $\begingroup$ Yes, it is a Markov chain, I will add the equations in a different form, maybe that will help $\endgroup$ Apr 14, 2022 at 20:51

You must log in to answer this question.