6
$\begingroup$

What is the expected number of flips until three consecutive heads or tails appear?

$\endgroup$
  • $\begingroup$ Try to do an easier case first, then you might get the idea. What is the expected number of flips until 1 consecutive heads or tails appears? What is the expected number of flips until 2 consecutive heads or tails appears? Can you get a formula for $n$ consecutive heads or tails? $\endgroup$ – Euler....IS_ALIVE Oct 6 '12 at 23:42
7
$\begingroup$

This can be seen as an MC with 4 states. Denote for convenience $S=\{HHH, TTT\}$

One thing to notice first, is that only before you have tossed any coins at all you need 3 matching tosses till $S$. After that, regardless of the outcome, you have no more than two matching tosses from $S$. Hence we have the following MC:

$S_0$: 3 matching tosses till $S$

$S_1$: 2 matching tosses till $S$

$S_2$: 1 matching tosses till $S$

$S_3$: 0 matching tosses till $S$

Denoting $m_{i,j}$ the mean hitting time of state $j$ starting in state $i$, we obtain the following set of recurrent equations: $$ m_{0,3}=1+m_{1,3}\\ m_{1,3}=1+0.5 m_{1,3} +0.5m_{2,3}\\ m_{2,3}=1+0.5 m_{1,3} +0.5m_{3,3} $$ And the boundary condition is of course $m_{3,3}=0$. Solving this set of equations we get $$ m_{0,3}=1+6=7 $$

$\endgroup$
  • $\begingroup$ For beginners, can you edit the answer to elaborate on what MC is? $\endgroup$ – Alexandros Dec 30 '16 at 12:36
  • $\begingroup$ MC=Markov chains $\endgroup$ – Alex Dec 30 '16 at 12:59
5
$\begingroup$

Let $P$ be the expected number when the last two flips match, $Q$ the expected number when the last two flips don't match (or there has only been one flip). Our answer is $Q+1$ as the first flip will take us to state $Q$.
Then $P=\frac 12 \text{(that we match the last 2)}+\frac 12 (Q+1)\text{ (as we are now in state } Q)$ $Q=\frac 12 (1+P)\text{(that we match the last flip)} + \frac 12 (1+Q)\text{(that we don't match the last flip)}$

This gives $P=4, Q=6$ and our final answer is $7$

$\endgroup$
  • $\begingroup$ sir , i am really new to this type of question.It will be of great help if you please help me to simplify your explanation. $\endgroup$ – laura Jul 4 '18 at 11:38
  • $\begingroup$ @laura: what don't you understand? $\endgroup$ – Ross Millikan Jul 4 '18 at 12:45
2
$\begingroup$

Here is probably another way and hope this can be easier to understand. Let us assume to get HHH for X number of times, then for {HHH, TTT} is just X/2.

1)first time get T, then just waste one time, everything turns to be same as before, plus this event chance is 1/2. Then to get HHH is 1/2*(X+1)

2)first time get H 2.1)second time get T, then waste two times plus 1/4 probability of this event. Then total number is 1/4*(X+2) 2.2)second time get H 2.2.1) third time get T, then waste 3 times plus 1/8 prob of this event. Then total number is 1/8*(X+3) 2.2.2) third time get H, this is perfect and prob is 1/8. So total number is 1/8*3.

Now, everything sum together should converge to X. we have: 1/2*(X+1) + 1/4*(X+2) + 1/8*(X+3) + 1/8*3 = X => X = 14.

So to get {HHH, TTT} is X/2 = 7.

$\endgroup$
1
$\begingroup$

I think it should be 14.

$X_k$=number of flips needed to obtain first k consecutive heads.

$$E[X_k]=\frac{1}{p}+\frac{1}{p*2}+\cdots+\frac{1}{p*k}$$ where $$p(\text{Heads})=p \\ p(\text{Tails})=1-p$$

and p is not equal to zero.

$\endgroup$
  • 1
    $\begingroup$ We were asked for either three heads or three tails. The other answers take account of this. $\endgroup$ – Ross Millikan Apr 24 '13 at 17:35
1
$\begingroup$

Let us keep it general and assume that $\mathrm{P(heads})=p$ and $\mathrm{P(tails})=1-p=q$, and start by analyzing only the event of three consecutive heads, which composes the larger event asked.

All sequences can be obtained by appending to the initial sequences {T,HT,HHT,HHH}, the last one already having our target event. So, these sequences induce a partition of the sample space. Furthermore, every time a T appears, the subsequent sequences will also be generated by these initial sequences, thus they induce also a partition of the sub-events, being recurrent. So, it is possible to express the probability $f(k)$ of three consecutive tails occurring after $k$ flippings, conditionally on those sequences: \begin{equation} \begin{array}{ll} f(k)=0, & k<3\\ f(3)=p^3 \\ f(k)=qf(k-1)+pqf(k-2)+p^2qf(k-3), & k >3; \end{array} \end{equation} where the interpretation of the recurrence equation is that each of its terms corresponds to each of the sequences {T,HT,HHT} occurring before the sub-events become a copy of the same recurrence relation.

If one prefers to interpret the flipping sequences being generated by transitions in a Markov Chain (MC), all transitions associated to the occurrence of a T point to the same state, which will need at least three more flippings to obtain the desired event. The states can be expressed as {{},H,HH,HHH}, each of these labels expressing uninterrupted sequences of heads in the last three flippings. Every time a T occurs, the system returns to the state {}. The state HHH is terminal. Then, the recurrence relation $f(k)$ above expressed can be obtained by analyzing the probabilities of trajectories in the MC.

Given that the expected number of flips (the expectation of the random variable $K_{3\mathrm{T}}$) until three consecutive heads appear can be expressed as $\mu=E(K_{3\mathrm{T}})=\sum_{k=1}^{\infty}kf(k)$, we apply this summation to the definition of $f(k)$ above and manipulate as following: \begin{equation} \mu=\sum_{k=1}^{\infty}kf(k)=3f(3)+\sum_{k=4}^{\infty}k\left[qf(k-1)+pqf(k-2)+p^2qf(k-3)\right]\\ =3p^3+q\sum_{k=4}^{\infty}kf(k-1)+pq\sum_{k=4}^{\infty}kf(k-2)+p^2q\sum_{k=4}^{\infty}kf(k-3), \end{equation} from which we can deduce that \begin{equation} \begin{array}{lll} \sum_{k=4}^{\infty}kf(k-1)=&4f(3)&[=f(3)+3f(3)]\\ & +5f(4)&[=f(4)+4f(4)]\\ & ...\\ & +(1+n)f(n)&[=f(n)+nf(n)]\\ &=\\ &1+\mu&[=\sum_{k=3}^{\infty}f(k)+\sum_{k=3}^{\infty}kf(k)]. \end{array} \end{equation} Applying the same reasoning for the other summations, we conclude that \begin{equation} \mu=q(1+\mu)+pq(2+\mu)+p^2q(3+\mu)+3p^3, \end{equation} from which we can use that $q=1-p$ and isolate $\mu$ such that \begin{equation} \mu=p^{-3}(1+p+p^2). \end{equation} The event of three consecutive tails is symmetric to three consecutive heads, so $\lambda=E(K_{3\mathrm{H}})=q^{-3}(1+q+q^2)$. If $p=q=1/2$, we have $\lambda=\mu=14$ and, with certain assumptions (e.g. independence, type of distribution), we could argue that the average time for either event occur is half of this time. However I am not sure about what assumptions would be needed and how they could be checked, so I will restart the demonstration from scratch using arguments similar to the ones used above.

A MC which generates the sequences until three consecutive heads or tails occur, for $p\in[0,1]$, has the following states: {{},H,HH,HHH,T,TT,TTT}, where {} occurs only at the beginning, and HHH and TTT are terminal or absorbing. The problem of establishing a recurrence relation from this MC is that it does not have a single state to which all of the non-absorbing states may return, as it happened for the example given above. However, we can consider the following two mutually exclusive events: the initial transition goes to H and the initial transition goes to T. This allows us to express the probability mass function $g(k)$ as: \begin{equation} g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T}), \end{equation} which is conditioned on either H or T occurring first. The MC associated to $g(k|\mathrm{H})$ has all the states of that associated to $g(k)$ except {}, and starts at the state H; similarly to that associated to $g(k|\mathrm{T})$, which starts at T. With each of these MCs, it is possible to find a recurrence relation.

Let us start by analyzing $g(k|\mathrm{T})$. In order to express its recurrence relation, we have to identify all possible trajectories which either terminate or return to the initial state T. These are {TTT,TTHT,TTHHT,TTHHH,THT,THHT,THHH}. They are used to identify the event partitions below: \begin{equation} \begin{array}{rlll} g(k|T)=& &=0, & k<3\\ g(3|T)=&\mathrm{P}(\mathrm{TTT}) &=q^2, \\ g(4|T)=&\mathrm{P}(\mathrm{THHH}) &=p^3,\\ g(5|T)=&\mathrm{P}(\mathrm{TTHHH})+\mathrm{P}(\mathrm{THT})g(3|\mathrm{T})&=p^3q+pq^3, \\ g(k|T)=&\mathrm{P}(\mathrm{TTHT})g(k-3|\mathrm{T})+\mathrm{P}(\mathrm{TTHHT})g(k-4|\mathrm{T})\\ &+\mathrm{P}(\mathrm{THT})g(k-2|\mathrm{T})+\mathrm{P}(\mathrm{THHT})g(k-3|\mathrm{T}) \\ =&pq.g(k-2|\mathrm{T})+(p^2q+pq^2)g(k-3|\mathrm{T})\\ &+p^2q^2.g(k-4|\mathrm{T}),& & k\geq 6. \end{array} \end{equation} Similarly to what I did for $f(k)$ above, I use the expectation formula $\mu_T=E(K_3|T)=\sum_{k=1}^{\infty}k.g(k|\mathrm{T})$ to obtain \begin{equation} \mu_t=3q^2+4p^3+5p^3q+pq(\mu_\mathrm{T}+2)+(p^2q+pq^2)(\mu_\mathrm{T}+3)+p^2q^2(\mu_\mathrm{T}+4) \end{equation} and, making $\mu_T$ explicit: \begin{equation} \mu_T=\frac{p^4-p^3-2p^2+p-3}{p^4-2p^3-p^2+2p-1}. \end{equation} In which the denominator never vanishes for $p\in[0,1]$. Because the problem structure is symmetric for $g(k|\mathrm{H})$, we can obtain $\mu_H=E(K_3|\mathrm{H})$ by substituting $q$ for $p$ in the formula above. And, from the fact that $g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T})$, we can deduce that \begin{equation} E(K_3)=p.E(K_3|\mathrm{H})+q.E(K_3|\mathrm{T})=p\mu_\mathrm{H}+q\mu_\mathrm{T}. \end{equation}

We can easily verify that a fair coin gives $E(K_3)=7$.

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