2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ $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)$. $\endgroup$ – James Yang Jan 18 at 19:19
  • $\begingroup$ The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads. $\endgroup$ – Hayk Jan 18 at 19:21
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Jan 18 at 19:21
  • $\begingroup$ 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. $\endgroup$ – James Yang Jan 18 at 19:25
  • $\begingroup$ @JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time. $\endgroup$ – Hayk Jan 18 at 19:28
2
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.