# Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $\textbf{E}(T)$.

A fair coin is tossed repeatedly. Let $$A_{n}$$ be the event that three heads have appeared in consecutive tosses for the first time on the $$n$$-th toss. Let $$T$$ be the number of tosses required until three consecutive heads appear for the first time. Find $$\textbf{P}(A_{n})$$ and $$\textbf{E}(T)$$.

Let $$U$$ be the number of tosses required until the sequence $$HTH$$ appears for the first time. Can you find $$\textbf{E}(U)$$?

EDIT

The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.

• $P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $n\geq 3$. Here $p=0.5$. So then $E(T) = \sum\limits_{n=3}^\infty nP(T=n)$. – James Yang Jan 18 '19 at 19:19
• The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads. – Hayk Jan 18 '19 at 19:21
• @JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end. – Ross Millikan Jan 18 '19 at 19:21
• I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer. – James Yang Jan 18 '19 at 19:25
• @JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time. – Hayk Jan 18 '19 at 19:28

What follows is a well-known approach to computing the expectation of $$T$$.

Consider the following gambling scheme: just before each time $$n\in \mathbb{N}$$ a new gambler arrives and bets $$1$$ \\$ that the $$n$$-th outcome of the coin toss is $$H$$. If the bet is correct the gambler wins $$2$$ (since the coin is fair) and bets it, the $$2$$, on the next outcome to be $$H$$ as well. Again, if the gambler win, he bets the fortune of $$4$$ on the next toss to be $$H$$. Winning that also, ends the game and leaves him with a fortune of $$8$$.

Now let $$X_k^i$$, where $$k\geq 1$$ and $$i=1,2,3$$ be the fortune of the $$k$$-th gambler after their $$i$$-th bet. For instance, the winner, if he was the $$k$$-th to enter the game, will have $$X_k^1 = 2$$, $$X_k^2 = 2^2$$ and $$X_k^3 = 2^3$$, while for all gamblers who did not make to the third from the last move, $$X_k^i = 0$$ for each $$i=1,2,3$$.

Define $$S_n = \sum_{\substack{k=1\\i=1,2,3\\ k + i \leq n + 1}}^n X_k^i$$ which is the total fortune of all gamblers after the $$n$$-th toss. Notice that exactly $$n$$ dollars were bet up to and including time $$n$$. Since the coin is fair and in view of our definition of $$X_k^i$$, it is easy to see that the sequence $$M_n: = S_n - n$$ is a martingale with respect to the natural filtration generated by $$\{X_n\}_{n\in \mathbb{N}}$$. Define $$\tau = \inf\{n\in \mathbb{N}: \ X_{n-2} X_{n-1} X_n = H H H \},$$ which is a stopping time, and defines the time when the game ends. We have $$\mathbb{E}(\tau) <\infty$$. Indeed, the probability of getting $$HHH$$ on tosses $$3k, 3k+1,3k+2$$ equals $$1/8$$, hence dividing the interval of integers $$[1,...,3k]$$ to length $$3$$ intervals, it follows that the probability of NOT getting $$HHH$$ up to time $$3k$$ is bounded above by $$1/8^k$$. Thus $$\mathbb{P}(\tau > 3k) \leq 1/8^k$$, hence the conclusion of $$\mathbb{E}(\tau) < \infty$$.

Now, using the fact that $$M_n$$ has bounded increments and $$\tau$$ has fininte expectation, we apply the optional stopping theorem to get $$\mathbb{E}M_\tau = 0$$, thus $$0 = \mathbb{E}M_\tau = \mathbb{E} S_\tau - \mathbb{E} \tau.$$ But observe, that at the time of finishing the game, i.e. at time $$\tau$$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $$\tau-1$$ and $$\tau$$ respectively. Each of these three gets $$2^3$$, $$2^2$$ and $$2$$, hence $$\mathbb{E} \tau = 2^3 + 2^2 + 2 = 14.$$

For instance, using the same argument, it follows that for the pattern $$HTH$$, the expected time equals $$2^3 + 2$$.

See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.

We can also get a formula for the probability of the event $$A_n$$. It was already mentioned in the other answer above that the event $$A_n$$ comprises of all sequence of length $$n$$ ending in $$THHH$$ and having at most $$2$$ consecutive $$H$$-s before time $$n-4$$.
Hence we need to compute the number of length $$n$$ sequences of $$\{H,T\}$$ with at most $$2$$ consecutive $$H$$. Denote this number by $$a_n$$.

Clearly $$a_1 = 1$$, $$a_2 = 3$$, $$a_3 = 5$$. For $$n>3$$ we claim that $$\tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.$$ Indeed, each such sequence of length $$n$$ either ends in $$H$$ or $$T$$. If it ends with $$T$$, we have length $$n-1$$ remaining which can end in both $$H$$ and $$T$$, hence $$a_{n-1}$$ of such contributions. For sequences ending with $$H$$, we continue tracking the $$n-1$$-th position: if it's $$H$$, then the $$n-2$$-th needs to be $$T$$, hence $$a_{n-3}$$ of these, otherwise, if it's $$T$$, we are free to choose the $$n-2$$-th, thus we get $$a_{n-2}$$.

Since the set $$A_n$$, sequences of length $$n$$ where $$HHH$$ appears for the first time on step $$n$$ has the following structure: $$\text{length } n-4 \ \text{sequences of at most } 2 \ \text{ Heads } \text{ followed by } THHH,$$ it follows $$\mathbb{P}(A_n) = 2^{-n}a_{n-4},$$ with $$a_n$$ as in $$(1)$$.

Let $$e$$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $$\frac{1}{2}$$) then the expected number is $$e+1$$. If we get a head then a tail (probability $$\frac{1}{4}$$), then the expected number is $$e+2$$ If we get $$2$$ heads then a tail, the expected number is $$e+3$$. Finally, if our first $$3$$ tosses are heads, then the expected number is $$3$$. Thus $$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{8}(3).$$

IF you solve the equation, you get $$e = 14$$.

Remark: emabraced the idea from Andre Nicolas's solution.

You can't have $$P(A_n)=2^{-n}$$ for $$n \ge 3$$ because the probabilities do not sum to $$1$$. It is true that $$P(A_3)=\frac 18$$ because you need $$HHH$$ and $$P(A_4)=\frac 1{16}$$ because you need $$THHH$$, but $$P(A_5)=\frac 1{16}$$ because you win with both $$TTHHH$$ and $$HTHHH$$. For $$n \ge 5, A_n$$ consists of a string of $$n-4$$ tosses that does not have three heads in a row followed by $$THHH$$. If you count the probability that you can have $$n-4$$ tosses without three heads in sequence the chance of $$A_n$$ is $$\frac 1{16}$$ of this.