8
$\begingroup$

I'm currently studying probability and I've come across a problem that I'm finding quite challenging. I would appreciate any help or guidance.

Problem Statement:

A fair coin is continually flipped until both heads and tails have appeared. I need to find:

(a) The expected number of flips (b) The probability that the last flip lands on heads

My Attempt:

For part (a), I understand that the expected value is the long-run average or mean of a random variable. Since the coin is fair, the probability of getting heads or tails is 0.5. However, I'm not sure how to apply this concept when the coin is flipped until both heads and tails have appeared.

For part (b), I'm a bit confused. My initial thought was that since the coin is fair, the probability that the last flip lands on heads would be 0.5. But I'm not sure if this is correct because the experiment doesn't stop until both heads and tails have appeared.

Background:

I'm an undergraduate student majoring in Mathematics. I've taken courses in Calculus and Linear Algebra, and I'm currently taking a course in Probability and Statistics. I'm familiar with the basics of probability, but this problem seems to involve concepts that I haven't fully grasped yet.

I found this problem in my textbook (unfortunately, I don't have the name of the book right now), in the chapter on expected values. I've tried to solve it using the concepts explained in the book, but I'm stuck.

I would really appreciate it if someone could explain the solution in a way that a beginner in probability could understand. Thank you in advance for your help!

$\endgroup$
4
  • $\begingroup$ Hint: If you get a tail on the first flip, what is the expected number of flips until you get a head? $\endgroup$ May 15 at 8:53
  • 2
    $\begingroup$ If I get a tail on the first flip, the expected number of flips until I get a head is 2. This is because, after getting a tail, the coin is fair and the probability of getting a head on the next flip is 0.5. Therefore, on average, it would take 2 flips to get a head. $\endgroup$
    – prob1 yuma
    May 15 at 8:55
  • $\begingroup$ You're very right to be careful for (b). But in this case by a symmetry argument, the probability still has to be 1/2. $\endgroup$
    – Stef
    May 15 at 22:13
  • $\begingroup$ For a slight generalization comparison: With a die instead of a coin, you do "roll repeatedly until the event 'something new' occurs" six times, where the probability of 'something new' is first $1$, then $\frac 56$, then $\frac46$, $\frac36$, $\frac26$, and finally $\frac16$. Hence the expected wait times are $1$, $\frac 65$, $\frac64=\frac32$, $\frac63=2$, $\frac62=3$, and $6$, respectively. This leads to a total wait time to collect all: $1+\frac65+\frac32+2+3+6$ $\endgroup$ May 16 at 12:16

5 Answers 5

4
$\begingroup$

A simple yet rigorous argument for (b) is that the last flip is a head if and only if the first flip is a tail, which has probability $1/2$ since the coin is fair.

$\endgroup$
1
3
$\begingroup$

You must flip at least two times. Then on the third flip, if you haven't got $HT$ or $TH$, you have $HH$ with probability $\frac{1}{4}$ and $TT$ with probability $\frac{1}{4}$. From here, as you note in the comments, the expected number of flips to get the needed $T$ or $H$, respectively, is 2. Thus if $X$ is the number of flips until you get at least one $H$ and one $T$: $$ E(X) = 2 + \frac{1}{4}(2) + \frac{1}{4}(2) = 2 + \frac{1}{2} + \frac{1}{2} = 3 $$ More detail in other questions, e.g., this one.

P.S. It can be fun to sanity check via numerical experiments. In this case, after $100,000$ trials I get an average number of flips needs to be $3.00025$.

import random

trials = 100000
num_flips_total = 0
for _ in range(trials):
    flip_counter = 0
    seen_head = seen_tail = False
    while not seen_head or not seen_tail:
        if random.random() > 0.5:
            seen_head = True
        else:
            seen_tail = True
        flip_counter += 1
    num_flips_total += flip_counter

print(f"Average number of flips: {num_flips_total/trials}")

>> Average number of flips: 3.00025
$\endgroup$
1
  • 1
    $\begingroup$ I think it should be 2+1/2+1/2=3, but thanks a lot, I got it now $\endgroup$
    – prob1 yuma
    May 15 at 9:09
3
$\begingroup$

(a) The expected number of flips until both heads and tails have appeared:

Let's denote by E the expected number of flips. If we get a head or a tail on the first flip (which will happen with probability 1), we then need to flip until we get the other side. The expected number of flips to get the other side is 2 (as we discussed earlier). Therefore, we can write the expected number of flips E as:

$$E = 1 + 2 = 3$$

So, the expected number of flips until both heads and tails have appeared is 3.

(b) The probability that the last flip lands on heads:

Since the coin is fair, the last flip is equally likely to be a head or a tail, regardless of what flips came before it. Therefore, the probability that the last flip lands on heads is 0.5.

$\endgroup$
7
  • 1
    $\begingroup$ I don't get it, why E=1+2=3? $\endgroup$
    – prob1 yuma
    May 15 at 9:01
  • $\begingroup$ @prob1yuma you have the first toss which is either tail or head plus the expected number of tosses of getting the other face which is 2. $\endgroup$
    – rcescon
    May 15 at 9:02
  • 2
    $\begingroup$ While the result for b) is correct the argument is not: If we denote the sequence of flips by $(X_n)_{n\in\mathbb N}$, then we are considering $X_\tau$ where $\tau$ is the stopping time defined as the smallest $n$ for which you have seen both heads and tails. In general, the distribution of $X_\tau$ need not be equal to the distribution of any of the $X_n$. So an additional argument is needed. $\endgroup$ May 15 at 9:27
  • 1
    $\begingroup$ For example, assume we were to stop at the first time we see heads. Then the last result we saw is heads with probability $1$. Briefly speaking your argument fails because one ensembles not only over the result of each flip, but also over the time at which one stops, which is itself random and possibly dependent on the result of the flips. $\endgroup$ May 15 at 9:30
  • 2
    $\begingroup$ Also a simpler argument may invoke symmetry: If you switch the labels heads and tails you end up with the same problem. $\endgroup$ May 15 at 12:00
2
$\begingroup$

The other answers provide an insight on how to solve the question using elementary methods. I will try to add to the discussion by outlining how one may use typical tools from Markov chain theory to solve this problem. While the solution I present is overkill, it can easily be generalized to a larger class of problems containing the one you presented.

We can consider the given process as an absorbing Markov chain with four states. The states are as follows:

  1. We have neither seen heads nor tails;
  2. We have seen only heads before;
  3. We have seen only tails before;
  4. We have seen both heads and tails before.

The matrix of transition probabilities for the four states is as follows:

$$A=\begin{pmatrix} 0 & \frac 12 & \frac 12 & 0 \\ 0 & \frac 12 & 0 & \frac 12 \\ 0 & 0 & \frac 12 & \frac 12 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$$

We want to calculate the expected time until we reach state 4 from state 1. Let $\tau$ we the time it takes to reach state 4 from state 1.

Consider now the matrix

$$B=\begin{pmatrix} 0 & \frac 12 & \frac 12 \\ 0 & \frac 12 & 0 \\ 0 & 0 & \frac 12\end{pmatrix}.$$

This matrix describes the transitions between the transient states. By the layer-cake formula, we have

$$\mathbb E(\tau) = \sum_{k=1}^\infty \mathbb P(\tau\ge k).$$

Now $\mathbb P(\tau\ge k)$ is just the probability that after $k$ steps we are still in one of the transient states after starting in state 1.

Thus $$\mathbb P(\tau \ge k) = \text{first entry of }B^k \begin{pmatrix} 1 \\ 1 \\ 1\end{pmatrix}.$$

In particular, $$\mathbb E(\tau) = \text{first entry of }\left(\sum_{k=1}^\infty B^k\right)\begin{pmatrix} 1 \\ 1 \\ 1\end{pmatrix} =\text{first entry of } (\operatorname{Id} - B)^{-1} \begin{pmatrix} 1 \\ 1 \\ 1\end{pmatrix}.$$

We calculate $$(\operatorname{Id} - B)^{-1} = \begin{pmatrix}1 & 1 & 1 \\ 0 & 2 & 0 \\ 0 & 0 & 2\end{pmatrix}$$ and thus $$\mathbb E(\tau) = 3.$$ In fact, by taking the second and third entry of $$(\operatorname{Id} - B)^{-1} \begin{pmatrix} 1 \\ 1 \\ 1\end{pmatrix}$$ you get, respectively, the expected number of steps until you go to state 4 if you started in state 2 or state 3.

In conclusion, the answer to question a) is $3$.


Let us go to question b). Let $(Y_t)_{t\in\mathbb Z_{\ge 0}}$ denote the Markov chain of the states we are in. That is, we start with $Y_0=1$ and once we see heads we jump to $Y_\cdot = 2$, once we see tails we jump to $Y_\cdot = 3$, and if we have seen both we jump to $Y_\cdot = 4$. Having heads on the last throw before we stopped is equivalent to $Y_{\tau - 1} = 3$. (Exercise: Why is that so?)

Therefore

$$\mathbb P(\text{last throw is heads}) = \mathbb P(Y_{\tau-1} = 3) = \sum_{n=1}^\infty \mathbb P(\tau=n\land Y_{n-1}=3) = \sum_{n=1}^\infty \mathbb P(Y_n=4\mid Y_{n-1}=3)\mathbb P(Y_{n-1}=3) = \frac 12\sum_{n=1}^\infty\mathbb P(Y_{n-1}=3).$$

But $\sum_{n=1}^\infty\mathbb P(Y_{n-1}=3)$ is just the expected number of times we visit state $3$ before getting absorved when starting at state 1. This is the entry at position $(1,3)$ of the matrix $(\operatorname{Id}-B)^{-1}$, which is thus $1$. We therefore conclude

$$\mathbb P(Y_{\tau-1}=3)=\frac 12,$$

which thus establishes that the answer to part b) is $\frac 12$.

$\endgroup$
0
$\begingroup$

For (a), with $N=$ number of flips required for both H and T to occur: $$\begin{align}E(N) &= 2\cdot P(HT\text{ or }TH)+3\cdot P(HHT\text{ or }TTH)+4\cdot P(HHHT\text{ or }TTTH)+...\\ E(N)&=2\cdot({1\over 2})^1+3\cdot({1\over 2})^2+4\cdot({1\over 2})^3+5\cdot({1\over 2})^4+...\\ 2\cdot E(N)&=2+3\cdot({1\over 2})^1+4\cdot({1\over 2})^2+5\cdot({1\over 2})^3+...\\ 2\cdot E(N)-E(N)&=2+1\cdot({1\over 2})^1+1\cdot({1\over 2})^2+1\cdot({1\over 2})^3+...\\ E(N)&=2+(0.1111...)_2\\ E(N)&=3\end{align}$$

$\endgroup$

You must log in to answer this question.

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