4
$\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$
5
  • 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
    Commented Jan 18, 2019 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
    Commented Jan 18, 2019 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$ Commented Jan 18, 2019 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
    Commented Jan 18, 2019 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
    Commented Jan 18, 2019 at 19:28

3 Answers 3

5
$\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 $(7/8)^k$. Thus $\mathbb{P}(\tau > 3k) \leq (7/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$
4
  • $\begingroup$ Thanks @Hayk for the great answer! I was wondering how the martingale method can be extended to the biased coin setting. $\endgroup$
    – Alex
    Commented Jan 16, 2023 at 19:11
  • 1
    $\begingroup$ A quick question, when showing the stopping time is finite, you claim "the probability of NOT getting HHH up to time 3k is bounded above by 1/8^k. How is that possible? Even if I just sub in k = 1, the probability of not getting HHH up to time 3 is clearly 7/8 which is much greater than your bound of 1/8? $\endgroup$
    – jmac
    Commented May 2, 2023 at 17:31
  • $\begingroup$ @jmac thanks for point this out. It is the complement indeed, 7/8, not 1/8; revised now. We split $3k$ into length $3$ non-overlapping steps and in each step consider the probability of not seeing HHH, thus ending up with $(7/8)^k$. This does not change the rest though. $\endgroup$
    – Hayk
    Commented May 3, 2023 at 5:17
  • $\begingroup$ Thank you for the prompt reply. I suspected that was the case but just wanted to make sure! $\endgroup$
    – jmac
    Commented May 3, 2023 at 20:24
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .