Geometric Series with coin tosses

Question

Suppose you toss a coin and observe the sequence of $H$’s and $T$’s. Let $N$ denote the number of tosses until you see “$TH$” for the first time. For example, for the sequence $HTTTTHHTHT$, we needed $N = 6$ tosses. In addition, let $M$ denote the number of tosses until we see “$HH$” for the first time. For the previous sequence, $M = 7$. Find $E[N]$ and $E[M]$.

The way I've tried solving this is using a geometric series. I know that each toss is independent, and we can assume that the coin is fair so for $N$ tosses, we're only counting all the tosses before we get the first "$TH$".

So this is the probability of getting the first Tails: $$p(j)=P(X=j)= \sum_{j=0}^{\infty} \left(\frac{1}{2}\right)^{j+1}$$

The thing is I've very confused as to how to incorporate getting a Head right after getting a tail. I thought about maybe finding the intersection and then multiplying $p(j)$ and $p(i)$ since each toss is independent. So I would get: $p(i)=p(j)$ since it's the same idea to calculate.

This whole problem just seems very confusing to me. Any assistance would be greatly appreciated! Thank you.

Answer 1

We use information that you may already know about geometrically distributed random variables. The mean waiting time until the first T is $2$. After that, the mean additional waiting time until the first H is $2$. And $2+2=4$.

Remark: There are many other approaches, including series. An interesting alternate approach uses conditioning on the result of the first toss. That is useful for the HH problem, but to leave you with something to do we use it on the TH problem.

It is reasonably clear that the expectation exists. Call it $a$. And let $b$ be the expected number of additional tosses given we have just tossed a T. We condition on the result of the first toss. If it is H, we have wasted a toss, and the expected number number of tosses is $1+a$. If it is T, then by the definition of $b$ it is $1+b$. Thus $$a=\frac{1}{2}(1+a)+\frac{1}{2}(1+b).$$ A similar argument shows that $$b=\frac{1}{2}(1)+\frac{1}{2}(1+b).$$ Solving, we obtain $b=2$ and then $a=4$.

Answer 2

Let $N$ denote the number of tosses until you see “TH” for the first time. Find $\mathsf E(N)$

In order to encounter the termination event we must toss a series of none or more heads, a series of one or more tails, and then one head. The pattern, $\mathsf{[T]_XH[H]_YT}$

Here $X$ and $Y$, the number of tosses of a given face before the opposite face have geometric distributions.

$$X,Y\sim \mathcal {Geom}(1/2) \implies \mathsf E(X) = \frac{1-1/2}{1/2}=\mathsf E(Y)$$

$$\mathsf E(N) = \mathsf E(X)+\mathsf E(Y) +2$$

---

Now let $M$ denote the number of tosses until we see “HH” for the first time.

In order to encounter the terminating event we toss none or more tails, a head then either another head (terminate) or a tail (then reiterate). The recursive pattern is $\mathsf{P:=[T]_ZH(H|T P)}$

Where $Z$ is again a geometrically distributed value.

$$\mathsf E[M]=\mathsf E[Z] + 2 + \tfrac12 \mathsf E[M]$$

Can you take it from here?